El método de las dos fases

Conceptos y Principios Básicos


Partimos de un problema de programación lineal en la forma
Minimizar \( C^t x \)

Sujeto a

\( \begin{matrix} Ax \leqslant b \\ x \geqslant 0 \end{matrix} \)

Donde

\( A \in \mathbb M _{mxn}, \, rnk(A)=m ,\,\, b \in R^{m}, \, C \in R^{n}, \,\, n \geqslant m \)
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.

El método de las dos fases



Fase 1

1) Añadimos k columnas a la matrix A mediante variables artificiales de modo que A contenga una submatriz identidad de tamaño mxm, por tanto k es menor o igual que m, o sea, la matriz A queda ahora con las dimensiones (n+k) x m. Esto hace que podamos iniciar el algoritmo ya que tendremos una submatriz identidad de dimensión mxm.

2) Cambiamos la función objetivo original por una que tiene todo ceros excepto en las últmas k componentes (aquellas que corresponden con las variables artificiales) que tienen el valor 1 (es decir, el vector C=(0, .., n-veces ..., 0, 1, .., k-veces ..., 1)

3) Iniciamos el algoritmo con este problema. Entonces pueden darse estos casos:

3a) Llegamos al caso de solución óptima cero: esto quiere decir que todas las variables artificiales han salido de la base, en este caso podemos pasar a la fase 2 del método.

3b) Llegamos al caso de solución optima finita distinta de cero: El problema original no tiene solución.

Fase 2

Eliminamos las variables artificiales y continuamos el algoritmo, para ello:

1) Usamos la función objetivo original C

2) Tomamos las m-primeras columnas de la matriz A

3) Continuamos el algoritmo con estos cambios hasta llegar a una de las 4 posibles salidas del problema.


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í.

Teoría en extensión


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

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 una variable artificial por cada una de nuestras restricciones, las cuales no tendrán incidencia sobre las mismas
3x1 + 2x2 + x3 + x4 + x7 = 10
2x1 + 5x2 + 3x3 + x5 + + x8 = 15
x1 + 9x2 - x3 - x6 + + x9= 4
x1, x2, x3, x4, x5, x6, x7, x8, x9 ≥ 0
La matriz A queda


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 a variables artificiales, es decir, tomamos la función objetivo

Min (x7 + x8 + x9)
Por tanto el Vector de Costes es

Ct = (0,0,0,0,0,0,1,1,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, x8, x9 = 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,0)

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 preescindir 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.59375000000000

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
(nm) = n!/m!(n-m)!
Pedimos disculpas por no tener una notación mejor para números combinatorios.





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios





Deja tu post