Ejemplo de programación lineal

Ejemplo completo del método de las dos fases

Considerar el siguiente problema de programación lineal:
Maximizar (2x1 + 3x2 + 4 x3)
Sujeto a
3x1 + 2x2 + x3 ≤ 10
2x1 + 3x2 + 3 x3 ≤ 15
x1 + x2 - x3 ≥ 4
x1, x2, x3 ≥ 0
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
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
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
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

Fase 1

Base
x4
x5
x7
Xb
10
15
4
Cb
0
0
-1
0000001
3211000
2330100
11-100-11
-1-110010

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
0001101
12/31/31/3000
05/37/3-2/3100
01/3-4/3-1/30-11
0-1/34/31/3010

Siguiente iteración

Base
x1
x5
x2
Xb
2
5
2
Cb
0
0
0
0000001
103102-2
009115-5
01-4-10-33
000 000 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 000
103 10 2
009 1 15
01-4 -10-3
00-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 000
1002/3 -1/3 1/3
0011/9 1/95/9
010 1/910/95/9
0001/910/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
Update cookies preferences