Tema 5

Tema 5: Dualidad y sensibilidad de los modelos lineales.

Objetivos del tema:
 Introducir el concepto de Sensibilidad en la Programación Lineal
 Introducir el concepto de Dualidad en la Programación Lineal
 Aprender a formular el modelo del problema Dual asociado al Primal
 Establecer la relación entre las sensibilidades del problema Primal y las soluciones del Dual

1
A. HERRÁN, INTRODUCCIÓNA LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL

Sensibilidad en la Programación Lineal
El análisis de sensibilidad para los modelos de Programación Lineal tiene por objetivo identificar el impacto sobre la solución del
problema original tras determinadas modificaciones en los parámetros del problema, sin tener que resolver el problema nuevamente
cadavez que se modifica uno de tales parámetro (como se verá más adelante, es suficiente con resolver el problema Dual).
•

Sea B* la base óptima de un problema de Programación Lineal en forma estándar, entonces:

x B*

  B*  b

z*

 cBT x B*

1

•

Si ahora se considera un cambio marginal en el vector de términos independientes b:

b  b*  b

•

Dicho cambio dará lugar a cambios en la solución(xB) y el valor de la función objetivo (z):

x *B



z*

 z *  z *

•

•

Por tanto, y dado que se trata de un problema Lineal, se puede escribir:

Dado lugar a

z  cTB x B  cBT  B*  b  λ*T b
1



λ*T  cBT  B* 

x *B  x B

x B

  B*  b

z

 c TB x B

1

1

Dicha ecuación, para una coordenada arbitraria j nos indica el cambio en el valor optimo de la función objetivocomo resultado de un
cambio marginal en la componente j del vector de términos independientes b.

z  λ*T b



 *j 

z
b j

Estos parámetros de sensibilidad juegan un papel fundamental en aplicaciones de ingeniería y científicas. Como se verá en las secciones
siguientes, los parámetros de sensibilidad son de hecho las variables del Problema Dual.

2
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓNMATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL

Ejemplo 1: Problema del carpintero
Un carpintero fabrica dos tipos de mesas de madera. Cada mesa del tipo 1 necesita 4 horas de mecanizado primario (preparación de
piezas) y 4 horas de mecanizado secundario (ensamblado y barnizado). Análogamente, cada mesa del tipo 2 necesita 3 horas de
mecanizado primario y 7 horas demecanizado secundario. Las disponibilidades diarias de mecanizados primario y secundario son
respectivamente de 40 y 56 horas-máquina. La venta de una mesa del tipo 1 reporta un beneficio de 70 euros, mientras que la venta de
una mesa del tipo 2 de 90 euros.
Tiempo de mecanizado (horas)
Tipo de mesa

Tipo 1

Tipo 2

Disponibilidad diaria
(horas-máquina)

Mecanizado primario

4

3

40

Mecanizadosecundario

4

7

56

Beneficio (€)

70

90

Se trata de determinar el número de mesas de cada tipo que han de producirse diariamente para maximizar el beneficio obtenido.

Solución: Problema del carpintero
Este p
problema p
puede formularse como el p
problema de Programación
g
Lineal siguiente:
g

Maximizar

z  70 x1  90 x2

sujeto a

4 x1  3 x2  40
4 x1  7 x2  56
x1 , x2  0

Donde:

x1
x2

cantidad diaria de mesas a fabricar del tipo 1
 cantidad diaria de mesas a fabricar del tipo 2

3
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL

Solución: Problema del carpintero (continuación 1)
La solución óptima de este problema, como se observa en la figura, establece que han de producirse diariamente 7 y 4 sillas de los tipos1 y 2 respectivamente, lo que da lugar a un beneficio de 850 euros.
Este resultado indica que ambos recursos de mecanizado (primario y secundario) están plenamente utilizados porque las restricciones
relacionadas con ellos están ambas activas.

//Variables de decisión
dvar float+ x1;
dvar float+ x2;
//Función objetivo
maximize 70*x1+90*x2;
//Restricciones
subject to {
4*x1 + 3*x2 <= 40;
4*x1 +...