Sistema Dual, investigación de operaciones
El método simplex dual resulta ser una estrategia algoritmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del métodosimplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.
Considere el siguiente modelo de Programación Lineal:
Paso 1: Se lleva el modeloa su forma estándar. En nuestro ejemplo esto se logra agregando variables de holgura en cada una de las restricciones. Luego, se multiplica cada fila de las restricciones por -1 teniendo comoresultado la siguiente tabla.
A
B
C
S1
S2
S3
-15
-2
-1
1
0
0
-200
-7,5
-3
-1
0
1
0
-150
-5
-2
-1
0
0
1
-120
315
110
50
0
0
0
0
Paso 2: Se selecciona el lado derecho masnegativo para indicar cual será la fila pivote y buscar la variable saliente. Para determinar cual de las variables entrará se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectivavariable no básica en la fija i (del lado derecho más negativo) y donde Yj es el costo reducido de la respectiva variable. De esta forma se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde elpivote se encuentra al hacer el primer cociente, por tanto A entra a la base.
Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado en el Método Simplex. En el ejemplo sedebe dejar a la variable A como básica y S1 como no básica. La tabla que resulta es la siguiente:
A
B
C
S1
S2
S3
1
2/15
1/15
-1/15
0
0
40/3
0
-2
-1/2
-1/2
1
0
-50
0
-4/3
-2/3-1/3
0
1
-160/3
0
68
29
21
0
0
-4.200
Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta disponer de una solución básica factible. Luego de unas iteraciones seobtiene la siguiente tabla final:
A
B
C
S1
S2
S3
1
0
0
-1/10
0
1/10
8
0
1
0
1/4
-1
3/4
10
0
0
1
0
2
-3
60
0
0
0
4
10
36
-6.620
La solución óptima es A=8, B=10, C=60...
Regístrate para leer el documento completo.