investigación de operaciones: dualidad sensibilidad

Dualidad y análisis de sensibilidad en programación lineal

55

3 Dualidad y análisis de sensibilidad en programación lineal
3.1 Introducción
En el tema anterior se describieron las características de los modelos de programación lineal, así como
los diferentes caminos a partir de los que podemos encontrar la solución: resolución gráfica, algoritmo
símplex o uso de programas informáticos.En este tema, se describen dos técnicas también relacionadas con la programación lineal: la dualidad y el análisis de sensibilidad.
La segunda sección del tema desarrolla la teoría asociada a la dualidad: cómo se obtiene el dual de un
programa lineal, la interpretación del concepto de precio sombra y una serie de teoremas y resultados
útiles para la interpretación de un modelo lineal.
Latercera sección muestra las posibilidades del análisis de sensibilidad de la programación lineal. Se
trata de analizar cómo varía la solución del modelo (tanto el valor de la función objetivo como el valor
de las variables de decisión) en función de dos conjuntos de parámetros del modelo: los coeficientes de
coste de la función objetivo y los términos independientes de las restricciones.
El temaconcluye con un problema resuelto y con un glosario de los términos más relevantes introducidos en el mismo.

3.2 Dualidad en programación lineal
Dado un modelo lineal determinado, podemos definir otro modelo lineal que nos permitirá obtener propiedades interesantes del primero y que será su dual. La solución del modelo dual permite obtener
interesantes resultados, relativos al análisis desensibilidad de los términos independientes. Más concretamente, para los rangos de valores de los términos independientes para los que se mantiene la base
óptima (que podemos conocer mediante el análisis de sensibilidad), la solución del dual nos permite
conocer el precio sombra de la restricción, que será la variación de la función objetivo por unidad incrementada del término independiente de larestricción.
En la primera parte de esta sección, encontramos cómo hallar el dual de un modelo lineal. En las siguientes, se define con más precisión el concepto de precio sombra, cómo obtener la solución del dual
a partir de la del primal, y su aplicación al análisis de sensibilidad. Finalmente, se enuncian algunas
propiedades de interés, como el teorema de la holgura complementaria y lasrelaciones entre las soluciones del primal con las soluciones del dual.

3.2.1 Reglas de obtención del dual
Si el modelo está escrito en la forma canónica, el dual resulta singularmente fácil de obtener. Por
ejemplo, partiendo de la forma canónica del modelo de máximo:

© Los autores, 2002; © Edicions UPC, 2002.

Métodos cuantitativos en organización industrial I

56

Primal

Dual

[MIN]z = c’· x

[MAX] w = b’· u

A· x ≥ b
xj ≥ 0

A’· u ≤ c
ui ≥ 0

Si se trata de obtener el dual del dual, se obtendrá el primal: se trata de una correspondencia biunívoca.
De forma más general, las reglas para obtener el dual de cualquier modelo lineal se indican en la tabla
adjunta:
Primal Dual
Maximizar la F.O.
Una variable no negativa
Una variable no positiva
Una variable norestringida en signo
Una restricción menor o igual
Una restricción mayor o igual
Una igualdad

Dual Primal
Minimizar la F. O.
Una restricción mayor o igual
Una restricción menor o igual
Una igualdad
Una variable no negativa
Una variable no positiva
Una variable no restringida en signo

En los ejemplos 4.2.1, 4.2.2 y 4.2.3 (además del ejemplo 5), se muestran diversos ejemplos deobtención del dual.
3.2.2 Interpretación de las variables duales: precios sombra
Cada variable del dual está asociada a una restricción del programa primal, y su valor óptimo representa el incremento de la función objetivo del primal por cada unidad que aumente el término independiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Es,
por tanto, el precio...