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:

...