El método de las dos fases

Partimos de un problema de programación lineal en la forma

Notar lo primero que este problema no está escrito en forma estándar (ver sección, el algoritmo del Simplex)

Ya hemos visto en la sección Elemento pivote del Simplex como escribir un problema de programación lineal en la forma estándar mediante el uso de las variables de holgura.

El problema es que, necesitamos encontrar una submatriz identidad mxm de A para inciar el algoritmo, cosa que no siempre tenemos una vez escrito el problema en forma estándar.

Si tenemos la submatriz identidad podemos iniciar el algoritmo y calcular las soluciones mediante el Algoritmo del Simplex.

En caso contrario, una opción es añadir k variables artificiales, con \(\ k \leqslant m \) con el fin de obtener una submatriz identidad en A.

Si este es el caso, ya podríamos iniciar el algoritmo pero como hemos añadido varianbles artificiales, es posible que el problema se nos complique. En lugar de aplicar Algoritmo del Simplex directamente, lo que hacemos es cambiar la función objetivo original por otra que solo tenga variables artificiales.

Si aplicando el algoritmo se nos anulan todas las variables artificiales, entonces, en una segunda fase podemos eliminar todas estas variables y ponemos nuestra función objetivo original. A esto se le llama método de las dos fases.

La idea de la fase 1 es eliminar las variables artificiales de la base y obtener la solución trivial.

Veremos en esta sección un ejemplo del método de las dos fases y como manejar las variables artificiales y de holgura. Un ejemplo aún más completo está aquí.

Ya vimos que todo problema de programación lineal puede transformarse en uno de la forma estándar, por ejemplo si tenemos

Max(2x1 + 3x2 + 4x3)
Sujeto a
3x1 + 2x2 + x3 ≤ 10
2x1 + 5x2 + 3x3 ≤ 15
x1 + 9x2 - x3 ≥ 4
x1, x2, x3 ≥ 0

Podemos transformarlo en un problema tipo e varias etapas, de la siguiente manera
1) Cambiamos de signo a la función objetivo para tener un problema de minimización

Min(-2x1 - 3x2 - 4x3)
2) Cambiamos de signo la última de las restricciones:

3x1 + 2x2 + x3 ≤ 10
2x1 + 5x2 + 3x3 ≤ 15
-x1 - 9x2 + x3 ≤ -4

3) Introducimos variables de holgura para quitar las desigualdades y transformarlas en igualdades:

3x1 + 2x2 + x3 + x4 = 10
2x1 + 5x2 + 3x3 + x5 = 15
-x1 - 9x2 + x3 + x6 = -4
x1, x2, x3, x4, x5, x6 ≥ 0

4) Y cambiamos de signo la última de las restricciones:

3x1 + 2x2 + x3 + x4 = 10
2x1 + 5x2 + 3x3 + x5 = 15
x1 + 9x2 - x3 - x6 = 4
x1, x2, x3, x4, x5, x6 ≥ 0

Ya tenemos el problema en formulación estándar, lo que antes era un problema en 3 dimensiones, se nos ha convertido en uno de 6 dimensiones, lo cual no es demasiado importante, pues los cálculos finales será el ordenador quien los haga por nosotros.
Con estos cambios, la matriz A queda de la siguiente forma:
\begin{pmatrix} 3 & 2 & 1 & 1 & 0 & 0 \\ 2 & 5 & 3 & 0 & 1 & 0\\ 1 & 9 & -1 & 0 & 0 &-1 \end{pmatrix}
Como vemos aún no tenemos una submatriz identidad para comenzar el algoritmo.
La solución, es aplicar el método de las dos fases, que consiste en lo siguiente:

FASE 1
1) Añadimos las variables artificiales, como mucho serán necesarias 3, en este caso con una es suficiente:
3x1 + 2x2 + x3 + x4 = 10
2x1 + 5x2 + 3x3 + x5 = 15
x1 + 9x2 - x3 - x6 + x7= 4
x1, x2, x3, x4, x5, x6, x7 ≥ 0
La matriz A queda de esta forma:
\begin{pmatrix} 3 & 2 & 1 & 1 & 0 & 0 & 0\\ 2 & 5 & 3 & 0 & 1 & 0 & 0\\ 1 & 9 & -1 & 0 & 0 &-1 & 1\end{pmatrix}
Obsérvese que ahora ya tenemos una submatriz identidad para iniciar el algoritmo del simplex.

2) Iniciamos el algoritmo, pero tomamos como vector de costes cero para todas sus componentes, excepto aquellas que corresponden variables artificiales de nuestra matrix de restricciones, 7, la función objetivo es ahora:

Min (x7)
Por tanto el Vector de Costes es

Ct = (0,0,0,0,0,0,1)

La idea es obtener una solución en la que todas las variables artificiales sean cero, es decir, queremos encontrar una solución S0 tal que

x7 = 0

De este modo, podremos sacar las variables artificiales de la base y podemos seguir iternado sin ellas.
Cualquier otra solución que obtengamos al final de la primera fase, hará que nuestro problema no tenga solución.

FASE 2
Si se ha dado la solución S0 al final de la primera fase, eliminamos las variables artificiales y cambiamos la función objetivo por la nuestra, en nuestro ejemplo volvemos a tomar como función objetivo

Min(-2x1 - 3x2 - 4x3)

por tanto el vector de costes es ahora:

Ct = (-2,-3,-4,0,0)

Véase que las varibles de holgura continuan en la base.

Ahora aplicamos el algoritmo, con este vector de costes y con la matriz A que haya restado de eliminar las variables artificiales en la primemra fase, obsérvese que podemos prescindir de ellas gracias a que al fin la de la fase 1 hemos obtenido la solución cero.
Debe tenerse en cuenta que si obtenemos solución óptima para las variables que no son originales (variables básicas) simplemente, tenemos que eliminarlas de nuestra solución, es decir, las hacemos cero.
Para este ejemplo tenemos la solución óptima finita obtenida numéricamente, Ejecutalo aquí:
x1 = 0.0
x2 = 0.84375
x3 = 3.59375

Lo que da una maximización para la fución objetivo de

Z = 16.90625

Ejecuta este ejemplo aquí

En la práctica el número de iteraciones del algoritmo del simplex está entre 3m/2 y 3m, lo cual no está nada mal si como sabemos de la teoría el número de puntos extremos es:

$$ \begin{pmatrix} n \\ m \end{pmatrix} = \frac{n!}{m!(n-m)!} $$