Programacion Lineal

Taller 3

Ejercicio 1
Dadas las tablas simplex inicial y óptima, hacer el análisis de sensibilidad para los coeficientes de una V.B y una V.N.B , y además para un recurso
Tabla simplex inicial

Análisis de sensibilidad y dualidad

V.B

Z 1

X

−3
1 3 1 1

1

X

−2
2 0 4 2

2

X

−5
1 2 0 1

3

X

−1
2 1 3 2

4

X

5

X

6

X

7

X

8

b 0430 460 420 500
2

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

X X

5 6

0 0 0 0

X7 X8
1

Tabla simplex óptima

V.B

Z 1

X

1

X

2

X

3

X

4

X

5

X

6

X

7

X

8

b
1350 100

Cualquier tabla del simplex se puede obtener a partir de:
1 -c A 0 I 0

4 -0.25 1.5 2 0

0 1 0 0 0

0 0 1 0 0

3

1

2

0 0 0 1 0

0 0 0 0 1X2 X3 X7 X8

0 0 0 0

0.75 0.5 -0.25 0.5 0 0 0 -2 -1 0.5 1 0

230 20 70

Tabla original
0 b

Recordemos el ejercicio.

algunos

conceptos

de

las

clases

de

1 0
3

c B B- 1 B- 1

análisis de sensibilidad, antes de empezar a resolver

Matriz que premultiplica a la tabla original
4

Como tenemos la tabla simplex inicial y la óptima podemos obtener todos loscomponentes de la matriz.

Lo primero que tenemos que hacer es obtener la base óptima.

BASE ÓPTIMA c B B- 1 B- 1

1 0

1 0

-c A

0 I

0 = b

[X
b b
5

2

X3

X7

X8 ] 0]
6

1 0

c B B- 1 A - c B- 1 A

c B B- 1 B- 1

c B B- 1 B- 1

De ahí que

CB =

[2

5

0

1

A=

1 3  1  1

2 0 4 2

1 2 0 1

2

  3  2
1

B=

2 0  4 2
0 0 1 0

1 2 0 1

0 0 1 0

0

  0  1
0
0 0 0 1

CB B -1 = 2 5 0 0

[

]

 0 .5   0  −2   −1

− 0 . 25
0 .5 1 0

0 0 1 0

0 0 0 1

     

 0 .5  0 B -1 =   −2   −1

− 0 . 25
0 .5 1 0

     
7

CB B -1 =

[1

2

0

0]
8

CB B -1 A=

[1

2

0

0

]

1 3  1  1

2 0 4 2

1 2 0 1

2 1 3 2 

=

[7

2

5

4

]

CB B -1 b=

[1

2

0

0

]

430 460  420  500
0 0 0 1

     

= 1350

CB B -1 A - c =

[7 [4

2

5

4

] ]

-

[3

2

5

1

]

 0 .5  B b=  0  −2   −1
-1

− 0 . 25
0 .5 1 0

0 0 1 0

     

430 460  420  500

100     = 230  20     70 

     

=

0

03

9

10

Recordemos que son 3 casos diferentes donde debemos entrar a realizar el análisis de sensibilidad.

1.Cambios en los coeficientes de una V.N.B

Recordemos que elementos cambian

• Para el coeficiente de una V.N.B • Para el coeficiente de una V.B

1 0

c B B- 1 A - c B- 1 A

c B B- 1 B- 1

c B B- 1 B- 1 b

b

Único elemento que cambia
• Para un recurso
11será cj (la componente j de c)
12

2

Cuando Xj es una V.N.B, la tabla sigue siendo óptima mientras zj - cj≥ 0 ( z j e s l a c o m p o n e n t e j d e z = c B B - 1 A)
2 5 4

2.Cambios en los coeficientes de una V.B

CB B -1 A - c = [7

] - [3

2

5

1

]=

[4

0

0

3

]

En la tabla óptima:

1 P a r a C1 q u e e s c o e f i c i e n t e d e V . N . B 0

c B B- 1 A- c B- 1 A

c B B- 1 B- 1

c B B- 1 B- 1 b

b

∆ ≤ zj - cj

∆≤ 7-3 -∝ ≤ 3 + ∆ ≤ 7

3+∆≤ 7

Elementos que cambian (aunque se garantiza que c B B- 1 A - c = 0 , p a r a l a s V . B ) . Se requiere que los La funció n objetivo
14

zj - c j ≥
13

0 y l o s c B B- 1

≥ 0.

c B B- 1 b p u e d e t o m a r c u a l q u i e r v a l o r .

P a r a C2 q u e e s c o e f i c i e n t ed e V . B

C B B- 1 A =

[1 + 0 . 5 ∆

2 − 0 . 25 ∆

0

0

]

c 2 = c2 + ∆
CB B- 1 =

[2+∆

5

0

0

]

 0 .5  0   −2   −1

− 0 .25
0.5 1 0

0 0 1 0

0 0 0 1

     

1 3  1  1

2 0 4 2

1 2 0 1

2 1 3 2

 

C B B- 1 A =

[7 − 0 .25 ∆

2

+∆

5

4

+ 0 .75 ∆]

C B B- 1 A - c =

[7 − 0 .25 ∆

2

+∆

5...