1. Ciencia

TEORÍA DE DUALIDAD
Definición Nº 1: La forma canónica de un P.P.L. de maximización es cuando todas sus
restricciones son menores e iguales.
Definición Nº 2: La forma canónica de un P.P.L. de minimización es cuando todas sus
restricciones son mayores e iguales.
DUALIDAD.
Para cada problema lineal, llamado Primal, existe otro problema lineal asociado que llamaremos
Dual.
Si el Primal es:
Máx Z = CX
s.a.
AX b
xi 0
El Dual es:
Min Z = bTY
s.a.
AT YCT
yi 0
PROPIEDADES DEL PRIMAL Y DEL DUAL.
1)
Si el Primal es un problema de Maximización (Minimización), el Dual es un problema
de Minimización (Maximización).
2)
Los valores de los recursos del Primal son los valores de los coeficientes de la función
objetivo del Dual. Y los valores de los coeficientes de la función objetivo del Primal
son los valores de los recursos del Dual.
3)
La matriz de los coeficientes tecnológicos del Dual es la matriz transpuesta de los
coeficientes tecnológicos del Primal. Y como (AT)T=A entonces el
Dual(Dual)=Primal.
4)
El número de restricciones del Primal es igual al número de variables de decisión del
Dual, es decir, por cada restricción del Primal existe una variable Dual asociada.
5)
El número de variables de decisión del Primal es igual al número de restricciones del
Dual, es decir, por cada variable del Primal existe una restricción asociada del Dual.
Investigación de Operaciones I
1
6)
Si una restricción del Primal esta en la forma canónica del problema, la variable Dual
asociada es no negativa y viceversa.
7)
Si una restricción del Primal no esta en la forma canónica del problema, la variable
Dual asociada es no positiva y viceversa.
8)
Si una restricción del Prima es una igualdad, la variable Dual asociada es sin
restricción de signo y viceversa.
TEOREMA FUNDAMENTAL DE DUALIDAD.
En un problema Primal y su Dual solo se cumple una de las siguientes proposiciones:
a) Ambos problemas tienen solución óptima finita y se cumple que el valor óptimo de la
función objetivo del Primal es igual al valor óptimo de la función objetivo del Dual.
b) Uno de los problemas es No Acotado y el otro es No Factible.
c) Ambos son No Factible.
TEOREMA DEBIL DE LA HOLGURA COMPLEMENTARIA.
Si una restricción tiene holgura no nula en la solución óptima, entonces la variable dual
asociada a esa restricción es nula y viceversa.
Si una restricción tiene holgura nula en la solución óptima, entonces la variable dual asociada
a esa restricción no es nula y viceversa si no tiene solución degenerada.
INTERPRETACIÓN ECONOMICA DE LAS VARIABLES DEL DUAL.
Considérese el siguiente problema lineal y su dual:
Si el Primal es:
Máx Z=CX
s.a.
AX b
xi 0
El Dual es:
Min Z=bTY
s.a.
T
A YCT
yi 0
Si B es la base óptima para el problema primal y CB es el vector de valores de los coeficientes de
las variables básicas en la función objetivo, se sabe entonces que:
Z*=CBB-1b=bTY* de lo cual se sigue que:
Investigación de Operaciones I
Z
*
b
 CBB-1=Y*
2
Por lo tanto, (yi)* es la rapidez de cambio del valor objetivo óptimo con un incremento unitario en
el i-ésimo valor del lado derecho de los recursos del primal.
Económicamente significa que cada incremento en una unidad de un recurso genera un
incremento en el valor de la función objetivo igual al valor de la variable dual de esa restricción,
por lo tanto el costo que genera el incremento en el recurso por una unidad no debe ser mayor al
valor del dual; conocido también como precio sombra.
INTERPRETACIÓN DEL PLANTEMIENTO.
EJEMPLO PRIMAL:
Una granja utiliza dos preparados alimenticios (P1 y P2) para la cría del ganado. El costo por
kilogramo de esos dos preparados es de 2 unidades monetarias y 3 unidades monetarias. Por otra
parte, los aportes vitamínicos de cada kilo de los preparados se expresan el la siguiente tabla:
Unidades de Vitamina A
Unidades de Vitamina B
Unidades de Vitamina C
Kg P1
5
1,5
1
Kg P2
3
3
1,5
Los expertos en nutrición animal recomiendan que cada animal reciba al menos las siguientes
unidades diarias de cada una de las vitaminas:
Unidades diarias de Vitamina A 27
Unidades diarias de Vitamina B 15
Unidades diarias de Vitamina C 9
El objetivo de los responsables de la granja es decidir las cantidades diarias de cada uno de los
dos preparados que deben suministrarse a cada animal, de forma que, por un lado se cumplan las
recomendaciones de los dietistas, y por otro se minimicen los costos de alimentación del ganado.
El Planteamiento del modelo es:
x1, x2 representan las cantidades diarias, en kilos, suministradas a cada animal de los preparados
P1, P2 respectivamente.
Min Z= 2x1+3x2 (costos en unidades monetarias por animal y día)
s.a.
5x1+3x2  27 (mínima cantidad unidades de vitamina A)
1,5x1+3x2  15 (mínima cantidad unidades de vitamina B)
1x1+1,5x2  9 (mínima cantidad unidades de vitamina C)
x1, x2  0
Luego el mínimo se alcanza en:
Investigación de Operaciones I
3
x1= 3 ( 3 kg. del preparado P1) x2= 4 ( 4 kg. del preparado P2)
Z= 18 ( 18 unidades monetarias por animal y día)
EL DUAL SERA:
Piénsese ahora en una empresa de productos alimenticios para ganado, que desea suministrar a la
granja del ejemplo anterior tres tipos de pastillas vitamínicas. Esta empresa debe convencer a los
responsables de la granja para que aporten las vitaminas que el ganado necesita mediante sus
pastillas, y no mediante los preparados que hasta ahora utilizaban. Para ello el precio de venta de
las pastillas debe resultar competitivo con respecto a los preparados P1, P2.
Sean y1, y2 y y3 los precios por unidad de las vitaminas A, B y C respectivamente. El objetivo de
la empresa es fijar unos precios que consigan maximizar sus beneficios pero que además resulten
atractivo para los responsables de la granja.
a) Cada kilogramo del preparado P1 aporta 5 unidades de vitamina A, 1.5 unidades de
vitamina B y 1 unidad de vitamina C. El precio que debería pagar la granja por conseguir
esas mismas cantidades de vitaminas en pastillas sería: 5y1+1,5y2+1y3. A la granja no le
resultarían rentables las pastillas a no ser que 5y1+1,5y2+1y3  2.
b) Cada kilogramo del preparado P2 aporta 3 unidades de vitamina A, 3 unidades de
vitamina B y 1,5 unidades de vitamina C. El precio que debería pagar la granja por
conseguir esas mismas cantidades de vitaminas en pastillas sería: 3y1+3y2+1,5y3. A la
granja no le resultarían rentables las pastillas a no ser que 3y1+3y2+1,5y3  3.
c) Por supuesto, los precios de las pastillas vitamínicas deben ser positivos, por tanto se
tienen además las condiciones de no negatividad de y1, y2 y y3.
Suponiendo que la granja se decida por utilizar las pastillas, comprarán justamente las necesarias
para aportar las necesidades mínimas del ganado de cada una de las vitaminas. Es decir, por cada
animal y día se comprarían 27 unidades de vitamina A, 15 de vitamina B y 9 de vitamina C. Por
tanto los ingresos de la empresa por la venta de las pastillas serían de Z = 27y1+15y2+9y3 por
animal y día.
Para establecer los precios, la empresa debería plantearse el programa lineal:
Máx Z=27y1+15y2+9y3
s.a.
5y1+1,5y2+1y3  2
3y1+3y2+1,5y3  3
y1,y2,y3  0
La solución de dicho problema se alcanza cuando:
y1= 0 y2= 0 y y3= 2 Z = 18
Observemos como dos de los precios han resultado ser nulos. Esto significa que la granja con los
preparados P1 y P2 solo debe preocuparse de aportar al ganado las unidades necesarias de
Investigación de Operaciones I
4
vitamina C, ya que con ello conseguirían también los aportes necesarios de vitamina A y B. Es la
razón por la cual la granja no necesita comprar unidades adicionales de vitamina A y B.
Además aumentarle una unidad más al mínimo de la vitamina C en el requerimiento alimenticio
representa un aumento marginal de 2 unidades monetarias en la función objetivo del primal.
Investigación de Operaciones I
5