MÉTODO SIMPLEX - uv.essala/Clase09.pdf · 1 MÉTODO SIMPLEX El primer procedimiento de solución...

1

MÉTODO SIMPLEX

El primer procedimiento de solución lo proporcionó

Dantzing en 1947, y este método se conoció con el nombre de

método simplex.

El algoritmo del simplex funciona básicamente como hemos

visto en el método algebraico, resolviendo el sistema de

ecuaciones que forman las restricciones, pero de forma

automática, y manteniendo la factibilidad de la solución actual,

para lo cual parte de una solución factible básica inicial y a partir

de ella obtiene otras soluciones factibles básicas que

proporcionan un mejor valor de la función objetivo, repitiendo el

proceso hasta que no es posible mejorar el valor de la función.

Programa lineal en forma estándar:

Max Z = c x

s.a: A x = b

x ≥ 0

2

Punto de partida: SFBI:

( )x x ,x , , x ,0, ,0 010

20

m0= L L

B x0 = b, es decir: P x P x P x bm m1 10

2 20 0+ + + =L

Pk = P1y1k+ P2y2k+ · · · + Pmymk

( )Py

P y P yk

k m mk11

2 21

= − − −Pk L

( )1

12 2 1

02 2

0 0

yP y P y x P x P x b

kk m mk m mPk − − −

+ + + =L L

P x yxy

P x yxy

Pxy

bkk

m m mkk

kk

2 20

210

1

0 10

1

10

1

−

+ + −

+ =L

Nuevo punto: Es una nueva SFB?. Condiciones:

a) Los m vectores son linealmente independientes, base B.

b) Es una solución factible ( A x = b, x ≥ 0 )

λ2 P2 + ... + λm Pm+λkPk = 0

si λk ≠ 0, entonces:

Pk = - 1λ k

(λ2P2+ L +λmPm)

Pk = P1y1k+ P2y2k+ · · · + Pmymk

Pk = - 1λ k

(λ2P2+ L +λmPm)

3

0 1 1 2 22= + +

+ + +

P y P y P yk k

km mk

m

k

λλ

λλ

L

Vamos a ver ahora la condición b),es decir, que sea una solución

factible (Ax=b, x ≥ 0 ).

Como ya hemos visto verifica A x = b:

P x yxy

P x yxy

Pxy

bkk

m m mkk

kk

2 20

210

1

0 10

1

10

1

−

+ + −

+ =L

por tanto solo queda por comprobar la no negatividad de las

variables. La estructura de las variables es de la siguiente forma:

Para i =k → xy k

10

1

Para i ≠ k → x yxyi ik

k

0 10

1

−

xi0 0> x

yi

k

0

1

> 0

y1k > 0, xy

xy

i

ik k

010

1

>

min { xy

i

jk

0

/ yjk> 0 }. criterio de salida

criterio de entrada

Z0 = c x c x c xm m1 10

2 20 0+ + +L

Z1 = c x yxy

c x yxy

cxyk

km m mk

kk

k2 2

02

10

1

0 10

1

10

1

−

+ + −

+L

habrá que comprobar si Z1>Z0,

Z1 - Z0 =− − − − +c x c yxy

c yxy

cxyk

km mk

kk

k1 1

02 2

10

1

10

1

10

1

L

4

Z1 - Z0 = ( )[ ]xy

c c y c y c yk

k k k m mk10

11 1 2 2− + + +L (8)

Zk = cB B-1Pk = c1y1k+ c2y2k+ · · · + cmymk (9)

Z1 - Z0 = xy k

10

1

(ck - Zk)

Z1 = Z0 + xy k

10

1

(ck - Zk)

: xy k

10

1

(ck - Zk) ≥ 0

Max { (ck- Zk / (ck- Zk ≥ 0 }.

5

3.- ALGORITMO DEL SIMPLEX EN FORMATO

TABLA.

Cj 0

Xj Sj

CB XB B-1·A B-1·b

Zj= CBB-1Pj Z=

Wj= Cj-Zj CBB-1b

Ejemplo:

Max Z = 4 x1 + 5 x2

s.a: 2 x1 + x2 ≤ 8

x2 ≤ 5

x1 ≥ 0 , x2 ≥ 0

Max Z = 4 x1 + 5 x2 + 0 s1 + 0 s2

s.a: 2 x1 + x2 + s1 = 8

x2 + s2 = 5

x1 ≥ 0 , x2 ≥ 0 , s1 ≥ 0 , s2 ≥ 0 .

B B=

= −

1 00 1

1

6

y entonces

B-1·A = A= 2 1 1 00 1 0 1

y B-1·b = b=

85

Así pues la tabla correspondiente a esta solución factible básica inicia (SFBI) será la siguiente:

4 5 0 0 x1 x2 s1 s2

0 s1 2 1 1 0 8 0 s2 0 1 0 1 5 Zj 4 5 0 0 Wj 4 5 0 0 0

Metodo Algebraico:

Max Z = 4 x1 + 5 x2 + 0 s1 + 0 s2 = 0

Max { (cj - Zj) / (cj - Zj) ≥ 0 }.

min { xy

i

ik

0

/ yik > 0 }.

en nuestro caso como la variable que entra es x2, habrá que elegir

min { xy

i

i

0

2 / yi2 > 0 }.

en nuestro caso

, yy

12

22

xx

ss

B P P10

20

1

2

12 2

85

11

=

=

= = =

−

por lo que habrá que elegir

7

min { 81

, 51

}

Así pues a partir de la tabla anterior

8

4 5 0 0 x1 x2 s1 s2

0 s1 0 s2 Zj Wj

4 5 0 0 X1 x2 s1 s2

0 s1 y11=2 y12=1 y13=1 y14=0 8 0 s2 y21=0 y22=1 y23=0 y24=1 5 Zj 4 5 0 0 Wj 4 5 0 0 0

9

4 5 0 0 x1 x2 s1 s2

0 s1 5 x2 Zj Wj

4 5 0 0 x1 x2 s1 s2

0 s1 2* 0 1 -1 3 5 x2 0 1 0 1 5 Zj 4 5 0 5 Wj 4 0 0 -5 25

2 x1 + s1 - s2 = 3

x2 - s2 = 5

Z = 25 + 4 x1 - 5 s2

10

4 5 0 0 x1 x2 s1 s2

4 x1 5 x2 Zj Wj

4 5 0 0 X1 x2 s1 s2

4 x1 1 0 1/2 -1/2 3/2 5 x2 0 1 0 1 5 Zj 4 5 2 3 Wj 0 0 -2 -3 31

Las ecuaciones finales del método algebraico eran:

x1 + ½ s1 - ½ s2 = 3/2

x2 + s2 = 5

Z = 31 - 2 s1 - 3 s2

11

Ejemplo:

Máx Z = 2 x1 + x2

s.a: - x1 + x2 ≤ 2

x1 + 2 x2 ≤ 6

2 x1 + x2 ≤ 6

x1 ≥ 0, x2 ≥ 0

(3,0)(0,0)

(2,2)

(0,2)

(2/3,8/3)

Gráfico 1

Vértice: (2,2) Z = 2·2 + 2 = 6

Vértice: (3,0) Z = 2·3 + 0 = 6

Los puntos del segmento lineal que une ambos vértices

(arista) serán de la forma:

x = λ x1 + (1 - λ ) x2 = λ (2,2) + (1 - λ ) (3,0) = (2 λ + 3 - 3 λ, 2 λ

) = (3 - λ, 2 λ )

12

Para cualquier punto genérico de la arista, es decir para (3 -

λ, 2 λ ), el valor de la función objetivo será:

Z = 2 · (3 - λ) + 2 λ = 6 - 2 λ + 2 λ = 6

como puede comprobarse el valor de la función objetivo es el

mismo que en los dos vértices solución.

Máx Z = 2 x1 + x2 + 0 ·( s1 + s2 + s3)

s.a: - x1 + x2 + s1 = 2

x1 + 2 x2 + s2 = 6

2 x1 + x2 + s3 = 6

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0.

13

2 1 0 0 0 x1 x2 s1 s2 s3 Zj Wj

2 1 0 0 0 x1 x2 s1 s2 s3

0 s1 -1 1 1 0 0 2 0 s2 1 2 0 1 0 6 0 s3 2* 1 0 0 1 6 Zj 2 1 0 0 Wj 2 1 0 0 0 0

14

2 1 0 0 0 x1 x2 s1 s2 s3

0 s1 0 s2 2 x1 Zj Wj

2 1 0 0 0 x1 x2 s1 s2 s3

0 s1 0 3/2 1 0 1/2 5 0 s2 0 3/2 0 1 -1/2 3 2 x1 1 1/2 0 0 1/2 3 Zj 2 1 0 0 1 Wj 0 0 0 0 -1 6

15

2 1 0 0 0 x1 x2 s1 s2 s3

0 s1 1 x2 2 x1 Zj Wj

2 1 0 0 0 x1 x2 s1 s2 s3

0 s1 0 0 1 -1 0 2 1 x2 0 1 0 2/3 -1/3 2 2 x1 1 0 0 -1/3 2/3 2 Zj 2 1 0 0 1 Wj 0 0 0 0 -1 6

16

Ejemplo :

Máx Z = x1 + 2 x2

s.a: - x1 + x2 ≤ 2

x2 ≤ 4

x1 ≥ 0, x2 ≥ 0.

Máx Z = x1 + 2 x2+ 0 (s1 + s2)

s.a: - x1 + x2 +s1 = 2

x2 + s2 = 4

x1 ≥ 0, x2 ≥ 0, s1≥0, s2≥0.

La tabla inicial del algoritmo del simplex, eligiendo como

variables básicas a la variables de holgura, será:

17

1 2 0 0 x1 x2 s1 s2 Zj Wj

1 2 0 0 X1 x2 s1 s2

0 s1 -1 1* 1 0 2 0 s2 0 1 0 1 4 Zj 0 0 0 0 Wj 1 2 0 0 0

18

1 2 0 0 x1 x2 s1 s2

2 x2 0 s2 Zj Wj

1 2 0 0 x1 x2 s1 s2

2 x2 -1 1 1 0 2 0 s2 1* 0 -1 1 2 Zj -2 2 2 0 Wj 3 0 -2 0 4

19

1 2 0 0 x1 x2 s1 s2

2 x2 1 x1 Zj Wj

1 2 0 0 X1 x2 s1 s2

2 x2 0 1 0 1 4 1 x1 1 0 -1 1 2 Zj 1 2 -1 3 Wj 0 0 1 -3 8

20

4. VARIABLES ARTIFICIALES. MÉTODO DE LAS

PENALIZACIONES

Si las restricciones son de la forma mayor-igual:

ak1 x1 + ak2 x2 + ... + akn xn ≥ bk

ak1 x1 + ak2 x2 + ... + akn xn - sk = bk

ak1 x1 + ak2 x2 + ... + akn xn - sk + Ak = bk

Restricciones de igualdad:

ak1 x1 + ak2 x2 + ... + akn xn + Ak = bk

Método de las penalizaciones

Ejercicio:

Max Z = 3 x1 + 2 x2

s.a: 2 x1 - x2 ≥ 3

x1 + x2 ≤ 6

x1 ≥ 0, x2 ≥ 0

21

(3,3)

(6,0)

Gráfico 3

Max Z = 3 x1 + 2 x2 + 0 s1 + 0 s1

s.a: 2 x1 - x2 - s1 = 3

x1 + x2 + s2 = 6

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0

Max Z = 3 x1 + 2 x2 + 0 s1 + 0 s1 -M A1

s.a: 2 x1 - x2 - s1 + A1 = 3

x1 + x2 + s2 = 6

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0, A1 ≥ 0

22

3 2 0 -M 0 x1 x2 s1 A1 s2 Zj Wj

3 2 0 -M 0 x1 x2 s1 A1 s2

-M A1 2* -1 -1 1 0 3 0 s2 1 1 0 0 1 6 Zj -2M M M -M 0 Wj 3+

2M 2

-M 0

-M 0 0 -3M

23

3 2 0 -M 0 x1 x2 s1 A1 s2

3 x1 0 s2 Zj Wj

3 2 0 -M 0 x1 x2 s1 A1 s2

3 x1 1 -1/2 -1/2 1/2 0 3/2 0 s2 0 3/2* 1/2 -1/2 1 9/2 Zj 3 -3/2 -3/2 3/2 0 Wj 0 7/2 3/2 -3/2

-M 0 9/2

24

3 2 0 -M 0 x1 x2 s1 A1 s2

3 x1 2 x2 Zj Wj

3 2 0 -M 0 X1 x2 s1 A1 s2

3 x1 1 0 -1/3 1/3 1/3 3 2 x2 0 1 1/3* -1/3 2/3 3 Zj 3 2 -1/3 1/3 7/3 Wj 0 0 1/3 -1/3

-M -7/3 15

25

3 2 0 -M 0 x1 x2 s1 A1 s2

3 x1 0 s1 Zj Wj

3 2 0 -M 0 x1 x2 s1 A1 s2

3 x1 1 1 0 0 1 6 0 s1 0 3 1 -1 2 9 Zj 3 3 0 0 3 Wj 0 -1 0 0

-M -3 18

26

Max Z = 2 x1 + 3 x2

s.a: 3 x1 + x2 ≥ 3

5 x1 + 2 x2 ≤ 4

x1 ≥ 0, x2 ≥ 0.

S=0

Gráfico 4

Max Z = 2 x1 + 3 x2 + 0 s1 + 0 s2 - M A1

s.a: 3 x1 + x2 - s1 + A1 = 3

5 x1 + 2 x2 + s2 = 4

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0, A1 ≥ 0.

27

2 3 0 -M 0 x1 x2 s1 A1 s2

-M A1 3 1 -1 1 0 3 0 s2 5* 2 0 0 1 4 Zj -3M -M M -M 0 Wj 2+

3M 3

+M

-M 0 0 -3M

2 3 0 -M 0 x1 x2 s1 A1 s2

-M A1 0 -1/5 -1 1 -3/5 3/5 2 x1 1 2/5 0 0 1/5 4/5 Zj 2 4/5+

1/5M M -M 2/5+

3/5M 8/5

Wj 0 11/5-1/5M

-M

0 -2/5-3/5M

-3/5M