documentos

Tema 3: El M´todo Simplex. Algoritmo de las
e
Dos Fases.
3.1 Motivaci´n Gr´fica del m´todo Simplex.
o
a
e
3.2 El m´todo Simplex.
e
3.3 El m´todo Simplex en Formato Tabla.
e
3.4 Casos especiales en la aplicaci´n del algoritmo.
o
3.4.1 Degeneraci´n.
o
´
3.4.2 Optimos alternativos.
3.4.3 Problema no acotado.
3.4.4 Problema Imposible.
3.5 El Algoritmo de las dos Fases.
3.5.1Problema imposible.
3.5.2 Problema posible.
1

3.1 Motivación Gráfica del Método Simplex
Región de soluciones posibles acotada
Existe al menos una solución óptima, que es un vértice

Región de soluciones posibles no acotada
Problema no acotado

z=+ ∞

c, dirección de mejora

Problema Acotado
Existe una solución óptima única

Problema acotado

Infinitas soluciones óptimas(Segmento)

c, dirección de mejora

Problema acotado

Infinitas soluciones óptimas (Semirrecta)

c, dirección de mejora

3.1 Motivaci´n Gr´fica del M´todo Simplex
o
a
e
1. Si el PPL tiene una unica soluci´n ´ptima, ser´ necesariamente un v´rti´
o o
a
e
ce de S.
2. Si el PPL tiene m´s de una soluci´n ´ptima y S es acotado, al menos dos
a
o o
de ellas son v´rtices adyacentes de S. SiS es no acotada, solo podemos
e
garantizar que al menos una de las soluciones ´ptimas es un v´rtice.
o
e
3. Existe un n´mero finito de v´rtices en S.
u
e
4. Si un v´rtice proporciona un valor objetivo mejor o igual que el resto de
e
v´rtices adyacentes entonces proporciona un valor objetivo mejor o igual
e
que cualquier otra soluci´n posible del problema, luego es una soluci´n
o
o´ptima para el problema.
o

2

E

+

D

+

H1

=

10

−E

+

D

+

H2

=

1

D

+

H3

=

4

Si hacemos H1 = H2 = 0, nos queda:
E

+

D

=

10

−E

+

D

=

1

=

4

D

+

H3

cuya soluci´n es:
o
E = 9/2, D = 11/2, H3 = −3/2

No puede ser soluci´n del PPL incumple la restricci´n de no negatividad.
o
o

3

( E,

D,H1 ,

H2 ,

H3 )

0

0

10

1

4

(0,0) Soluci´n posible
o

0

10

0

-9

-6

(0,10) no es soluci´n posible
o

0

1

9

0

3

(0,1) Soluci´n posible
o

0

4

6

-3

0

(0,4) no es soluci´n posible
o

10

0

0

11

4

(10,0) Soluci´n posible
o

?

0

?

?

0

Sistema Incompatible

-1

0

11

0

4(-1,0) no es soluci´n posible
o

9/2

11/2

0

0

-3/2

6

4

0

3

0

(6,4) Soluci´n posible
o

3

4

3

0

0

(3,4) Soluci´n posible
o

(9/2,11/2) no es soluci´n posible
o

4

´
´
Como obtener los vertices
del
conjunto de soluciones de un PPL
Para un problema cuya forma est´ndar incluya un sistema de m ecuaa
e
ciones linealmente independientes y ninc´gnitas, los v´rtices del poo
liedro se obtienen resolviendo los sistemas de m ecuaciones con m
inc´gnitas que resultan al igualar a cero subconjuntos de n − m variao
bles.
Solo ser´n soluciones posibles (v´rtices) aqu´llos puntos cuyas variaa
e
e
bles, tanto de holgura como originales sean no negativas.

5

3.2 El M´todo Simplex
e
Desarrollado por George Dantzig en 1947.
Primeraaplicaci´n importante: J. Laderman resolvi´ un problema de elaboo
o
raci´n de una dieta en la que hab´ 9 restricciones de igualdad y 27 variables.
o
ıa
Necesit´ ´l trabajo de 120 d´
oe
ıas-hombre.
Dado un PPL expresado en forma est´ndar con m ecuaciones y n
a
inc´gnitas, m ≤ n, podemos dividir las variables en dos grupos:
o
1. n − m variables a las cu´les les damos el valor 0, y quedenomia
naremos variables no b´sicas.
a
2. m variables cuyo valor se determinar´ resolviendo el sistema de
a
m ecuaciones y m inc´gnitas resultante de igualar a cero el resto
o
de variables. Si dicho sistema tiene una unica soluci´n, diremos
´
o
que las m variables son variables b´sicas.
a
Soluci´n del sistema −→ soluci´n b´sica
o
o a
Si adem´s las variables ≥ 0 −→ soluci´n posible...