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étodo simplex no es inmediata o más bien
compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.
Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetivo de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.
Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetivo de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.
Ejemplo Simplex Dual
Considere el siguiente modelo de Programación Lineal:
Considere el siguiente modelo de Programación Lineal:
Paso 1: Se lleva el modelo a su forma
estándar. En nuestro ejemplo esto se logra agregando variables de exceso en
cada una de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego,
se multiplica cada fila de las restricciones por -1 de modo de disponer una
solución básica inicial (infactible) en las variables de exceso S1, S2 y S3. De
esta forma se obtiene la siguiente tabla inicial.
|
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
"más negativo" lo cual indicará cuál de las actuales variables
básicas deberá abandonar la base. En el ejemplo el lado derecho más negativo se
encuentra en la primera fila, por tanto S1 deja la base. Para determinar cual
de las actuales variables no básicas (A, B, C) entrará a la base se busca el
mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no
básica en la fija i (del lado derecho más negativo, marcado en verde) y donde
Yj es el costo reducido de la respectiva variable no básica. De esta forma se
obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en
rojo) se encuentra al hacer el primer cuociente, 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 se debe 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 se obtiene 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 (marcado en verde) con valor
óptimo V(P)=6.620(marcado en rojo - se obtiene con signo cambiado).
También es interesante notar que los costos reducidos de las variables
artificiales S1, S2 y S3 (marcado en amarillo), corresponde a la solución
óptima del modelo presentado en el tutorial de solver, esto dado que dicho modelo resulta ser elproblema dual de nuestro ejemplo.
OTRA MANERA
DE VER EL METODO SIMPLEX DUAL:
Aprovechando las propiedades de
los problemas asociados primal y dual, se desarrolló el método dual-simplex que
se aplica: en algunos casos de análisis de sensibilidad, como ocurre en cambios
de los recursos del problema; también para resolver problemas de objetivo
mínimo y al menos una restricción de tipo >=, o para ahorro en cálculos
evitando los métodos simplex penal y dos fases. Se aplica cuando el problema
cambia a no factible, pero el renglón Z se presenta óptimo. Ahora observe y
compare la aplicación (
) de criterios del simplex en
coeficientes del modelo de PL resumido, a los problemas primal y dual.
) de criterios del simplex en
coeficientes del modelo de PL resumido, a los problemas primal y dual.
Figura 3-1. Criterios
del simplex en coeficientes del modelo de PL resumido, a los problemas primal y
dual.
Enseguida se presenta una
comparación funcional del simplex y el dual simplex.
Figura 3-2.
Comparación funcional del simplex y el dual simplex.
-Criterios
del método dual-simplex para el cambio de base.
En el algoritmo dual-simplex
aplican los siguientes criterios para cambio de base:
Criterio
de factibilidad.- Se
aplica en el dual-simplex para determinar, entre las variables básicas, una VS que salga de
la base, eligiendo para salir la que corresponda al valor más negativo en la
columna de solución. Esto es válido tanto para el objetivo mínimo como para el
máximo.
Criterio
de optimalidad.- Se
aplica en el dual-simplex para determinar, entre las variables no básicas, una VE que entre a
la base con el siguiente procedimiento:
Figura 3-3. Criterio
de Optimalidad en el método dual-simplex.
Elemento
Pivote.- Se ubica como pivote al coeficiente que corresponde al
cruce del renglón y columna elegidos con los criterios del cambio de base.
Ejemplo 3-1. Aplica
dual simplex a un PL con 4 restricciones >= (DUX1).
PASOS:
1) Consiga infactibilidad en restricciones tipo >=,
(multiplique por -1):
2) Arregle la función Z; consiga la matriz I de base,
sume holguras Hi, como sigue:
3) Tabule coeficientes y aplique el dual-simplex;
elija variables VS, VE y pivote así:
Figura
3-4. Tablas del Dual-simplex aplicado al ejemplo DUX1.
PASOS:
1) Consiga infactibilidad, multiplique por (-1) en
restricción tipo >= como sigue:
2) Arregle el objetivo Z; consiga la solución básica
(sume holguras Hi), como sigue:
3) Construya la tabla y aplique el algoritmo dual
simplex:
Figura
3-5. Tablas del Dual-simplex aplicado en ejemplo DUX2.
