Ingeniero

OBTENCIÓN DEL MODELO DUAL

Vamos a derivar una regla general para construir el modelo dual de cualquier modelo de programación lineal. Veremos como es posible obtener directamente el modelo dual de cualquier modelo sin efectuar una transformación similar a la que hicimos para los dos problemas presentados.

EL DUAL CUANDO EL PRIMO ESTA EN FORMATO CANÓNICO

Hasta el momento hemos evaluadodos modelos primos en formato canónico, y en el análisis de las relaciones entre ambos modelos y sus correspondientes modelos duales, comentábamos varios detalles, que ahora podemos generalizar en las siguientes reglas

1. Sí un modelo esta en formato canónico, su modelo dual también estará en formato canónico pero con objetivo opuesto al del modelo primo.

Recordemos que si el objetivode un modelo es maximizar, estará en formato canónico cuando todas sus restricciones sean del tipo ≤ y todas sus variables no negativas; y por lo tanto el dual también tendrá formato canónico, siendo su objetivo minimizar, todas sus restricciones del tipo ≥ y todas las variables igualmente mayores o iguales que cero.

2. El vector de coeficientes objetivo de un modelo es la transpuestadel vector de coeficientes recurso del otro y viceversa.

3. La matriz de coeficientes tecnológicos de un problema es la transpuesta de la matriz de coeficientes tecnológicos del otro.

Es decir, si el primo es un modelo como el siguiente

Maximizar Z = CX

sujeta a AX ≤ b

con X ≥ 0


Su dual es el modelo

Minimizar ZD= btY

Sujeta AtY ≥ Ct

con Y ≥ 0



De la misma manera, si el modelo primo es

Minimizar Z = CX

sujeta a AX ≥ b

con X ≥ 0


Su dual será el modelo

Maximizar ZD = btY

sujeta a AtY ≤ CtCon Y ≥ 0


EJEMPLO:

Ilustremos la deducción del dual a partir del primo en formato canónico, mediante el siguiente ejemplo:

Modelo primo

Maximizar Z = 4X1 + 6X2 + 2X3

Sujeta a 7X1 + 4X2 - 1X3 ≤ 27
3X1 + 5X2 + 6X3 ≤ 64con Xj ≥ 0; j = 1, 2, 3


Tenemos que C = 4 6 2 b = 27 64 t 7 4 -1
A =
3 5 6
Aplicando las reglas para este caso, obtenemos:

Modelo dual

Minimizar: ZD = 27Y1 + 64Y2

Sujeta a: 7Y1 + 3Y2 ≥ 44Y1 + 5Y2 ≥ 6
-Y1 + 6Y2 ≥ 2

con Yj ≥ 0, j = 1, 2
EL DUAL CUANDO EL PRIMO ESTA EN FORMATO ESTÁNDAR

Consideremos el siguiente modelo primo:

Minimizar: Z = 3X1 + 5X2 - 2X3

Sujeta a: 7X1 + 4X2 - 1X3 = 36 (P)
-4X1 + 6X2 + 2X3 = 85

con X1, X2, X3 ≥ 0

Parahallar su modelo dual podemos llevarlo a formato canónico y aprovechar las reglas expresadas en el caso anterior.

Utilizando las transformaciones aprendidas en el capítulo de Fundamentos Teóricos del método simplex, planteamos el modelo así:

Minimizar: Z = 3X1+ 5X2 - 2X3

Sujeta a: 7X1 + 4X2 - 1X3 36
7X1 + 4X2 - 1X3 36
-4X1+ 6X2 + 2X3 85
-4X1 + 6X2 + 2X3 85

con X1, X2 , X3 ≥ 0

Y para que tenga formato canónico, convertimos todas las desigualdades del tipo a sus equivalentes del tipo ≥, quedando:

Minimizar: Z = 3X1 + 5X2 - 2X3

Sujeta a: 7X1 + 4X2 - 1X3 36
-7X1 - 4X2 + 1X3 -36
-4X1 + 6X2 + 2X3 85
4X1 - 6X2 - 2X3...