Simplex

Universidad de Chile Facultad de Ciencias F´ ısicas y Matem´ticas a Departamento de Ingenier´ Industrial ıa

IN34A: Clase Auxiliar

Simplex

Marcel Goic F.1

Esta es una versi´n bastante preliminar por lo que puede contar con numerosas faltas de ortografa y o errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@ing.uchile.cl

1

IN34A: Optimizaci´n o

Pag. 1

1.Una brev´ ısima introducci´n. o

El ´ptimo de un problema lineal (si existe) est´ en un v´rtice del poliedro factible o en los o a e infinitos puntos que forman la arista que une dos de ellos en el caso de infinitas soluciones. De ah´ la importancia de contar con un algoritmo que examine el valor de la funci´n objetivo ı o en dichos v´rtices, recorriendolo de una forma (emp´ e ıricamente)eficiente. Este es el papel que juega simplex. Examinaremos el algoritmo simplex, partiendo por la forma can´nica o usando ecuaciones para luego revisar la forma matricial y de tablas. Adem´s veremos la fase a I del algoritmo que nos servir´ para encontrar una vertice inicial del espacio de soluciones a factibles, requerimiento fundamental en el desarrollo del algoritmo.

2.

Ese trabalenguas llamadobase...

Queremos resolver un problema en la forma est´ndar: a m´ ct · x ın s.a A · x = b x≥0 El algoritmo simplex es iterativo. Supongamos que disponemos de m restricciones y n variables 2 . Queremos poder representar f´cilmente v´rtices del poliedro factible, lo que en la a e forma est´ndar es bastante f´cil: basta con escoger m variables iguales a cero. En efecto, fijar a a una variable iguala cero significa que estamos haciendo activa una restricci´n: ya sea la de o no negatividad si es variable original o la restrici´n que le di´ origen si es variable de holgura o o y por tanto si fijamos m de ellas como nulas tendremos un v´rtice del espacio factible. A e las m variables que fijamos nulas las llamaremos variables no b´sicas y las otras (las que a determinamos resolviendo el sistemaresultante) son las variables b´sicas. En cada iteraci´n a o lo que haremos es movernos a un v´rtice adyacente al actual haciendo que una variable no e b´sica deje de serlo (dejamos que aumente su valor) y viendo cual es la variable b´sica que a a primero se anula (se hace no b´sica). a Matricialmente, lo anterior puede verse como que en cada iteraci´n escogeremos m columnas o de A (asociadas a mvariables), formando una submatriz cuadrada B, matriz b´sica. Las a columnas restantes se agrupan en otra submatriz R, matriz no b´sica. Las variables asociadas a a las columnas de B son las variables b´sicas y las agruparemos en un subvector xB . Del a mismo modo, las variables asociadas a las columnas de R son las variables no b´sicas y las a agruparemos en un subvector de x que llamaremos xR .Si le asignamos arbitrariamente el valor 0 a todas las componentes del vector xR , tendremos una soluci´n b´sica (xR := 0). o a Para poder realizar el proceso iterativo, debemos ser capaces de respondernos en cada iteraci´n: o
Para tener un problema que optimizar, es decir, para que exista un espacio de soluciones factibles mayor que un solo punto, debe tenerse que n > m (restricciones l.i)
2IN34A: Optimizaci´n o 1. ¿Es ´ptima la soluci´n? o o 2. ¿Que variable xs debe entrar a la base? 3. ¿Que variable xr debe salir de la base (dado que entra xs )?

Pag. 2

3.

Los se˜ ores optimizantes no se ponen de acuerdo n

Si bien el principio es siempre el mismo, existen varias formas de escribirlo y en cada una de ellas las condiciones de optimalidad, los criterios de entrada y salidade la base varian en su forma (no en su fondo). En clases de c´tedra vieron varias formas con probabilidad → 1, discutiendo el trasfondo a matem´tico que hay detr´s de cada criterio por lo que no me extender´ mayormente aqu´ a a e ı. Sin embargo, adjunto un resumen del algoritmo con la forma que toma simplex por medio de tablas y matricial.

3.1.

Simplex usando ecuaciones

Esta versi´n...