DUALIDAD: PLANTEAMIENTO DEL PROBLEMA DUAL.

Existe un principio fundamental llamado dualidad, que permite resolver un problema de maximización, al resolver el problema de
minimización relacionado.
Suponga que una compañía fabrica dos tipos de podadoras, manuales y eléctricas, y cada una requiere del uso de las máquinas A
y B para su producción. Una podadora manual requiere del uso de A durante 1 hora y de B durante otra hora. Las eléctricas requieren
de A durante 2 horas y de B durante 4 horas. Los números máximos de horas disponibles por mes para las máquinas A y B, son 120
y 180, respectivamente. La utilidad por una podadora manual es de $10 y por una eléctrica es de $24. Suponga que la compañía
puede vender todos los artículos que produce, determine la utilidad mensual máxima.

Máquina A Máquina B Utilidad/unidad

Manual 1h 1h $10
Eléctrico 2h 4h $24
Horas disponibles 120h 180h

Las variables de decisión son:

𝑥1 : Cantidad de podadoras manuales a fabricarse.
𝑥2 : Cantidad de podadoras eléctricas a fabricarse.
Nuestro modelo matemático asociado al problema es:
𝑍 = 10𝑥1 + 24𝑥2
Sujeta a
𝑥1 + 2𝑥2 ≤ 120
x1 + 4x2 ≤ 180
x1 , x2 ≥ 0
El primer paso es transformar las desigualdades en ecuaciones agregando variables de holgura:

𝑥1 + 2𝑥2 + 𝑠1 = 120
x1 + 4x2 + 𝑠2 = 180
−10𝑥1 − 24𝑥2 + 𝑍 = 0
𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 ≥ 0
𝑥1 + 2𝑥2 , es el número de horas que se utiliza la máquina A, 𝑠1 representa para A el número de horas no usadas.
x1 + 4x2 es el número de horas que se utiliza la máquina B, 𝑠2 representa para B el número de horas no usadas.

TABLA SIMPLEX I
𝑥1 𝑥2 𝑠1 𝑠2 Z B
𝑠1 1 2 1 0 0 120
𝑠2 1 4 0 1 0 180
Z -10 -24 0 0 1 0
El primer paso los indicadores y señalar la columna del indicador más negativo:

𝑥1 𝑥2 𝑠1 𝑠2 Z B
𝑠1 1 2 1 0 0 120 120꞉2=60

𝑠2 1 4 0 1 0 180 180꞉4=45
Z -10 -24 0 0 1 0

INDICADORESS
𝑥1 𝑥2 𝑠1 𝑠2 Z B
𝑠1 1 2 1 0 0 120
𝒙𝟐 1/4 1 0 ¼ 0 45
Z -10 -24 0 0 1 0

TABLA SIMPLEX II

𝑥1 𝑥2 𝑠1 𝑠2 Z B
𝑠1 1/2 0 1 -1/2 0 30
𝑥2 1/4 1 0 ¼ 0 45
Z -4 0 0 6 1 1080
 -2F2+F1

24F2+F3

𝑥1 𝑥2 𝑠1 𝑠2 Z B
30꞉1/2=60
𝑠1 1/2 0 1 -1/2 0 30
𝑥2 1/4 1 0 1/4 0 45 45꞉1/4=180
Z -4 0 0 6 1 1080

TABLA SIMPLEX III

𝑥1 𝑥2 𝑠1 𝑠2 Z B
𝒙𝟏 1 0 2 -1 0 60
-1/4F1+F2 𝑥2 0 1 -1/2 1/2 0 30
4F1+F3 Z 0 0 8 2 1 1320

Como todos los indicadores son no negativos, el método simplex finaliza.

La utilidad máxima es de 1320, cuando se fabrican 60 podadoras manuales y 30 eléctricas.

Ahora se verá la situación desde un punto de vista diferente. Suponga que la compañía desea rentar sus máquinas A y B. ¿Cuál es
la renta mensual mínima que debe cobrar? Ciertamente, si el cobro es muy alto, nadie le rentaría las máquinas. Por otra parte, si el
cobro es muy bajo, no le convendría rentarlas en absoluto, pues perdería. Es obvio que la renta mínima debe ser de $1320. Es decir,
el mínimo que la compañía debe cobrar es la utilidad que podría tener si ella misma utilizara las máquinas. Podemos llegar a este
costo de renta mínimo de manera directa, al resolver un problema de programación lineal.

Máquina A Máquina B Utilidad/unidad

Manual 1h 1h $10
Eléctrico 2h 4h $24
Horas disponibles 120h 180h

Sea F el costo de la renta mensual. Para determinar F, se supone que la compañía asigna valores monetarios a cada hora de
capacidad en las máquinas A y B. Sean estos valores 𝑦1 y 𝑦2 dólares, respectivamente, donde 𝑦1 , 𝑦2 ≥ 0. Entonces el valor
mensual de la máquina A es 120𝑦1 y para la B es 180𝑦2 . Por lo tanto, 𝐹 = 120𝑦1 + 180𝑦2 .
El valor total del tiempo de máquina para producir una podadora manual es 1𝑦1 + 1𝑦2 Esto debe ser al menos igual a los $10 de
utilidad que la compañía puede recibir por producir dicho artículo. De lo contrario, la compañía ganaría más dinero si destina el
tiempo de la máquina a producir una podadora manual. De acuerdo con esto, 1𝑦1 + 1𝑦2 ≥ 10; Del mismo modo, el valor total del
tiempo de máquina para producir una podadora eléctrica debe ser al menos de $24: 2𝑦1 + 4𝑦2 ≥ 24.
Por tanto, la compañía necesita
Minimizar 𝐹 = 120𝑦1 + 180𝑦2
Sujeta a:
1𝑦1 + 1𝑦2 ≥ 10
2𝑦1 + 4𝑦2 ≥ 24
𝑦1 , 𝑦2 ≥ 0
Para minimizar F, se maximiza –F. Como las restricciones son de forma ≥, debemos utilizar variables de holgura y variables
artificiales. La función objetivo se transforma en una función objetivo artificial:

Maximizar −𝐹 = −120𝑦1 − 180𝑦2 → 𝑊 = −120𝑦 − 180𝑦 1 2 − 𝑀𝑡1 − 𝑀𝑡2

Sujeta a:
1𝑦1 + 1𝑦2 − 𝑟1 + 𝑡1 = 10
2𝑦1 + 4𝑦2 − 𝑟2 + 𝑡2 = 24
𝑦1 , 𝑦2 , 𝑟1 , 𝑟2 , 𝑡1 , 𝑡2 ≥ 0

120𝑦1 + 180𝑦2 + 𝑀𝑡1 + 𝑀𝑡2 + 𝑊 = 0

TABLA SIMPLEX INICIAL

𝑦1 𝑦2 𝑟1 𝑟2 𝑡1 𝑡2 W B
𝑡1 1 1 -1 0 1 0 0 10
𝑡2 2 4 0 -1 0 1 0 24
W 120 180 0 0 M M 1 0

TABLA SIMPLEX INICIAL

 𝑦1 𝑦2 𝑟1 𝑟2 𝑡1 𝑡2 W B
𝑡1 1 1 -1 0 1 0 0 10
𝑡2 2 4 0 -1 0 1 0 24
W -M+120 -M+180 -M 0 0 M 1 -10M

TABLA SIMPLEX I
𝑦1 𝑦2 𝑟1 𝑟2 𝑡1 𝑡2 W B
𝑡 1 1 -1 0 1 0 0 10
𝑡2 2 4 0 -1 0 1 0 24
W -3M+120 -5M+180 -M M 0 0 1 -34M

TABLA SIMPLEX I
𝑦1 𝑦2 𝑟1 𝑟2 𝑡1 𝑡2 W B
𝑡1 1/2 0 -1 1/4 1 -1/4 0 4
𝑦2 1/2 1 0 -1/4 0 1/4 0 6
W -3M+120 -5M+180 -M M 0 0 1 -
34
M

TABLA SIMPLEX FINAL

𝑦1 𝑦2 𝑟1 𝑟2 -F B
𝑦1 1 0 -2 1/2 0 8
𝑦2 0 1 1 -1/2 0 2
-F 0 0 60 30 1 -1320

El valor Como el valor máximo de -F es -1320, el valor mínimo de F es -(-1320) = $1320. Esto ocurre cuando
𝑦1 = 8 y 𝑦2 = 2. Por lo tanto, se ha determinado el valor óptimo de un problema de programación lineal (maximización de utilidad),
al encontrar el valor óptimo de otro problema de programación lineal (minimización del costo de la renta). Los valores 𝑦1 = 8 y 𝑦2 = 2
podrían haberse anticipado a partir de la tabla final del problema de maximización. En la tabla final del problema de maximización
inicial el indicador 8 en la columna 𝑠1 significa que en el nivel óptimo de producción, si 𝑠1 aumenta una unidad, entonces la utilidad
disminuye en 8. Esto es, 1 hora de capacidad sin uso de A disminuye la utilidad máxima en $8. Entonces, una hora de capacidad de
A tiene un valor monetario de $8. Se dice que el precio sombra de 1 hora de capacidad de A es de $8. Ahora, recuerde que 𝑦1 en
el problema de la renta es el valor de 1 hora de capacidad de A. Así, 𝑦1 debe ser igual a 8 en la solución óptima para ese problema.
De manera similar, como el indicador en la columna 𝑠2 es 2, el precio sombra de 1 hora de capacidad de B es de $2, que es el valor
de 𝑦2 en la solución óptima del problema de la renta.
Analizando la estructura de los dos problemas de programación lineal tenemos:

PRIMAL DUAL
Maximizar (1) Minimizar (2)
𝑍 = 10𝑥1 + 24𝑥2 𝐹 = 120𝑦1 + 180𝑦2
Sujeta a Sujeta a
𝑥1 + 2𝑥2 ≤ 120 1𝑦1 + 1𝑦2 ≥ 10
x1 + 4x2 ≤ 180 2𝑦1 + 4𝑦2 ≥ 24
x1 , x2 ≥ 0 𝑦1 , 𝑦2 ≥ 0

Se observa que para el problema de maximización (1) todas las desigualdades son ≤, en cambio, en el problema de minimización
(2) son todas de ≥. Los coeficientes de la función objetivo del problema (1) son los términos constantes en (2). Los términos
constantes en (1) son los coeficientes de la función objetivo del problema (2). Los coeficientes de 𝑦1 en (2) son los coeficientes de
𝑥1 𝑦 𝑥2 en la primera restricción de (1); los coeficientes de 𝑦2 en (2), son los coeficientes de 𝑥1 𝑦 𝑥2 en la segunda restricción de (1).
El problema de minimización es llamado el dual del problema de maximización y viceversa. En general, es posible asociar cualquier
problema de programación lineal con otro problema de programación lineal llamado su dual. El problema dado se llama primal. Si
el primal es un problema de maximización, entonces su dual es de minimización. De manera similar, si el problema primal implica
minimización, su dual implica maximización.
En general se tiene:

PRIMAL (3) DUAL (4)

Maximizar Minimizar

𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 𝑅 = 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚
Sujeta a Sujeta a
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 𝑐1

𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2 𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≥ 𝑐2

. . . . . . . .
. . . . . . . .
. . . . . . . .

𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚 𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚 ≥ 𝑐𝑛

𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0 𝑦1 , 𝑦2 , … , 𝑦𝑚 ≥ 0
No existe restricciones sobre los valores de b No existe restricciones sobre los valores de c

RELACIÓN EXISTENTE ENTRE EL PROBLEMA DUAL –PRIMAL Y VICEVERSA.

Si una restricción de desigualdad incluye ≥ al multiplicar ambos lados por -1 se obtiene una desigualdad que incluye ≤. Si una
restricción es una igualdad, puede rescribirse en términos de dos desigualdades: una que involucre ≥ y otra que involucre ≤.

Ahora se comparará el primal y su dual en las tablas (3) y (4). Se observa que si todas las restricciones del problema primal involucran
≤ (≥) (sin incluir las condiciones de no negatividad), entonces todas las restricciones en su dual implican ≥ (≤). Los coeficientes en
la función objetivo del dual son los términos constantes en las restricciones del primal. De manera similar, los términos constantes
en las restricciones del dual son los coeficientes de la función objetivo del primal. La matriz de coeficientes de los lados izquierdos
de las restricciones del dual, es la transpuesta de la matriz de coeficientes de los lados izquierdos de las restricciones del primal.
Esto es,
T
𝑎11 𝑎12 … 𝑎1𝑛 𝑎11 𝑎21 … 𝑎𝑚1

𝑎21 𝑎22 … 𝑎2𝑛 𝑎12 𝑎22 … 𝑎𝑚2

. . . . . .
. . . . . .
. . . . . .

𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑥𝑛 𝑎1𝑛 𝑎2𝑛 … 𝑎𝑚𝑛

Si el primal involucra n variables de decisión y m variables de holgura, entonces el dual involucra m variables de decisión y n variables
de holgura. Debe notarse que el dual del dual es el primal. Existe una relación importante entre el primal y el dual:
Si el primal tiene una solución óptima, también la tiene el dual, y el valor óptimo de la función objetivo del primal es el mismo que el
del dual. Además, suponga que la función objetivo del primal es 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 . Entonces, si 𝑠1 es la variable de holgura
asociada con la í-esima restricción en el dual, entonces el indicador de la columna 𝑠𝑖 de la tabla simplex final del dual es el valor de
𝑥𝑖 en la solución óptima del primal. Por eso es posible resolver el problema primal con sólo resolver el dual. En ocasiones, esto es
más conveniente que resolver directamente el primal. La relación entre el primal y el dual, se puede expresar mediante notación
matricial. Sean:


𝑥1

C= 𝑐1 𝑐2 … 𝑐𝑛 𝑥2
X =
 .
.
.

𝑥𝑛

entonces la función objetivo del problema primal puede escribirse como 𝑍 = 𝑪𝑿

Además, si se escribe

𝑎11 𝑎12 … 𝑎1𝑛 𝑏1

𝑎21 𝑎22 … 𝑎2𝑛 𝑏2

A= . . . Y B= .
. . . .
. . . .

𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑥𝑛 𝑏𝑚

entonces el sistema de restricciones para el problema primal se transforma en

𝑨𝑿 ≤ 𝑩 y 𝑿 ≥ 𝟎
𝑏1
𝑏2

Ahora sea: Y= .
.
.
𝑏𝑚

En forma matricial tenemos 𝑾 = 𝑩𝑻 𝒀 y su sistema de restricciones es 𝑨𝑻 𝒀 ≥ 𝑪𝑻 y 𝒀 ≥ 𝟎

Ejemplo 1:
Encuentre el dual de
PRIMAL
Maximizar
𝑍 = 3𝑥1 + 4𝑥2 + 2𝑥3
Sujeta a
𝑥1 + 2𝑥2 + 0𝑥3 ≤ 10
2𝑥1 + 2𝑥2 + 𝑥3 ≤ 10
x1 , x2 , 𝑥3 ≥ 0

DUAL
Minimizar (2)
𝐹 = 10𝑦1 + 10𝑦2
Sujeta a
𝑦1 + 2𝑦2 ≥ 3
2𝑦1 + 2𝑦2 ≥ 4
0𝑦1 + 𝑦2 ≥ 2
𝑦1 , 𝑦2 ≥ 0

EJEMPLO 2

PRIMAL
Minimizar
𝑍 = 4𝑥1 + 3𝑥2
Sujeta a
3𝑥1 − 𝑥2 ≥ 2
𝑥1 + 𝑥2 ≤ 1
−4𝑥1 + 𝑥2 ≤ 3
x1 , x2 ≥ 0
Minimizar
𝑍 = 4𝑥1 + 3𝑥2
Sujeta a
3𝑥1 − 𝑥2 ≥ 2
−𝑥1 − 𝑥2 ≥ −1
4𝑥1 − 𝑥2 ≥ −3
x1 , x2 ≥ 0

DUAL
Maximizar (2)
𝐹 = 2𝑦1 − 𝑦2 − 3𝑦3
Sujeta a
3𝑦1 − 𝑦2 + 4𝑦3 ≤ 4
−𝑦1 − 𝑦2 − 𝑦3 ≤ 3
𝑦1 , 𝑦2 , 𝑦3 ≥ 0