método de la gran m
DESCRIPTION
Se presentan dos ejemplos que resuelven problemas de programación lineal. El primer método utilizado es el de la gran M. El segundo está relacionado con el método de las dos fases.TRANSCRIPT
Instrucciones: Resuelve los siguientes ejercicios
Ejercicio 1 Considera el siguiente problema. Maximizar Z = 2X1 + 5X2 + 3X3 Sujeto a: X1 - 2X2 + X3 ≥ 20 2X1 + 4X2 + X3 = 50 X1, X2, X3 ≥ 0
1.- Utiliza el método de la gran M y construye la primera tabla simplex completa para el método simplex e identifica la solución BF inicial (artificial) correspondiente. También identifica la variable básica entrante inicial y la variable básica que sale. 2.- Aplica el método simplex paso a paso para resolver el problema. 3.-Utiliza el método de las dos fases para construir la primera tabla simplex completa para la fase 1 e identifica la solución BF inicial (artificial) correspondiente. También identifica la variable básica entrante inicial y la variable básica que sale 4.- Aplica la fase 1 paso a paso. 5.- Construye la primera tabla simplex completa de la fase 2. 6.- Aplica la fase 2 paso a paso para resolver el problema. 7.- Compara la secuencia de soluciones BF que obtuvo en el paso 2 con los pasos 4 y 6. Contesta la pregunta.
¿Cuáles de estas soluciones son factibles sólo para el problema artificial obtenido al introducir las variables artificiales y cuáles son factibles para el problema real?
8.-Utiliza un paquete de software basado en el método simplex para comparar sus resultados con los hechos a mano. En el contenido de la unidad 1 y en la bibliografía encontrarás sugerencias de sitios en Internet para usar dicho software.
Ejercicio 2 Considera el siguiente problema. Minimizar Z = 3X1 + 2X2 + 4X3 Sujeto a: 2X1 + X2 + 3X3 = 60 3X1 + 3X2 + 5X3 ≥ 120 X1, X2, X3 ≥ 0
1.- Utiliza el método de la gran M para aplicar el método simplex paso a paso a fin de resolver el problema. 2.- Emplea el método de las dos fases para aplicar el método simplex paso a paso y resolver el problema. 3.- Compara la serie de soluciones BF de los pasos 1 y 2. Contesta la pregunta. ¿Cuáles de esta soluciones son factibles sólo para el problema artificial que se obtuvo al introducir las variables artificiales y cuáles son factibles para el problema real? 4.- Utiliza un paquete de software basado en el método simplex para comparar sus resultados con los hechos a mano. En el contenido de la unidad 1 y en la bibliografía encontrarás sugerencias de sitios en Internet para usar dicho software.
Respuesta
Ejercicio 1. Método de la gran M
Problema original Debido a la forma de las restricciones el problema de programación lineal sufre modificaciones
Primer cambio Segundo Cambio Tercer cambio Maximizar Z = 2X1 + 5X2 + 3X3
Sujeto a: X1 - 2X2 + X3 ≥ 20 2X1 + 4X2 + X3 = 50 X1, X2, X3 ≥ 0
En la desigualdad X1 - 2X2 + X3 ≥ 20 se resta una variable de exceso X4≥0 de tal manera que la desigualdad se convierte en igualdad X1 - 2X2 + X3 - X4= 20. Con este cambio, el problema original se convierte en el siguiente:
Maximizar Z = 2X1 + 5X2 + 3X3
Sujeto a: X1 - 2X2 + X3 – X4 = 20
2X1 + 4X2 + X3 = 50 X1, X2, X3, X4 ≥ 0
Este nuevo problema se convierte a un problema artificial para este fin se agregan, variables artificiales A1 y A2 a cada desigualdad y una penalización a la función objetivo, es decir: Maximizar Z = 2X1 + 5X2 + 3X3 – MA1 - MA2
Sujeto a: X1 - 2X2 + X3 – X4 + A1 = 20
2X1 + 4X2 + X3 + A2 = 50 X1, X2, X3, X4, A1, A2 ≥ 0
Antes de iniciar el método simplex con este nuevo problema, se deben quitar las variables artificiales A1, y A2 de la función objetivo. Para este fin, despejamos A1 de la primera restricción y A2 de la segunda restricción. Posteriormente se sustituye ambos despejes en la función objetivo.
Despeje X1 - 2X2 + X3 – X4 + A1 = 20 A1 = 20 - X1 + 2X2 - X3 + X4 2X1 + 4X2 + X3 + A2 = 50 A2 = 50 - 2X1 - 4X2 - X3
Sustitución Z = 2X1 + 5X2 + 3X3 – MA1 - MA2 Z = 2X1 + 5X2 + 3X3 – M(20 - X1 + 2X2 - X3 + X4 ) - M(50 - 2X1 - 4X2 - X3) Z = 2X1 + 5X2 + 3X3 – 20M + M X1 - 2MX2 +M X3 - MX4 - 50M + 2MX1 + 4MX2 +MX3 Z = (2+M+2M )X1 +(5- 2M +4M)X2 + (3 +M+ M )X3 - MX4 – 70M Z = (2+3M )X1 +(5 +2M)X2 + (3 +2M )X3 - MX4 – 70M
De esta manera, el problema a resolver por el método simplex es. Maximizar Z = (2+3M )X1 +(5 +2M)X2 + (3 +2M )X3 - MX4 – 70M Sujeto a: X1 - 2X2 + X3 – X4 + A1 = 20
2X1 + 4X2 + X3 + A2 = 50 X1, X2, X3, X4, A1, A2 ≥ 0
a. Construcción de la tabla simplex
Ec.
Variable Z x1| x2 x3 x4 A1 A2
Lado Solución BF inicial Entrada (E)
básica Derecho (X1, X2, X3, X4, A1,A2) Salida (S)
0 Z 1 -3M-2 -2M-5 -2M-3 M 0 0 -70M 0 0 0 0 20 50 E=X1
1 A1 0 1 -2 1 -1 1 0 20 S=A1
2 A2 0 2 4 1 0 0 1 50
b. Método simplex paso a paso
Nota. En la tabla algunos no se obtuvieron y se representaron con *. Pero este hecho no afecta el procedimiento del método simplex
Paso 1. Sistema de acuerdo a iteración Paso 2. Paso 3 Paso 4 Variables
Iteración Ec.
Variable Z x1| x2 x3 x4 A1 A2
Lado Obtención del vértice ¿Z es óptima en vértice?
Cociente Entrada (E)
básica Derecho (X1, X2, X3, X4, A1,A2) Mínimo Salida (S)
0
0 Z 1 -3M-2 -2M-5 -2M-3 M 0 0 -70M 0 0 0 0 20 50 Z= -70M E=X1
1 A1 0 1 -2 1 -1 1 0 20 No aumenta si 20/1=20 S=A1
2 A2 0 2 4 1 0 0 1 50 x1 aumenta y x2=x3=x4=0
1
0 Z 1 0 -8M-9 M-1 -2M-2 3M+2 0 -10M+40 * 0 0 0 * * Z= * E=X2
1 X1 0 1 -2 1 -1 1 0 20 No aumenta si S=A2
2 A2 0 0 8 -1 2 -2 1 10 x2 aumenta y x3=x4=A1=0 10/8=1.25
2
0 Z 1 0 0 -17/8 0.25 M-1/4 M+9/8 205/4 * 0 0 0 * * Z= * E=X3
1 X1 0 1 0 0.75 -0.5 0.5 0.25 22.5 No aumenta si 22.5/0.75=30 S=X1
2 X2 0 0 1 -0.125 0.25 -0.25 0.125 1.25 x3 aumenta y x4=A1=A2=0
3
0 Z 1 17/6 0 0 -7/6 M+7/6 M+11/6 115 * 0 0 0 * * Z= * E=X4
1 X3 0 4/3 0 1 -2/3 2/3 1/3 30 No aumenta si S=X2
2 X2 0 1/6 1 0 1/6 -1/6 1/6 5 x4 aumenta y x1=A1=A2=0 5/(1/6)=30
4
0 Z 1 4 7 0 0 M M+3 150 0 0 50 30 0 0 Z= 150
1 X3 0 2 4 1 0 0 1 50 SI. Ya no aumenta Fin del proceso Fin
2 X4 0 1 6 0 1 -1 1 30
Solución del problema:
(a) artificial Z= 150 en el punto (X1, X2, X3, X4, A1,A2) = (0, 0 , 50, 30, 0 ,0) (b) original Z= 150 en el punto (X1, X2, X3) = (0, 0 , 50)
Ejercicio 1. Método de las dos fases
Este método implementa el problema artificial de la gran M en dos etapas, llamadas fase 1 y fase 2. Se describe las fases a continuación.
Problema artificial Problema de la fase 1 Problema de la fase 2 Maximizar Z = 2X1 + 5X2 + 3X3 – MA1 - MA2
Sujeto a: X1 - 2X2 + X3 – X4 + A1 = 20
2X1 + 4X2 + X3 + A2 = 50 X1, X2, X3, X4, A1, A2 ≥ 0
Minimizar Z = A1 + A2
Sujeto a: X1 - 2X2 + X3 – X4 + A1 = 20
2X1 + 4X2 + X3 + A2 = 50 X1, X2, X3, X4, A1, A2 ≥ 0 Objetivo es encontrar una solución factible para el problema real.
Minimizar Z = 2X1 + 5X2 + 3X3 Sujeto a: X1 - 2X2 + X3 – X4 = 20
2X1 + 4X2 + X3 = 50 X1, X2, X3, X4,≥ 0 Objetivo es encontrar una solución óptima para el problema real
c. Tabla simplex de la primera fase
Para proporcionar la tabla simplex del problema enunciado en esta fase, primero se debe despejar las variables artificiales de las restricciones y sustituirlas en la función objetivo
Despeje Sustitución Problema a resolver en simplex
X1 - 2X2 + X3 – X4 + A1 = 20 => A1 = 20 -X1 + 2X2 - X3 + X4 2X1 + 4X2 + X3 + A2 = 50 => A2 = 50- 2X1 – 4X2
– X3
Z=A1+A2
Z=20 -X1 + 2X2 - X3 + X4 +50- 2X1 – 4X2 – X3 Z= -3X1 - 2X2 - 2X3 + X4 +50
Z= -3X1 - 2X2 - 2X3 + X4 +70 Sujeto a: X1 - 2X2 + X3 – X4 + A1 = 20 2X1 + 4X2 + X3 + A2 = 50 X1, X2, X3, X4, A1, A2 ≥ 0
Ec.
Variable -Z x1| x2 x3 x4 A1 A2
Lado Solución BF inicial Entrada= E
básica Derecho (X1, X2, X3, X4, A1,A2) Salida=S
0 Z -1 -3 -2 -2 1 0 0 -70 0 0 0 0 20 500 E=X1
1 A1 0 1 -2 1 -1 1 0 20 S=A1
2 A2 0 2 4 1 0 0 1 50
d. Método simplex paso a paso: fase 1
Paso 1. Sistema de acuerdo a iteración Paso 2. Paso 3 Paso 4 Variable
Iteración Ec.
Variable -Z x1| x2 x3 x4 A1 A2
Lado Obtención del vértice ¿Z es óptima en vértice?
Cociente Entrada(E)
básica Derecho (X1, X2, X3, X4, A1,A2) Mínimo Salida(S)
0
0 Z -1 -3 -2 -2 1 0 0 -70 0 0 0 0 20 500 Z=-70 E=X1
1 A1 0 1 -2 1 -1 1 0 20 No, aumenta si 20/1=20 S=A1
2 A2 0 2 4 1 0 0 1 50 x1 aumenta x2=x3=x4=0
1
0 Z -1 0 -8 1 -2 3 0 -10 Z=-10 E=X2
1 X1 0 1 -2 1 -1 1 0 20 No necesario No, aumenta si S=A2
2 A2 0 0 8 -1 2 -2 1 10 x2 aumenta x3=x4=A1=0 10/8=1.25
2
0 Z -1 0 0 0 0 1 1 0 Z=0
1 X1 0 1 0 0.75 -0.5 0.5 0.25 22.5 No necesario Si, ya no aumenta Fin fase uno Fin
2 X2 0 0 1 -0.125 0.25 -0.25 0.125 1.25
e. Tabla simplex de la fase 2
Iteración Ec.
Variable Z x1| x2 x3 x4 A1 A2
Lado
básica Derecho
Tabla 0 Z -1 0 0 0 0 1 1 0
simplex 1 X1 0 1 0 0.75 -0.5 0.5 0.25 22.5
fase 1 2 X2 0 0 1 -0.125 0.25 -0.25 0.125 1.25
Elimino 0 Z -1 0 0 0 0 0
artificiales 1 X1 0 1 0 0.75 -0.5 22.5
2 X2 0 0 1 -0.125 0.25 1.25
Sustitución 0 Z -1 -2 -5 -3 0 0
función 1 X1 0 1 0 0.75 -0.5 22.5
objetivo 2 X2 0 0 1 -0.125 0.25 1.25
Forma 0 Z -1 0 -5 -1.5 -1 45
gaussiana 1 X1 0 1 0 0.75 -0.5 22.5 Paso 1 apropiada 2 X2 0 0 1 -0.125 0.25 1.25
Forma 0 Z -1 0 0 -2.125 0.25 51.25
gaussiana 1 X1 0 1 0 0.75 -0.5 22.5 Paso 2 apropiada 2 X2 0 0 1 -0.125 0.25 1.25
f. Método simplex paso a paso
Paso 1. Sistema de acuerdo a iteración 2 Paso 3 Paso 4 Variable
Iteración Ec. Variable -Z x1| x2 x3 x4 Lado Obtención del vértice ¿Z es óptima en vértice? Cociente Entrada(E)
básica Derecho (X1, X2, X3, X4) Mínimo Salida(S)
0 0 Z -1 0 0 -2.125 0.25 51.25 22.5 1.25 0 0 Z=51.25 E=X3 1 X1 0 1 0 0.75 -0.5 22.5 NO, aumenta si 22.5/0.75=30 S=X1
2 X2 0 0 1 -0.125 0.25 1.25 x3 aumenta x4=0
1 0 Z -1 2.83333333 0 0 -1.167 0 0 115 0 * 0 * Z=115 E=X4
1 X3 0 1.33333333 0 1 -0.667 0 0 30 NO, aumenta si S=X2
2 X2 0 0.16666667 1 0 0.1667 0 0 5 x4 aumenta x1=0; 5/0.125=40
2
0 Z -1 4 7 0 0 0 0 150 0 0 50 30 Z=150
1 X3 0 2 4 1 0 0 0 50 Si, ya no aumenta Fin del proceso Fin
2 X4 0 1 6 0 1 0 0 30
Solución del problema original Z= 150 en el vértice (X1,X2,X3) = (0,0,50)
g. Comparación de soluciones obtenidos con el método de la gran M y de las dos fases Solución con el método de la gran M
4
0 Z 1 4 7 0 0 M M+3 150 0 0 50 30 0 0 Z= 150
1 X3 0 2 4 1 0 0 1 50 SI. Ya no aumenta Fin del proceso Fin
2 X4 0 1 6 0 1 -1 1 30
Solución con el método de las dos fases
2
0 Z -1 4 7 0 0 0 0 150 0 0 50 30 Z=150
1 X3 0 2 4 1 0 0 0 50 Si, ya no aumenta Fin del proceso Fin
2 X4 0 1 6 0 1 0 0 30
¿Cuáles de estas soluciones son factibles sólo para el problema artificial obtenido al introducir las variables artificiales y cuáles son factibles para el problema real? Podemos notar que con ambos métodos se obtienen las mismas soluciones. Solución del problema artificial Z= 150 en (0,0, 50, 30, 0, 0). Mientras que la solución en el problema original es Z=150 en el vértice (0, 0, 50)
Ejercicio 2. Método de la gran M
Problema original Debido a la forma de las restricciones el problema de programación lineal sufre modificaciones
Primer cambio Segundo Cambio Tercer cambio Minimizar Z = 3X1 + 2X2 + 4X3
Sujeto a: 2X1 + X2 + 3X3 = 60 3X1 + 3X2 + 5X3 ≥ 120 X1, X2, X3 ≥ 0
En la desigualdad 3X1 + 3X2 + 5X3 ≥ 120 se resta una variable de exceso X4≥0 de tal manera que la desigualdad se convierte en igualdad 3X1 + 3X2 + 5X3 - X4 = 120. Con este cambio, el problema original se convierte en el siguiente: Minimizar Z = 3X1 + 2X2 + 4X3
Sujeto a: 2X1 + X2 + 3X3 = 60 3X1 + 3X2 + 5X3 –X4 = 120 X1, X2, X3, X4 ≥ 0
Este nuevo problema se convierte a un problema artificial para este fin se agregan, variables artificiales A1 y A2 a cada desigualdad y una penalización a la función objetivo, es decir: Minimizar Z = 3X1 + 2X2 + 4X3 + MA1 + MA2
Sujeto a: 2X1 + X2 + 3X3 + A1 = 60
3X1 + 3X2 + 5X3 –X4 + A2 = 120 X1, X2, X3, X4, A1, A2 ≥ 0
Antes de iniciar el método simplex con este nuevo problema, se deben quitar las variables artificiales A1, y A2 de la función objetivo. Para este fin, despejamos A1 de la primera restricción y A2 de la segunda restricción. Posteriormente se sustituirá ambos despejes realizados en la función objetivo.
Despeje 2X1 + X2 + 3X3 + A1 = 60 A1 = 60 - 2X1 - X2 - 3X3
3X1 + 3X2 + 5X3 –X4 + A2 = 120 A2 = 120 - 3X1 - 3X2 - 5X3 +X4
Sustitución Z = 3X1 + 2X2 + 4X3 + MA1 + MA2
Z = 3X1 + 2X2 + 4X3 +M(60 - 2X1 - X2 - 3X3) + M(120 - 3X1 - 3X2 - 5X3 +X4) Z = 3X1 + 2X2 + 4X3 + 60M - 2MX1 - MX2 - 3MX3 +120M - 3MX1 - 3MX2 - 5MX3 + MX4 Z =(3 -2M-3M)X1 + (2-M-3M)X2 + (4-3M -5M)X3 -MX4 -180M Z =(3 -5M)X1 + (2 -4M)X2 + (4- 8M)X3 + MX4 +180M
Problema al cual se le aplicará el método simplex es. Maximizar -Z =-(3 - 5M)X1 - (2- 4M)X2 - (4 -8M)X3 - MX4 - 180M Sujeto a: 2X1 + X2 + 3X3 + A1 = 60 3X1 + 3X2 + 5X3 –X4 + A2 = 120 X1, X2, X3, X4, A1, A2 ≥ 0
a. Tabla simplex
Ec.
Variable -Z x1| x2 x3 x4 A1 A2
Lado Solución BF inicial Entrada(E)
básica Derecho (X1, X2, X3, X4, A1,A2) Salida(S)
0 -Z -1 -5M+3 -4M+2 -8M+4 M 0 0 -180M 0 0 0 0 60 120 E=X3
1 A1 0 2 1 3 0 1 0 60 S=A1
2 A2 0 3 3 5 -1 0 1 120
b. Método simplex paso a paso
Paso 1. Sistema de acuerdo a iteración Paso 2. Paso 3 Paso 4 Variable
Iteración Ec.
Variable -Z x1| x2 x3 x4 A1 A2
Lado Obtención del vértice ¿Z es óptima en vértice?
Cociente Entrada(E)
básica Derecho (X1, X2, X3, X4, A1,A2) Mínimo Salida(S)
0
0 -Z -1 -5M+3 -4M+2 -8M+4 M 0 0 -180M 0 0 0 0 60 120 -Z=-180M E=X3
1 A1 0 2 1 3 0 1 0 60 No. Aumenta si 60/3=20 S=A1
2 A2 0 3 3 5 -1 0 1 120 x3 aumenta x1=x2=x4=0
1
0 -Z -1 M/3+1/3 -4M/3+2/3 0 M 8M/3-4/3 0 -20M-80 0 0 * 0 * * -Z=* E=X2
1 X3 0 2/3 1/3 1 0 1/3 0 20 No. Aumenta si S=A2
2 A2 0 -1/3 4/3 0 -1 -5/3 1 20 X2 aumenta x1=x4=A1=0 20/(4/3)=15
2
0 -Z -1 1/2 0 0 1/2 M-1/2 M-1/2 -90 0 15 15 0 0 0 -Z=-90 Fin
1 X3 0 3/4 0 1 1/4 3/4 -1/4 15 SI
Fin del proceso Proceso
2 X2 0 -1/4 1 0
-3/4 -5/4 3/4 15
Por lo tanto, la solución del problema artificial es -Z=-90 en el vértice (X1, X2, X3, X4, A1, A2)= (0, 15, 15, 0, 0, 0). De esta manera, la solución del problema original es: Z=90 en el vértice (X1, X2, X3)= (0, 15, 15)
Ejercicio 2. Método de las dos fases
Problema artificial Problema de la fase 1 Problema de la fase 2 Minimizar Z = 3X1 + 2X2 + 4X3 + MA1 + MA2
Sujeto a: 2X1 + X2 + 3X3 + A1 = 60
3X1 + 3X2 + 5X3 –X4 + A2 = 120 X1, X2, X3, X4, A1, A2 ≥ 0
Minimizar Z = A1 + A2
Sujeto a: 2X1 + X2 + 3X3 + A1 = 60
3X1 + 3X2 + 5X3 –X4 + A2 = 120 X1, X2, X3, X4, A1, A2 ≥ 0 Objetivo es encontrar una solución factible para el problema real.
Maximizar Z = 3X1 + 2X2 + 4X3 Sujeto a: 2X1 + X2 + 3X3 = 60
3X1 + 3X2 + 5X3 –X4 + = 120 X1, X2, X3, X4 ≥ 0 Objetivo es encontrar una solución óptima para el problema real
c. Tabla simplex de la primera fase
Para proporcionar la tabla simplex, se debe despejar las variables artificiales de las restricciones y sustituirlas en la función objetivo
Despeje Sustitución Problema a resolver en simplex 2X1 + X2 + 3X3 + A1 = 60 => A1 = 60 - 2X1 - X2 - 3X3 3X1 + 3X2 + 5X3 –X4 + A2 = 120 => A2 = 120 - 3X1 - 3X2 - 5X3 + X4
Z=A1+A2
Z= 60 - 2X1 - X2 - 3X3 Z= 120 - 3X1 - 3X2 - 5X3 + X4
Maximizar -Z= -(-5X1 - 4X2 - 8X3 + X4 +180) Sujeto a: 2X1 + X2 + 3X3 + A1 = 60 3X1 + 3X2 + 5X3 –X4 + A2 = 120
X1, X2, X3, X4, A1, A2 ≥ 0
Ec.
Variable -Z x1| x2 x3 x4 A1 A2
Lado Solución BF inicial Entrada(E)
básica Derecho (X1, X2, X3, X4, A1,A2) Salida(S)
0 Z -1 -5 -4 -8 1 0 0 -180 0 0 0 0 60 120 E=X3 1 A1 0 2 1 3 0 1 0 60 S=A1
2 A2 0 3 3 5 -1 0 1 120
d. Método simplex paso a paso: fase 1
Paso 1. Sistema de acuerdo a iteración Paso 2. Paso 3 Paso 4 Variable
Iteración Ec.
Variable -Z x1| x2 x3 x4 A1 A2
Lado Obtención del vértice ¿Z es óptima en vértice?
Cociente Entrada(E)
básica Derecho (X1, X2, X3, X4, A1,A2) Mínimo Salida(S)
0
0 Z -1 -5 -4 -8 1 0 0 -180 0 0 0 0 60 120 Z=-180 E=X3
1 A1 0 2 1 3 0 1 0 60 No, aumenta si 60/3=20 S=A1
2 A2 0 3 3 5 -1 0 1 120
x3 aumenta x1=x2=x4=0
1
0 Z -1 0.33333333 -1.3333333 0 1 2.666667 0 -20 * * * * * * Z=-20 E=X2
1 X3 0 0.66666667 0.3333333 1 0 0.333333 0 20 No, aumenta si S=A2
2 A2 0 -0.3333333 1.3333333 0 -1 -1.666667 1 20
x2 aumenta x1=x4=A1=0 20/1.333=15
2
0 Z -1 0 0 0 0 1 1 0 * * * * * * Z=0
1 X3 0 0.75 0 1 0.25 0.75
-0.25 15 Si, ya no aumenta. Fin fase 1 Fin
2 X2 0 -0.25 1 0
-0.75 -1.25 0.75 15
e. Obtención tabla simplex: fase 2
Ec.
Variable Z x1| x2 x3 x4 A1 A2
Lado
básica Derecho
Tabla 0 Z -1 0 0 0 0 1 1 0
simplex 1 X3 0 0.75 0 1 0.25 0.75 -0.25 15
fase 1 2 X2 0 -0.25 1 0 -0.75 -1.25 0.75 15
Elimino 0 Z -1 -3 -2 4 0 0
artificiales 1 X3 0 0.75 0 1 0.25 15
2 X2 0 -0.25 1 0 -0.75 15
sustitución 0 Z -1 3 2 4 0 0
función 1 X3 0 0.75 0 1 0.25 15
objetivo 2 X2 0 -0.25 1 0 -0.75 15
Forma 0 Z -1 0.5 0 0 0.5 -90
gaussiana 1 X3 0 0.75 0 1 0.25 15
apropiada 2 X2 0 -0.25 1 0 -0.75 15
f. Método simplex: fase dos
Paso 1. Sistema de acuerdo a iteración Paso 2. Paso 3 Paso 4 Variable
Iteración Ec.
Variable Z x1| x2 x3 x4
Lado Solución BF ¿Z es óptima en vértice?
Cociente Entrada(E)
básica Derecho (X1, X2, X3, X4) Mínimo Salida(S)
0
0 Z -1 0.5 0 -0 0.5 -90 0 15 15 0 Z=-90
1 X3 0 0.75 0 1 0.25 15 Si, ya no aumenta
Fin de proceso Fin
2 X2 0 -0.25 1 0 -0.75 15
g. Comparación de soluciones del método de la gran M y el método de las dos fases Solución con el método de la gran M
2
0 -Z -1 1/2 0 0 1/2 M-1/2
M-1/2 -90 0 15 15 0 0 0 -Z=-90 Fin
1 X3 0 3/4 0 1 1/4 3/4 -1/4 15 SI
Fin del proceso Proceso
2 X2 0 -1/4 1 0
-3/4 -5/4 3/4 15
Solución con el método de las dos fases
0
0 Z -1 0.5 0 -0 0.5 -90 0 15 15 0 -Z=-90
1 X3 0 0.75 0 1 0.25 15 Si, ya no aumenta
Fin de proceso Fin
¿Cuáles de estas soluciones son factibles sólo para el problema artificial obtenido al introducir las variables artificiales y cuáles son factibles para el problema real? Podemos notar que con ambos métodos se obtienen las mismas soluciones. Solución del problema artificial Z= 90 en (0,15, 15, 0, 0, 0). Mientras que la solución en el problema original es Z=90 en el vértice (0, 0, 50)