|
Ingeniería Industrial (Academia de IO de la UPIICSA) 1.-Exprese el modelo matemático en la forma estándar. Todas las restricciones del modelo matemático deben convertirse enigualdades. 2. Elabore la tablainicial del simplex:
3. Determine la variableno básica que entra: Se elige como la variable que entra en maximización (minimización) como lavariable no básica que tiene el indicador más negativo (positivo), en la filade coeficientes de la Función Objetivo (Z). Los empates se rompenarbitrariamente. 4. Determine lavariable que sale: Se determina tomando el cociente de los valores en la columna del ladoderecho (LD) de cada restricción entre los coeficientes positivos de la columnade la variable que entra. Si el coeficiente es "cero o negativo"entonces el cociente se considera infinito. La variable básica asociada alcociente más pequeño (en ambos casos, maximización y minimización) es lavariable que sale. Los empates se rompen arbitrariamente. Sin embargo, en casode haber empate y que una de las variables involucradas sea una variableartificial, se elige a ésta como la variable saliente. 5. Aplicación del método Gauss-Jordan (o de operaciones sobre renglones). Mediante este procedimiento se elimina (en realidad se sustituye) la variableque entra, en todas las filas de la tabla. Es decir, se tiene que convertir lacolumna de la variable que entra en un vector columna unitario (un 1 y purosceros). Esto se logra de la siguiente manera: Es decir, se multiplica la fila pivote por el negativo del número que deseamos que se convierta en cero y el resultado de esta multiplicación se suma a la fila donde queremos que aparezca el cero. Los pasos 2, 3, 4 y 5 se repiten hasta que todos los indicadores de la función objetivo sean no negativos (si es de maximización) o sean no positivos (si es de minimización). Cuando esto ocurre se dice que se ha llegado a la solución óptima del problema. Variables artificiales En los problemas anteriores del método simplex hemos utilizado las variablesde holgura como una solución inicial factible. Sin embargo, si la restricciónoriginal es una ecuación ("=") o es del tipo "" , ya no tenemos una solución factible inicial preparada. Por lo que es necesario generar una solución inicial. La idea de utilizarVariables Artificiales es muy simple. Es necesario sumar una variable nonegativa a todas la ecuaciones que no tengan variables básicas iniciales.Las variables agregadas desempeñarán la misma función que una variable deholgura. Sin embargo, como estas variables no tienen un significado físicodesde el punto de vista del problema original ( de aquí el nombre de"artificial"), el procedimiento será valido sólo si hacemos queestas variables sean cero cuando se llegue a la tabla óptima. Algoritmo del Método de la Gran M
Cuando tenemos restricciones de igualdad, de mayor o igual; cuandoalgunas de las bi son negativas o queremos minimizar, para usar elsimplex, debemos identificar una solución básica inicial. Se revisa el problema añadiendo variables artificiales, sólo con el propósitode que sea la variable básica inicial para esa ecuación. Son variablesno-negativas y se altera la función objetivo para que imponer una penalidadexhorbitante en que estas variables artificiales tengan valores mayores de cero.El método del simplex entonces hace desaparecer estas variables hasta que elproblema real es resuelto. Utilizando el método simplex resuelva el siguiente problemade programación lineal. Max Z = 40X1 + 60X2 + 50X3 s.a. 10 X1 + 4 X2 + 2 X3 950 2 X1 + 2 X2 + 410 X1 + + 2 X3 610 X1 , X2 , X3 0
Max Z -40X1 - 60X2 - 50X3 s.a. 10 X1 + 4 X2 + 2 X3 + X4= 950 2 X1 + 2 X2 + + X5 = 410 X1 + + 2 X3 + X6 = 610 X1 , X2 , X3 , X4 , X5, X6 ³ 0
X4 = 950 min í950/4 , 410/2 , -ý X5 = 410 min í237.5 , 205 , -ý X6 = 610
X4 = 130 min í130/2 , - , 610/2ý X2 = 205 min í65 , - , 305ý X6 =610
X3 = 65 min í- , 205/0.5 , 480/2ý X2 = 205 min í- , 410 , 240ý X6 =480
Z* = 20350 X2* = 85 X3* = 305 X5* = 240 X1* = X4* = X6* = 0
Max Z = 40X1 + 60X2 + 50X3 Z = 4 (0) + 3 (85) + 50(305) Z = 20350
10 X1 + 4 X2 + 2 X3 + X4 10(0) + 4( 85) + 2(305) + 0 = 950 2 X1 + 2 X2 + X5 2(0) + 2(85) + 240 = 410 X1 + 2 X3 + X6
Utilizando el método simplex resuelva el siguiente problemade programación lineal. Max Z = 5X1 + X2 + 3X3 s.a. 2 X1 - X2 + 2 X3 £ 4 X1 + X2 + 4 X3 £ 4 X1 , X2 , X3 ³ 0
Max Z - 5X1 - X2 - 3X3 s.a. 2 X1 - X2 + 2 X3 + X4 = 4 X1 + X2 + 4 X3 + X5 = 4 X1 , X2 , X3 , X4 , X5³ 0
X4 = 4 min í 4/2 , 4/1ý X5 = 4 min í 2 , 4ý
X1 = 2 min í - , 2/1.5ý X5 = 2 min í - , 1.33ý
Z* = 44/3 X1* = 8/3 X2* = 4/3 X3* = X4* = X5* = 0
Max Z = 5X1 + X2 + 3X3 Z = 5 (8/3) + 4/3 + 0 Z = 44/3
2 X1 - X2 + 2 X3 + X4 2 (8/3) – 4/3 + 2 (0) + 0 = 4 X1 + X2 + 4 X3 + X5 8/3 + 4/3 + 4 (0) + 0 = 4 Utilizando el método simplex resuelva el siguiente problemade programación lineal. Max Z = 25X1 + 50X2 s.a. 2 X1 + 2X2 £ 1000 3 X1 £ 600 X1 + 3X2 £ 600 X1 , X2 ³ 0
25X1 - 50X2 s.a. 2 X1 + 2X2 + X3 = 1000 3 X1 + X4 = 600 X1 + 3X2 + X5 = 600 X1 , X2 , X3 , X4 , X5³ 0
X3 = 1000 min í 1000/2 , - , 600/3ý X4 = 600 min í 500 , - , 200ý X5 = 600
X3 = 600 min í 600/4/3 , 600/3 , 200/1/3ý X4 = 600 min í 450 , 200 , 600ý X2 = 200
Z* = 35000/3 X1* = 200 X2* = 400/3 X3* = 1000/3 X4* = X5* = 0
Max Z = 25X1 + 50X2 Z = 25 (200) + 50 (400/3) Z = 35000/3
2 X1 + 2X2 + X3 2 (200) + 2 (400/3) + 1000/3 = 1000 3 X1 + X4 3 (200) + 0 = 600 X1 + 3X2 + X5 200 + 3 (400/3) + 0 = 600 Considere el siguiente problema. Min W = 3X1 + 5X2 + X3 s.a. 4 X1 + 2 X2 + X3 ³ 1 8 X1 , X2 , X3 ³ 0 Dual Max Z= 18Y s.a. 4Y1 £ 3 2Y1 £ 5 Y1 £ 1 Y1 ³ 0 Para el primal Min W –3X1 – 5X2 –X3 =0 s.a. –4X1 – 2X2 –X3 +S1 = -18 X1 , X2 , X3 , S1³ 0
El primal no tiene solución porque no se puedeestablecer la variable de entrada. Para el dual Max Z- 18Y1 =0 s.a. 4Y1 + S1 = 3 2Y1 + S2 = 5 Y1 + S3 = 1 Y1 , S1 ,S2, S3 ³ 0
S1 = 3 min í 3/4 , 5/2 , 1/1ý S2 = 5 min í 0.75 , 2.5 , 1ý S3 = 1
Z* = 27/2 Y1* = 3/4 S2* = S3 =0
Z = 18(3/4) = 27/2 4(3/4) = 3 ACTIVA 2(3/4)=1.5 < 5 INACTIVA Y DEFICIT 3/4 = 0.75< 1 INACTIVA Y DÉFICIT Cambiar el coeficiente de x1 a 4 de la funciónobjetivo y resolver el primal y el dual. Min W = 4X1 + 5X2 + X3 s.a. 4 X1 + 2 X2 + X3 ³ 1 8 X1 , X2 , X3 ³ 0 Dual Max Z= 18Y s.a. 4Y1 £ 4 2Y1 £ 5 Y1 £ 1 Y1 ³ 0 Para el primal Min W –4X1 – 5X2 –X3 =0 s.a. –4X1 – 2X2 –X3 +S1 = -18 X1 , X2 , X3 , S1³ 0
El primal no tiene solución porque no se puedeestablecer la variable de entrada. Para el dual: Max Z- 18Y1 =0 s.a. 4Y1 + S1 = 4 2Y1 + S2 = 5 Y1 + S3 = 1 Y1 , S1 ,S2, S3 ³ 0
S1 = 4 min í 4/4 , 5/2 , 1/1ý S2 = 5 min í 1 , 2.5 , 1ý S3 = 1
Z* = 18 Y1* = 1 S2* = S3 =0
Z = 18(1) = 18 4(1) = 4=4 ACTIVA 2(1)=2 < 5 INACTIVA Y DEFICIT 1 = 1 ACTIVA Y DÉFICIT Cambiar el coeficiente de x3 a –1 y a la funciónobjetivo y resolver el primal y el dual. Min W = 3X1 + 5X2 *- X3 s.a. 4 X1 + 2 X2 + X3 ³ 1 8 X1 , X2 , X3 ³ 0 Dual Max Z= 18Y s.a. 4Y1 £ 3 2Y1 £ 5 Y1 £ -1 Y1 ³ 0 Para el primal Min W –3X1 – 5X2 +X3 =0 s.a. –4X1 – 2X2 –X3 +S1 = -18 X1 ,X2 , X3, S1 ³0
-RP+FO -RP
S1 = -18 min í -18/-1 ý min í 18ý
W* = -18 X3* = 18 X1*, X2*, S1*,= 0
W = 3(0) + 5(0) – 18 = -18 4(0) + 2(0) + 18 = 18 ACTIVA Para el dual: Max Z- 18Y1 =0 s.a. 4Y1 + S1 = 3 2Y1 + S2 = 5 Y1 + S3 = -1 Y1 , S1 ,S2, S3 ³ 0
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||