• Author / Uploaded
• jddlxo

Citation preview

Carlos Agreda, Ph. D

Por: 1

Programación Lineal

Como se sabe, para llevar a cabo la optimización de cualquier proceso minero o de cualquier otro proceso, es necesario tener un líder. Por tanto, la sucesión del poder consiste en trasmitir la responsabilidad, el patrimonio y el capital humano al descendiente que se va a ocupar de la empresa y/o negocio. Cuanto no se encuentra al sucesor dentro de la familia, se puede buscar un candidato externo o pensar en la posibilidad de vender la empresa.

Carlos Agreda, Ph. D

Generalidades

2

1

     

Ser un integrador y motivador Dar el ejemplo Proponer metas posibles y atractivas Procurar los medios para conseguirlas Saber motivar Alcanzar un compromiso personal con toda la organización; a esto se le denomina el contrato psicológico: aceptar y ser aceptado, no impuesto

Carlos Agreda, Ph. D

El perfil del líder sucesor, debe tener capacidades desarrolladas para:

3

Carlos Agreda, Ph. D

Pasos a seguir para seleccionar al líder sucesor, son los siguiente: 1. Identificar retos: Conocer e identificar los retos internos que tiene la empresa y definir el panorama estratégico: ¿Cual es la visión de la empresa?

4

2

Carlos Agreda, Ph. D

2. Diseñar el perfil de liderazgo: ¿Cuál deberá ser el perfil del próximo líder de la empresa?; si es una empresa familiar, esto primero se define en el concejo de familia y luego en los lideres del directorio, etc.

5

Carlos Agreda, Ph. D

3. Recopilar información del futuro líder sucesor

6

3

Carlos Agreda, Ph. D

4. Evaluar a los futuros lideres que estarán al frente de la empresa: Conocer las posibilidades y habilidades de cada uno de los candidatos.

7

Carlos Agreda, Ph. D

5. Existen buenos candidatos dentro de la familia?: De no existir un candidato interno que reúne las condiciones y expectativas, se debe buscar candidatos externos.

8

4

Carlos Agreda, Ph. D

6. Escoger el mas idóneo.

9

Carlos Agreda, Ph. D

7. Anunciar la decisión

10

5

Programación Lineal Entre los avances científicos más importantes de la mitad del siglo XX es la Programación Lineal, por su impacto desde 1950 ha sido extraordinario por sus aplicaciones. Especialmente en el calculo científico que se lleva a cabo por medio de las computadoras.

Carlos Agreda, Ph. D

Introducción:

11

Carlos Agreda, Ph. D

Un modelo de P. L. proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles y/o alternativas.

12

6

Programación Lineal En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones. Posteriormente el matemático fránces Jean BaptisteJoseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.

Carlos Agreda, Ph. D

Origen

13

En este año, el matemático ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada actualmente programación lineal .

Carlos Agreda, Ph. D

Si no se le toma en cuenta al matemático Gaspar Monge (1746-1818), quien en 1776 se interesó por problemas de este género, se debe enfatizar que en el año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal.

14

7

Carlos Agreda, Ph. D

En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch, razón por la cual se suele conocer con el nombre de problema de KoopmansKantarovitch. Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal. En estos años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.

15

En 1947, G.B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo denominado SCOOP (Scientific Computation of Optimum Programs).

Carlos Agreda, Ph. D

Paralelamente a los hechos descritos se desarrollan los modelos de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban originando.

16

8

Respecto al método del algoritmo simplex, que se estudiara mas adelante, se puede enfatizar que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma IBM. Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903-1957), quien en 1928 publicó: “La Teoría de Juegos”. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y, desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran en el desarrollo de esta disciplina.

Carlos Agreda, Ph. D

17

Carlos Agreda, Ph. D

Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puente aéreo de Berlin. Luego se continuó con una serie de aplicaciones de tipo preferentemente militar. Hacia 1950 se constituyen, fundamentalmente en Estados Unidos, distintos grupos de estudio para ir desarrollando las diferentes ramificaciones de la programación lineal. Cabe citar, entre otros, Rand Corporation, con Dantzig, Orchard-Hays, Ford, Fulkerson y Gale, el departamento de Matemáticas de la Universidad de Princenton, con Tucker y Kuhn, así como la Escuela Graduada de Administración Industrial, dependiente del Carnegie Institute of Technology , con Charnes y Cooper.

18

9

Se ha estimado, de una manera general, que si un país subdesarrollado utilizase el modelo de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año.

Carlos Agreda, Ph. D

En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costos previstos.

19

Programación Lineal La programación lineal es uno de los primeros modelos matemáticos de la investigación de operaciones el cual es usado para encontrar un valor extremo de una función lineal dada y compuesta de varias variables; cuando estas deben ser no negativas y ellas deben satisfacer ciertas restricciones las cuales se presentan en la forma de ecuaciones o inecuaciones lineales. El problema mas simple de programación lineal generalmente contiene un total de 2 a 3 variables.

Carlos Agreda, Ph. D

Definición:

20

10

Investigación De Operaciones Minimiza costos operaciones

Consecuentemente maximiza la rentabilidad de las empresas de cualquier actividad económica Carlos Agreda, Ph. D

Máxima producción y productividad

21

Objetivo:

Construir modelos de programación lineal para problemas propios de la industria, en este caso minero-metalúrgica. Discutir las propiedades de las soluciones optimas en modelos de programación lineal, etc.

Carlos Agreda, Ph. D

Es optimizar la utilización de los recursos disponibles.

22

11

Carlos Agreda, Ph. D

23

¿Qué es Programación? Programación es el planeamiento generalmente de actividades económicas con propósitos de optimización.

Maximizar ganancias

+

o

-

Minimizar costos

Carlos Agreda, Ph. D

Por ejemplo:

24

12

uso

de

interpretación

El método simplex. Modelo dual y precio optimo. Análisis de pos-optimalidad y P. L. bajo incertidumbre.

Carlos Agreda, Ph. D

Programación Lineal

Modelo y geométrica.

25

Características de la programación lineal.

Es un modelo de la investigación de operaciones usada para maximizar y/o minimizar una función objetivo cualquiera, sujeta a ciertas restricciones. Las variables que intervienen tanto en la función objetivo como en las restricciones son lineales o de primer grado; además dichas variables deben ser continuas. La programación lineal generalmente es usada para optimizar la distribución de recursos disponibles.

Carlos Agreda, Ph. D

Las características principales de la programación lineal entre otras son las siguientes:

26

13

Para solucionar los problemas aplicando la programación lineal existen algoritmos genéricos que simplifican dicha solución. En la actualidad, existen varios softwares para solucionar problemas de cualquier tipo aplicando programación lineal; los cuales representan una gran ayuda técnico-económica, etc., etc.

Carlos Agreda, Ph. D

El valor optimo obtenido usando la programación lineal es único, no siendo necesario utilizar las condiciones de segundo grado que complican los cálculos.

27

Proporcionalidad: En un modelo de P. L la función objetivo y cada restricción de las variables de decisión tienen que ser lineales. Es decir el indicador de eficiencia (utilidad o costo) en la función objetivo y la cantidad de cada recurso usado tienen que ser proporcionales, al valor de cada variable de decisión considerada individualmente.

Carlos Agreda, Ph. D

Otras características de los problemas de P. L. son:

28

14

Carlos Agreda, Ph. D

Aditividad: En un modelo de P. L, es necesario que cada variable sea “aditiva” respecto a la utilidad (o costo) y a la cantidad de recursos usados.

Divisibilidad: Para muchos de los problemas propios de los negocios es muy frecuente el caso de que las variables de decisión puedan tener significado físico, solamente si tienen valores enteros. Por lo tanto, otra limitación de la P. L es que para obtener una solución optima los niveles fraccionarios de las variables de decisión, tienen que ser descontados.

Carlos Agreda, Ph. D

29

30

15

Carlos Agreda, Ph. D

Optimalidad: Es un problema de P. L una solución de máxima utilidad o mínimo costo siempre ocurre en uno de los vértices del conjunto de soluciones factibles.

31

Planteamiento general del problema de programación lineal El problema general de programación lineal puede ser planteado, como sigue:

Min

Sujeto a: m

a i 1

ij xj

n

( Z )   cj xj j 1

≥ = bi ≤

i  1, 2....., m

Donde:

j  1,2......, n

aij, cj y bj son constantes.

y, xj  0

xj, son variables continuas

Carlos Agreda, Ph. D

Max

32

16

En otras palabras, se tiene: Función objetivo. n

F , O.( Z )   cj xj (Maximización o minimización).

Restricciones funcionales m

a j 1

ij xj

≤ = bi ≥

i  1, 2....., m j  1, 2......, n

Carlos Agreda, Ph. D

j 1

33

Condiciones de no negatividad. xj ≥ 0 j = 1, 2, …., n

En otras palabras, se cumple que: xj = irrestricta en signo para algunos valores de j Si se considera el problema con tres variables y tres restricciones; la maximización de Z se puede expresar matemáticamente mediante la siguiente expresión:

Max Z  C1 X 1  C2 X 2  .......  Cn X n

Carlos Agreda, Ph. D

Se debe mencionar que para algunas situaciones especiales se elimina las condiciones de no negatividad para algunas variables de decisión.

34

17

Sujeto a: A1 1 x1 + a1 2 x2 + ………+ a1 n ≤ b1 A2 1 x1 + a2 2 x2 + ………+ a2 n ≤ b2 A3 1 x1 + a3 2 x2 + ………+ a3 n ≤ b3 Carlos Agreda, Ph. D

. . . Am 1 x1 + am 2 x 2 + ………+ am n ≤ bm

35

La condición de no negatividad, será: x1 ≥ 0; x2 ≥0, …….., xn ≥0

Max ( Z )  c1 , c2 , c3 ,......., cn  Donde:

bi  vector columna

 x1  x   2  x3    .  .     xn 

 cx

Carlos Agreda, Ph. D

El problema de maximización también puede ser expresado de la siguiente manera:

c  vector fila x  vector columna

36

A  matriz mxn

18

a1 1 a1 2 ......a1n    a2 1 a2 2 ......a2 n       .     .    am1 am2 ......amn   

 x1  x   2 .    .   xm   

b ≥  1 b  2 =   .  ≤   .  bm   

Ax

≥



≤

b

Carlos Agreda, Ph. D

Las restricciones pueden expresarse matricialmente de la siguiente manera:

37

 x1  0 x     2  0  .   .  x  0     .  0  xm  0   Por otro lado, el problema de programación lineal puede también plantearse de la siguiente manera:

Carlos Agreda, Ph. D

La condición de no negatividad puede también expresarse matricialmente de la siguiente manera:

38

19

Uso del recurso/unidad

Recurso

1 2 3 ……….n

1 2 3 . . . . m

a11 a12 a13 …….. a1 n a21 a22 a23 …….. a2 n a31 a32 a33 …….. a3n

am1 am2 am3 …….. amn ∆z/unidad nivel

c1 X1

Cantidad del recurso disponible b1 b2 b3 . . . . Bm

Carlos Agreda, Ph. D

Actividad

c2 c3 ……... cn x2 x3 …….. xn

Donde: xj = Nivel de la variable j (variable de decisión) (j = 1, 2, …., n) cj = incremento en Z que resultaría debido a cada unidad de incremento en xj. (j = 1, 2, …., n) coeficiente de beneficio de la j-enesima variable z = medida global de la efectividad. Función objetivo, funcional o función preferencial (maximizar o minimizar ganancias o costos) bi = Cantidad de recursos disponibles en la i-esima restricción unidad de recurso, i = 1, 2 …., m aij = cantidad de recurso i consumida por cada unidad de la actividad j. Coeficiente de la j-esima variable de decisión en i-esima restricción

Carlos Agreda, Ph. D

39

40

20

Resumiendo se tiene que en forma vectorial el planteamiento de un problema de programación lineal seria como sigue: Zopt = C x } función objetivo

Ax X

≥ B } Restricción ≤ = ≥o } Condiciòn de no negatividad

Carlos Agreda, Ph. D

Sujeto a:

Donde: X = (x1, x2, …., xn)T = Vector columna con n componentes. Se le denomina vector de actividad; y sus componentes son variables de decisión.

41

C = (c1, c2, …., cn) = vector fila con n componentes. Se le denomina vector de precios o costos unitarios (coeficiente beneficio) B = (b1, b2, …., bm) T = Vector columna con m componentes.

0 = (0, 0, …., 0) T = vector columna de n ceros.

 a11a12 ....a1n     a21a22 ....a2 n  Matriz de m filas y n   A .  columnas. Se le denomina   matriz de coeficientes. .     am1am 2 ....amn 

Carlos Agreda, Ph. D

Se le denomina vector de disponibilidad de recursos.

42

21

aij = Representa la cantidad de recursos j que se necesita por unidad de la actividad i. i = 1 …. m j = 1 …. n ser

Carlos Agreda, Ph. D

En forma esquemática la programación lineal puede representada como se muestra en el siguiente diagrama: Sistema real

x

Programación lineal

Variable xj

x

x

Modelo

x

Sistema real “supuesto” o “simulado”

Representación matemática f(x) funciones lineales

43

Métodos de solución de los problemas de programación lineal.

•Grafico •Algebraico •Del algoritmo simplex •Del algoritmo del tablero simplex.

Cada uno de estos métodos tienen sus ventajas, desventajas y/o limitaciones, por lo tanto, cada uno de ellos serán analizados, evaluados y discutidos a través de varios ejemplos prácticos aplicables a cualquier actividad económica en general.

Carlos Agreda, Ph. D

La aplicación del modelo de P. L para resolver cualquier problema, se puede efectuar usando los siguientes métodos:

44

22

Método Grafico

El método de solución será mostrado a través de un problema sencillo que se presenta con frecuencia en la industria minera, cuyo enunciado es el siguiente:

Carlos Agreda, Ph. D

El método grafico de solución de los problemas de programación lineal esta restringido solamente a 2 ó 3 variables y por lo tanto, sus limitaciones son obvias.

45

Summary Para solucionar los problemas usando el modelo matemático de programación lineal en la técnica de transporte, se debe tener en cuenta lo siguiente: 2. Overtime in one center versus straight time in another 3. Addition of more machines (additional available time in the machine center) 4. Addition of new machines, special tools or improvements (reduction in unit production rates)

Carlos Agreda, Ph. D

1. Addition of extra shifts

46

23

5. Changes in prices to meet a competitive market 6. Cost (reduction in profits) of good-will items 7. Direction of sales effort Carlos Agreda, Ph. D

8. Optimum product mix

47

Problema de aplicación Nº 1.

Labores mineras Tajeo 1 Tajeo 2

Zn (%)

Pb (%)

Producción planificada (Tm/día)

Costo ($) (Hr/hombre/Tm)

4 8

6 4

40 60

4 6

Carlos Agreda, Ph. D

En una operación minera subterránea que explota los minerales de plomo (Pb) y Zinc (Zn), las estadísticas de producción son las siguientes:

48

24

Los requerimientos de producción son los siguientes: i) 80 Tm de mineral por día

Se pide: i. Usando el método grafico, calcular la producción que debe extraerse de cada uno de los tajeos, de tal manera de cumplir con los requerimientos de esta, a un costo mínimo por hora/hombre.

Carlos Agreda, Ph. D

ii) El contenido de mineral en promedio debe ser: No menor de 6.5% de Zn, y no menor de 4.5% de Pb.

49

ii. Discutir los resultados

Solución. Sea x1 el tonelaje explotado por día del tajeo 1. Sea x2 el tonelaje explotado por día del tajeo 2.

 Hrs / hom bre   Hrs / hom bre  Min ( Z )   4  x1   6  x2 Tm Tm    

Sujeto a las siguientes restricciones: i) La capacidad de producción del:

Carlos Agreda, Ph. D

En este caso la función objetivo será planteada de la siguiente manera:

Tajeo 1 …….. x1 ≤ 40 Tm/dia ii) La capacidad de producción del:

50

Tajeo 2 …….. X2 ≤ 60 Tm/dia

25

Min Z  4 x1  6 x2 Luego el planeamiento matemático para resolver este problema de programación lineal mediante el método grafico será el siguiente:

Carlos Agreda, Ph. D

iii. La producción requerida es: x1 + x2 = 80 Tm/día. iv. Contenido mínimo de Zn: 0.04x1 + 0.08x2 ≥0.065 (x1+x2) v. Contenido mínimo de Pb: 0.06x1 + 0.04x2 ≥0.045 (x1+x2)

Sujeto a:

x1

≤ 40 …..

(1)

x2

≤ 60 …..

(2)

x1 + x2

≤ 80 …..

(3)

-2.5x1 + 1.5x2

≥ 000 …..

(4)

1.5x1 - 0.5x2

≥ 000 …..

(5)

y obviamente: x1, x2 ≥ 0 ….. (6) Por lo tanto, la solución grafica estará contenida en el primer cuadrante (esta prácticamente es una condición general para este tipo de problemas, desde que ellos tratan acerca de tonelajes, dólares, recursos, etc., etc. en los cuales valores negativos no son aceptables.

Carlos Agreda, Ph. D

51

52

26

Carlos Agreda, Ph. D Carlos Agreda, Ph. D

La solución grafica para este problema se muestra en el diagrama conceptual siguiente: 53

54

27

En el cual se puede observar lo siguiente:

El área ABC incluye todos los puntos interiores o al costado del triangulo ABC. Se debe notar que el área es convexa y que la solución optima es un punto extremo de esta área convexa.

Carlos Agreda, Ph. D

Las coordenadas (x1, x2) de un punto satisfacerían todas las restricciones si y solamente si; este punto esta contenido en el área ABC; esto hablando en términos del álgebra de espacios vectoriales.

55

x1 = 0, x2 = 0

z=0

x1 = 30, x2 = 50

 z = 420

x1 = 20, x2 = 60

 z = 440

La solución optima se puede apreciar que es:

Carlos Agreda, Ph. D

Se puede observar también que, para:

x1 = 30 x2 = 50 56

28

Carlos Agreda, Ph. D

Se debe mencionar también que la mayoría de los problemas que son necesarios resolver en las diversas organizaciones industriales constan de 2 ò 3 variables por lo tanto, se debe trabajar con poliedros convexos en lugar de polígonos convexos; y en estos casos ya el método grafico no es aplicable; entonces, es necesario buscar otros métodos de solución para este tipo de problemas.

57

Terminología usada en la solución de problemas de programación lineal.

Solución básica factible: Es una solución factible de tantas soluciones variables como ecuaciones tiene el sistema en estudio. Solución Optima: Es una solución básica factible que tiene el valor mas favorable de la función objetivo. (El mayor o el menor, dependiendo si se trata de maximización o de minimización) El objetivo de la P. L es encontrar la solución factible que sea la optima.

Carlos Agreda, Ph. D

Solución factible: Es una solución que satisface todas las restricciones aplicables al sistema en estudio.

58

29

La posibilidad de que un problema no tenga soluciones optimas ocurre cuando: a) Si no tiene soluciones factibles b) Si las restricciones no evitan el crecimiento de la F. O., indefinidamente en la dirección favorable z.

Carlos Agreda, Ph. D

Generalmente, un problema de P.L. tendrá una solución optima. Sin embargo, también es posible tener soluciones optimas múltiples (Rectas que representan a las restricciones paralelas al funcional).

59

Problema de aplicación Nº 2. Se tiene el siguiente problema de programación lineal.

Subject to:

X1 + x2 ≤ 20

→ (1)

X1 = 15

→ (2)

X1 + 3x2 ≤ 45

→ (3)

-3X1 + 5x2 ≤ 60

→ (4)

Carlos Agreda, Ph. D

Max Z = 3x1 + 2x2

Se pide: • Solucionar el problema de P. L, usando el método grafico.

60

• Discutir los resultados

30

una compañía minera subterránea, ubicada a 4500 MOSL produce dos tipos de concentrados. La mezcla proviene del mineral que se explota de 4 labores subterráneas (tajeos). La disponibilidad del tonelaje de mineral proviene de cada labor minera y el beneficio económico $/Tm. Se muestra en la tabla I Tabla I Mining stopes A B C D Utility (US$/Tm)

Tipos de concentrados I (TM)

II (TM)

Disponibilidad (Tm/month)

1 2 2 1

3 1 2 1

15,000 10,000 12,000 10,000

4

3

Carlos Agreda, Ph. D

Problema de aplicación Nº 3.

61

Se pide:

Carlos Agreda, Ph. D

i. Calcular el tonelaje de concentrado de cada tipos de mineral que debe producirse, para maximizar la rentabilidad de dicha empresa minera ii. Discutir los resultados

62

31

Método Algebraico El presente método de solución será mostrado a través del siguiente ejemplo:

Sujeto a: 1x1 + 3x2

≤ 15000 ….. (A)

2x1 + 1X2

≤ 10000 ….. (B)

2x1 + 2X2

≤ 12000 ….. (C)

1x1 + 1X2

≤ 10000 ….. (D)

x1 ≥ 0

Carlos Agreda, Ph. D

Max Z  4 x1  3 x2

63

x2 ≥ 0

En primer lugar se agregan las variables de holgura para transformar las inecuaciones en ecuaciones y se tiene lo siguiente:

2x1 + 1x2 2x1 + 2x2 1x1 + 1x2

=15000 (A) + x4

= 10000 (B) + x5 + x6

= 12000 (C) = 10000 (D)

Carlos Agreda, Ph. D

1x1 + 3x2 + x3

Max. Z = 4x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 64

32

Como hay cuatro ecuaciones (m) y seis incógnitas (n) → se debe suponer que el problema tendrá n – m = 2 variables iguales a cero. En este caso se tiene:

m

=

6 2

= 15 combinaciones posibles.

Es decir, hay que resolver 15 veces el sistema de ecuaciones asignando el valor cero a un par de variables en cada solución o iteración respectiva.

Carlos Agreda, Ph. D

n

65

Solución básica factible: Se elige x1 = 0 x2 = 0 y se obtiene la 1era. Solución básica factible.

x1 = 0 x3 = 15000 x4 = 10000 x5 = 12000

Z = 0 Es decir esta solución es no producir nada y las variables de holgura x3, x4, x5, x6; solo reportan disponibilidad.

Carlos Agreda, Ph. D

x2 = 0

x6 = 10000 66

33

¿Qué variable saldría de la solución básica factible? ¿Cuál de las variables no nulas se convertirían o se le deben asignar el valor cero para obtener la siguiente solución? Para ello se expresa el conjunto de variables no nulas del sistema de ecuaciones (1) en función de x1 (la variable que ingresa).

Carlos Agreda, Ph. D

Como se esta maximizando, se debe introducir en la solución, aquella variable que reporte mayor beneficio, cj es mayor. En este caso el cj de la función objetivo de mayor beneficio es c1 = 4 que corresponde a x1.

67

x2 = 0 x1 + x3 = 15000 --- x3

= 15,000 – x1 → x1 = 15000

2x1 + x5 = 12000 --- x5

= 12,000 – 2x1 → x1 = 6000

x1 + x6 = 10000 --- x6

= 12,000 – x1 → x1

= 10000

Al igualar x3, x4, x5, x6 = 0 se obtendrá varios valores de x1 y se elige el menor porque si se toma alguno de los otros, cualquiera de las ecuaciones del sistema (2) tomaría un valor negativo, contradiciendo las condiciones de no negatividad.

Carlos Agreda, Ph. D

2x1 + x4 = 10000 (2) --- x4 = 10,000 – 2x1 → x1 = 5000

68

34

 x1  5000   Re ales x  0  2  x3 = 15000 - 5000 = 10000 x4 = 10000 - 2 x 5000 = 0

z = 20000

x5 = 12000 – 2 x 5000 = 2000

Carlos Agreda, Ph. D

Se elige → x1 = 5000 y el sistema será:

x6 = 10000 – 5000 = 5000 69

Búsqueda de la mejor solución.

De la ecuación (1) se busca aquellas que contengan a x2 y x4; es decir (B): 2x1 + 1x2 + x4 = 10000 → x1 = 5000 - ½x2 - ½x4

Carlos Agreda, Ph. D

Como x2 = 0 y x4 = 0 se debe introducir una nueva variable a la solución, Entre x2 y x4.

70

35

Zmax = 4x1 + 3x2 Zmax = 20000 + x2 – 2x4  Se introduce x2

Como se maximiza, se ve que la incorporación de x2 lo beneficia, mientras que x4 lo perjudica.

Carlos Agreda, Ph. D

Reemplazando este valor de x1 en el funcional Z se obtiene:

71

Obtención de la tercera solución. Como x2 ingresa al conjunto solución, el sistema (1). Se despejan las variables para ponerlas en función de:

De A) x1 + 3x2 + x3 = 15000 x3 = 15000 – x1 – 3x2 x3 = 15000 – (5000 – ½x2) -3x2

Carlos Agreda, Ph. D

x2 (x4 = 0 ….)

x3 = 10000 – 5/2x2 → () 72

36

De B) 2x1 + x2 + x4 = 10000

De C) 2x1 + 2x2 + x3 = 12000 x5 = 12000 – 2 (5000- ½x2) – 2x2 x5 = 2000 – x2 → () De D) x1 + x2 + x6 = 10000 x6 = 10000 – (5000- ½x2) – x2 x6= 5000 – ½x2 → (w)

Carlos Agreda, Ph. D

x1 = 5000 – ½x2 → ()

73

De: () x3 = 0 cuando x2 = 4000 () x1 = 0 cuando x2 = 10000 (se elige el valor menor para () x5 = 0 cuando x2 = 2000

evitar valores negativos)

La tercera solución quedaría: x1 = 4000 x2 = 2000 (4)

x3 = 5000

Z = 22,000

x4 = 0

Se ha mejorado la solución

x5 = 0

¿será la optima?

Carlos Agreda, Ph. D

(w) x6 = 0 cuando x2 = 10000

74

x6 = 4000

37

Veamos si se puede introducir x4 ò x5 que valen cero: En el sistema (1) se buscan aquellas soluciones que contengan x4 y x5 ò x4 y x5 en forma independiente. (B) 2x1 + x2 x4 = 10000 x1 = 5000 – ½x2 – ½x4 x1 = 6000 – x2 – ½x5

Carlos Agreda, Ph. D

(C) 2x1 + 2x2 + x5 = 12000

Igualando a ambas: 5000 – ½x2 – ½x4 = 6000 – x2 – ½x5 x2 = 2000 + x4 – x5

75

Reemplazando x2, se tiene lo siguiente: Z = 20000 + (2000 + x4 – x5) 2x4

La introducción de x4 ò x5 no mejora al funcional, la solución obtenida en ) es la optima. Como se puede apreciar este método algebraico es tedioso y consume mucho tiempo para solucionar problemas de P. L que se presentan en todas y cada de las organizaciones industriales; por lo que los diferentes investigadores propusieron métodos matemáticos mas directos para dar solución a este tipo de problemas y se planteo el método y el algoritmo simplex.

Carlos Agreda, Ph. D

Z = 22000 – x4 – x5

76

38

Conceptos fundamentales del algoritmo simplex.

Básicamente el método simplex traslada la definición geométrica del punto extremo a una definición algebraica. Fundamentalmente, la transición del procedimiento grafico al algebraico se basa en la validez de la siguiente relación:

Carlos Agreda, Ph. D

Se expondrán los conceptos básicos y las definiciones del álgebra lineal del espacio n-dimensional que son necesarias para la solución de problemas de P. L usando el algoritmo simplex.

77

Creación del método simplex

Para ello se debe tener en cuenta lo siguiente: • Los algoritmos del método simplex primal y, • Los simplex dual.

Carlos Agreda, Ph. D

Se inicia con la elaboración de la forma estándar necesaria para representar el espacio de soluciones de la programación lineal, por medio de un sistema de ecuaciones simultaneas.

78

39

Adicione las variables de holgura a todas las desigualdades.

Paso 1

Encontrar una solución básica factible

Paso 2

Si

¿puede encontrar una solución básica factible “mejor” (una que aporte una utilidad mas alta)

Resuelva para la “mejor” solución básica factible

Paso 3

No

La solución básica factible es la Paso 4 optima

Stop.

Carlos Agreda, Ph. D

Paso 0

79

Aspectos generales sobre el método simplex.

2. El método simplex es un método de cambio de bases. Una variable entra a la base, la variable básica entrante, y una variable sale de la base, la variable básica saliente. 3. El método de cambio de base implica el reemplazo de un sistema de restriccionesecuaciones por un sistema equivalente de restricciones-ecuaciones.

Carlos Agreda, Ph. D

1. El método simplex encuentra una solución optima (o una solución básica optima factible).

80

40

O1: Reemplazar una ecuación por si misma, tantas veces una constante diferente de cero. O2: Reemplazar una ecuación por si misma, sumada a tantas veces una constante diferente de cero otra ecuación restricción. 5. El método simplex requiere que la función objetivo sea expresada de tal forma que cada variable básica, tenga como coeficiente 0.

Carlos Agreda, Ph. D

4. En un sistema de restricciones-ecuaciones, una ecuación puede ser reemplazada por una ecuación equivalente aplicando las operaciones siguientes:

81

Carlos Agreda, Ph. D

6. El método simplex requiere que cada variable básica aparezca en una y solamente una ecuación-restricción.

82

41

Carlos Agreda, Ph. D

Lo mas importante de un ser humano es reclamar su propia y vital vocación. “La vocación actúa como una ley divina de la que no hay escapatoria”, pero muy pocos se atreven a luchar por su sueño, además de que en nuestro sistema educativo, se nos enseña a ser conformistas y dar gusto a los demás, aun cuando tengamos que renunciar a nuestro propio llamado.

Carlos Agreda, Ph. D Profesor

83

42