Metodo De Las Dos Fases

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.1 Problema imposible. 3.5.2Problema 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 demejora

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. Si S es no acotada, solo podemos egarantizar 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 −E

+ +

D DD

+ + +

H1 H2 H3

= = =

10 1 4

Si hacemos H1 = H2 = 0, nos queda: E −E + + D D D cuya soluci´n es: o E = 9/2, D = 11/2, H3 = −3/2 + H3 = = = 10 1 4

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

3

( E, 0 0 0 0 10 ? -1 9/2 6 3

D, 0 10 1 4 0 0 0 11/2 4 4

H1 , 10 0 9 6 0 ? 11 0 0 3

H2 , 1 -9 0 -3 11 ? 0 0 3 0

H3 ) 4 -6 3 0 4 0 4 -3/20 0 (0,0) Soluci´n posible o (0,10) no es soluci´n posible o (0,1) Soluci´n posible o (0,4) no es soluci´n posible o (10,0) Soluci´n posible o Sistema Incompatible (-1,0) no es soluci´n posible o (9/2,11/2) no es soluci´n posible o (6,4) Soluci´n posible o (3,4) Soluci´n posible o

4

´ ´ Como obtener los vertices del conjunto de soluciones de un PPL Para un problema cuya forma est´ndarincluya un sistema de m ecuaa e ciones linealmente independientes y n inc´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´todoSimplex e
Desarrollado por George Dantzig en 1947. Primera aplicaci´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 − mvariables a las cu´les les damos el valor 0, y que denomia 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 lasvariables ≥ 0 −→ soluci´n posible b´sica a o a
6

´ ´ Formalizacion algebraica
PPL Min s.a.: z = ct x Ax = b x ≥ 0n B := {columnas de A de coeficientes de las variables b´sicas} a N := A \ B := { columnas de A coeficientes de las variables no b´sicas} a     x c  B , c =  B A = (B, N ), x = xN cN Min s.a.: z z− ct xB − ct xN = 0 B N BxB + N xN = b xB ≥ 0, xN ≥ 0

7

B −1 (BxB + N xN ) =...