Repaso Programación Lineal
Modelo Giepetto
Variables de Decisiónx1 = número de soldados producidos cada semana
x2 = número de trenes producidos cada semana
Función Objetivo Maximize z = 3x1 + 2x2
Restricciones:1 En cada semana se dispone de un máximo de 100 hrs para terminado 2 x1 + x2 ≤ 100
2 En cada semana se dispone de a lo más 80 horas de carpintería
x1 + x2 ≤ 80
3 A lo más se deben producir 40 soldados.
x1 ≤ 40
Un conjunto de puntos S es un conjunto convexo si el segmento que une cualquier par de puntos en S está contenido totalmente en S.
Para cualquier conjunto convexo S, un punto p en S es un punto extremo si cada segmento que está completamente en S que contiene el punto P tiene P como punto final del segmento
Considere las figuras (a) – (d):
A E B
DC
A B
A B
(a) (b) (c) (d)
Max z = 3x1 + 2x2 (función objetivo)
Sujeto a (s.a.):2 x1 + x2 ≤ 100 (terminado)
x1 + x2 ≤ 80 (carpintería)
x1 ≤ 40 (máx demanda de soldados)
x1 ≥ 0 (positivo)
x2 ≥ 0 (positivo)
X1
X2
10 20 40 50 60 80
20
40
60
80
10
0
finishing constraint
carpentry constraint
demand constraint
z = 60
z = 100
z = 180
Feasible Region
G
A
B
C
D
E
F
H
Se tiene que:
La región factible para cualquier problema de PL será un conjunto convexo.
La región factible para cualquier problema de PL tiene sólo un número finito de puntos extremos.
Cualquier problema de PL que tiene una solución óptima tiene un punto extremo que es óptimo.
Infinitas soluciones
140
x1⋅160
x2⋅+ 1≤
150
x1⋅150
x2⋅+ 1≤
x1 x2 0≥,
140
x1⋅160
x2⋅+ 1≤
150
x1⋅150
x2⋅+ 1≤
x1 x2 0≥,
max z = 3x1 + 2x2
X1
X2
10 20 30 4010
2030
4050
Feasible Region
F50
60
z = 60
z = 100 z = 120
A
B
C
D
E
s.a.
max z = 3x1 + 2x2
140
x1⋅160
x2⋅+ 1≤
150
x1⋅150
x2⋅+ 1≤
x1 30≥
x2 20≥
x1 x2 0≥,
No existe región factible X1
X2
10 20 30 4010
2030
4050
No Feasible Region
5060
x1 >= 0
x2 >=0
Sin solución
max z = 2x1 – x2
s.t. x1 – x2 ≤ 1
2x1 +x2 ≥ 6
x1, x2 ≥ 0
X11 2 3 4
1
2
3
4
X2
5
6
5 6A
B
C
Feasible Region
z = 4
z = 6
D
No acotado, con soluciones factibles
Forma Standard Problema de Programación Lineal: Método Simplex
Min Z = CT X
s.a. Ax = b x≥0
Min(-z) = -3x1 - 2x2 (función objetivo)
Sujeto a (s.a.):2 x1 + x2 + x3 = 100 (terminado)
x1 + x2 + x4 = 80 (carpintería)
x1 + x5 = 40 (máx demanda de soldados)
xi ≥ 0, i=1,..,5
x3 , x4 ,x5 variables de holgura
Tableau 1 del Ejemplo
X1 X2 X3 X4 X5
Cj -3 -2 0 0 0 bi bi / aij
X3 0 2 1 1 0 0 100 100/2X4 0 1 1 0 1 0 80 80/1X5 0 1 0 0 0 1 40 40/1
Zj 0 0 0 0 0 0Cj-Zj -3 -2 0 0 0 ↑
↑ Z
Tableau 2 del Ejemplo
X1 X2 X3 X4 X5
Cj -3 -2 0 0 0 bi bi / aij
X3 0 0 1 1 0 -2 20 20/1 ←X4 0 0 1 0 1 -1 40 40/1X1 -3 1 0 0 0 1 40 No
acota
Zj -3 0 0 0 -3 -120Cj-Zj 0 -2 0 0 3 ↑
↑ Z
Tableau 3 del Ejemplo
X1 X2 X3 X4 X5
Cj -3 -2 0 0 0 bi bi / aij
X2 -2 0 1 1 0 -2 20 Noacota
X4 0 0 0 -1 1 1 20 20/1 ←X1 -3 1 0 0 0 1 40 40/1
Zj -3 -2 -2 0 1 -160Cj-Zj 0 0 2 0 -1 ↑
↑ Z
Tableau 4 del Ejemplo
X1 X2 X3 X4 X5
Cj -3+∆C1 -2 0 0 0 bi
bi/
aij
X2 -2 0 1 -1 2 0 60
X5 0 0 0 -1 1 1 20
X1 -3+∆C1 1 0 1 -1 0 20
Zj C1 -2 -1+∆C1 -1-∆C1 0 -180+20∆C1
Cj-Zj 0 0 1-∆C1 1+∆C1 0 ↑
Z
Min z = c ·x s.a. Ax = b x ≥ 0
Solución óptima: x*, z* , B*
♦ Sensibilidad: ¿cuánto puede variar el valor de un coeficiente, de modo que B* siga siendo óptima?
♦ Postoptimal: - uno de los coeficientes asume un nuevo valor
- obtener nueva solución óptima de la anterior
Análisis de Sensibilidad y Postoptimal
Análisis de Sensibilidad y Postoptimal
Teorema de Holgura complementaria
x solución factible para (P) y solución factible para (D)
( Ai . x - bi ) yi = 0 i =1,...., m x óptimo para (P)
( cj - y A .j ) xj = 0 j =1,...., n y óptimo para (D)
Factibilidad primal ( b ≥ 0 ) optimalidad dual
Optimalidad primal ( c ≥ 0 ) factibilidad dual
Condiciones Holgura complementaria
Análisis de Sensibilidad y Postoptimal
Productos
• Trigo (x1) [hq]
• Alfalfa (x2) [hq]
•Maíz (x3 ) [hq]
Recursos
• Tierra [ha]
• Mano Obra [hh]
Demanda máxima trigo =18
F.O. = ingreso total
•
¿plan de producción temporada?
Max z = 6x1 + 3x2 + 2x3
s.a.
x1 + x2 +x3 ≤ 36 (1)
x1 + x2 + 4x3 ≤ 24 (2)
x1 ≤ 18 (3)
x1, x2 ≥ 0
1 [q] = 4 [@] = 46 [kg]
b (B*) –1 x4 12 1 -1 0 x2 6 0 1 -1 x1 18 0 0 1
z* = 126
Precio maíz (c3) puede tener variaciones ¿cuánto podría variar sin modificar composición del plan óptimo?
X1 X2 X3 X4 X5 X6
Cj 6 3 2 0 0 0 bX4 0 0 0 -3 1 -1 0 12X2 3 0 1 4 0 1 -1 6X1 6 1 0 0 0 0 1 18
Zj 6 3 12 0 3 3Cj-Zj 0 0 -10 0 -3 -3 126
X1 X2 X3 X4 X5 X6
Cj 6 3 C3 0 0 0 bX4 0 0 0 -3 1 -1 0 12X2 3 0 1 4 0 1 -1 6X1 6 1 0 0 0 0 1 18
Zj 6 3 12 0 3 3Cj-Zj 0 0 C3-12 0 -3 -3 126
c3 −12 ≤ 0 Mientras Utilidad c3 se mantenga bajo 12 Nada Pasa. Pero si crece sobre los $ 12, entonces DEBIERA entrar a la base
_
Análisis PostOptimal para C3
Se tiene el rango de insignificancia para C3 ≤12
Si C'3 vale 15?
X1 X2 X3 X4 X5 X6
Cj 6 3 15 0 0 0 bX4 0 0 0 -3 1 -1 0 12X2 3 0 1 4 0 1 -1 6X1 6 1 0 0 0 0 1 18
Zj 6 3 12 0 3 3Cj-Zj 0 0 3 0 -3 -3 126
Análisis PostOptimal para C3
Se tiene el rango de insignificancia para C3 ≤12
Si C'3 vale 15?
X1 X2 X3 X4 X5 X6
Cj 6 3 15 0 0 0 bX4 0 0 3/4 0 1 3/4 -3/4 33/2X3 15 0 1/4 1 0 1/4 -1/4 3/2X1 6 1 1 0 0 0 1 18
Zj 6 39/4 15 0 15/4 9/4Cj-Zj 0 -3-15/4 0 0 -15/4 -9/4 130,5
2-4c2 ≤ 0 Mientras Utilidad c3 se mantenga bajo 12 Nada Pasa. Pero si crece sobre los $ 12, entonces DEBIERA entrar a la base
_
¿y si el precio de la alfalfa (c2) varia?
X1 X2 X3 X4 X5 X6
Cj 6 C2 2 0 0 0 bX4 0 0 0 -3 1 -1 0 12X2 C2 0 1 4 0 1 -1 6X1 6 1 0 0 0 0 1 18
Zj 6 C2 4C2 0 C2 6-C2
Cj-Zj 0 0 2-4C2 0 -C2 C2-6 108+6C2
-c2 ≤ 0
c2 −6 ≤ 0
1/2 ≤ precio ≤ 6
b (B*) –1 x4 12 1 -1 0 x2 6 0 1 -1 x1 18 0 0 1
z* = 126
Precio maíz (c3) puede tener variaciones ¿cuánto podría variar sin modificar composición del plan óptimo?
π* = cB*T (B*)–1.
ck - π* A.k = 0ck - π* A.k < 0
X1 X2 X3 X4 X5 X6
Cj 6 3 2 0 0 0 bX4 0 0 0 -3 1 -1 0 12X2 3 0 1 4 0 1 -1 6X1 6 1 0 0 0 0 1 18
Zj 6 3 12 0 3 3Cj-Zj 0 0 -10 0 -3 -3 126
Max z = 6x1 + 3x2 + 2x3
s.a.
x1 + x2 +x3 ≤ 36 (1)
x1 + x2 + 4x3 ≤ 24 (2)
x1 ≤ 18 (3)
x1, x2 ≥ 0
Cambios en los coeficientes del lado derecho:
●La variación afecta una restricción no activa●La variación afecta una restricción activa
Rango de Factibilidad:
- Restricción ≤solución nueva = sol + Δ bi (columna var holgura i )
X1 X2 X3 X4 X5 X6
Cj 6 3 2 0 0 0 bX5 0 0 0 -3 -1 1 0 2X2 3 0 1 1 0 0 -1 18X1 6 1 0 0 0 0 1 18
Zj 6 3 3 0 0 3Cj-Zj 0 0 -1 0 0 -3 162
Max z = 6x1 + 3x2 + 2x3
s.a.
x1 + x2 +x3 ≤ 36 (1)
x1 + x2 + 4x3 ≤ 24 (2)
x1 ≤ 18 (3)
x1, x2 ≥ 0
Rango de Factibilidad: -6 ≤ Δ bi ≤ 12 (2)
Si Δ bi = 14 ?
- Llevar factibilidad al límite- Cambiar variable con valor =0, por variable de holgura- Agregar la cantidad faltante
Rango de Factibilidad:Valores Positivos
- Restricción ≤solución nueva = sol + Δ bi (columna var holgura i )
- Restricción ≥solución nueva = sol - Δ bi (columna var exceso i )
- Restricción =solución nueva = sol + Δ bi (columna var artificial i )
Se puede plantar arroz (x7); A.7 T = (1, 2, 0)
Agregar Variables
Columna de x7 :(B*) –1A.7
X1 X2 X3 X4 X5 X6 X7
Cj 6 3 2 0 0 0 C7 bX5 0 0 0 -3 1 -1 0 -1 12X2 3 0 1 4 0 1 -1 2 6X1 6 1 0 0 0 0 1 0 18
Zj 6 3 12 0 3 3 6Cj-Zj 0 0 -10 0 -3 -3 -6+C7
X1 X2 X3 X4 X5 X6
Cj 6 -M 2 0 0 0 bX4 0 0 0 -3 1 -1 0 12X2 -M 0 1 4 0 1 -1 6X1 6 1 0 0 0 0 1 18
Zj 6 -M -4M 0 -M M+6Cj-Zj 0 0 2+4M 0 M -M-6
Eliminar Variables:
- Si no está en la base, sacarla- Si está en la base, hacerla salir de la base, cambiarla y eliminarla