UNIVERSIDAD NACIONAL DE INGENIERIA Curso: Investigación de Operaciones IFACULTAD DE INGENIERIA CIVIL Profesor: Ing. Juan Carlos Ubillus C.DEPARTAMENTO DE CONSTRUCCION

METODO SIMPLEX EN CASOS DE MINIMIZACIONy CONSIDERAND RESTRICCIONES DEL TIPO IGUAL QUE, MENOR IGUAL QUE y/o MAYOR IGUAL QUE

Min Z = 5x1 + 6x2restricciones

1x1 + 1x2 = 10001x1 <= 300 1x2 >= 150

convirtiendo restricciones en igualdades1x1 + 1x2 + 1A1 = 10001x1 + 1 s1 = 3001x2 -1s2 +1A2 =150

incluyendo todas las variables en cada ecuaciónMin Z = 5x1 + 6x2 + 0s1 + 0s2 +MA1 + MA2prim.rest. 1x1 + 1x2 + 0s1 + 0s2 +1A1 + 0A2 = 1000seg,rest. 1x1 + 0x2 + 1s1 + 0s2 +0A1 + 0A2 = 300terc.rest. 0x1 + 1x2 + 0s1 -1s2 +0A1 + 1A2 = 150

MATRIZ SIMPLEX (INICIAL)Cj $5 $6 $0 $0 $M $M

mezcla sol. x1 x2 s1 s2 A1 A2 RHS$M A1 1 1 0 0 1 0 1000$0 s1 1 0 1 0 0 0 300$M A2 0 1 0 -1 0 1 150

Zj $M $2M $0 -$M $M $M $1150MCj-Z -$M+5 -2$M+6 $0 $M $0 $0 costo total

en minimización escoger como columna pivote el valor negativo más grande

pivoteMATRIZ SIMPLEX (segunda)

Cj $5 $6 $0 $0 $M $Mmezcla sol. x1 x2 s1 s2 A1 A2 RHS

$M A1 1 0 0 1 1 -1 850$0 s1 1 0 1 0 0 0 300$6 x2 0 1 0 -1 0 1 150

Zj $M $6 $0 $M-6 $M -$M+6 $850M+900Cj-Z -$M+5 $0 $0 -$M+6 $0 $2M-6 costo total

en minimización escoger como columna pivote el valor negativo más grande completar tablas tercera y cuarta hasta obtener todos los valores ceros o psitivos

x1=300, x2=700,s2=550, costo=5700

Resumen del Método Simplex para MaximizaciónElegir variable con Cj-Zj positiva más grande para que entre en la mezcla soluciónDeterminar renglón a reemplazar, dividiendo rhs/columna pivote, valor más bajo no negativo Calcular los nuevos valores para el renglón pivoteCalcular los nuevos valores para los otros renglonesCalcular los valores Cj y Cj-Z, regresar al primer paso si resulta algún valor mayor que cero.

Resumen del Método Simplex para MinimizaciónElegir variable con Cj-Zj negativa más grande para que entre en la mezcla soluciónDeterminar renglón a reemplazar, dividiendo rhs/columna pivote, valor más bajo no negativo Calcular los nuevos valores para el renglón pivoteCalcular los nuevos valores para los otros renglonesCalcular los valores Cj y Cj-Z, regresar al primer paso si resulta algún valor menor que cero.

Ejemplo:Min Z = 6x1 + 5x2restricciones

1x1 + 1x2 = 20001x1 >= 300 1x2 <= 600

x1, x2 >=0

convirtiendo restricciones en igualdades1x1 + 1x2 + 1A1 = 2000 con A1 variable de hogura muy grande1x1 - 1 s1 + A2 = 300 1x2 + s2 = 600 con s2 variable de holgura

incluyendo todas las variables en cada ecuaciónMin Z = 6x1 + 5x2 + 0s1 + 0s2 +MA1 + MA2prim.rest. 1x1 + 1x2 + 0s1 + 0s2 +1A1 + 0A2 = 2000seg,rest. 1x1 + 0x2 - 1s1 + 0s2 +0A1 + 1A2 = 300terc.rest. 0x1 + 1x2 + 0s1 +1s2 +0A1 + 0A2 = 600

MATRIZ SIMPLEX (INICIAL)Cj $6 $5 $0 $0 $M $M

mezcla sol. x1 x2 s1 s2 A1 A2 RHS$M A1 1 1 0 0 1 0 2000$M A2 1 0 -1 0 0 1 300$0 s2 0 1 0 1 0 0 600

Zj $2M $M $-M 0 $M $M $2300MCj-Z 6-2M 5-M M $0 $0 $0 costo total

en minimización escoger como columna pivote el valor negativo más grande

pivote

MATRIZ SIMPLEX (segunda)Cj $6 $5 $0 $0 $M $M

mezcla sol. x1 x2 s1 s2 A1 A2 RHS$M A1 0 1 1 0 1 -1 1700$6 x1 -1 0 -1 0 0 1 300$0 s2 0 1 0 1 0 0 600

Zj $6 $M $M-6 $0 $M -$M+6 700M+1800Cj-Z $0 $5-M $6-M $0 $0 $2M-6 costo total

MATRIZ SIMPLEX (tercera)Cj $6 $5 $0 $0 $M $M

mezcla sol. x1 x2 s1 s2 A1 A2 RHS$M A1 0 0 1 -1 1 -1 1100$6 x1 1 0 -1 0 0 1 300$5 x2 0 1 0 1 0 0 600

Zj $6 $5 $M-6 -$M+5 $M -$M+6 100M+4800Cj-Z $0 $0 $6-M -5+M $0 $2M-6 costo total

MATRIZ SIMPLEX (cuarta)Cj $6 $5 $0 $0 $M $M

mezcla sol. x1 x2 s1 s2 A1 A2 RHS$0 s1 0 0 1 -1 1 -1 1100$6 x1 1 0 0 -1 1 0 1400$5 x2 0 1 0 1 0 0 600

Zj $6 $5 $0 -1 $6 $0 11400Cj-Z $0 $0 0 1 $M-6 $M costo total

x1=1100; x2=1400; Z= 1100(0)+1400(6)+600(5)=11,400