Simplex

OPTIMIZACIÓN
¡¡ la ciencia de lo mejor !!
¿Cómo hace Simplex el cambio de base?

2010 - 2

Optimización – Carmen Ortiz Z. ©

1

Optimización – Carmen Ortiz Z. ©

2

CAMBIO DE BASE

CAMBIO DE BASE
2x1 + 3x2 + x3 = 27 3x1 + 3/2x2 + x4 = 24 x5 = 10 x1 + x2 +

B0 = [ A.3 , A.4 , A.5] A.1

• x3 x2 = 0

+ 2x1 + 3x2 = 27 ⇒ x3 +2x1 = 27 x1 ↑ ⇒ x3 ↓ ⇒ max {x1} = 27/2

¿ cuálsacamos ?

• x4 x2 = 0 • x5 x2 = 0

+ 3x1 + 3/2x2 = 24 ⇒ x4 + 3x1 = 24 ⇒ + x1 + x2 = 10 ⇒ x5 + x1 = 10 ⇒ max {x1} = 10
4

max {x1} = 8 {

Optimización – Carmen Ortiz Z. ©

3

Optimización – Carmen Ortiz Z. ©

CAMBIO DE BASE
2x1 + 3x2 + x3 = 27 3x1 + 3/2x2 + x4 = 24 x5 = 10 x1 + x2 +

CAMBIO DE BASE
B0 = [A .3 , A .4 , A .5 ] Min z = – 60 x1 – 50 x2 s.a. x3 + 2x1 + 3x2 = 27 x4 + 3x1+ 3/2x2 = 24 x5 + x1 + x2 = 10 x1 , x2 , x3 , x4 , x5 ≥ 0 B1 = [A .3 , A .1 , A .5] Min z = - 480 - 20x2 +20 x4 s.a + 2 x2 - 2/3 x4 = 11 x3 x1 + 1/2x2 + 1/3 x4 = 8 x5 + 1/2x2 - 3/8 x4 = 2 x1 , x2 , x3 , x4 , x5 ≥ 0

max {x2} = min {27/2, 8, 10} = 8 ⇒ x4 = 0
sale A.4 de la base

Sol. Básica Factible

Sol. Básica Factible

Nueva base B1 = [A.3 , A.1 , A.5 ] = y R 1 = [ A .2 , A .4 ]

1 20 0 3 0 0 1 1

x3 = 27 x4 = 24 x5 = 10 x1 = x2 = 0 z= 0 vértice E
5
Optimización – Carmen Ortiz Z. ©

x3 = 11 x1 = 8 x5 = 2 x2 = x4 = 0 z = - 480 vértice D
6

Optimización – Carmen Ortiz Z. ©

CAMBIO DE BASE
16
Sol. Básica Factible

CAMBIO DE BASE
B0 = [A .3 , A .4 , A .5 ] Min z = – 60 x1 – 50 x2 s.a. x3 + 2x1 + 3x2 = 27 x4 + 3x1 + 3/2x2 = 24 x5 + x1 + x2 = 10 x1 , x2 , x3 , x4 ,x5 ≥ 0 B1 = [A .3 , A .1 , A .5] Min z = - 480 - 20x2 +20 x4 s.a + 2 x2 - 2/3 x4 = 11 x3 x1 + 1/2x2 + 1/3 x4 = 8 x5 + 1/2x2 - 3/8 x4 = 2 x1 , x2 , x3 , x4 , x5 ≥ 0 B2 = [A .3 , A .1 , A .2] Min z= - 560 + 20/3 x4+ 40x5 s.a. + 2/3 x4 - 4x5 = 3 x3 x1 + 2/3 x4 - x5 = 6 x2 - 2/3 x4 + 2x5 = 4 x x1 , x2 , x3 , x4 , x5 ≥ 0

14 12 10 8 6 4 2

x3 = 11 x1 = 8 x5 = 2 x2 = x4 = 0 z = - 480 vértice DSol. Básica Factible

Sol. Básica Factible

Sol. Básica Factible

x3 = 27 x4 = 24 x5 = 10

x3 = 11 x1 = 8 x5 = 2 x2 = x4 = 0 z = - 480 vértice D

x3 = 3 x1 = 6 x2 = 4 x4 = x5 = 0 z = - 560 vértice C
8

E
2 4 6 8
Optimización – Carmen Ortiz Z. ©

D
10 12 14 7

x1 = x2 = 0 z= 0 vértice E
Optimización – Carmen Ortiz Z. ©

CAMBIO DE BASE
16
Sol. Básica Factible

Formaestándar F tá d Min Mi z = – 60 x1 – 50 x2 s.a. x3 + 2x1 + 3x2 = 27 x4 + 3x1 + 3/2x2 = 24 x5 + x1 + x2 = 10 x1 , x2 , x3 , x4 , x5 ≥ 0

Forma Canónica para F C ó i
B2 = [A .3 , A .1 , A .2 ]

14 12 10 8 6

x3 = 3 x1 = 6 x2 = 4 x4 = x5 = 0 z = - 560 vértice C

Min Mi z= - 560 + 20/3 x4+ 40 5 40x s.a. x3 + 2/3 x4 - 4x5 = 3 x1 + 2/3 x4 - x5 = 6 x2 - 2/3 x4 + 2x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0

C4 2

Solución Básica Factible OPTIMA x1 * = 6 x2 * = 4 x 3 * = 3 D
2 4 6 8 10 12 14 9
Optimización – Carmen Ortiz Z. ©

x4 * = x5 * = 0

E
Optimización – Carmen Ortiz Z. ©

z* = - 560 *

vértice C é ti
10

ALGORITMO SIMPLEX

PASO 0: Determinar un vertice factible inicial ⇔ Determinar una base B primal factible 1) Determinar forma canónica asociada a B:

ALGORITMO SIMPLEX

•Determinar B-1 •
•
Reordenar ecuaciones y premultiplicar p B-1 p p por

• Calcular costos reducidos

π = cB B-1

⎯c

j

= cj - π A. j ∀j

• Determinar solución básica factible asociada a B

xR = 0 ⇒ xB = ⎯b
Optimización – Carmen Ortiz Z. ©

11

Optimización – Carmen Ortiz Z. ©

ALGORITMO

12

ALGORITMO SIMPLEX

ALGORITMO SIMPLEX PASO 2 C it i de Optimalidad 2: Criteriod O ti lid d

PASO 1:
Dada una base B obtener la forma canónica asociada a B Forma canónica asociada a

Si

⎯cj ≥ 0 ∀j, entonces la solución es OPTIMA. FIN

B = [A .3 , A .4 , A .5 ]
Min z = – 60 x1 – 50 x2 s.a. 2x1 + 3x2 + x3 = 27 3x1 + 3/2x2 + x4 = 24 x1 + x2 + x5 = 10 x1 , x2 , x3 , x4 , x5 ≥ 0

Min z = cB⎯ b + ⎯cR xR s.a. I x B +⎯ R x R = ⎯ b xB , xR ≥ 0

Min z = cB⎯ b + ⎯cR...