Clase Practica N4 Metodo Grafico 21-04-21

Vista previa del material en texto

CLASE PRACTICA: Investigación Operativa
Trabajo Practico Nº 2 – Método Grafico
Profesores: JTP. Ing. Néstor O. Cruz
AY1. Ing. Mariela E. Rodríguez
Facultad de Ingeniería
Universidad Nacional de Jujuy
Forma Canónica
Forma equivalente de la P.L.
MAX Z = C X
s.a.
A X ≤ b
x ≥0
FORMA ESTANDAR
Es posible transformar las inecuaciones en igualdades introduciendo las 
variables de holgura (V. H.).
Las V. de H. no tienen un beneficio (su coeficiente de beneficio = 0), 
representan físicamente los sobrantes de cada recurso.
Regla 1:
a) Maximizar C X ≈ Minimizar – C X
b) Minimizar C X ≈ Maximizar – C X
Regla 2:
a) A X ≤ b ≈ - A X ≥ -b
b) A X ≥ b ≈ - A X ≤ -b
Regla 3:
A X = b A X ≤ b 
A X ≥ b 
Regla 4:
Regla 5:
Una variable No restringida puede tomar toda clase de valores:
X1= X2 – X3 ; X2 , X3 ≥0 
b) A X ≥ b 
adición de un vector superfluo.
Xs1
Xs= Xs2
…
Xsn
Modelo P.L:
Z = 3 X1 + 3 X2 (MAX)
s.a.
2X1 + X2 ≤ 16
1X1 + 3X2 ≤ 20
2X1 + 5X2 ≤ 20
X1 ≥ 0 , X2 ≥ 0 
Forma Estándar:
Z = 3 X1 + 3 X2 + 0 X3 + 0 X4 + 0X5 (MAX)
s.a.
2X1 + 1X2 + 1 X3 + 0 X4 + 0 X5 = 16
1X1 + 3X2 + 0 X3 + 1 X4 + 0 X5 = 20
2X1 + 5X2 + 0 X3 +0 X4 + 1 X5 = 20
X1 ≥ 0 , X2 ≥ 0 X3 ≥ 0 , X4 ≥ 0 X5 ≥ 0 
Modelo P.L:
Z = 230 X1 + 240 X2 (MIN)
s.a.
30X1 + 11X2 ≥ 16
12X1 + 50X2 ≥ 15
23X1 + 30X2 ≥ 34
X1 ≥ 0 , X2 N.R. 
Por regla 5: X2 = X3 - X4 X3 ≥ 0 ; X4 ≥ 0 
Z = 230 X1 + 240 (X3 - X4 ) (MIN)
s.a.
30X1 + 11 (X3 - X4 ) ≥ 16
12X1 + 50 (X3 - X4 ) ≥ 15
23X1 + 30 (X3 - X4 ) ≥ 34
X1 ≥ 0 , X3 ≥ 0 , X4 ≥ 0 
Z = 230 X1 + 240 X3 – 240 X4 (MIN)
s.a.
30X1 + 11 X3 – 11 X4 ≥ 16
12X1 + 50 X3 – 50 X4 ≥ 15
23X1 + 30 X3 – 50 X4 ≥ 34
X1 ≥ 0 , X3 ≥ 0 , X4 ≥ 0 
Z = 230 X1 + 240 X3 – 240 X4 (MIN)
s.a.
30X1 + 11 X3 – 11 X4 ≥ 16
12X1 + 50 X3 – 50 X4 ≥ 15
23X1 + 30 X3 – 30 X4 ≥ 34
X1 ≥ 0 , X3 ≥ 0 , X4 ≥ 0 
Forma Estándar:
-Z = -230 X1 - 240 X3 + 240 X4 (MAX)
s.a.
30X1 + 11 X3 – 11 X4 –1 X5 +0x6 +0x7 = 16
12X1 + 50 X3 – 50 X4 +0x5 -1 x6 +0x7 = 15
23X1 + 30 X3 – 30 X4 +0x5 +0x6 – 1x7 = 34
X1 ≥ 0 , X3 ≥ 0 , X4 ≥ 0 , X5 ≥ 0 , X6 ≥ 0 , X7 ≥ 0 
Forma Estándar:
-Z = -230 X1 - 240 X3 + 240 X4 - Mµ1 - Mµ2 - Mµ3 (MAX)
s.a.
30X1 + 11 X3 – 11 X4 –1 X5 + 1 µ1 + 0x6 +0x7 = 16
12X1 + 50 X3 – 50 X4 +0x5 -1 x6 + 1 µ2 + 0x7 = 15
23X1 + 30 X3 – 50 X4 +0x6 +0x6 – 1x7 + 1 µ3 = 34
X1 ≥ 0 , X3 ≥ 0 , X4 ≥ 0 , X5 ≥ 0 , X6 ≥ 0 , X7 ≥ 0 , µ1,2,3 ≥0
Ejemplo:
Min Z = 3 X1 – 4 X2 + X3
s.a.
0,5X1 + 2X2 ≥ 3 (1)
1X2 - 1X3 = 4 (2)
X1 ≥ 0 , X2 ≤ 0 , X3 (N.R.) 
Pasamos el problema a la forma estándar, aplicando las reglas: 
Añadiendo variables de holgura, superfluas y artificiales.
• Por regla1:
MAX h = - Z = - 3 X1 + 4 X2 - X3
• Como la restricción 1 es del tipo “≥” se agrega la variable de X4 (-1)
Y la variable artificial µ1 (+1).
• Como la restricción 2 es del tipo “=“ se agrega la variable artificial µ2 (+1).
• Como X2 ≤ 0 , hacemos: X5 = - X2 ; X5 ≥ 0
• Como X3 es NR , Por regla 5: se tiene X3 = X6 – X7 X6 ≥ 0 y X7 ≥ 0
Resumiendo todos los elementos, se tiene:
Max H = - Z = -3 X1 – 4 X5 - 1 X6 + 1X7 - Mµ1 - Mµ2
s.a.
0,5X1 - 2 X5 + 1µ1 = 3 (1)
-1X5 - 1X6 + 1X7 + 1 µ2 = 4 (2)
X1 ≥ 0 , X4 ≥ 0, X5 ≥ 0, X6 ≥ 0, X7 ≥ 0, µ1 ≥ 0, µ2 ≥ 0 
Recordar que H = - Z ; X5 = - X2 ; X3 = X6 – X7
Forma Estándar:
MAX H= - Z = -10 X1 + 32 X4 - Mµ1 - Mµ2
s.a.
14 X1 – 1 X4 - 1 X3 + µ1 = 14
10 X1 - 5 X4 + 0 X3 + µ2 = 50
X1 ≥ 0 , X4 ≥ 0 , µ1 ≥ 0 , µ2 ≥ 0 
* Resolver en Clase * 
Método Grafico : Caso de Múltiples soluciones:
Max Z = 1 X1 + 3 X2
s.a.
1X1 + 1X2 ≤ 3 
1X1 + 3X2 ≤ 12
-1X1 +2X2 ≤ 4
X1 ≥ 0 , X2 ≥ 0 
Método Grafico : Caso de Múltiples soluciones:
Método Grafico : Caso de Múltiples soluciones:
2,6
4,2
Combinación lineal de dos vectores 
Coeficiente (0≤ α ≤ 1)
Solución
Particular
PREGUNTAS
Muchas Gracias