Simplex

EL ALGORITMO SIMPLEX1

Departamento de Ingenier´ Matem´tica y ıa a Centro de Modelamiento Matem´tico a Universidad de Chile Abril de 2005

Prof. Jorge Amaya A.

Este texto es un apunte de clases, destinado exclusivamente a los alumnos del curso MA37AOPTIMIZACION de la Escuela de Ingenier´ de la Universidad de Chile. ıa

1

1

Idea b´sica a

Sabemos que para poder resolver unproblema de programaci´n lineal necesitamos solao mente considerar los v´rtices del poliedro P = {x ∈ IRn /Ax = b, x ≥ 0} como candidatos e a soluci´n ´ptima del problema. Para un n´mero grande de variables vimos tambi´n que o o u e n el n´mero de v´rtices u e puede ser enorme, por lo que una metodolog´ de b´squeda ıa u m sistem´tica se hace necesaria. a El m´todo simplex, desarrollado originalmente porG. Dantzig (1947), se basa en una idea e geom´trica muy simple: primero se encuentra una base factible (un v´rtice de P). Luego e e el m´todo permite moverse de v´rtice en v´rtice, a trav´s de las aristas de P que sean die e e e recciones de descenso para la funci´n objetivo, generando una sucesi´n de v´rtices xk cuyos o o e valores cT xk son (estrictamente) decrecientes. Esto asegura que unmismo v´rtice no es e visitado dos veces. As´ como el n´mero de v´rtices es finito, el algoritmo converge en un ı, u e n´mero finito de pasos; esto significa que encuentra una soluci´n ´ptima, o una arista a lo u o o largo de la cual la funci´n objetivo es no acotada. o A la b´squeda de una base factible (punto extremo) inicial se la llama Fase I del Algoritmo u Simplex. El resto del procedimiento seconoce como Fase II, que expondremos a continuaci´n. o

2

Fase II del Algoritmo Simplex

Consideremos el problema (PL) min cT x
x∈P

Supongamos que A ∈ Mmn es de rango m, entonces puede escribirse de la forma A = [B, N ], con B ∈ Mmm invertible. Si denotamos x = cB xB , c= xN cN implica que xB = B −1 b − B −1 N xN . , entonces Ax = BxB + N xN = b, lo que finalmente

donde P = {x ∈ IRn /Ax= b, x ≥ 0}.

El problema (PL) es entonces equivalente a 2

min (cT − cT B −1 N )xN +cT B −1 b B N B xB + B −1 N xN = B −1 b xN ≥ 0 xB ≥ 0 Consideremos un punto x extremo (es factible), xB xN = B −1 b 0 ≥0

Con esto, cT x = cT xB + cT xN = cT B −1 b. Se observa que, si cT − cT B −1 N ≥ 0, entonces B N B N B dar valor positivo a las variables xN produce un crecimiento del valor de cT x.Entonces, la B −1 b xB ≥ 0 es ´ptima. o = soluci´n o 0 xN o De aqu´ en adelante llamaremos π T al vector fila cT B −1 , por lo cual el valor de la funci´n ı B T objetivo tambi´n se puede escribir π b. e a Se llamar´ vector de costos reducidos al resultado de reemplazar las variables b´sicas en a T T −1 la funci´n objetivo. Es decir, el vector cN − cB B N corresponde al costo reducido de las o variablesno b´sicas. a

2.1

CASO 1: soluci´n en curso es ´ptima o o

Veamos un ejemplo para ilustrar este concepto. Ejemplo 2.1 min 3x3 −3x3 −8x3 +x4 +3x4 ≤ 6 +4x4 ≤ 4 x3 , x4 ≥ 0

Escribamos el problema en la forma can´nica: o +0 min 0x1 +0x2 +3x3 +x4 x1 −3x3 +3x4 = 6 x2 −8x3 +4x4 = 4 xi ≥ 0 i = 1, 2, 3, 4 3

Elijamos B = donde

1 0 0 1

,N=

−3 3 , −8 4

xB xN

  x1 x2  =  ,x3  x4

cB cN

  0 0 =  , 3 1

xB : variables b´sicas o en la base a xN : variables no-b´sicas o fuera de la base a Adem´s, en este caso, a x1 , x2 : variables de holgura x3 , x4 : variables estructurales (es decir, las del problema original). Se puede despejar x1 , x2 en funci´n de x3 , x4 y reemplazar en la funci´n objetivo. Notar o o que todo queda igual, pues B = I y los costosreducidos de las variables b´sicas son siempre a T T T nulos, en efecto, cB = cB − π B = 0. ¯   6 −1 4 B b xB T Como cN = cN − π T N = (3, 1) ≥ 0, la soluci´n ¯T = =   es ´ptima. o 0 o 0 xN 0 Criterio de Optimalidad En un problema de minimizaci´n escrito en la forma can´nica, si las variables no b´sicas o o a T T T o tienen asociado un vector de costos reducidos cN = cN − π N ≥ 0,...