Nombre: MIGUEL CYBAK

Dirección: VALENCIA EDO. CARABOBO

CORREO: cybakmiguegmail.com

 

 

Teoria de la dualidad

Dualidad.

INTRODUCCION

Todo problema de Programación Lineal tiene asociado un segundo problema, conocido como su problema Dual. Ambos están relacionados estrechamente, hasta el punto de que el modelo de uno puede obtenerse a partir del modelo del otro y la solución óptima del modelo del primero proporciona información completa acerca de la solución óptima del segundo.

Una de las ventajas de la existencia del problema dual es la posibilidad de reducir el esfuerzo computacional al resolver ciertos modelos de Programación Lineal. Pero más importante aún es la relación que existe entre la dualidad y el análisis de sensibilidad, tema del próximo.

Dualidad

El concepto de dualidad desempeña importantes papeles dentro de la programación lineal (también en la no lineal), tanto desde un punto de vista teórico como práctico. Todo programa lineal lleva asociado otro programa lineal conocido como su programa dual; el programa inicial se conoce también como programa primal. Para comprender el concepto de dualidad y sus posibles interpretaciones, pueden analizarse los siguientes ejemplos.

 

Ejemplo primal:

Una granja utiliza dos preparados alimentícios (P1 y P2) para la cría del ganado. El coste por kilogramo de esos dos preparados es de 2 unidades monetarias y 3 unidades monetarias respectivamente. Por otra parte, los aportes vitamínicos de cada kilo de los preparados se expresan en la siguiente tabla:

 

Kg P1

Kg P2

Unidades de Vitamina A

5

3

Unidades de Vitamina B

1.5

3

Unidades de Vitamina C

1

1.3

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

20

Unidades diarias de Vitamina B

15

Unidades diarias de Vitamina C

8

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 minimizen los costes de alimentación del ganado. Dicho objetivo supone resolver el siguiente programa lineal:

min 2x1+3x2
5x1+3x2 >= 20
1.5x1+3x2 >= 15
x1+1.3x2 >= 8
x1,x2 >= 0

donde x1 y x2 representan las cantidades diarias, en kilos, suministradas a cada animal de los preparados P1 y P2 respectivamente.

El mínimo del problema anterior se alcanza sobre el punto:

x1 = 4.286 x2 = 2.857

siendo por tanto el coste mínimo de 17.143 unidades monetarias por animal y día.

 

Ejemplo dual:

Piénsese ahora en una empresa de productos alimentícios 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 y P2.

Sean z1, z2 y z3 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 atractivos para los responsables de la granja.

  • Cada kilogramo del preparado P1 aportaba 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: 5z1+1.5z2+z3. A la granja no le resultarían rentables las pastillas a no ser que 5z1+1.5z2+z3 <= 2
  • De la misma forma, otra restricción que debería plantearse la empresa es: 3z1+3z2+1.3z3 <= 2
  • Por supuesto, los precios de las pastillas vitamínicas deben ser positivos, por tanto se tienen además las restricciones z1,z2,z3 >= 0

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 20 unidades de vitamina A, 15 de vitamina B y 8 de vitamina C. Por tanto los ingresos de la empresa por la venta de las pastillas serían de

V(z1,z2,z3) = 20z1+15z2+8z3

por animal y día.

Para establecer los precios, la empresa debería plantearse el programa lineal

max 20z1+15z2+8z3
5z1+1.5z2+z3 <= 2
3z1+3z2+1.3z3 <= 3
z1,z2,z3 >= 0

La solución de dicho programa se alcanza sobre el punto

z1 = 0

z2 = 0.381

z3 = 1.428

siendo entonces el valor máximo V(0,0.381,1.428) = 17.143 unidades monetarias. Observar como uno de los precios ha resultado ser nulo. Esto significa que la granja con los preparados P1 y P2 solo debe preocuparse de aportar al ganado las unidades necesarias de vitaminas B y C, ya que con ello conseguiría también la aportación necesaria de vitamina A. Es la razón por la cual la granja no necesita comprar unidades adicionales de vitamina A.

 

En estos dos ejemplos se observa una relación interesante entre los problemas primal y dual. Como puede observarse:

  • Uno de ellos es de minimización, el otro en cambio es de maximización.
  • Los coeficientes en la función objetivo y los elementos de la derecha de las restricciones, intercambian su papel.
  • La matriz de coeficientes en las restricciones del problema dual es la traspuesta de la del problema primal.
  • Las restricciones del problema primal son de tipo >=, en cambio en el dual son de tipo <=.
  • Cada restricción en el problema primal se corresponde con una variable en el dual.
  • El punto óptimo del programa dual se corresponde con las variables duales (multiplicadores de Kuhn-Tucker) del programa primal.
  • Otro aspecto importante es que, aunque el punto óptimo es diferente, los valores óptimos de los dos problemas son los mismos.

La resolución del programa dual puede interpretarse como la asignación a cada recurso de un precio o valor, que coincide con el incremento que provoca en el valor óptimo del problema primal un aumento de una unidad en el recurso.

La construcción realizada en los ejemplos anteriores puede generalizarse para cualquier programa lineal:

 

Definición:

Dado un programa lineal de la forma

min cx
Ax >= b
x >= 0

su programa dual es

max b'z
A'z <= c'
z >= 0

Donde A', b' y c' son los traspuestos de A, b y c respectivamente. En esta definición no es necesario que todos los elementos del vector b sean mayores o iguales que cero.


Pero no solamente pueden construirse los programas duales para programas de la forma anterior; en general se puede para cualquier programa lineal (también hay una teoría de dualidad para programas no lineales), pero teniendo en cuenta lo siguiente:

  • Una restricción de igualdad en el programa primal hace que la correspondiente variable dual pueda tener cualquier signo.
  • En cambio, una restricción de desigualdad del tipo >= en el primal implica que la variable dual sea mayor o igual que cero.
  • Si las variables del primal son mayores o iguales que cero, las restricciones del dual son del tipo <=.
  • Cuando las variables del primal no están sometidas a ninguna limitación sobre su signo, las restricciones del dual son de igualdad.

 

Ejemplo:

 Programa primal

Programa dual

min x1+x2-x3
2x1+x2 >= 3
x1-x3 = 2
x3 >= 0
max 3z1+2z2
2z1+z2 = 1
z1 = 1
-z2 <= -1
z1 >= 0

 

La importancia del programa dual queda de manifiesto en el siguiente resultado.

Teorema fundamental de dualidad:

Dado un programa P y su dual D, se cumple necesariamente una de las siguientes afirmaciones:

  • Los dos programas tienen soluciones óptimas y los valores de sus respectivas funciones objetivo en el óptimo coinciden.
  • Uno de los programas tiene óptimo no acotado y el otro no tiene ninguna solución factible.
  • Los dos programas son infactibles (no tienen soluciones factibles).

 

A partir de este teorema se puede deducir el valor óptimo de un programa lineal, o si dicho programa es factible, analizando la forma de su programa dual. En algunos casos el estudio del programa dual puede resultar más sencillo que el del primal.