Universidad Tecnológica de Pereira – Colombia
Posgrado en Ingeniería – Maestría/Doctorado
Programación Lineal
Antonio H. Escobar Z.
2012
Optimalidad en PL e interpretación
económica de las variables duales:
Ejemplo:
* Una fábrica produce mesas construidas con tubos metálicos y con
superficie de vidrio.
* La cantidad de mesas fabricadas semanalmente está limitada por la
cantidad máxima disponible de tubos metálicos y de metros cuadrados de
láminas de vidrio que puede adquirir en el mercado:
50 tubos/semana
75 m2 vidrio/semana
* Se asume que la fábrica vende todas las mesas producidas.
Ejemplo:
Con el propósito de maximizar las ganancias, la fábrica diversifica sus
productos. Para esto se diseñan cuatro tipos de mesas y se evalúa la
ganancia neta que cada una produce y sus requerimientos de tubos y vidrio.
Ejemplo:
Lucro:
150
500
400
200
1
4
3
1
50
1
1
1
2
75
hierro:
(tubos)
vidrio:
(m2)
cantidad disponible
Que modelos debe fabricar y en que cantidad para obtener el máximo lucro?
Ejemplo:
variables de decisión:
x1
x2
x3
150
500
400
200
hierro:
1
4
3
1
50
vidrio:
1
1
1
2
75
x4
Lucro:
cantidad máxima disponible
Modelamiento:
max
150
x1 + 500 x2
4 x2
1
x1
+
1
x1
+ 1
x2
+ 400 x3
+ 200 x4
+ 3 x3
+ 1
x4
≤
50
: hierro
+ 1 x3
+ 2
x4
≤
75
: vidrio
Modelamiento:
max
150
x1 + 500 x2
4 x2
1
x1
+
1
x1
+ 1
x2
+ 400 x3
+ 200 x4
+ 3 x3
+ 1
x4
+
x5 =
50
: hierro
+ 1 x3
+ 2
x4
+
x6 =
75
: vidrio
Variables de holgura
Caso de estudio: la empresa fabrica únicamente
mesas tipo 1 y evalúa la posibilidad de fabricar
otro tipo de mesa.
max
150
x1 + 500 x2
4 x2
1
x1
+
1
x1
+ 1
x2
+ 400 x3
+ 200 x4
+ 3 x3
+ 1
x4
+
x5 =
50
: hierro
+ 1 x3
+ 2
x4
+
x6 =
75
: vidrio
Solución básica:
max
150
1
1
x1
x1
x1 + 500 x2
+
0
4 x2
+ 1
0
x2
+ 400 x3
+ 200 x4
0
0
+ 3 x3
+ 1 x3
0
Solución básica: Lucro = 7500 ;
+ 1
+ 2
x4
x4
0
+
x5 =
50
: hierro
+
x6 =
75
: vidrio
0
x1 = 50 ;
x6 = 25 ;
La cantidad de mesas tipo 1 construidas son limitadas por el recurso que
primero se agota: cantidad de tubos de hierro disponibles (recurso1). Con
50 tubos puedo hacer 50 mesas tipo 1 (se requiere 1 tubo por mesa). Del
recurso 2 (m2 de vidrio) se usan 50 m2 y quedan 25 m2 sobrantes.
La restricción 1 se activa y la restricción 2 queda com holgura: x6 = 25 m2
max
150
1
1
x1
x1
x1 + 500 x2
+
0
4 x2
+ 1
0
x2
+ 400 x3
+ 200 x4
0
0
+ 3 x3
+ 1 x3
0
+ 1
+ 2
x4
x4
+
0
x5 =
51
w1 = 150
50
76
0
+
x6 =
75
w2 = 0
Variable dual w: beneficio adicional obtenido cuando se aumenta un
recurso en una unidad
Al incrementar el recurso 1 de 50 a 51 tubos puedo hacer 51 mesas tipo 1
obteniendo un lucro adicional de 150 (1 mesa más).
Al incrementar el recurso 2 de 75 a 76 m2 de vidrio no obtengo un lucro
adicional porque este recurso tiene holgura.
Es conveniente fabricar mesas tipo 2 en lugar de mesas tipo 1 ?
max
150
1
1
x1
x1
x1 + 500 x2
+
4 x2
+ 1
x2
+ 400 x3
+ 200 x4
0
0
+ 3 x3
+ 1 x3
0
+ 1
+ 2
x4
x4
0
+
x5 =
50
w1 = 150
+
x6 =
75
w2 = 0
0
•
Una mesa tipo 2 fabricada (que requiere 4 tubos de hierro) desplaza 4 mesas
tipo 1 (que requiere 1 tubo de hierro cada una). Esto porque esta restricción está
en su límite.
•
Respecto al recurso: m2 de vidrio, no hay afectación de mesas tipo 1 porque
esta restricción tiene holgura.
•
En consecuencia, el beneficio neto de fabricar una mesa tipo 2 en lugar de una
mesa tipo 1 es: 500 – 4(150) = -100. (no es conveniente).
Es conveniente fabricar mesas tipo 3 en lugar de mesas tipo 1 ?
max
150
1
1
x1
x1
x1 + 500 x2
+
0
4 x2
+ 1
0
x2
+ 400 x3
+ 3 x3
+ 1 x3
+ 200 x4
+ 1
+ 2
x4
x4
0
0
+
x5 =
50
w1 = 150
+
x6 =
75
w2 = 0
0
•
Una mesa tipo 3 fabricada (que requiere 3 tubos de hierro) desplaza 3 mesas
tipo 1 (que requiere 1 tubo de hierro cada una). Esto porque esta restricción está
en su límite.
•
Respecto al recurso: m2 de vidrio, no hay afectación de mesas tipo 1 porque
esta restricción tiene holgura.
•
En consecuencia, el beneficio neto de fabricar una mesa tipo 3 en lugar de una
mesa tipo 1 es: 400 – 3(150) = - 50. (no es conveniente).
Es conveniente fabricar mesas tipo 4 en lugar de mesas tipo 1 ?
max
150
1
1
x1
x1
x1 + 500 x2
+
0
4 x2
+ 1
0
x2
+ 400 x3
0
+ 3 x3
0
+ 1 x3
+ 200 x4
0
+ 1
x4
+
x5 =
50
w1 = 150
+ 2
x4
+
x6 =
75
w2 = 0
•
Una mesa tipo 4 fabricada (que requiere 1 tubo de hierro) desplaza 1 mesa
tipo 1 (que requiere 1 tubo de hierro cada una). Esto porque esta restricción
está en su límite.
•
Respecto al recurso: m2 de vidrio, no hay afectación de mesas tipo 1 porque
esta restricción tiene holgura.
•
En consecuencia, el beneficio neto de fabricar una mesa tipo 4 en lugar de una
mesa tipo 1 es: 200 – 1*(150) = + 50. (si es conveniente).
Descargar

Diapositiva 1