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í.
Ya vimos que todo problema de programación lineal puede
transformarse en uno de la forma estándar, por ejemplo si
tenemos
Max(2x
1 + 3x
2 + 4x
3)
Sujeto a
3x
1 + 2x
2 + x
3 ≤ 10
2x
1 + 5x
2 + 3x
3 ≤ 15
x
1 + 9x
2 - x
3 ≥ 4
x
1, x
2, x
3 ≥ 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(-2x
1 - 3x
2 - 4x
3)
2) Cambiamos de signo la última de las restricciones:
3x
1 + 2x
2 + x
3 ≤ 10
2x
1 + 5x
2 + 3x
3 ≤ 15
-x
1 - 9x
2 + x
3 ≥ -4
3) Introducimos
variables de holgura para quitar las
desigualdades y transformarlas en igualdades:
3x
1 + 2x
2 + x
3 + x
4 = 10
2x
1 + 5x
2 + 3x
3 + x
5 = 15
-x
1 - 9x
2 + x
3 + x
6 = -4
x
1, x
2, x
3, x
4, x
5, x
6 ≥ 0
4) Y cambiamos de signo la última de las restricciones
3x
1 + 2x
2 + x
3 + x
4 = 10
2x
1 + 5x
2 + 3x
3 + x
5 = 15
x
1 + 9x
2 - x
3 - x
6 = 4
x
1, x
2, x
3, x
4, x
5, x
6 ≥ 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
3x
1 + 2x
2 + x
3 + x
4 + x
7 = 10
2x
1 + 5x
2 + 3x
3 + x
5 + + x
8 = 15
x
1 + 9x
2 - x
3 - x
6 + + x
9= 4
x
1, x
2, x
3, x
4, x
5, x
6, x
7, x
8, x
9 ≥ 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 (x
7 + x
8 + x
9)
Por tanto el Vector de Costes es
C
t = (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 S
0 tal que
x
7, x
8, x
9 = 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 S
0 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(-2x
1 - 3x
2 - 4x
3)
por tanto el vector de costes es ahora:
C
t = (-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.
