La dualidad puede definirse con el siguiente enunciado: Para todo problema de maximización de programación lineal, habrá otro problema asociado de minimización y, por otra parte, para todo problema de minimización, habrá otro problema asociado de maximización.

Al primer problema se le llama primario y al problema asociado correspondiente se le conoce como dual.

En este capítulo veremos cómo plantear un problema dual, dado un problema primario cualquiera.

La dualidad es importante por las siguientes razones:

1. El problema dual puede ahorrar un número considerable de cálculos, en particular cuando el problema primario tiene muchas restricciones y pocas variables, lo cual implicará un número elevado de cálculos para su resolución por el método Simplex.
2. La dualidad tiene una relación importante con el análisis de sensibilidad que se verá en el siguiente capítulo. Esto es muy útil para analizar cómo puede cambiar la función objetivo ante variaciones en las diferentes condiciones del problema de programación lineal.
3. El problema dual proporciona información importante sobre la manera óptima de aplicar recursos que son escasos a fin de obtener beneficios económicos.
    

El planteamiento del problema dual para un problema primario cualquiera puede hacerse basado en los siguientes puntos:

A continuación, ilustraremos los puntos anteriores con el ejemplo #1:

"Una panadería prepara 2 tipos de pan, uno con mermelada y el otro con cajeta." 

Hay mermelada para preparar hasta 5 kg. del primer tipo de pan y cajeta para 8 kg. del segundo tipo.

El primer tipo requiere para su preparación  2 unidades de harina, mientras que el segundo tipo solo de una. El expendio cuenta con un total de 15 unidades de harina.

El primer tipo de pan deja una utilidad de $ 3.00 /kg y el segundo tipo  $ 4.00 / kg.

¿Cuántos kilogramos de cada tipo debe preparar el expendio a fin de maximizar sus utilidades?

Plantear el problema primario y luego pasar  al dual teniendo en cuenta los pasos este caso.

 

Solución:

          Para el problema primario  existen 2 variables, X1 y X2, siendo

                              X₁  = Kgs de pan del primer tipo

                              X₂  = Kgs de pan del segundo tipo

                              Z_P   = Utilidad en $

          Entonces la función objetivo será:

Max   Z_P = 3X₁   + 4X₂

Aquí 3 y 4 son los coeficientes de la función objetivo, los cuales representan la utilidad de cada tipo de pan en $/kilogramo.

          Las restricciones son:

                    (1)     X₁<  5                              Cantidad disponible de mermelada

                    (2)     X₂ < 8                              Cantidad disponible de cajeta

                    (3)     2X₁ +  X₂  <  15               Cantidad disponible de harina

                    Siendo X₁, X₂                             No negativas

 

Para resolver el problema dual aplicaremos la metodología descrita antes. De acuerdo con el primer punto, el problema dual será de minimización, dado que el primario fue de maximización. Conforme al segundo punto, para el problema dual se tendrán restricciones del tipo mayor o igual que (>), dado que las del primario son del tipo menor o igual que (<).

Ahora pasaremos al punto 3, los coeficientes de la función objetivo del primario, que son 3 y 4 serán ahora las constantes de las restricciones del dual, teniendo este, por lo tanto, 2 restricciones. De acuerdo con el punto 4, las constantes de las restricciones del primario son 5, 8 y 15, por lo que estos serán los coeficientes de la función objetivo del problema dual, el cual tendrá 3 variables.

 

Ahora conforme al punto 5, los coeficientes de las restricciones para el primario son:

1	0
0	1
2	1

Los cuales deben transponerse  para el dual, es decir colocar los renglones como columnas, con esto tendremos:

1	0	2
0	1	1

Los cuales serán ahora los coeficientes de las 2 restricciones del dual. Finalmente, de acuerdo con el paso 6, habrá 3 variables para el problema dual, las cuales serán Y₁, Y₂ y Y₃.

Con esto el planteamiento del dual será:

                              Min    Z_D = 5 Y₁ + 8Y₂  + 15 Y₃

Con las restricciones:

                                   (1)        Y₁ + 2 Y₃  >  3

                                   (2)         Y₂  +  Y₃  > 4

                                 Siendo  Y₁, Y₂ y Y₃ >=0  No negativas

 

Aquí es importante señalar que las variables duales son costos marginales de los recursos utilizados, para el caso del ejemplo anterior tendremos:

                               Y₁ = Costo marginal de la mermelada, $/unidad de mermelada

                               Y₂ = Costo marginal de la cajeta, $/unidad de cajeta

                               Y₃ = Costo marginal de la harina, $/unidad de harina

El objetivo del problema dual es ahora el de minimizar el consumo de los recursos disponibles, es decir, la Z_D que es el costo por este concepto.

En este enlace presentaremos el ejemplo con la resolución de los problemas primario y dual.       Click aquí  

Pueden existir otros tipos de restricciones para un problema primario dado. En el ejemplo hemos planteado un problema primario de  maximización con restricciones del tipo menor o igual que (<), ¿Cómo se hubiera manejado el problema si contuviese restricciones del tipo mayor o igual que (>), o del tipo igual que (=)? En principio todas las restricciones de un problema primario de maximización deberán ser del tipo menor o igual que (<), por consiguiente, las restricciones distintas deberán convertirse a este tipo.

Para las restricciones del tipo mayor o igual que (>), lo que debe hacerse es multiplicar toda la desigualdad por (-1) e invertir su sentido, con esto la transformaremos al tipo menor o igual que (<).

Por su parte, para las restricciones de igualdad (=), esta restricción se cambia  por 2 nuevas restricciones: una del tipo menor o igual que (<) y la otra del tipo mayor o igual que (>), la cual debe convertirse a su vez al tipo menor o igual que (<) en la forma como se explicó anteriormente.

Ver desarrollo del Ejemplo #2       Click aquí  

En esta sección presentaremos algunas propiedades de la dualidad.

Principio de dualidad fuerte.

Si el problema primario tiene una solución óptima, entonces el problema dual también tendrá una solución óptima con idénticos valores para la función objetivo, es decir:

          Z_p = Z_D                           Ec. (2.1)

          Donde:    Z_p = Valor de la función objetivo para el problema primario.

                         Z_D = Valor de la función objetivo para el problema dual.

Este teorema ya se ha comprobado al resolver el ejemplo 2.2, ya que en este ejercicio Z_p fue igual a Z_D con un valor de 42.5 para la solución óptima.

Principio de dualidad débil

Para cualquier otra solución de un problema que no sea la óptima, se cumplirá que:

                                                Zp < ZD                             Ec. (2.2)

Donde el signo de desigualdad de menor que (<) aplica para aquellos casos en los cuales ambas soluciones del primario y del dual son factibles.

Por su parte, el signo de igualdad surtirá efecto cuando la solución del dual no sea factible por no cumplir con las restricciones.

Si aplicamos este principio al ejemplo 2, vemos que para la segunda tabla la solución primaria y dual son:

Aquí se observa la igualdad Z_p = Z_D para la ecuación (2.2), por lo que, conforme a lo establecido anteriormente, la solución dual no es factible, de esto nos damos cuenta al  revisar que el problema dual no cumple con su primera restricción la cual indica que Y₁+2Y₃ > 4, siendo que tanto Y₁ como Y₃ son cero, por lo cual  la solución dual no es factible.

Los problemas duales se clasifican en 2 grandes grupos: Simétricos y Asimétricos.

Los Simétricos son aquellos casos en los cuales tanto el problema primario como el dual incluyen restricciones de desigualdad (un problema de un tipo y el otro del tipo contrario). En el caso del ejemplo 2.1 el problema primario y el dual son simétricos, ya que el primario incluye restricciones del tipo menor o igual que (<), mientras que el dual contiene restricciones del tipo mayor o igual que (>).

Los problemas asimétricos por su parte, son aquellos en los cuales el primario contiene restricciones de igualdad, como el caso del ejemplo 2.3.

Propiedad  de Simetría. 

Para cualquier problema primario y su dual, las relaciones entre ellos son simétricas, ya que, si el segundo problema es el dual del primero, entonces el primer problema será a su vez el dual del segundo.

Esto es claro si nos remitimos al ejemplo 2.1 donde el problema de minimización fue el dual del de maximización, pero también este a su vez será el dual del primero.

Propiedades de Soluciones Complementarias. 

Para cada iteración, el método Simplex halla una solución factible en un vértice para el problema primario y una solución complementaria para el dual, en donde

Z_p = Z_D

Si dicha solución no es la óptima para el primario, entonces la solución dual no será factible.

Esta propiedad es equivalente al principio de dualidad débil.

Propiedad de Soluciones Complementarias Óptimas. 

Al encontrar una solución óptima, el método Simplex lo hace simultáneamente para los problemas primario y dual, entonces

Z_p = Z_D

Donde la solución dual es la solución óptima complementaria.

Debido a estas dos últimas propiedades, el método Simplex actúa sobre el problema primario como si lo hiciera  sobre el dual al mismo tiempo.

Propiedad de Holgura Complementaria. 

Una variable de holgura cualquiera que sea básica en el problema primario será no básica en el dual y viceversa, teniendo una relación simétrica entre ambas, de tal modo que las soluciones que las contienen son complementarias entre sí.

Esto lo podemos ilustrar si nos referimos al ejemplo 2.2, donde si observamos la segunda tabla, veremos que la solución básica del problema primario es:

S₁ = 5

X₂ = 8

S₃ = 7

Z_p = 32

De esta misma tabla al revisar los coeficientes índices de  las variables de holgura, vemos que son:

S₁ (Y₁) = 0

S₂ (Y₂) = 4

S₃ (Y₃) = 0

Si analizamos la situación de esta tabla respecto a esta propiedad, veremos que S₂ es la variable de holgura que no es básica en el problema primario y que sí lo es en el problema dual (valor diferente de cero); mientras que S₁ y S₃ son variables de holgura  básicas en el primario y  que corresponden a variables no básicas (valor cero) en el problema dual.

La interpretación de la solución dual nos proporciona una visión sobre la manera óptima de utilizar los recursos de que disponemos.

Estaríamos dispuestos a pagar un costo mayor por un recurso hasta por el valor de su variable dual correspondiente a la solución óptima.

Para ilustrar esto retomaremos el caso del expendio de pan donde para el caso de la cajeta, Y₂ fue en la tabla dual final 2.5, lo que significa que podríamos pagar hasta $ 2.5 adicionales como máximo por cada unidad extra de cajeta usada, dado que esta cantidad es la utilidad adicional que se obtendría por su empleo. 

Dado que los coeficientes del renglón índice de las variables de holgura de la tabla Simplex final del problema primario son los valores óptimos de las variables duales en el problema dual, lo que indica que la utilización óptima de los recursos disponibles nos lleva al mismo tiempo a lograr una utilidad máxima.  

Problemas propuestos       Click aquí