El Mtodo Simplex
El primer mtodo formal para encontrar soluciones ptimas el mtodo
Simplex- fue
desarrollado por Dantzig en 1947 y mejorado por Charnes entre 1948 y
1952. Actualmente es el mtodo ms utilizado en la bsqueda de
soluciones ptimas de programas lineales. En este apartado se examina su
funcionamiento de forma simple e intuitiva.
En primer lugar recordemos como encontrbamos soluciones con el
mtodo grfico. Primero formbamos un conjunto convexo con las
restricciones del modelo. Segundo, se dibujaba la funcin objetivo fuera
del conjunto convexo dando un valor arbitrario al propio objetivo y se iba
desplazando sta paralelamente (ya que su pendiente es siempre
constante) hasta encontrarse con un punto extremo. Intuitivamente,
podemos ver que sea cual sea la funcin objetivo lineal, la solucin ptima
se encontrar en un punto extremo, como mnimo6. Esto reduce bastante
el espectro de soluciones del problema, limitando la bsqueda del ptimo
a los puntos extremos. An as, pueden haber muchsimos puntos
extremos en un problema. Por ejemplo, un problema grande con 2000
variables y 4000 restricciones tiene exactamente 22000 puntos extremos,
es decir, aproximadamente 10600. Por lo tanto, tenemos que encontrar un
mtodo para reducir el nmero de soluciones factibles posibles de ser
ptimas. Dantzig hizo estas mismas suposiciones (o eso creemos) y
observ primero las caractersticas matemticas siguientes:
1. El conjunto formado por las restricciones es convexo
2. La solucin siempre ocurre en un punto extremo
3. Un punto extremo siempre tiene como mnimo dos puntos extremos
adyacentes
Y a partir de ellas desarroll el mtodo siguiente:
Encontrar una solucin inicial factible en uno de los puntos extremos del
conjunto convexo y calcular el valor de la funcin objetivo.
Examinar un punto extremo adyacente al encontrado en la etapa 1 y
calcular el nuevo valor de la funcin objetivo. Si este nuevo valor mejora el
objetivo, guardar la nueva solucin y repetir la etapa 2. En caso contrario,
ignorar la solucin nueva y volver a examinar otro punto extremo.
Regla de parada: cuando no existe ningn extremo adyacente que mejore
la solucin, nos hallamos en el ptimo. Es decir, que vamos de punto
extremo a punto extremo adyacente siempre que podamos mejorar la
solucin, hasta llegar a un punto en donde no existe ningn punto
extremo adyacente al que nos encontramos. Dantzig y ms tarde Charnes
desarrollaron un mtodo matemtico para poder efectuar estas
operaciones, es decir, encontrar los valores de los puntos extremos
adyacentes. Para poder ver como funciona, es necesario realizar las
consideraciones siguientes:
Como hemos visto, un programa lineal est compuesto por una funcin
objetivo que queremos optimizar (maximizar o minimizar), unas variables
que denominaremos estructurales y un conjunto de restricciones. En
general, podemos encontrar tres tipos de restricciones en funcin de la
direccin de la desigualdad: <, > =. Toda restriccin con los sentidos <
> pueden transformarse en una restriccin con igualdad aadiendo una
variable. Si la desigualdad tiene la direccin <, podemos aadir una
variable de holgura. Por ejemplo, la restriccin X1 + 3X2 < 144 se puede
transformar en X1 + 3X2 + X3 = 144. Si en la solucin final del modelo la
restriccin se cumple con igualdad dados unos valores finales de X1 y X2
entonces la variable de holgura asociada a la restriccin es igual a 0. En
otras palabras, la variable de holgura mide la diferencia entre los recursos
utilizados realmente y los discursos disponibles. As mismo, si la
restriccin tiene la direccin _, podemos aadir una variable de exceso
para obtener una ecuacin lineal. Por ejemplo, una restriccin de tipo X1 +
X2 > 12 puede transformarse en X1 + X2 X3 = 12. La interpretacin es la
misma que en el caso anterior: si en la solucin final X3 = 0, la restriccin
se cumplir con igualdad. En este caso, la variable de exceso mide el
consumo adicional que realizamos de un recurso disponible.
Con estas consideraciones, cualquier programa lineal con restricciones de
desigualdad puede transformarse en un problema lineal con todas las
restricciones con forma de igualdad sin alterar la naturaleza matemtica
del problema. Esta transformacin se denomina la forma cannica o forma
aumentada de un programa lineal. Si tenemos n variables y m restricciones
con desigualdad, cuando escribimos la forma cannica del problema lineal
tendremos m nuevas variables de holgura o exceso, es decir, un total de m
+ n variables y m restricciones. En resumen, tendremos que el conjunto de
restricciones forma un conjunto de ecuaciones lineales con ms variables
que ecuaciones. En este caso, existen infinitas soluciones del sistema y
nuestro objetivo es escoger entre ellas la que optimice el valor de la
funcin objetivo. Por otro lado, si tenemos un programa lineal con n
variables, m restricciones con desigualdad y r restricciones con igualdad,
tendremos m+n variables y m+r restricciones con igualdad en la forma
cannica. En este caso, para que el problema sea factible, se tiene que
cumplir lo siguiente: m+n _ m+r, el nmero de restricciones no puede
superar el nmero de variables.