Esta vez discutiremos los problemas de programación lineal y el uso del algoritmo simplex para resolverlos. Estos problemas lineales tienen una pecularidad, tener un problema Dual. ¿Pero qué implicaciones tiene esta característica y en qué sentido podemos aprovecharla? Si quiere más información de cómo usar la dualidad del problema con el algoritmo Simplex Dual puede consultar esta páginaTambién tenemos un ejemplo de aplicación de este algoritmo sobre la red del Metro de la Ciudad de México para encontrar el mejor camino entre dos estaciones

Para cada problema primal existe uno dual, de tal forma que las desigualdades serán convertidas a duales. El dual de un primal será el certificado de la óptimidad del de uno y viceversa. Las formas genéricas del primal en una forma matricial y su dual son:

\[ \begin{array}{c |c} \text{Primal LP }&\text{Dual LP} \\ \hline \max c^T x & \min \pi^T b \\ Ax \leq b & y^T A \geq c^T \\ x \geq 0 & x \geq 0  \end{array} \]

En el caso general tenemos un conjunto I de desigualdades y un conjunto de E de igualdades, un total de m = |I| + |E| restricciones sobre n variables, con un N es un subconjunto no negativo. El dual tiene m = |I| + |E| variables, donde únicamente I tiene restricciones no negativas. A continuación daré un equivalente entre las restricciones y variables de en dual y primal.  Dado un problema de programación lineal en la forma primal, el dual está definido por:

\[ \begin{array}{c c c} \text{Primal }& & \text{Dual} \\ \hline \min c'x & & \max \pi 'b \\ a'_ix = b_t & i \in M & \pi_i \gtrless 0 \\ a'_ix \geq b_i & i \in \bar{M} & \pi_i \geq 0 \\ x_i \geq 0 & j \in N & \pi ' A_j \leq c_j \\ x_j \gtrless 0 & j \in \bar{N} & \pi'A_j = c_j \end{array} \]

donde x y pi son una solución factible para un problema primal y uno dual respectivamente, y por lo que si existe una solución óptima de un problema de programación lineal también existe un óptimo costo dual. Pero al igual de que existe un dual para todo primar, también el dual del dual es el primal. 

La relación entre uno y otro se resume en que cada restricción de un problema corresponde a una variable en el otro y que los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivo en el otro. 

También hay que aclarar que en un problema de programación lineal sólo existen tres posible resultados: óptimos finitos, infinitos o inviables; y en una pareja dual-primal existen las siguientes combinaciones: finito-finito, inviable-infinito y inviable-inviable. 

Comenzaremos entonces introducirnos en como resolver el simplex dual: con la forma dual 

\[\begin{align*} \min \pi 'b& \\ \pi'A \geq& -c' \\ \pi' \geq& 0 \end{align*}\]

Para generar un igualdad agregaremos una variable de exceso $s \in R^n$, y podemos escribir esto de la forma

\[\begin{align*} \min \pi 'b& \\ \pi'A - s'=& -c' \\ \pi', s' \geq& 0 \end{align*}\]

O como la forma estándar del programa

\[\begin{align*} \min p'\pi & \\ (-A')\pi + s'=& c \\ \pi, s \geq& 0 \end{align*} \]

Para comenzar a trabajar sobre la tabla que formaremos se comenzará a tomar una hilera $b_r < 0$. El elemento pivote se escoge por:

\[ \min_{j \text{ tal que } (-a_{rj}>0)}[\frac{c_j}{(-a_{rj})}]=-\max_{j \text{ tal que } a_{rj}}[\frac{c_j}{a_{rj}}] \]

Ahora veamos las versiones de simplex que más son útiles para su implementación en computación. Si fuéramos a implementar simplex de la manera simple se necesitaría una actualización total de la matriz (m+1)X(n+1) y generar costos cj y columnas Xj cómo los necesitamos. Se puede utilizar en este caso el método revisado de simplex o el método de la matriz invertida. Si comenzamos con una matriz identidad en la tabla inicial, entonces en la ultima interacción con una base B, la matriz B-1 reside en su lugar.

Los pasos para resolver la tabla son los siguientes partiendo de que la matriz está en su lugar:

 

  • Genera los costos cj = cj - pi'Aj relativos uno a la vez hasta encontrar uno que sea negativo, hasta que j=s o terminamos con una solución óptima.
  • Generamos la columna Xrs por el uso del test o descubrimos que la solución es infinita.
    \[ \min_{i \text{ tal que } x_{is}>0}(\frac{\bar{b}_i}{x_{is}}) \]
  • Hacemos pivote y actualizamos la matriz contenedora para obtener Mj+1.
  • Remplazar el elemento r de B por s.

El paso crucial de generar la columna identificada aquí con el número 2 teniendo la matriz inversa significa que tenemos suficiente información para generar cualquier parte de la tabla que queremos. Si se quiere usar este método en una forma de las dos fases debemos tener en cuenta algunas consideraciones. En primer lugar, si comenzamos con la variable artificial con un costo de unidad, tenemos que jacer el costo de la hilera cero. Esto se consigue restando todas las columnas de hilera 0. Cuando se entre a la a la fase dos, se debe cambiar el costo  de la siguiente manera: El costo dj debe ser llevado a convertirse en cj, el costo original -pi' = -cB'B^-1.

 

Este método nos permite ahorrar tiempo computacional al actualizar una matriz (m+1)X(m + 1) en vez de (m+1)X(n+1). Con esto no se necesita calcular los costos de cada columna no básica, y en segundo lugar el método revisado parte del hecho de valuar las operaciones que usa en las columnas Aj de la tabla original. 

 

 

 

Share This