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