22/08/2016
INVESTIGACION DE OPERACIONES II
Ing. Enrique M. Avendao Delgado
ead@[Link]
REGLAS DE CONVIVENCIA:
PUNTUALIDAD
Hora de Inicio de Clase: Lunes 14.30 pm
Laboratorio: Lunes 11.50 am y 12.30 pm
ASISTENCIA
Lmite de Faltas: 11
Exmenes en al Fecha
Trmite en la Oficina de Bienestar Universitario
Norma: GF-BU-P01-N01
CELULAR en vibrador.
No Mensajes de Texto, ni Internet
Phubbing
DESCANSO POR SESION
Clase Teora: 3.00 pm (10 min)
22/08/2016
AULA VIRTUAL
22/08/2016
AULA VIRTUAL
FORMAS DE COMUNICACIN:
Al trmino de Clase
eavendano@[Link]
[Link]/[Link]
22/08/2016
REGLAS
ASISTENCIA
PUNTUALIDAD
EXAMENES EN LA FECHA
PARTICIPACION EN CLASES
HORIZONTALIDAD
DELEGADOS DE CLASE:
22/08/2016
Unidad 1
Modelos Determinsticos De Decisin
PROGRAMACIN ENTERA Y
BINARIA
Ing. Enrique M. Avendao Delgado
[Link]@[Link]
INTRODUCCIN
Hasta ahora hemos visto los problemas de programacin lineal en el dominio de los
reales. Sin embargo, en muchos modelos algunas o todas las variables de decisin
deben ser enteras. Estos modelos son conocidos como modelos de programacin lineal
entera (ILP).
A primera vista podra parecer ms fcil resolver problemas con restriccin de enteros,
ya que transforman un problema continuo en un problema discreto. Los modelos de
programacin lineal entera se pueden clasificar en:
Modelo
Tipos de Variables de Decisin
Completamente entero
Todas son enteras
(AILP)
Algunas, pero no todas son
Mixto (MILP)
enteras
Binaria (BILP)
Todas son binarias (0 1)
22/08/2016
PROGRAMACIN ENTERA
La PE tiene gran cantidad de aplicaciones en todos los campos.
Hay problemas que no pueden resolverse con las tcnicas actuales por:
Disponibilidad de tiempo de ordenador
Capacidad de memoria
Para evitar esto parece sensato calcular la solucin de un PE redondeando la solucin
continua.
Pero el redondeo no es aconsejable debido a:
La solucin redondeada no es necesariamente ptima. En muchos casos, ni
siquiera estar cera del ptimo.
La solucin redondeada puede no ser factible.
PROGRAMACIN ENTERA
Programacin Entera es un termino general para
los modelos de programacin matemtica que
presentan condiciones de integridad (condiciones
que estipulan que algunas o todas las variables
de decisin deben tener valores enteros). Ya
hemos apuntado que los modelos de
programacin lineal entera son modelos de
programacin lineal que tienen la caracterstica
adicional de que algunas de las variables de
decisin deben tener valores enteros. Existen
diversas clasificaciones de esta categora de
modelos.
Programas Enteros Puros, Un modelo entero
puro (PLE) es, como su nombre lo indica, un
problema en el que se exige que todas las
variables de decisin tengan valores enteros
22/08/2016
IMPORTANCIA DE LAS SOLUCIONES
ENTERAS
Existen muchos problemas importantes en los que la solucin
redondeada simplemente no funciona.
Por ejemplo, si la solucin de un modelo de programacin lineal
recomienda que la Boeing construya 11,6 aparatos 747 y 6,8
aparatos 727, el administrador probablemente no quedara
contento con la simple medida de tomar la decisin de construir
11 de los primeros y 6 de los segundos, o cualquier otra
solucin redondeada. La magnitud del rendimiento y la
asignacin de recursos asociados con cada unidad del
problema aconsejan determinar la mejor solucin entera
posible.
IMPORTANCIA DE LAS SOLUCIONES ENTERAS
Con otro ejemplo, s vera que muchos modelos usan variables enteras
para indicar decisiones lgicas. Por ejemplo, veremos que problemas
en los que queramos que una variable x sea igual a 1 si vamos a
construir un almacn o x sea igual a cero (si-no). Supngase que la
solucin de una versin de programacin lineal de este problema
produce un valor no entero, por ejemplo, x = 0,38. Vemos que este
valor no contiene informacin aprovechable como solucin al problema
real.
22/08/2016
IMPORTANCIA DE LAS SOLUCIONES ENTERAS
Es claro que no podemos construir 0,38 de un almacn. Es cierto que
podemos elegir almacenes de diversos tamaos, pero en todo caso, o
bien tenemos un almacn o no lo tenemos. Se podra suponer que en un
caso como este se tratara de redondear al entero ms prximo (0 en
este caso) como forma de salvar la dificultad. Por desgracia, esto no
garantiza que se obtenga una buena (y no digamos ptima) solucin.
En realidad, veremos que el redondeo no siempre conduce a solucione
factibles en casos como este.
IMPORTANCIA DE LAS SOLUCIONES ENTERAS
El fondo del asunto es que existen muchos problemas administrativos
importantes que serian de programacin lineal si no fuese por el
requerimiento de que sean enteros los valores de algunas variables
de decisin, en los que no se puede encontrar una buena solucin
mediante el uso del mtodo Simplex seguido del redondeo de los
valores ptimos resultantes para variables de decisin. Estos
problemas deben ser resueltos mediante algoritmos especialmente
diseados para resolver problemas de programacin entera.
22/08/2016
VARIABLES
PLANEAMIENTO DE PROBLEMAS
DE PROGRAMACIN ENTERA
22/08/2016
EJEMPLO 1:
PE DE UN PRESUPUESTO DE CAPITAL (*)
Stockco proyecta cuatro inversiones. La inversin 1 genera un valor neto actual
(VNA) de 16 000 dlares; la inversin 2, un VNA de 22 000 dlares; la inversin 3,
un VNA de 12 000 dlares, y la inversin 4, una VNA de 8 000 dlares. Para cada
inversin se requiere una cierta salida de efectivo en el tiempo presente; la
inversin 1, 5 000 dlares; la inversin 2, 7 000 dlares; la inversin 3, 4 000
dlares; la inversin 4, 3 000 dlares. Dispone en la actualidad de 14 000 dlares
para invertir. Plantee un PE cuya solucin le indique a Stockco el modo de
maximizar el VNA obtenido de las inversiones 1 a 4.
(*) Investigacin de Operaciones W. Winston Pg. 478
EJEMPLO 1
Solucin:
la inversion
X j ( j 1, 2,3, 4) 10 SiSi senoefectua
se efectua la inversion
Por ejemplo: X2 = 1 si invierte en la inversin 2, pero X2 = 0 no se invierte
El VNA que logra Stockco (en miles de dlares) es:
VNA total que logra Stockco = 16X1 + 22X2 + 12X3 + 8X4
10
22/08/2016
EJEMPLO 1
Por ejemplo: Si Stockco invierte en 1 y en 4, entonces obtiene un
VNA de 16 000 + 8 000 = 24 000 dlares. Esta combinacin de
inversiones corresponde a:
X1 = X4 = 1,
X2 = X3 = 0
El VNA para esta combinacin de inversiones es:
VNA = 16(1) + 22(0) +12(0) + 8(1) = 24 (miles) dlares.
max z 16 x1 22 x2 12 x3 8 x4
EJEMPLO 1
Stockco se enfrenta a la restriccin de que se puede invertir
cuando mucho 14 000 dlares. Si se aplica el mismo
razonamiento utilizado. Se tiene:
Cantidad total invertida = 5x1 + 7x2 +4x3 +3x4
(en miles de dlares)
Por ejemplo, s X1 = 0, X2 = X3 = X4 = 1, entonces Stockco invierte en 2,3 y 4.
En este caso, Stokco tiene que invertir 7 + 4 + 3 = 14 (miles de) dlares.
5(0) +7(1) + 4(1) + 3(1) = 14 mi dlares.
5 X1 7 X 2 4 X 3 3 X 4 14
11
22/08/2016
EJEMPLO 2
Modifique la formulacin de Stockco para tomar en
cuenta cada una de las condiciones siguientes:
1. Stockco puede invertir cuando mucho en dos
inversiones.
2. Si Stockco invierte en 2, entonces tambin debe
invertir en 1
3. Si Stockco invierte en 2, no puede invertir en 4
Ejercicios de Aplicacin
Material:
Papel
Lapicero
Calculadora
12
22/08/2016
PROBLEMA 1
Gandhi Cloth Company fabrica tres tipos de prendas de
vestir: camisetas, shorts y pantalones. La elaboracin de
cada tipo de prenda requiere que Gandhi tenga
disponible el tipo de maquinaria apropiada. La
maquinaria necesaria para manufacturar cada tipo de
prenda se tiene que rentar a las tarifas siguientes:
maquinaria para camisetas, 200 dlares por semana;
maquinaria para shorts, 150 dlares por semana;
maquinaria para pantalones, 100 dlares por semana. La
hechura de cada tipo de prenda tambin requiere las
cantidades de tela y mano de obra que se indican en la
tabla 1. Estn disponibles cada semana 150 horas de
mano de obra y 160 yardas cuadradas de tela. El costo
unitario variable y el precio de venta para cada tipo de
prenda, se proporcionan en la tabla 2. Formule un PE
cuyo solucin maximice la utilidad semana de Gandhi.
Tabla 1: Recursos necesarias para Gandhi
Tipo de
Prenda
Mano de
Obra (H)
Tela (Yardas
cuadradas)
Camiseta
Shorts
Pantalones
Tabla 2: Ingresos e Informacin del costo para Gandhi
Tipo de
Prenda
Precio de
Venta (Dl)
Costo Variable
(Dl)
12
Shorts
Pantalones
15
Camiseta
PROBLEMA 2
Hay seis ciudades (ciudad 1 a 6) en el condado de Kilroy. EL
condado debe decidir donde construir la estacin de bomberos.
Asimismo, el condado quiere construir la cantidad mnima de
estaciones de bomberos necesarios para tener la certeza de que
por lo menos una est dentro de 15 minutos (tiempo de manejo) de
cada ciudad. Los tiempos (en minutos) necesarios para ir en
automvil de una ciudad a otra del condado se indican en la tabla
siguiente. Plantee un PE mediante el cual Kilroy sepa cuntas
estaciones de bomberos debe construir y dnde ubicarlas.
A
Desde
Ciudad 1
Ciudad 2
Ciudad 3
Ciudad 4
Ciudad 5
Ciudad 6
Ciudad 1
10
20
30
30
20
Ciudad 2
10
25
35
20
10
Ciudad 3
20
25
15
30
20
Ciudad 4
30
35
15
15
25
Ciudad 5
30
20
30
15
14
Ciudad 6
20
10
20
25
14
13
22/08/2016
PROBLEMA 3
La empresa Mirasol, planea la produccin de 2000
unidades de un producto, escritorio ejecutivo, que
se fabrican en tres mquinas. Los costos de
preparacin, los costos de produccin por unidad, y
la capacidad de produccin mxima para cada
mquina estn tabulados a continuacin. El objetivo
es minimizar el costo total de produccin del lote
requerido.
Mquina
Costo
Fijo
Costo de
Prod/Unid
Capacidad
(Nn Unid)
100
10
600
300
800
200
1200
PROBLEMA 4
Pegajoso, fbrica tres tipos de pegamento en dos lneas de produccin distintas, Hasta 7
trabajadores usan a la vez cada lnea. Cada trabajador recibe un pago de 500 dlares por
semana en la lnea de produccin 1, y 900 dlares por semana en la lnea de produccin 2.
Una semana de produccin en la lnea de produccin 1 cuesta 1 000 dlares para
organizarla y 2 000 dlares en la lnea de produccin 2. Durante una semana en una lnea
de produccin cada trabajador elabora la cantidad de unidades de pegamento que se
proporcionan en la tabla adjunta. Se tiene que elaborar a la semana, por lo menos, 120
unidades del pegamento 1, por lo menos 150 unidades del pegamento 2 y por lo menos s
200 unidades del pegamento 3. Formule un PE para minimizar el costo total por cumplir con
las demandas semanales.
Lnea de
Produccin
Pegamento
1
20
30
40
50
35
45
14
22/08/2016
EJERCICIO 5
Una fbrica de automviles construye tres tipos de autos:
Compactos, medianos y grandes. Los requerimientos de
materiales, manos de obra y el beneficio obtenido por cada tipo
de auto fabricado se muestra en cuadro siguiente; Actualmente, la
fbrica dispone de 6000 toneladas de materiales y 60000 horas
de mano de obra. Para que la produccin de un tipo de vehculo
sea econmicamente factible, se debe producir al menos 1000
unidades de cada tipo que se fabrique. Formule un PLE que
permita maximizar el beneficio de la fbrica.
Compacto
Mediano
Grande
Materiales
1.5
Mano de Obra
30
25
40
2000
3000
4000
Beneficio $
PROBLEMA 6
IBM computer, fabrica 4 tipos de computadores desktop, para el
mercado de Latinoamrica, estas computadores se venden en 4 pases,
Per, Chile, Argentina y Colombia; los tipos de computadores, mano de
obra, numero de microprocesadores , costos fijos y precio de venta se
detallan en la tabla siguiente, Se dispone de un total de 20000
microprocesadores y de 10000 horas hombre. Plantee un PE para
ayudar a IBM a maximizar sus utilidades si el costo de mano de obra por
hora es de 200 dlares
Desktop
Mano de
Obra
Micro
Costos Fijo de
Fabricacin
(dlares)
Precio de
Venta
(Dlares)
G-55
1 hora
10000
800
P-56
2 horas
13000
1000
I-56
3 horas
15000
1500
G-60
3 horas
16000
2000
15
22/08/2016
Problema 7
Mabe SA fabrica diferentes modelos de lavadoras, y dispone de dos plantas de
montaje (Fbrica1 y Fbrica2). Mabe est estudiando la fabricacin de 4 nuevos
modelos (Modelo1, Mdelo2, Modelo3 y Modelo4) para aprovechar el exceso de
capacidad de 2500 horas y 3.200 horas respectivamente, y ha recolectado los
siguientes datos de inters (tiempos en horas y costos en cientos de dlares):
a) Formular un modelo de optimizacin que se pueda utilizar para maximizar el beneficio
de Mabe, y escribir el modelo en PLE.
b) Obtener la solucin ptima e indicar si va a quedar exceso de capacidad en alguna de
las plantas. Utilice Lindo
P1
P2
Tiempo/u en F1
Tiempo/u en F2
2.8
3
Costo/u en F1
P3
P4
3.5
2.5
4.5
2.5
5.2
2.2
Costo/u en F2
2.8
2.3
4.8
2.1
Costo de Lanzamiento
600
500
700
400
Precio de venta
6.5
9.2
5.2
Problema 8
Motorsa, un fabricante de automviles, tiene cinco plantas obsoletas, que indicaremos como P1 hasta
P5. La administracin est considerando la modernizacin de estas plantas para la produccin de los
bloques motor y transmisiones de un nuevo modelo. El costo de modernizar cada una de las plantas
(en millones de dlares) y la capacidad de produccin despus de la modernizacin (en miles de
unidades) son como se muestra en la siguiente tabla. Se tiene prevista la produccin de 1.200.000
unidades del nuevo modelo.
a) Formular un modelo para determinar qu plantas va a modernizar Motorsa, y en cuales se fabricar
cada componente.
b) Aadir las siguientes restricciones impuestas por razones de poltica comercial:
1) Las plantas P2 y P3 no pueden ser modernizadas simultneamente,
2) Como mximo se pueden modernizar 3 plantas.
3) Se moderniza la Planta 5, tambin debe modernizarse la Planta 1
Planta
Costo
Capacidad
Bloques de motor
Capacidad
Transmisiones
P1
25
500
300
P2
35
800
400
P3
35
400
800
P4
40
900
600
P5
20
200
300
16
22/08/2016
EJERCICIO 10
Una joven pareja Juan y Cinthia quieren dividir las principales tareas del
hogar (ir de compras, cocinar, lavar platos y lavar ropa) entre los dos,
de manera que cada uno tenga dos obligaciones y que el tiempo total
para hacer estas tareas sea el mnimo. La eficiencia en cada una de las
tareas difiere entre ellos; la siguiente tabla proporciona el tiempo que
cada uno necesita para cada tarea. Formule un modelo de
programacin entera binaria y resolver por software.
Juan (1)
Cinthia (2)
Compras
(1)
4.5
4.9
Horas necesarias por semana
Cocinar
Lavar platos
(2)
(3)
7.8
3.6
7.2
4.3
Lavar ropa
(4)
2.9
3.1
EJERCICIO 11
SOUTHWESTERN AIRWAYS necesita asignar sus tripulaciones para cubrir todos sus vuelos programados.
Se estudiara el problema de asignar tres tripulaciones con base en San Francisco (SF) a los vuelos
enumerados en la tabla. Las otras 12 columnas muestran 12 secuencias de vuelos factibles de una
tripulacin. (Los nmeros en cada columna indican el orden de los vuelos.) Es necesario elegir tres de
estas secuencias (una por tripulacin) de tal manera que se cubran todos los vuelos. (Se permite tener mas
de una tripulacin en un vuelo, en el cual los miembros de la tripulacin adicional volaran como pasajeros,
pero los contratos colectivos de trabajo requieren que se pague el tiempo de la tripulacin adicional como si
estuviera en horario de trabajo)
El costo de asignar una
tripulacin a una secuencia
de vuelos especifica se
muestra (en miles de
dlares) en el rengln
inferior de la tabla. El
objetivo es minimizar el
costo total de asignar las
tres tripulaciones de manera
que cubran todos los vuelos.
17
22/08/2016
EJERCICIO 12
Datos:
1 Kgr. De madera =
1 pie
Productos
8 horas da
26 das mes
MO:
4.5 hr
5hr
4.3 hr
Madera:
40 pies
20 pies
22 pies
MO Acabado: 1 hr
Precio Venta:
100 $
0.7hr
80 $
0.4 hr
90 $
Recursos:
11 Toneladas
16 trabajadores
2 Trab. Acabado
Las bancas se
producen como
mnimo 25 und.
Las mesas de noche
deben ser por lo
menos el doble de
las sillas menos 10
unidades
Los costos de
preparacin de
planta para la
fabricacin de cada
producto es:
10000, 7500 y
12500
18
