Maximizar (2x1 + 3x2 + 4 x3)
Sujeto a
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
Sujeto a
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
Ejemplo de programación lineal
Ejemplo completo del método de las dos fases
Considerar el siguiente problema de programación lineal:
Lo primero que haremos, como ya hemos visto es cambiar el signo a la función objetivo para tener un problema de minimización, después ponemos las variables de holgura para transformar las desigualdades en igualdades x4, x5, x6
Minimizar (-2x1 - 3x2 - 4 x3)
Sujeto a
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5= 15
x1 + x2 - x3 - x6 = 4
xi ≥ 0, ∀ i=1,2, ..,6
Sujeto a
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5= 15
x1 + x2 - x3 - x6 = 4
xi ≥ 0, ∀ i=1,2, ..,6
Ahora, queremos tener una submatriz 3x3 de la matriz de restricciones. Con esta idea, introducimos las variables artificiales que necesitemos.
Es suficiente con usar una única variable para la tercera restricción, la llamamos x7.
El problema queda como sigue
El problema queda como sigue
Minimizar (-2x1 - 3x2 - 4 x3)
Subjeto a
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5 = 15
x1 + x2 - x3 - x6 + x7 = 4
xi ≥ 0, , ∀ i=1,2, ..,7
Subjeto a
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5 = 15
x1 + x2 - x3 - x6 + x7 = 4
xi ≥ 0, , ∀ i=1,2, ..,7
Muy bien, ahora sí, podemos identificar una submatriz 3x3 con la que podemos comenzar las iteraciones del método de las dos fases. La submatriz identidad es aquella formada por las columnas correspondientes a las variables x4, x5, x7, o sea, consideramos
Minimizar (-x7)
Subjeto a
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5 = 15
x1 + x2 - x3 - x6 + x7 = 4
xi ≥ 0, , ∀ i=1,2, ..,7
Subjeto a
3x1 + 2x2 + x3 + x4 = 10
2x1 + 3x2 + 3 x3 + x5 = 15
x1 + x2 - x3 - x6 + x7 = 4
xi ≥ 0, , ∀ i=1,2, ..,7
Fase 1
| Base |
| x4 |
| x5 |
| x7 |
| Xb |
| 10 |
| 15 |
| 4 |
| Cb |
| 0 |
| 0 |
| -1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 3 | 2 | 1 | 1 | 0 | 0 | 0 |
| 2 | 3 | 3 | 0 | 1 | 0 | 0 |
| 1 | 1 | -1 | 0 | 0 | -1 | 1 |
| -1 | -1 | 1 | 0 | 0 | 1 | 0 |
El elemento pivote es 3 porque -1 es el mínimo de los negativos zj - cj, subindice es 1 así la variable entrante es x 1. También tenemos
10/3 = min (10/3, 15/2, 4/1), así, la variable que sale de la base es la que ocupa el primer lugar, es decir x4.
Así, los nombres que hemos usado en la teoria, tenemos k=1 y el índice i=1
y el elemento pivote está en el índice aik = a11
Hacemos una iteración del algoritmo del simplex de la manera siguiente:
1) Si la fila es la del elemento pivote, simplemente dividimos cada elemento por el elemento pivote (incluyendo el mismo)
2) Para las otras filas operamos como hemos visto en la teoría: para el elemento anm restamos ani lo multiplicamos por anj y dividimos por el pivote, por ejemplo, p la segunda fila completa:
| 25/3 = 15-(2*10/3) |
| 0 = 2-(2*3/3) |
| 5/3 = 3-(2*2/3) |
| 7/3 = 3-(2*1/3) |
| -2/3 = 0 - (2*1/3) |
| 1 = 1 - (2*0/3) |
| 0 = 0 - (2*0/3) |
| 0 = 0 - (1*0/3) |
Como se ve los cálculos son más fáciles de entender y hacer que de explicar.
La tabla se transforma en
| Base |
| x1 |
| x5 |
| x7 |
| Xb |
| 10/3 |
| 25/3 |
| 2/3 |
| Cb |
| 0 |
| 0 |
| -1 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 2/3 | 1/3 | 1/3 | 0 | 0 | 0 |
| 0 | 5/3 | 7/3 | -2/3 | 1 | 0 | 0 |
| 0 | 1/3 | -4/3 | -1/3 | 0 | -1 | 1 |
| 0 | -1/3 | 4/3 | 1/3 | 0 | 1 | 0 |
Siguiente iteración
| Base |
| x1 |
| x5 |
| x2 |
| Xb |
| 2 |
| 5 |
| 2 |
| Cb |
| 0 |
| 0 |
| 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 3 | 1 | 0 | 2 | -2 |
| 0 | 0 | 9 | 1 | 1 | 5 | -5 |
| 0 | 1 | -4 | -1 | 0 | -3 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Así, hemos llegado al final de la primera fase con la solución x7=0 y el valor óptimo obtenido es el trivial. Ello quiere decir que podemos pasar a la segunda fase
Fase 2
Pasamos a la segunda fase, eliminamos las variables artificiales y reestablecemos la función original, o sea reconstruímos la tabla como sigue.
| Base |
| x1 |
| x3 |
| x2 |
| Xb |
| 1/3 |
| 5/9 |
| 38/9 |
| Cb |
| -2 |
| -4 |
| -3 |
| -2 | -3 | -4 | 0 | 0 | 0 |
| 1 | 0 | 3 | 1 | 0 | 2 |
| 0 | 0 | 9 | 1 | 1 | 5 |
| 0 | 1 | -4 | -1 | 0 | -3 |
| 0 | 0 | -10 | -1 | 0 | -5 |
Nueva iteración, ya en la fase 2.
| Base |
| x1 |
| x3 |
| x2 |
| Xb |
| 1/3 |
| 5/9 |
| 38/9 |
| Cb |
| -2 |
| -4 |
| -3 |
| -2 | -3 | -4 | 0 | 0 | 0 |
| 1 | 0 | 0 | 2/3 | -1/3 | 1/3 |
| 0 | 0 | 1 | 1/9 | 1/9 | 5/9 |
| 0 | 1 | 0 | 1/9 | 10/9 | 5/9 |
| 0 | 0 | 0 | 1/9 | 10/9 | 5/9 |
Así, hemos llegado al final de la fase 2 porque el criterio de optimalidad se verifica sin hacer ninguna otra itereración. Tenemos solución óptima finita en el punto extremo de coordenadas:
| x1 = 1/3 |
| x2 = 38/9 |
| x3 = 5/9 |
con el valor óptimo (recordar cambiar de nuevo la función objetivo original)
| 2 * 1/3 | + 3 * 38/9 | + 4 * 5/9 | = 140/9 |
Ejecuta este ejemplo aquí!
Ha sido util? Alguna idea para complementar el texto?
Deja tu post
Comentarios de otros usuarios
Deja tu post
