INVESTIGACION OPERATIVA
Programación Lineal
Formulación de problemas
Diciembre 2008
Conceptualización
Un Problema de Programación Lineal (PPL) es un
problema de optimización que consiste en
encontrar los valores de las variables de decisión
que maximicen o minimicen una función objetivo.
Modelo matemático PPL
(Forma estándar)
Maximizar
Z  c1X 1  c 2 X 2    c n X n
Sujeto a :
a 11 X 1  a 12 X 2    a 1n X n  b 1
a 21 X 1  a 22 X 2    a 2n X n  b 2

a m1 X 1  a m2 X 2    a mn X n  b m
X1, X 2 ,  , X n  0
Interpretación
X1, X2, …, Xn son las Variables de Decisión
generalmente se asocia a productos a fabricar
c1, c2, …, cn representan Utilidades (o Costos)
b1, b2, …, bm son las Capacidades de recursos
disponibles
a11, a12, …, amn representan cantidad que consume
un producto de un determinado recurso
Interpretación
Max Z  c 1 X 1  c 2 X 2    c n X n
Función
Objetivo
a 11 X 1  a 12 X 2    a 1n X n  b 1
Restricció
n1
a 21 X 1  a 22 X 2    a 2n X n  b 2
Restricció
n2

a m1 X 1  a m2 X 2    a mn X n  b m Restricció
X 1 , X 2 ,  , X n  0 Restricció
n m
n de No Negativida
d
Ejemplo 1
La mueblería del Sr. X elabora 2 tipos de mesas, la mesa
estándar y la mesa de lujo. Las operaciones necesarias
para la fabricación de ambos productos son:
• Cortar el material (C)
• Ensamblar (E)
• Pintar (P)
• Embalar (M)
La información de sus 2 principales productos es:
Ejemplo 1
Para el próximo periodo se estima una
disponibilidad máxima de 200 hr. de (C), 100 hr
para (E), 150 hr. para (P) y 80 hr. para (M).
¿Cuántas bolsas de cada tipo se deben fabricar
para maximizar las utilidades?
Formulación
Si X1=Nº de mesas estándar a fabricar
X2=Nº de mesas de lujo a fabricar
 10X
Max Z
1
 20 X 2
s .a .
2X 1  3 X 2  200
X1 
0.5X
1
X1 
X 2  10 0
 X 2  150
2X
2
 80
X1, X 2  0
Modelo matemático PPL
(Forma general)
Max ( o Min ) Z  c 1 X 1  c 2 X 2    c n X n
Sujeto a :
a 11 X 1  a 12 X 2    a 1n X n  (  o  ) b 1
a 21 X 1  a 22 X 2    a 2n X n  (  o  ) b 2

a m1 X 1  a m2 X 2    a mn X n  (  o  ) b m
X1, X 2 ,  , X n  0
Ejemplo 2
Consiste en determinar una dieta de manera
eficiente, a partir de un conjunto dado de
alimentos, de modo de satisfacer ciertos
requerimientos nutricionales.
Supongamos que se tiene la siguiente
información:
Ejemplo 2
Leche
(galon)
Legumbre
(1 porción)
Naranjas
(unidad)
Requerimientos
Nutricionales
Niacina
3,2
4,9
0,8
13
Tianina
1,12
1,3
0,19
15
Vitamina C
32
0
93
45
Costo
2
0,2
0,25
Ejemplo 2
Variables de decisión:
x1 : galones de leche utilizados en la dieta.
x2 : porciones de legumbre utilizadas en la dieta.
x3 : unidades de naranja utilizadas en la dieta.
Función Objetivo:
Minimizar el costo total de la dieta, dado por:
2 x1 + 0.2 x2 + 0.25 x3
Ejemplo 2
Restricciones del problema:
Requerimientos mínimos de los nutrientes
considerados:
3.2 x1 + 4.9 x2 + 0.8 x3  13
1.12 x1+ 1.3 x2 + 0.19 x3  15
32 x1+
9 x3  45
x1  0 ; x 2  0 ; x 3  0
Ejemplo 3
La empresa Caravana de Marco Polo Inc. transporta
higos secos desde Bagdad hasta La Meca, usando para
ello camellos y dromedarios.
Un camello puede transportar 1.000 kg. y un dromedario
500 kg. En el viaje un camello consume 3 fardos de heno
y 100 litros de agua. Un dromedario consume 2 fardos de
heno y 80 litros de agua.
Los lugares de abastecimientos de la empresa están
ubicados en varios oasis a lo largo del camino,
disponiéndose sólo de 1.600 litros de agua y 60 fardos de
heno.
Ejemplo 3
Los camellos y dromedarios son arrendados a un pastor
localizado en Bagdad, arrendándolos a 11 y 5 dinares
cada uno respectivamente.
Si la empresa tiene una carga de 10 ton. de higos secos a
ser transportada ¿Cuántos camellos y dromedarios deben
ser usados para minimizar el arriendo?.
Ejemplo 3
Minimizar
Z  11X 1  5X 2
s .a . 1.000X
1
 500X
3X 1 
2
 10.000
2X 2  60
100X 1  80X
2
 1.600
X1, X 2  0
Descargar

Presentación 2