• Author / Uploaded
• Carlos Mauricio Quintero

Citation preview

PROGRAMACIÓN LINEAL Fragmento tomado de GUZMÁN A, Gloria L. Módulo de Programación Lineal, UNAD 2010, y modificado por William Montoya.

METODO SIMPLEX PARA LA SOLUCIÓN DE EJERCICIOS El mejor método para resolver un problema de programación lineal es el método simplex, ya que es un método de fácil aplicación, de tipo algorítmico y conduce a una eficiente solución del problema. CONCEPTO El método simplex fue desarrollado por George dantzig (1947) y es un método algebraico que se utiliza para resolver problemas de programación lineal en un número finito de pasos en una computadora. Este método establece una solución factible y luego prueba si es óptima o no. Si no lo es busca una mejor solución y si esta no es optima entonces repite el proceso hasta hallar una solución óptima. PASOS PARA EL DESARROLLO DEL METODO SIMPLEX 1. Elaborar la tabla simplex inicial.

X1 X 2 X3 S1  a11 a12 a13  S 2  a 21 a 22 a 23 S 3  a31 a32 a33  S 4  a 41 a 42 a 43 Z  − C1 − C 2 − C 3

S1 S 2 S 3 S 4 Z b 1 0 0 0 0 b1   0 1 0 0 0 b2  0 0 1 0 0 b3   0 0 0 1 0 b4  0 0 0 0 1 0 

Indicadores Existen cuatro variables de holgura, S1, S2, S3, y S4; una para cada restricción.

2. Si todos lo indicadores del último renglón son no negativos, entonces Z tiene un máximo cuando X1=0, X2=0 y X3=0. El valor máximo es 0. Si existen indicadores negativos, localizar la columna en la que aparezca el indicador más negativo. Esta columna señala la variable entrante. 3. Dividir cada uno de los elementos de la columna de b que se encuentran por encima de la recta punteada entre el correspondiente elemento de la columna de la variable entrante. Se debe realizar esta división solo en los casos en los que el elemento de la variable que entra sea positivo.

4. encerrar en un círculo el elemento de la columna de la variable entrante que corresponde al menor cociente del paso 3. Este es un elemento pivote. La variable saliente es la que se encuentra al lado izquierdo del renglón del elemento pivote. 5. Utilizar operaciones elementales sobre renglones para transformar la tabla en otra tabla equivalente que tenga un 1 en donde se encuentra el elemento pivote y 0 en las demás posiciones de esa columna. 6. la variable entrante debe reemplazar a la variable saliente en el lado izquierdo de esta nueva tabla. 7. si todos los indicadores de la tabla nueva son no negativos, ya se tiene una solución óptima. El valor máximo de Z es el elemento del último renglón y la última columna. Ocurre esto cuando las variables se encuentran del lado izquierdo de la tabla son iguales a lo elementos correspondiente de la última columna. Todas las demás variables son ceros. Si cuando menos uno de los indicadores es negativo, se debe repetir el mismo proceso con la nueva tabla, comenzando con el paso 2. EJEMPLOS DESARROLLADOS EJEMPLO 1 Maximizar Z= 5X1+4X2 Sujeto a: X1+X2 ≤ 20 2X1+X2 ≤ 35 -3X1+X2 ≤ 12 X1≥0, X2≥0 Este problema de programación lineal se ajusta a la forma normal. La tabla simplex inicial es:

X 1 X 2 S1 S 2 S 3 Z

Variable saliente

S1  1 1  S2 2 1 S3 − 3 1  Z  − 5 − 4 Variable Entrante

1 0 0 0

0 1 0 0

0 0 1 0

Indicadores

b

0 20   0 35  0 12   1 0 

Cocientes 20÷1=20 35÷2=17,5

El indicador mas negativo, -5, aparece en la columna x1. Por ello, x1 es la variable entrante. El menor cociente es 17.5, de modo que, S2 es la variable saliente. El elemento pivote es 2. Utilizando operaciones elementales sobre los renglones para obtener un 1 en la posición del pivote y 0 en las demás posiciones de esa columna, se tienen:

X 1 X 2 S1 S 2 S 3 Z

S1  1 1  S2 2 1 S3  − 3 1  Z  − 5 − 4

1 0 0 0

S1  1 1  S 2  1 1/ 2 S3  − 3 1  Z  − 5 − 4

1 0 0 1/ 2 0 0 0 0

S1  0 1 / 2  S 2 1 1/ 2 S3 0 5 / 2  Z  0 − 3 / 2

1 −1/ 2 0 1/ 2 0 3/ 2 0 5/ 2

0 1 0 0

0 0 1 0

b

0 20   0 35  0 12   1 0  0 20   0 35 / 2  0 12   1 0 

0 0 1 0 0 0 1 0

Multiplicando el renglón 2 por 1/2

al renglón 1 el renglón 2 0 5 / 2  Sumando multiplicado por -1;  0 35 / 2  sumando al renglón 3 el renglón 2 0 129 / 2  multiplicado por 3;  1 175 / 2  Sumando al renglón 4 el renglón 2 multiplicado por 5

La nueva tabla es:

Variable saliente

X1 X 2 S1  0 1 / 2  X 1 1 1 / 2 S3 0 5 / 2  Z  0 − 3 / 2

S1 S 2 S3 Z b 1 −1/ 2 0 0 5 / 2   0 1 / 2 0 0 35 / 2  0 3 / 2 1 0 129 / 2   0 5 / 2 0 1 175 / 2 

Cocientes 5/2 ÷ ½=5 35/2÷1/2=35 129/2÷5/2=25(4/5)

Variable entrante

Obsérvese que en el lado izquierdo, x1 reemplazó a S2. Ya que -3/2 es el indicador más negativo se debe continuar con el proceso. La variable entrante es ahora x2. El menor cociente es 5. De modo que S1 es la variable saliente y ½ es el elemento pivote. Utilizando operaciones elementales sobre renglones, se tiene:

X1 S1  0  X 1 1 S3 0  Z  0

X 2 S1 S 2 S3 Z 1/ 2 1 −1/ 2 0 0

1/ 2 0 5/ 2 0 − 3/ 2 0

1/ 2 3/ 2 5/ 2

S1  0 1 / 2 1 − 1 / 2  X 1 1 0 − 1 1 S3  0 0 − 5 4  Z  0 0 3 1

b 5/ 2   0 0 35 / 2  1 0 129 / 2   0 1 175 / 2 

0 0 1 0

0 5 / 2  Sumando al renglón 2 el renglón 1 0 15  multiplicado por -1; sumando al renglón 3 el renglón 1 0 52  multiplicado por -5;  Sumando al renglón 4 el renglón 1 1 95  multiplicado por 3

S1  0  X 1 1 S3  0  Z  0

1 2 −1 0 −1 1 0 −5 4 0 3 1

0 0 1 0

0 5  0 15  0 52   1 95 

Multiplicando el renglón 1 por 2.

La nueva tabla es:

X 1 X 2 S1 S 2 S 3 Z

X 20  X1 1 S3  0  Z  0

1 2 −1 0 −1 1 0 −5 4 0 3 1

0 0 1 0

b

0 5  0 15  0 52   1 95 

En donde x2 reemplazo a S1 en el lado izquierdo. Como todos los indicadores son no negativos, el valor máximo de Z es 95 y aparece cuando x2=5 y x1=15 (y S3=52, S1=0, S2=0). EJEMPLO 2 Maximizar Z= 3x1 + 4x2 + 3/2x3 Sujeta a: -x1-2x2 ≥ -10 2x1+2x2+x3 ≤ 10 x1, x2, x3 ≥ 0 La restricción -x1-2x2 ≥ -10 no se ajusta a la forma normal. Sin embargo, multiplicando ambos lados por -1 resulta:

x1+2x2 ≤10 TABLA SIMPLEX I

Variable saliente

S1 S2 Z

X1 X 2 1 2

2

X 3 S1 S 2 Z b 0 1 0 0 10

2

1

0 1 0 10

− 3 − 4 − 3/ 2 0 0 1

Cocientes 10÷2=5 10÷2=5

0

Variable entrante

La variable entrante es x2. Dado que existe un empate en el menor cociente, se puede elegir cualquiera de los dos, S1 o S2, como la variable saliente. Se escoge S1. Se encierra en un círculo el pivote. Utilizando operaciones elementales sobre renglones, se obtiene la tabla 2.

TABLA SIMPLEX II

Variable saliente

X1 X 2 X 2 1/ 2 1

X 3 S1 S 2 Z 0 1/ 2 0 0

b 5

S2

1

0

1

−1

1 0

0

Z

−1

0 − 3/ 2

2

0 1 20

Cocientes No hay puesto, que 0 no es positivo 0÷1=0

Variable entrante

La tabla II corresponde a una SFB (solución básica factible) en la que una variable básica S2 es 0. Por ello, la SFB es degenerada. Ya que existen indicadores negativos, se continúa el proceso. La variable entrante es ahora x3, la variable saliente es S2 y el pivote se encuentra encerrado en un círculo. Utilizando operaciones elementales sobre renglones, se obtiene la tabla III.

TABLA SIMPLEX III

X1 X 2

X 3 S1 S 2

X 2 1/ 2 1 0 1/ 2 X 3 1 0 1 −1 Z

0 1

Z

b

0 0

5 0

1 / 2 0 0 1 / 2 3 / 2 1 20 indicadores

En virtud de que todos los indicadores son no negativos, Z es máxima cuando x2=5 y x3=0, y x1=S1=S2=0. El máximo valor es Z=20. Obsérvese que este valor es igual al valor de Z correspondiente a la tabla II. En problemas con degeneración es posible llegar al mismo valor de Z en varias etapas del proceso simplex. EJERCICIOS PARA PRACTICAR POR MÉTODO SIMPLEX 1. MAXIMIZAR Z= x1 + 2x2 Sujeta a 2x1 + x2 ≤ 8 2x1 + 3x2 ≤ 12 x1, x2 ≥ 0 2. MAXIMIZAR Z= -x1 + 3x2 Sujeta a x1 + x2 ≤ 6 -x1 + x2 ≤ 4 x1, x2 ≥ 0 3. MAXIMIZAR Z= 8x1 + 2x2 Sujeta a x1 – x2 ≤ 1 x1 + 2x2 ≤ 8 x1 + x2 ≤ 5

x1, x2 ≥ 0 4. Una compañía de carga maneja envíos para 2 compañías, A y B, que se encuentran en la misma ciudad. La empresa A envía cajas que pesan 3 libras cada una y tiene un volumen de 2 pies³; la B envía cajas de 1 pie³ con peso de 5 libras cada una. Tanto A como B hacen envíos a los mismos destinos. El costo de trasporte para cada caja de A es $7500 y para B es $5000. la compañía transportadora tiene un camión con espacio de carga para 2400 pies³ y capacidad máxima de 9200 libras. En un viaje, ¿Cuántas cajas de cada empresa debe transportar el camión para que la compañía de transportes obtenga el máximo ingreso? ¿cual es este máximo? 5. una compañía fabrica 3 productos X, Y, Z. cada producto requiere de los tiempos de maquina y tiempo de terminado como se muestran en la tabla. Los números de horas de tiempo de maquinas y de tiempo de terminado disponibles por mes son 900 y 5000 respectivamente. La utilidad por unidad X, Y y Z es $3000, $4000 y $6000 respectivamente. ¿Cual es la utilidad máxima al mes que puede obtenerse?

X Y Z

TIEMPO MÁQUINA 1 2 3

TIEMPO DE TERMINADO 4 4 8