DUAL

CAPÍTULO 5

ANÁLISIS DE DUALIDAD Y SENSIBILIDAD DE LA PROGRAMACIÓN LINEAL

1. Introducción

La solución de la programación lineal se basa en una toma instantánea de las condiciones que prevalecen en el momento de formular y resolver el modelo. Pero se debe tener en cuenta que en el mundo real, los ambientes de decisiones rara vez permanecen estáticos, y es fundamental determinar como cambia la solución óptima cuando cambian los parámetros del modelo. Eso es lo que hace el análisis de sensibilidad.

1. Definición del problema dual

El problema dual es una programación lineal definida en forma directa y sistemática a partir del modelo original (o primal) de programación lineal. Los dos problemas están relacionados de forma tan estrecha que la resolución óptima de un problema produce de forma automática la resolución óptima del otro.

En la programación lineal, el dual se define para varias formas del primal, dependiendo del sentido de la optimización (maximización o minimización), tipos de restricciones (≤, ≥ o =), y la orientación de las variables (no negativa o no restringida).

Nuestra definición del problema dual requiere expresar el problema primal en forma de ecuaciones, todas las restricciones son ecuaciones, con lado derecho no negativo y todas las variables son no negativas.

Para mostrar como se forma el problema dual, se define el primal en forma de ecuaciones, como se muestra a continuación:

Maximizar o Minimizar[pic 1]

Sujeta a:

[pic 2]

Las variables xi,j =1,2,…..., n, incluyen las variables que se denominan de excedencia, holgura y artificiales, si las hubiera.

        La tabla 5.1 el cual muestra como convertir un problema dual a partir de un primal, lo que se tiene a continuación son las condiciones que requieren:

1. Se define una variable dual por cada ecuación primal (restricciones).
2. Se define una restricción dual por cada variable primal.
3. Los coeficientes de restricción (columna) de una variable primal definen los coeficientes en el lado izquierdo de la restricción dual, y su coeficientes objetivo define el lado derecho.
4. Los coeficientes objetivos del problema dual son iguales a lados derecho de las ecuaciones de restricción primal.

[pic 3]

Las reglas para determinar el sentido de la optimización (ya sea maximización o minimización), el tipo de restricción [pic 4], y el signo de las variables duales (siempre no restringido), esta en resumen en la tabla 5.2; obsérvese que el sentido de la optimización de problema dual siempre es el opuesto al del primal.

        En los siguientes ejemplos se demuestra el uso de la tabla 5.2 y también demuestra que la definición comprende todas las formas del primal, en forma automática.

Ejemplo de aplicación 5.1

Como se puede  observar en el ejemplo se debe tener en cuenta las 4 condiciones:

1. como se tiene dos restricciones se tiene dos variables duales ([pic 14]).
2. como se ve en la forma de ecuación el problema primal tiene cuatro variables ([pic 15]) por lo tanto

Se deberá tener 4 restricciones [pic 16]

1. como indica esta condición se ve claramente en este ejemplo que los coeficientes columna de las dos restricciones [pic 17] que corresponden a los coeficientes de cada variable, lo cual se observa de la variable x1 son 1 y 10, de la variable x2 son 2 y 5, así sucesivamente son utilizadas en el lado izquierdo de las restricciones como se ve:

[pic 18]

También se indica que los coeficientes del lado derecho de las restricciones del problema primal son utilizados como coeficientes en la función objetivo del problema dual del lado derecho. Como se muestra a continuación:[pic 19]

[pic 20]

1. como señala esta condición, los coeficientes de la función objetivo del problema primal que son 10, 8, 5 y 0 son utilizados en el lado derecho de las restricciones del problema dual. Como se muestra a continuación:

[pic 21]

        Y como se comento sobre la tabla 5.2 cuando se trata de maximizar en el problema primal, en el problema dual se tiene que minimizar la función objetivo, según esta tabla todas las restricciones en el problema son del signo ≥.

Ejercicio de aplicación

        Cierta dietista necesita preparar una comida que contenga determinados nutrientes, al menos en las cantidades que se indican en la siguiente tabla. Dispone de tres ingredientes cuyos costos y contenidos de cada nutriente (unidades por gramo de ingrediente) se dan en la misma tabla.

        El problema a resolver consiste en definir la combinación de ingredientes que permite obtener, al mínimo costo, el alimento con el contenido nutricional deseado.

...