El método de las dos fases

Conceptos y Principios Básicos


Partimos de un problema de programación lineal en la forma
     Minimizar Ctx
Sujeto a
     Ax ≤ b
     x ≥ 0
Donde, como siempre
     A∈ Mmxn, con rango(A)=m, b∈ Rm, C∈ Rn
Loo primero que hacemos es escribir este problema en la forma estándar como hemos visto en la sección Elemento pivote del Simplex. Mediante el uso de variables de holgura sies preciso, es posible transformar este problema en otro en la forma
Minimizar Ctx
Sujeto a
Ax = b
x ≥ 0
Donde, como siempre
A∈ Mmxn, con rango(A)=m, b∈ Rm, C∈ Rn
Entonces a partir de ahora consideraremos el problema escrito en forma estándar.

Para comenzar las iteraciones del algoritmo del simplex necesitamos encontrar una submatriz identidad mxm de A. La mayoria de las veces no tendremos esto.

En ese caso, aplicamos el llamado médodo de las dos fases que consiste en lo siguiente:

El método de las dos fases



Fase 1

1) Buscamos una submatriz identidad de dimensión mxn dentro de la matriz total A, una vez añadidas las variables de holgura serán necesarias como mucho m variables artificiales artificiales nuevas para iniciar el algoritmo, digamos que tendremos k variables artificiales, con k ≤ m.



2) Cambiamos la función objetivo original por una que tiene todo ceros excepto en las k componentes que se refieren a las variables artificiales, en cuyo caso tienen el valor 1 (es decir, el vector C=(0, .., n-veces ..., 0, 1, .., k-veces ..., 1)

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

       3a) Llegamos al caso de solución óptima cero: esto quiere decir que las 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) tomamos 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 para ella

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 de 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 ya hemos prescindido de las variables artificiales, esto es gracias a que al finla 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