Universidad de Chile Facultad de Ciencias F sicas y Matemticas a Departamento de Ingenier Industrial a

Repaso del algoritmo SIMPLEX

Marcel Goic F.1

IN70K: Clase Auxiliar

Esta es una versin bastante preliminar por lo que puede contar con numerosas faltas de ortograa y o errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@[Link]

IN70K: Programacin Matemtica o a

Pag. 1

1.

Desempolvando lo que ya sabemos

Algunos resultados importantes de programacin lineal: o El ptimo de todo PL (en caso de existir) se encuentra en un vrtice del poliedro que o e dene el conjunto factible. Sea un poliedro denido por A x = b con A I mn , x I n , b I m , rg(A) = m. R R R Todo vrtice del poliedro puede ser caracterizado como una solucin bsica en que e o a se escogen m variables (asociadas a m columnas de A)para que formen la base y las (n m) variables restantes (asociadas a (n m) columnas de A) para ser jadas en 0. Para encontrar el valor de las m componentes no nulas del vrtice, resolvemos el e sistema de ecuaciones de m m resultante. Finalmente, para resolver el sitema de ecuaciones lo mas directo es realizar eliminacin gaussiana. o De esta manera, lo que hace simplex es ir escogiendo columnas de manera inteligente de modo de ir recorriendo los vrtices del poliedro factible. As cada vez que tenemos un e , vrtice necesitamos: e 1. Ver si es ptimo. o 2. Si no es optimo, escoger cual es el nuevo vrtice determinando cual variable entra a la e base y cual sale. 3. Adicionalmente debemos ser capaces de determinar cuando: La solucin es no acotada: se puede mejorar innitamente el valor de la funcin o o objetivo. Existen ptimos alternativos: toda una cara del poliedro tiene el mismo valor de o la funcin objetivo. o La solucin es degenerada: un vrtice esta sobredeterminado por lo que de una o e iteracin a la otra estaremos en el mismo vrtice. o e

2.

Algoritmo SIMPLEX (para problemas de minimizacin) o

La presente seccion corresponde a la transcripcion de material de clase preparado por el distinguid simo catedratico [Link] Caro V. Forma cannica o usando tablas o Se tiene el problema lineal en su forma cannica para alguna solucin bsica factible o o a dada (bi 0i = 1, ..., m)). Las variables bsicas son aquellas que tienen costo reducido a nulo y su respectiva columna es un vector cannico de Rm . o

IN70K: Programacin Matemtica o a c1 a11 . . . am1 ... cn a1n . . . amn z 1 b . . . m b

Pag. 2

1. Si cj 0 j = 1, ..., n entonces la solucin es ptima (las variables bsicas son o o a a iguales a bi y las no bsicas son nulas). 2. Si alguno de los costos reducidos es negativo (j < 0 para algn j) entonces se c u debe escoger una variable no bsica xs para que entre a la base. No es obligatorio, a n{ c pero usualmente se usa el criterio cs = m cj |j < 0}. 3. Si ais 0 i = 1, ..., m entonces el problema es no acotado. Si ais > 0 para algn i, entonces se determina la variable que sale de la base mediante el criterio: u r b m n = ais > 0 ars i b ais

4. Se pivotea sobre ars para actualizar la tabla o la forma cannica. Las frmulas de o o actualizacin son: o aij aij ais arj ars i i ais br b b ars z z cs r b ars

c j cj 5. Volver a 1. Forma matricial

cs arj ars

Se el problema en su forma estandar y se asume que se conoce una base B primal factible (o sea se tiene un vrtice factible inicial) e m z = ct x n s.a A x = b x0 1. Determinar la inversa B 1 de la base. 2. Determinar la solucin bsica factible asociada a la base B. Para ello se tiene que o a resolver el sistema B xb = b que tiene solucin unica. Luego xb = = B 1 b y o b b. z = ct B 3. Determinar si esta solucin es ptima aplicandoel criterio de optimalidad. Para o o esto es necesario calcular los costos reducidos asociados a las variables no bsicas a cj = cj ct B 1 Aj . Si cj 0 j = 1, ..., n entonces la solucin es ptima. En o o B caso contrario, efectuar el cambio de base.

IN70K: Programacin Matemtica o a

Pag. 3

4. Determinar la columna que entra a la base. Sea cs = m cj |j < 0}, entonces la n{ c a variable xs aumentar su valor y la columna As entra a la base. 5. Determinar la columna que sale de la base. Calcular As = B 1 As . Si As 0 entonces el problema es no acotado. De lo contrario determinar r tal que r i b b m n = ais > 0 ais ars Entonces la variable bsica de la ecuacin r es la primera que se anula cuando xs a o crece, por lo tanto la columna Ar sale de la base. 6. Actualizar la base y volver a 1.

3.

Fase I del algoritmo Simplex.

Para iniciar el proceso iterativo, simplex necesita un vrtice (base) factible inicial. Si en los e coecientes del problema original aparece una identidad y todos los lados derechos tenemos una base factible inicial trivial: la correspondiente a las variables que forman la identidad2 . Sin embargo, en muchos casos esto no ocurre, por lo que tenemos que disponer de un mtodo e para hallar soluciones bsica factibles si las hay. Esto consiste en agregar tantas variables a articiales como sea necesario para formar una identidad y luego resolver un problema de optimizacin consistente en tratar de que dichas variables articiales se hagan nulas y por o tanto se puedan eliminar. Para ello tratamos de minimizar la suma de variables articiales: Si la suma optima de variables articiales es no nula signica que alguna variable articial es positiva y por tanto no la podemos eliminar. En dicho caso, el problema es infactible. Si la suma optima de variables articiales es nula signica que todas las variables articiales son nulas y por tanto las podemos eliminar obteniendo un vrtice factible: e Si ninguna variable articial est en la base optima de fase I, entonces tomamos a dicha base como vrtice inicial para la fase II. e Si existen variables articiales en la base optima de fase I, entonces podemos in tentar reemplazarla por cualquier variable no bsica para formar una base factible a para la fase II.

4.
4.1.

Problemas
Problema 1

Resolver usando el algoritmo simplex el siguiente problema:

2

t picamente las variables de holgura

IN70K: Programacin Matemtica o a

Pag. 4

mx z = 2x1 + 3x2 a s.a x1 + x2 5 x1 3x2 9 0 x1 , x 2 Solucin o Pasamos el problema a forma estandar: m z = 5x1 3x4 n s.a x1 + x2 + x2 = 5 x1 + 3x2 + x4 = 0 0 x1 , x2 , x3 , x4

Iteracion 1:
Trivialmente tenemos una base factible formada por las variables de holgura x3 y x4 : x3 0 1 0 x4 0 0 1 x1 -2 1 1 x2 -3 1 3

0 5 9

Notamos que esta en forma aannica porque las variables bsicas forman cada una un o a 2 o , vector caanico de I y tienen funciones coeceintes en la funcin objetivo nulos. As o R podemos aplicar los criterios de optimalidad, entrada y salida de la base: 1. Optimalidad: No es ptimo porque existen variables no bsicas con costos reo a ducidos negatiaos. 2. Entrada: Entra la variable con menor costo reducido: x2 . 3. Salida: m 5 , 9 } = 3, luego, sale x4 . n{ 1 3

Iteracion 2:
Al intercambiar las variables x2 por x4 nuestra base queda conformada por las variables x3 y x 2 : x3 0 1 0 x7 -3 1 3 x1 -2 0 1 x4 0 0 1

0 5 9

IN70K: Programacin Matemtica o a Notamos que no esta en forma cannica porque lo que tenemos que pyvotear: o x3 0 1 0 x2 0 0 1 x1 -1 2/3 1/3 x4 1 -1/3 1/3

Pag. 5

9 3 3

Notar aqu que nuestra solucion en curso es (0, 3, 2, 2) con valor de la funcin objetivo o de 9. Como ahora est en forma cannica por lo que podemos aplicar los criterios de a o optimalidad, entrada y salida de la base: 1. Optimalidad: No es ptimo porque existen variables no bsicas con costos reo a ducidos negativos. 2. Entrada: Entra la varianle con menor costo reducido: x1 . 3. Salida: m 2/3 , 1/3 } = 3, luego, sale x3 . n{ 2 3

Iteracion 3:
Al intercambiar las variables x1 por x3 nuestra base queda conformada por las variables x1 y x 2 : x1 x2 -1 0 2/3 0 1/3 1 x3 0 1 0 x4 0 -1/3 1/3

9 2 3

Notamos que no esta en forma cannica porque lo que tenemos que pivotear: o x1 0 1 0 x2 0 0 1 x3 3/2 3/2 -1/2 x4 1/2 -1/2 1/2

12 3 2

Notar aqu que nuestra solucion en curso es (3, 2, 0, 0) con valor de la funcin objetivo o de 12. Como ahora est en forma cannica por lo que podemos aplicar los criterios de a o optimalidad, entrada y salida de la base: 1. Optimalidad: Es ptimo porque no existen variables no bsicas con costos reo a ducidos negativos. La forma matricial es completamente anloga, solo que en vez de pivotear, todas las actuala izaciones se explicitan por medio del calculo de operaciones matriciales: cR = cR cB B 1 R

IN70K: Programacin Matemtica o a b = B 1 b Aj = B 1 Aj As por ejemplo, la iteracion 2 se realizar matricialmente como sigue: a (c1 , c4 ) = (2, 0) (0, 3) b1 b2 a11 a12 1 1 0 3 1 1 0 3
1

Pag. 6

1 1 0 3 5 9 1 1

= (1, 1) 2 3 2/3 1/3

= =

= =

1. Optimalidad: Como c1 < 0 no es optimo 2. Entrada: Entra la unica variable con costo reducido negativo: x1 3. Salida: m 2/3 , 1/3 } = 3 por lo que sale x3 n{ 2 3

4.2.

Problema 2
Resolver el siguiente problema usando el algoritmo simplex: mx z = 6x1 + 4x2 a s.a x1 + x2 10 2x1 + x2 4 0 x1 , x2

Solucin o Como siempre, comenzamos por escribir el problema en la forma estandar: m z = 6x1 4x2 n s.a x1 + x2 + x3 = 10 2x1 + x2 x4 = 4 0 x1 , x 2 , x 3 , x 4

IN70K: Programacin Matemtica o a

Pag. 7

Si bien tenemos lados derechos positivos, no tenemos una submatriz identidad en la matriz de coecientes y por lo tanto no tenemos una solucin bsica factible inicial para comenzar o a a iterar con el algoritmo simplex. Luego debemos resolver la Fase I del algoritmo simplex. Para ello agregamos variables articiales y resolvemos el siguiente problema: m w = x5 n s.a x1 + x2 + x3 = 10 2x1 + x2 x4 + x5 = 4 0 x1 , x2 , x3 , x4 , x5

Iteracion 1 (Fase I):

Nuestra base esta compuesta por las variables x3 y x5 . Luego el tableau asociado es: x3 0 1 0 x5 1 0 1 x1 0 1 2 x2 0 1 1 x4 0 0 -1

0 10 4

No esta en forma cannica (hay costos reducidos de variables bsicas no nulos), por lo o a que debemos pivotear llegando al siguiente tableau: x3 0 1 0 x5 0 0 1 x1 -2 1 2 x2 -1 1 1 x4 1 0 -1

-4 10 4

Ahora, como esta en forma estandar podemos aplicar los criterios de optimalidad, entrada y salida: 1. Optimalidad: No es ptimo porque existen costos reducidos negativos. o 2. Entrada: Entra x1 porque tiene el minimo costo reducido. 3. Salida: m 10 , 4 } = 2 sale x5 . n{ 1 2

Iteracion 2 (Fase I):

Nuestra base ahora esta compuesta por las variables x3 y x1 . Luego el tableau asociado es: x3 0 1 0 x1 -2 1 2 x5 0 0 1 x2 -1 1 1 x4 1 0 -1

-4 10 4

No esta en forma cannica por lo que debemos pivotear llegando al siguiente tableau: o

IN70K: Programacin Matemtica o a x3 0 1 0 x1 0 0 1 x5 1 -1/2 1/2 x2 0 1/2 1/2 x4 0 1/2 -1/2

Pag. 8

0 8 2

Ahora, como esta en forma estandar podemos aplicar los criterios de optimalidad, entrada y salida: 1. Optimalidad: Es ptimo porque no existen costos reducidos negativos. o Ahora, como (variables articiales) = 0 tenemos una solucin basica factible la cual o esta dada por: x1 = 2, x3 = 8 (variables bsicas) y x2 = 0, x4 = 0 (variables no bsicas). a a Con esto, podr amos tomar esta solucin y partir todo de nuevo para resolver la Fase II, o pero es mas eciente continuar con la solucin en curso cambiando la funcin objetivo y o o eliminando las variable articiales (que ya sabemos que no nulas).

Iteracion 1 (Fase II):

Nuestra base esta compuesta por las variables x3 y x1 . Luego el tableau asociado es: x3 0 1 0 x1 -6 0 1 x2 -4 1/2 1/2 x3 0 1/2 -1/2

0 8 2

No esta en forma cannica (hay costos reducidos de variables bsicas no nulos), por lo o a que debemos pivotear llegando al siguiente tableau: x3 0 1 0 x1 0 0 1 x2 -1 1/2 1/2 x4 -3 1/2 -1/2

12 8 2

Ahora, como esta en forma estandar podemos aplicar los criterios de optimalidad, entrada y salida: 1. Optimalidad: No es ptimo porque existen costos reducidos negativos. o 2. Entrada: Entra x4 porque tiene el minimo costo reducido.
2 3. Salida: m 1/2 , 1/2 } sale x3 . n{ 8

Iteracion 2 (Fase II):

Nuestra base ahora esta compuesta por las variables x4 y x1 . Luego el tableau asociado es:

IN70K: Programacin Matemtica o a x4 x1 -3 0 1/2 0 -1/2 1 x2 x3 -1 0 1/2 1 1/2 -1

Pag. 9

12 8 2

No esta en forma cannica por lo que debemos pivotear llegando al siguiente tableau: o x4 0 1 0 x1 0 0 1 x2 2 1 1 x3 6 2 1

60 16 10

Ahora, como esta en forma estandar podemos aplicar los criterios de optimalidad, entrada y salida: 1. Optimalidad: Es ptimo porque no existen costos reducidos negativos. o