22/08/2016

INVESTIGACION DE OPERACIONES II

Ing. Enrique M. Avendaño Delgado

[email protected]

REGLAS DE CONVIVENCIA:

• PUNTUALIDAD
Hora de Inicio de Clase: Lunes 14.30 pm
Laboratorio: Lunes 11.50 am y 12.30 pm

• ASISTENCIA
Límite de Faltas: 11

• Exámenes en al Fecha
Trámite 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 Teoría: 3.00 pm (10 min)

1
 22/08/2016

AULA VIRTUAL

2
 22/08/2016

AULA VIRTUAL

FORMAS DE COMUNICACIÓN:

Al término de Clase

[email protected]

facebook.com/enrique.avendanodelgado

3
 22/08/2016

REGLAS

• ASISTENCIA
• PUNTUALIDAD
• EXAMENES EN LA FECHA
• PARTICIPACION EN CLASES
• HORIZONTALIDAD

DELEGADOS DE CLASE:

4
 22/08/2016

Unidad 1
Modelos Determinísticos De Decisión

PROGRAMACIÓN ENTERA Y
BINARIA

Ing. Enrique M. Avendaño Delgado

[email protected]

INTRODUCCIÓN

• Hasta ahora hemos visto los problemas de programación lineal en el dominio de los
reales. Sin embargo, en muchos modelos algunas o todas las variables de decisión
deben ser enteras. Estos modelos son conocidos como modelos de programación lineal
entera (ILP).
• A primera vista podría parecer más fácil resolver problemas con restricción de enteros,
ya que transforman un problema continuo en un problema discreto. Los modelos de
programación lineal entera se pueden clasificar en:

Modelo Tipos de Variables de Decisión

Completamente entero
Todas son enteras
(AILP)
Algunas, pero no todas son
Mixto (MILP)
enteras
Binaria (BILP) Todas son binarias (0 ó 1)

5
 22/08/2016

PROGRAMACIÓN ENTERA

• La PE tiene gran cantidad de aplicaciones en todos los campos.

• Hay problemas que no pueden resolverse con las técnicas actuales por:
– Disponibilidad de tiempo de ordenador
– Capacidad de memoria
• Para evitar esto parece sensato calcular la solución de un PE redondeando la solución
continua.
• Pero el redondeo no es aconsejable debido a:
– La solución redondeada no es necesariamente óptima. En muchos casos, ni
siquiera estará cera del óptimo.
– La solución redondeada puede no ser factible.

PROGRAMACIÓN ENTERA

• Programación Entera es un termino general para

los modelos de programación matemática que
presentan condiciones de integridad (condiciones
que estipulan que algunas o todas las variables
de decisión deben tener valores enteros). Ya
hemos apuntado que los modelos de
programación lineal entera son modelos de
programación lineal que tienen la característica
adicional de que algunas de las variables de
decisión deben tener valores enteros. Existen
diversas clasificaciones de esta categoría 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 decisión tengan valores enteros

6
 22/08/2016

IMPORTANCIA DE LAS SOLUCIONES

ENTERAS

• Existen muchos problemas importantes en los que la “solución

redondeada” simplemente no funciona.
• Por ejemplo, si la solución de un modelo de programación 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 decisión de construir
11 de los primeros y 6 de los segundos, o cualquier otra
solución redondeada. La magnitud del rendimiento y la
asignación de recursos asociados con cada unidad del
problema aconsejan determinar la mejor solución entera
posible.

IMPORTANCIA DE LAS SOLUCIONES ENTERAS

• Con otro ejemplo, sé vera que muchos modelos usan variables enteras
para indicar decisiones lógicas. Por ejemplo, veremos que problemas
en los que queramos que una variable “x” sea igual a 1 si vamos a
construir un almacén o x sea igual a cero (si-no). Supóngase que la
solución de una versión de programación lineal de este problema
produce un valor no entero, por ejemplo, x = 0,38. Vemos que este
valor no contiene información aprovechable como solución al problema
real.

7
 22/08/2016

IMPORTANCIA DE LAS SOLUCIONES ENTERAS

• Es claro que no podemos construir 0,38 de un almacén. Es cierto que

podemos elegir almacenes de diversos tamaños, pero en todo caso, o
bien tenemos un almacén o no lo tenemos. Se podría suponer que en un
caso como este se trataría de redondear al entero más próximo (0 en
este caso) como forma de salvar la dificultad. Por desgracia, esto no
garantiza que se obtenga una buena (y no digamos óptima) solución.
• 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 programación lineal si no fuese por el
requerimiento de que sean enteros los valores de algunas variables
de decisión, en los que no se puede encontrar una buena solución
mediante el uso del método Simplex seguido del redondeo de los
valores óptimos resultantes para variables de decisión. Estos
problemas deben ser resueltos mediante algoritmos especialmente
diseñados para resolver problemas de programación entera.

8
 22/08/2016

VARIABLES

PLANEAMIENTO DE PROBLEMAS
DE PROGRAMACIÓN ENTERA

9
 22/08/2016

EJEMPLO 1:
PE DE UN PRESUPUESTO DE CAPITAL (*)

• Stockco proyecta cuatro inversiones. La inversión 1 genera un valor neto actual

(VNA) de 16 000 dólares; la inversión 2, un VNA de 22 000 dólares; la inversión 3,
un VNA de 12 000 dólares, y la inversión 4, una VNA de 8 000 dólares. Para cada
inversión se requiere una cierta salida de efectivo en el tiempo presente; la
inversión 1, 5 000 dólares; la inversión 2, 7 000 dólares; la inversión 3, 4 000
dólares; la inversión 4, 3 000 dólares. Dispone en la actualidad de 14 000 dólares
para invertir. Plantee un PE cuya solución le indique a Stockco el modo de
maximizar el VNA obtenido de las inversiones 1 a 4.

(*) Investigación de Operaciones – W. Winston Pág. 478

EJEMPLO 1

Solución:

X j ( j  1, 2,3, 4)  10 SiSi senoefectua

se efectua la inversion 
la inversion

Por ejemplo: X2 = 1 si invierte en la inversión 2, pero X2 = 0 no se invierte

El VNA que logra Stockco (en miles de dólares) 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 dólares. Esta combinación de
inversiones corresponde a:

• X1 = X4 = 1, X2 = X3 = 0

• El VNA para esta combinación de inversiones es:

• VNA = 16(1) + 22(0) +12(0) + 8(1) = 24 (miles) dólares.

max z  16 x1  22 x2 12 x3  8 x4

EJEMPLO 1

• Stockco se enfrenta a la restricción de que se puede invertir

cuando mucho 14 000 dólares. Si se aplica el mismo
razonamiento utilizado. Se tiene:

Cantidad total invertida = 5x1 + 7x2 +4x3 +3x4

(en miles de dólares)
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) dólares.

5(0) +7(1) + 4(1) + 3(1) = 14 mi dólares.

5 X1  7 X 2  4 X 3  3 X 4  14

11
 22/08/2016

EJEMPLO 2

Modifique la formulación 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 también debe
invertir en 1
3. Si Stockco invierte en 2, no puede invertir en 4

Ejercicios de Aplicación
Material:

•Papel
•Lapicero
•Calculadora

12
 22/08/2016

PROBLEMA 1
Tabla 1: Recursos necesarias para Gandhi
Gandhi Cloth Company fabrica tres tipos de prendas de
vestir: camisetas, shorts y pantalones. La elaboración de Tipo de Mano de Tela (Yardas
Prenda Obra (H) cuadradas)
cada tipo de prenda requiere que Gandhi tenga
disponible el tipo de maquinaria apropiada. La Camiseta 3 4
maquinaria necesaria para manufacturar cada tipo de Shorts 2 3
prenda se tiene que rentar a las tarifas siguientes: Pantalones 6 4
maquinaria para camisetas, 200 dólares por semana;
maquinaria para shorts, 150 dólares por semana; Tabla 2: Ingresos e Información del costo para Gandhi

maquinaria para pantalones, 100 dólares por semana. La

Tipo de Precio de Costo Variable
hechura de cada tipo de prenda también requiere las Prenda Venta (Dól) (Dól)
cantidades de tela y mano de obra que se indican en la Camiseta 12 6
tabla 1. Están disponibles cada semana 150 horas de
Shorts 8 4
mano de obra y 160 yardas cuadradas de tela. El costo
unitario variable y el precio de venta para cada tipo de Pantalones 15 8
prenda, se proporcionan en la tabla 2. Formule un PE
cuyo solución maximice la utilidad semana de Gandhi.

PROBLEMA 2
• Hay seis ciudades (ciudad 1 a 6) en el condado de Kilroy. EL
condado debe decidir donde construir la estación de bomberos.
Asimismo, el condado quiere construir la cantidad mínima 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
automóvil de una ciudad a otra del condado se indican en la tabla
siguiente. Plantee un PE mediante el cual Kilroy sepa cuántas
estaciones de bomberos debe construir y dónde ubicarlas.

A
Desde Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Ciudad 5 Ciudad 6
Ciudad 1 0 10 20 30 30 20
Ciudad 2 10 0 25 35 20 10
Ciudad 3 20 25 0 15 30 20
Ciudad 4 30 35 15 0 15 25
Ciudad 5 30 20 30 15 0 14
Ciudad 6 20 10 20 25 14 0

13
 22/08/2016

PROBLEMA 3

• La empresa Mirasol, planea la producción de 2000

unidades de un producto, escritorio ejecutivo, que
se fabrican en tres máquinas. Los costos de
preparación, los costos de producción por unidad, y
la capacidad de producción máxima para cada
máquina están tabulados a continuación. El objetivo
es minimizar el costo total de producción del lote
requerido.

Máquina Costo Costo de Capacidad

Fijo Prod/Unid (Nún Unid)
1 100 10 600
2 300 2 800
3 200 5 1200

PROBLEMA 4

Pegajoso, fábrica tres tipos de pegamento en dos líneas de producción distintas, Hasta 7
trabajadores usan a la vez cada línea. Cada trabajador recibe un pago de 500 dólares por
semana en la línea de producción 1, y 900 dólares por semana en la línea de producción 2.
Una semana de producción en la línea de producción 1 cuesta 1 000 dólares para
organizarla y 2 000 dólares en la línea de producción 2. Durante una semana en una línea
de producción 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.

Línea de Pegamento
Producción
1 2 3

1 20 30 40
2 50 35 45

14
 22/08/2016

EJERCICIO 5

Una fábrica de automóviles 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
fábrica dispone de 6000 toneladas de materiales y 60000 horas
de mano de obra. Para que la producción de un tipo de vehículo
sea económicamente factible, se debe producir al menos 1000
unidades de cada tipo que se fabrique. Formule un PLE que
permita maximizar el beneficio de la fábrica.

Compacto Mediano Grande

Materiales 1.5 3 5
Mano de Obra 30 25 40
Beneficio $ 2000 3000 4000

PROBLEMA 6

IBM computer, fabrica 4 tipos de computadores desktop, para el

mercado de Latinoamérica, estas computadores se venden en 4 países,
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 dólares

Desktop Mano de Micro Costos Fijo de Precio de

Obra Fabricación Venta
(dólares) (Dólares)
G-55 1 hora 1 10000 800
P-56 2 horas 1 13000 1000
I-56 3 horas 2 15000 1500
G-60 3 horas 4 16000 2000

15
 22/08/2016

Problema 7
• Mabe SA fabrica diferentes modelos de lavadoras, y dispone de dos plantas de
montaje (Fábrica1 y Fábrica2). Mabe está estudiando la fabricación 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 interés (tiempos en horas y costos en cientos de dólares):
a) Formular un modelo de optimización que se pueda utilizar para maximizar el beneficio
de Mabe, y escribir el modelo en PLE.
b) Obtener la solución óptima e indicar si va a quedar exceso de capacidad en alguna de
las plantas. Utilice Lindo

P1 P2 P3 P4
Tiempo/u en F1 3 3.5 5 2.5
Tiempo/u en F2 2.8 4 4.5 2
Costo/u en F1 3 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 7 9.2 5.2

Problema 8
Motorsa, un fabricante de automóviles, tiene cinco plantas obsoletas, que indicaremos como P1 hasta
P5. La administración está considerando la modernización de estas plantas para la producción de los
bloques motor y transmisiones de un nuevo modelo. El costo de modernizar cada una de las plantas
(en millones de dólares) y la capacidad de producción después de la modernización (en miles de
unidades) son como se muestra en la siguiente tabla. Se tiene prevista la producción 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) Añadir las siguientes restricciones impuestas por razones de política comercial:
1) Las plantas P2 y P3 no pueden ser modernizadas simultáneamente,
2) Como máximo se pueden modernizar 3 plantas.
3) Se moderniza la Planta 5, también debe modernizarse la Planta 1
Planta Costo Capacidad Capacidad
Bloques de motor 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 mínimo. 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
programación entera binaria y resolver por software.

Horas necesarias por semana

Compras Cocinar Lavar platos Lavar ropa
(1) (2) (3) (4)
Juan (1) 4.5 7.8 3.6 2.9
Cinthia (2) 4.9 7.2 4.3 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
tripulación. (Los números en cada columna indican el orden de los vuelos.) Es necesario elegir tres de
estas secuencias (una por tripulación) de tal manera que se cubran todos los vuelos. (Se permite tener mas
de una tripulación en un vuelo, en el cual los miembros de la tripulación adicional volarían como pasajeros,
pero los contratos colectivos de trabajo requieren que se pague el tiempo de la tripulación adicional como si
estuviera en horario de trabajo)

El costo de asignar una

tripulación a una secuencia
de vuelos especifica se
muestra (en miles de
dólares) en el renglón
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 =
Productos 1 pie

8 horas día
26 días mes
Las bancas se
MO: 4.5 hr 5hr 4.3 hr producen como
Madera: 40 pies 20 pies 22 pies mínimo 25 und.
Las mesas de noche
MO Acabado: 1 hr 0.7hr 0.4 hr deben ser por lo
Precio Venta: 100 $ 80 $ 90 $ menos el doble de
las sillas menos 10
Recursos: unidades
Los costos de
preparación de
planta para la
fabricación de cada
producto es:
10000, 7500 y
11 Toneladas 16 trabajadores 2 Trab. Acabado 12500

18