Programacin mixta
Mara Guzmn Valle
[email protected]Investigacin de Operaciones I
www.usat.edu.pe
www.usat.edu.pe
Logro
Formula y resuelve modelos de programacin lineal
mixta.
2 www.usat.edu.pe
Objetivos
Obtener conocimiento y comprensin de los
fundamentos tericos de los modelos de programacin
lineal entera, su formulacin, su proceso de solucin y
el anlisis e interpretacin de los resultados.
Identificar situaciones en las que los modelos de
programacin lineal entera pueden ser utilizados para
darles solucin.
www.usat.edu.pe
Problemas mixtos
Los problemas en los que se requiere que
algunas, pero no todas las variables, sean enteras,
se denominan problemas mixtos de
programacin lineal entera. Estos problemas
permiten la combinacin de variables enteras y
reales. Las variables enteras pueden ser generales
o binarias, dependiendo de la situacin que se
representa.
www.usat.edu.pe
Problemas mixtos
Ejemplo 3
Hospital Estatal de la ciudad: paciente con una dieta especial que consta
de dos alimentos.
Requerimientos nutritivos mnimos por da: 1,000 unidades del
nutriente A, 2,000 unidades del nutriente B y 1,500 unidades del
nutriente C.
Una onza del alimento 1 contiene 100 unidades del nutriente A, 400
unidades del nutriente B y 200 unidades del nutriente C.
Una onza del alimento 2 contiene 200 unidades del nutriente A, 250
unidades del nutriente B y 200 unidades del nutriente C.
www.usat.edu.pe
Problemas mixtos
Ejemplo 3 (continuacin)
El alimento 1 cuesta $6.00 por libra y el alimento 2
cuesta $8.00 por libra.
Los costos de los pedidos para el alimento 1 son $5.00
y para el alimento 2 son $7.50.
www.usat.edu.pe
Problemas mixtos
Ejemplo 3 (continuacin)
Variables de decisin
Xj: cantidad de onzas del alimento j que debe consumir
diariamente el paciente
Yj: decisin de utilizar o no el alimento j
Donde j = 1, 2
Funcin objetivo
Minimizar costos de preparacin y envo de alimentos
Minimizar Z = 0.375 X1 + 0.5 X2 + 5 Y1 + 7.50 Y2
www.usat.edu.pe
Problemas mixtos
Ejemplo 3 (continuacin)
Restricciones
Requerimiento mnimo del nutriente A
100 X1 + 200 X2 1000
Requerimiento mnimo del nutriente B
400 X1 + 250 X2 2000
Requerimiento mnimo del nutriente C
200 X1 + 200 X2 1500
www.usat.edu.pe
Problemas mixtos
Ejemplo 3 (continuacin)
Restricciones
Disponibilidad de los alimentos (M -> )
X1 M Y1 0
X1 Y1 0
X2 M Y2 0
X2 Y2 0
Rango de existencia
Xj 0 y enteros
Yj = 0 1
www.usat.edu.pe
Aplicaciones de PLE
2.1 Problema de cargo fijo
2.2 Problema de recubrimiento de conjuntos
2.3 Restricciones inclusivas o distributivas
2.4 Restricciones si ... entonces
2.5 Funciones lineales por segmentos
www.usat.edu.pe
Problema de cargo fijo
Ejemplo 4
La compaa DYNAMIX tiene tres alternativas para ubicar un nuevo almacn
que d servicio a la parte norte de Per. Existen 5 clientes importantes en
esta regin. En la siguiente tabla se muestran los datos pertinentes de
oferta, demanda y costos de transporte ($ por tonelada).
Ubicacin Costo de la Capacidad Ubicacin del cliente
del Ubicacin ($) del almacn
Almacn (miles de
Tumbes Cajamarca Pacasmayo Huaraz Casma
tonelada)
Piura 50,000 200 $20 $20 $40 $45 $35
Trujillo 30,000 150 $30 $40 $15 $20 $45
Chimbote 90,000 300 $5 $25 $30 $35 $35
Pronstico de la demanda 75 50 35 75 35
(miles de tonelada)
www.usat.edu.pe
Restricciones inclusivas o distributivas
Ejemplo 5
Un granjero desea determinar cul es la mejor
seleccin de ganado para su granja con el objeto de
maximizar las utilidades provenientes de las ventas de
los animales. Puede comprar ovejas, reses o cabras.
Cada oveja necesita un acre de pasto y $15.00 de
alimentacin y tratamiento. Una oveja cuesta $25.00 y
puede venderse en $60.00. Para las reses, estos valores
son 4 acres, $30.00, $40.00 y $100.00. Y para las cabras,
estos valores son 0.5 acres, $5.00, $10.00 y $20.00.
www.usat.edu.pe
Restricciones inclusivas o distributivas
Ejemplo 5 (continuacin)
La granja tiene 300 acres y el granjero dispone de $2500 para
comprar y mantener su ganado. Por ltimo, el granjero ha
fijado un lmite inferior al nmero de animales que desea
adquirir, si es que compra alguno de cada tipo. Este lmite
inferior es de 50 para las ovejas, 25 para las reses y 100 para
las cabras.
www.usat.edu.pe
Restricciones si entonces
Ejemplo 6
La Compaa DYNAMIX se encuentra en proceso de
planear nuevas instalaciones de produccin, y de
desarrollar un diseo ms eficiente de su sistema de
distribucin.
Capacidad de Planta en Chincha: 30,000 unidades
Cuatro nuevos lugares potenciales para plantas: Ica,
Arequipa, Chimbote y Trujillo.
www.usat.edu.pe
Restricciones si entonces
Costos unitarios de Capacidad de
transporte Lima Huancayo Cuzco planta
($ por unidad) (unidades)
Ica 5 2 3 10,000
Arequipa 4 3 4 20,000
Chimbote 9 7 5 30,000
Trujillo 10 4 2 40,000
Chincha 8 4 3 30,000
Demanda mxima
30,000 20,000 20,000
(unidades)
www.usat.edu.pe
Restricciones si entonces
Ejemplo 6 (continuacin)
Ciudad Costo fijo
Ica $175,000
Arequipa $300,000
Chimbote $375,000
Trujillo $500,000
www.usat.edu.pe
Funciones lineales por segmentos
Ejemplo 7
La compaa DYNAMIX elabora dos productos A y B.
A B Disponible
Mano de obra (horas) 3 2 900 horas
Espacio (pies cbicos) 2 1 400 pies3
Costo fijo de produccin ($) 80 75
Materia Prima (Libras) 1 2
www.usat.edu.pe
Funciones lineales por segmentos
Ejemplo 7 (continuacin)
La materia prima se adquiere de un proveedor al precio
de $2.50 por libra. Los costos unitarios de fabricacin de
los productos dependen de la cantidad fabricada, dichos
costos se muestran en las siguientes tablas (estos costos
no incluyen el costo de materia prima). Los productos A
y B se venden a $18 y $16 por cada unidad
respectivamente.
www.usat.edu.pe
Funciones lineales por segmentos
Ejemplo 7 (continuacin)
Producto A Costo Producto B Costo
0 100 $10.00 0 130 $10.00
101 180 $12.00 131 200 $9.00
181 300 $14.00 201 280 $8.00
www.usat.edu.pe
Solucin computacional de problemas de PLE
La compaa TODO HOGAR produce dos productos
muy apreciados con los restauradores de casas:
candelabros y ventiladores de techo de estilo
antiguo.
Tanto los candelabros como los ventiladores
requieren un proceso de produccin de dos pasos
que involucran cableado y ensamble.
www.usat.edu.pe
Variables Enteras
Se requieren 2 horas para cablear cada candelabro y
3 horas para cablear un ventilador de techo. El
cableado final de los candelabros y ventiladores
requiere 6 y 5 horas, respectivamente.
La capacidad de produccin es tal que slo estn
disponibles 12 horas de cableado y 30 horas de
ensamble.
Cada candelabro producido redita a la firma $7.00
y cada ventilador $6.00.
www.usat.edu.pe
Variables Enteras
Variables de decisin
X1: nmero de candelabros que sern producidos y vendidos
X2: nmero de ventiladores de techo que sern producidos y
vendidos
Maximizar Z = 7 X1 + 6 X2 (maximizar utilidades)
Sujeta a
2X1 + 3X2 12 (horas de cableado)
6X1 + 5X2 30 (horas de ensamble)
Con X1, X2 0 y enteros
www.usat.edu.pe
Variables Enteras
MAX 7 X1 + 6 X2
SUBJECT TO
2) 2 X1 + 3 X2 <= 12
3) 6 X1 + 5 X2 <= 30
END
GIN 2
OBJECTIVE FUNCTION VALUE
1) 35.00000
VARIABLE VALUE REDUCED COST
X1 5.000000 -7.000000
X2 0.000000 -6.000000
www.usat.edu.pe
Variables Enteras
Solucin ptima
X1 = 5, X2 = 0
Valor ptimo de la funcin objetivo
Z = 35
Se producirn y vendern 5 candelabros y
ningn de techo, para obtener una utilidad de
$35.00.
www.usat.edu.pe
Variables binarias
Para graduarse en la especialidad de Investigacin de Operaciones, un
estudiante debe completar por lo menos dos cursos de matemticas, por lo
menos dos cursos de investigacin de operaciones y por lo menos dos cursos
de computacin.
Se pueden utilizar algunos cursos para satisfacer ms de un requisito:
Clculo puede satisfacer el requerimiento de las matemticas;
Investigacin de Operaciones puede satisfacer los requerimientos de
matemticas e investigacin de operaciones;
Estructura de Datos, los de matemticas y de computacin;
Estadstica para Administracin, los de matemticas y de investigacin
de operaciones;
Simulacin por Computadora los de investigacin de operaciones y de
computacin;
Introduccin a la Programacin de Computadoras los de computacin;
y
Pronsticos los de investigacin de operaciones y de matemticas.
Maestra de Ingeniera Industrial 30
Walter Silva 30
www.usat.edu.pe
Variables binarias
Algunos cursos son pre-requisitos para otros:
Clculo es un requisito para Estadstica para
Administracin;
Introduccin a la Programacin de Computadoras es un
requisito para Simulacin por Computadora y para
Estructura de Datos; y
Estadstica para Administracin es requisito para
Pronsticos.
www.usat.edu.pe
Variables binarias
Variables de decisin
X1: decisin de llevar o no el curso de Clculo
X2: decisin de llevar o no el curso de Investigacin de
Operaciones
X3: decisin de llevar o no el curso de Estructura de Datos
X4: decisin de llevar o no el curso de Estadstica para
Administracin
X5: decisin de llevar o no el curso de Simulacin por
Computadora
X6: decisin de llevar o no el curso de Introduccin a la
Programacin de Computadoras
X7: decisin de llevar o no el curso de Pronsticos
www.usat.edu.pe
Variables binarias
Funcin objetivo
Minimizar el nmero de cursos a llevar
Minimizar Z = X1 + X2 + X3 + X4 + X5 + X6 + X7
Restricciones
Cursos mnimos de matemticas
X1 + X2 + X3 + X4 + X7 2
Cursos mnimos de investigacin de operaciones
X 2 + X4 + X 5 + X 7 2
Cursos mnimos de computacin
X3 + X5 + X6 2
Clculo es requisito para Estadstica para Administracin
X4 X1 0
www.usat.edu.pe
Variables binarias
MIN X1 + X2 + X3 + X4 + X5 + X6 + X7
SUBJECT TO
2) X1 + X2 + X3 + X4 + X7 >= 2
3) X2 + X4 + X5 + X7 <= 2
4) X3 + X5 + X6 >= 2
5) - X1 + X4 <= 0
6) X5 - X6 <= 0
7) X3 - X6 <= 0
8) - X4 + X7 <= 0
END
INTE 7
www.usat.edu.pe
Variables binarias
OBJECTIVE FUNCTION VALUE
1) 3.000000
VARIABLE VALUE REDUCED COST
X1 1.000000 1.000000
X2 0.000000 1.000000
X3 1.000000 1.000000
X4 0.000000 1.000000
X5 0.000000 1.000000
X6 1.000000 1.000000
X7 0.000000 1.000000
www.usat.edu.pe
Variables binarias
Solucin ptima
X1 = 1, X2 = 0, X3 = 1, X4 = 0, X5 = 0, X6 = 1,
X7 = 0
Valor ptimo de la funcin objetivo
Z=3
El estudiante debe llevar los cursos de
Clculo, Estructura de Datos e Introduccin a
la Programacin de Computadoras.
www.usat.edu.pe
PLM-Introduccin
La programacin por metas es una
extensin de la programacin lineal que
permite establecer ms de un objetivo.
www.usat.edu.pe
PLM-Introduccin
Las firmas usualmente tienen ms de una meta. Por
ejemplo:
Maximizacin de utilidades,
Maximizacin la participacin del mercado,
Mantener el empleo completo,
Proporcionar una administracin ecolgica de
calidad,
Minimizar el nivel de ruido en el vecindario, y
Satisfacer otras numerosas metas no
econmicas.
No es posible para la PL tener mltiples metas a
www.usat.edu.pe
PLM-Introduccin
La programacin por metas satisface
En oposicin a la PL, que trata de optimizar .
Satisface significa: acercarse tanto como sea posible al logro de las metas.
La funcin objetivo es la diferencia principal entre la
programacin por metas y la programacin lineal.
En la programacin por metas, el propsito es minimizar las
variables de desviacin.
Los cuales son los nicos trminos en la funcin objetivo.
www.usat.edu.pe
P.Metas vs. P.Lineal
Mltiples metas (en vez de una meta)
Variables de desviacin minimizadas (en vez de
maximizar utilidades o minimizar costos)
Satisfacer (en vez de optimizar)
Variables de desviacin son reales (y reemplazan a
las variables de holgura y superfluas)
www.usat.edu.pe
Formulacin de problemas de programacin por metas
2.1 Problemas de un solo objetivo.
2.2 Problema de objetivos mltiples sin
prioridades.
2.3 Problema de objetivos mltiples con
prioridades.
2.4 Problema de objetivos mltiples con
prioridades y ponderaciones.
www.usat.edu.pe
Problemas de un solo objetivo
Una empresa fabrica dos productos. Cada producto requiere tiempo en
dos departamentos de produccin: el producto 1 requiere 20 horas en el
departamento 1 y 10 horas en el departamento 2; el producto 2
requiere 10 horas en el departamento 1 y 10 horas en el departamento
2.
El tiempo de produccin est limitado a 60 horas en el departamento 1
y a 40 horas en el departamento 2. La contribucin de los dos productos
a las utilidades es de $40 y $80, respectivamente. La empresa desea
alcanzar $1000 de utilidades.
El objetivo es maximizar las utilidades.
www.usat.edu.pe
Problemas de un solo objetivo
Variables de decisin
X1 : cantidad de unidades a producir del producto 1
X2 : cantidad de unidades a producir del producto 2
Variables de desviacin
U1 : cantidad de dinero que falta para alcanzar la meta de
utilidades de $1,000
V1 : cantidad de dinero que excede la meta de utilidades
de $1,000
www.usat.edu.pe
Problemas de un solo objetivo
Minimizar Z = U1
Sujeta a:
20 X1 + 10 X2 60 (tiempo disponible en el
Departamento 1)
10 X1 + 10 X2 40 (tiempo disponible en el
Departamento 2)
40 X1 + 80 X2 + U1 V1 = 1000 (meta de utilidades)
Con X1, X2, U1, V1 0
www.usat.edu.pe
Problemas de un solo objetivo
Solucin ptima
X1 = 0, X2 = 4, U1 = 680, V1 = 0
Valor ptimo de la funcin objetivo
Z = 680
Meta: maximizar utilidades
$320 (= 1000 + 0 - 680 = 1000 + V1 - U1)
Conclusin
La utilidad mxima lograda es $320.
www.usat.edu.pe
Problemas de objetivos mltiples sin prioridades
Consideremos el problema anterior.
Ahora se debe producir cuando menos dos unidades
de cada tipo de producto. Los administradores
consideran que esa segunda meta es tan importante
como la meta de utilidades.
www.usat.edu.pe
Problemas de objetivos mltiples sin prioridades
Variables de decisin
X1 : cantidad de unidades a producir del producto 1
X2 : cantidad de unidades a producir del producto 2
Variables de desviacin
U1 : cantidad de dinero que falta para alcanzar la meta
de utilidades de $1,000
V1 : cantidad de dinero que excede la meta de utilidades
de $1,000
www.usat.edu.pe
Problemas de objetivos mltiples sin prioridades
Variables de desviacin (continuacin)
U2 : cantidad de unidades del producto 1 que faltan
para alcanzar la meta de producir cuando menos 2
unidades
V2 : cantidad de unidades del producto 1 que exceden
la meta de producir cuando menos 2 unidades
U3 : cantidad de unidades del producto 2 que faltan
para alcanzar la meta de producir cuando menos 2
unidades
V3 : cantidad de unidades del producto 2 que exceden
la meta de producir cuando menos 2 unidades
www.usat.edu.pe
Problemas de objetivos mltiples sin prioridades
Minimizar Z = U1 + U2 + U3
Sujeta a:
20 X1 + 10 X2 60 (tiempo disponible en el
Departamento 1)
10 X1 + 10 X2 40 (tiempo disponible en el
Departamento 2)
40 X1 + 80 X2 + U1 V1 = 1000 (meta de utilidades)
X1 + U2 V2 = 2 (meta del producto 1)
X2 + U3 V3 = 2 (meta del producto 2)
Con X1, X2, U1, V1, U2, V2, U3, V3 0
www.usat.edu.pe
Problemas de objetivos mltiples sin
prioridades
Solucin ptima
X1 = 0, X2 = 4, U1 = 680, V1 = 0, U2 = 2, V2 = 0, U3 = 0 y V3 =
2
Valor ptimo de la funcin objetivo
Z = 682
Meta 1: maximizar utilidades
$320 (= 1000 + 0 - 680 = 1000 + V1 - U1)
Meta 2: producir cuando menos dos unidades de cada
tipo de producto
Producto 1: 0 (= 2 + 0 2 = 2 + V2 - U2)
Producto 2: 4 (= 2 + 0 - 2 = 2 + V3 U3)
www.usat.edu.pe
Problemas de objetivos mltiples sin prioridades
Conclusin
La utilidad mxima lograda es $320.
La meta de producir cuando menos dos unidades de
cada tipo de producto no se logr. Se produjeron
cuatro unidades del producto 2 y ninguna del
producto 1.
www.usat.edu.pe
Problema de enlatados de tomate,
Una compaa tiene un contrato para recibir 60000
libras de tomates maduros a 0.7$/lb de las cuales
producir jugo de tomate y pur de tomate enlatados.
Los productos enlatados se empacan en cajas de 24
latas cada una. Una lata de jugo requiere 1 lb de
tomates frescos en tanto que una de pur requiere solo
de 1/3 de lb. La participacin de la compaa en el
mercado esta limitada a 2000 cajas de jugo y 6000
cajas de pur. Los precios al mayoreo por caja de jugo
y de pur son $18 y $9. Genere un programa de
produccin para esta compaa.
a. Se desea alcanzar una meta de $22000
b. Se desea alcanzarwww.usat.edu.pe
adicional una meta de 6000 cajas
Max 1.2X1+3.4X2
St
24X1+8X2<=60000
X1<=2000
X2<=6000
end
www.usat.edu.pe
www.usat.edu.pe
Mara Guzmn Valle
[email protected]
http://www.facebook.com/usat.peru
https://twitter.com/usatenlinea
https://www.youtube.com/user/tvusat
https://plus.google.com/+usateduperu
www.usat.edu.pe
