Metodo Simplex Dual

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.

Ejemplo Simplex Dual
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.

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 H_i, 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.

Ejemplo 3-2. Aplica dual-simplex a un PL con 2 restricciones >= y 1 restricción <= (DUX2).

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 H_i), como sigue:

3) Construya la tabla y aplique el algoritmo dual simplex:

Figura 3-5. Tablas del Dual-simplex aplicado en ejemplo DUX2.