Dualidad Y Sensibilidad

Analisis de dualidad y sensibilidad

La solución optima de una programación lineal se basa en una toma instantanea de las condiciones que prevalecen en el momento de formular y resolver el modelo. En el mundo real, los ambientes de decisión rara vez permanecen estaticos, y es esencial determinar como cambia la solución optima, cuando cambian los parametros del modelo.

Eso es lo que hace el analisis de sensibilidad. Proporciona técnicas de cómputo eficientes para estudiar el comportamiento dinamico de la solución optima, que resulta al hacer cambios en los parametros del modelo.

DEFINICION DEL PROBLEMA DUAL

El problema dual es una programación lineal detenida en forma directa y sistematica a partir del modelo original (o primal) de programación lineal. Los dos problemas estan relacionados en forma tan estrecha que la resolución optima de un problema produce en forma automatica la resolución optima del otro.

En la mayor parte de las presentaciones de programación lineal, el dual se define para varias formas del primal, dependiendo del sentido de la optimización (maximización o mini-mización), tipos de restricciones (<= ¸ => o =), y la orientación de las variables (no negativa o no restringida). Este tipo de tratamiento puede confundir. Por esta razón presentaremos una sola definición que comprenda en forma automatica a todas las formas del primal.

Nuestra definición del problema dual requiere expresar el problema primal en forma de ecuaciones, como se presento anteriormente: todas las restricciones son ecuaciones, con lado derecho no negativo y todas las variables son no negativos. Este requisito es consistente con el formato de la tabla de inicio simplex. En consecuencia, todo resultado obtenido a partir de la solución primal optima se aplican en forma directa al problema dual asociado.

Para mostrar como se forma el problema dual, se define el primal en forma de ecuación como sigue:

Las variables xj; j = 1; 2; : : : ; n, incluyen las variables excedentes, holguras y artificiales les, si las hay.

La tabla 1 muestra como se construye el problema dual a partir del primal. De hecho se tiene que:

1. Se define una variable dual por cada ecuación primal (restricción).

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 coeficiente objetivo define el lado derecho.

4. Los coeficientes objetivo del dual son iguales al lado derecho de las ecuaciones de restricción primal. Las reglas para determinar el sentido de la optimización (maximización o minimización), el tipo de restricción (<=¸=> o =), y el signo de las variables duales (siempre no restringido) se resumen en la tabla 2. Notese que el sentido de la optimización

...