Prof.

Rosa Delgadillo


Modelos de Programacin Entera

Problema de Transporte
1. Una empresa distribuidora desea establecer un plano de distribucin de una misma clase de
productos desde sus 3 almacenes para sus 4 clientes. Los datos sobre costos de transporte por
unidad de producto, las demandas y las ofertas son dados en la siguiente tabla

Cliente 1 Cliente 2 Cliente 3 Cliente 4 Oferta
Almacn 1 1.0 1.1 1.1 1.2 70
Almacn 2 1.1 0.9 1.2 1.0 80
Almacn 3 1.1 1.0 1.1 1.3 40
Demanda 50 30 50 60

2. La compaa Bass Gravel ha recibido un contrato para abastecer de grava a tres nuevas
carreteras proyectadas a localizarse en las ciudades de Greenville, Fountain y Ayden. Los
ingenieros constructores han estimados las cantidades requeridas de grava que sern
necesarias en los tres proyectos de construccin de carreteras:

Proyecto

Ubicacin
Requerimientos
semanales (camin)
A Greenville 72
B Fountain 102
C Ayden 41
Total 215

La Bass Company tiene tres plantas de grava localizada en las ciudades de Kinston, Wilson y
Bethel. La grava requerida para los proyectos de construccin se puede abastecer de estas tres
plantas. El jefe despachador ha calculado las cantidades de grava que pueden ser abastecidas
por cada planta.


Planta

Ubicacin
Inventario disponible
por semana (camin)
X Kinston 60
Y Wilson 82
Z Bethel 77
Total 219
Los costos de entrega en dlares por carga de camin son:

P R O Y E C T O S
PLANTAS A B C
W 4 8 8
X 16 24 16
Y 8 16 24
Prof. Rosa Delgadillo



Determine un programa para los embarques de cada planta a cada proyecto, de tal manera que
minimice el costo total de transporte.
3. Una empresa industrial fbrica un producto en 3 plantas (Piura, Lima y Arequipa),
abasteciendo el mercado nacional (Norte, Centro, Sur y Oriente).
A continuacin se muestran los costos de transporte ($/unidad), los costos de distribucin por
regin ($/unidad), el precio de venta ($/unidad). Adems para cada planta se da su capacidad
mxima de produccin (unidades/ao) y el costo de produccin variable ($/unidad).

Norte Centro Sur Oriente Capacidad Costo de produc.
Piura 100 300 500 600 900 000 3 500
Lima 300 100 200 400 1 900 000 3 000
Arequipa 500 200 100 700 1 400 000 3 300
Distribucin 1 000 1 500 2 000 2 500
Precio de vta 5 500 6 000 6 500 7 000
Demanda 800 000 1 300 000 1 000 000 500 000

Adems la empresa soporta costos fijos de 2000,000 de dlares anuales. Determine cual es el
plano de distribucin.
Problema de Asignacin
4. Metal Machine hace trabajo de metalurgia por encargo, para varias plantas locales. Metal
actualmente tiene tres trabajos que hacer A, B y C. Metal tambin tres mquinas X Y Z para
realizar estos trabajos. Cualquiera de los trabajos puede ser procesado totalmente en
cualquiera de las mquinas. Determine una asignacin de trabajos para las mquinas (uno a
uno) de forma a minimizar el costo total. Considere la siguiente tabla de costos:
Mquina
Trabajo M1 M2 M3
T1 25 31 35
T2 15 20 24
T3 22 19 17
Tabla de costos en $


5. Un bufete de abogados ha aceptado 6 nuevos casos, cada uno de los cuales puede ser
llevado adecuadamente por cualquiera de los 6 asociados ms recientes.
Debido a la diferencia de experiencia y prctica, los abogados emplearn distintos tiempos en
los casos. Uno de los asociados ms experimentados ha estimado las necesidades de tiempo
en horas, de la siguiente manera:





Prof. Rosa Delgadillo


Abogado Caso 1 Caso 2 Caso 3 Caso 4 Caso 5 Caso 6
1 145 122 130 95 115 121
2 80 63 85 48 78 71
3 121 107 93 69 95 97
4 118 83 116 80 105 100
5 97 75 120 80 111 96
6 112 90 109 74 101 98

Determine la forma ptima de asignar los casos a los abogados, de manera que cada uno de
ellos se dedique a un caso diferente y que el tiempo total de horas sea mnimo.

Problema de Seleccin de Proyectos
6. Una fundacin en ciencia y tecnologa desea seleccionar proyectos de desarrollo cientfico
tecnolgico para ser ejecutados en el prximo periodo. Los datos sobre costos y utilidades en
miles de dlares son dados a seguir:

Proyecto P1 P2 P3 P4 P5 P6 P7 P8
Costo 10 16 17 18 21 32 12 16
Utilidad 15 19 22 25 28 36 30 20


Seleccione que proyectos se deben ejecutar de forma que presenten mayor suma de utilidades
sabiendo que la organizacin tiene un capital de inversin de $65,000.



7. Para el problema anterior, suponga que cada proyecto solo presenta utilidad si este es
completado en su totalidad. Considere el riesgo de no completar cada proyecto como sigue:

Proyecto P1 P2 P3 P4 P5 P6 P7 P8
Riesgo (%) 15 10 12 8 11 12 13 8

Que proyectos deben ser seleccionados de forma que presenten mayor suma de utilidad
esperada.



Problema: Cartera de Inversin
8. Un capitalista desea invertir en la compra de paquetes de acciones de la bolsa de valores.
Los datos sobre los costos y utilidades en miles de dlares por cada paquete y los riesgos en
porcentaje sobre el no retorno son dados en la siguiente tabla

Empresas: E1 E2 E3 E4 E5 E6 E7 E8
Costo ($) 10 16 17 18 21 32 12 16
Utilidad ($) 15 19 22 25 28 36 30 20
Riesgo (%) 15 10 12 8 11 12 13 8
Prof. Rosa Delgadillo


Determine donde y cuanto debe invertir el capitalista de forma a tener mxima utilidad
esperada. Suponga que el capital de inversin es de $100,000.

Problema de Programacin de Autobuses
9. Una empresa de transporte desea programar la flota de autobuses para cubrir al mnimo las
necesidades de transportes en una lnea. Despus de recolectar informacin el ingeniero de la
municipalidad advierte que el nmero mnimo de autobuses que se necesita para cubrir la
demanda flucta con la hora del da. Estudiando los datos ms a fondo se descubri que el
nmero necesario para cubrir la demanda de autobuses se puede asumir constante en
intervalos sucesivos de 4 horas cada uno. La siguiente tabla resume los hallazgos del
ingeniero. Se decidi que cada unidad debe operar solo 8 horas sucesivas al da.

Horario Requerimiento de autobuses
0:00 4:00 4
4:00 8:00 8
8:00 12:00 10
12:00 16:00 7
16:00 20:00 12
20:00 0:00 4


Cortes de Una Dimensin (Desperdicios)
10. Una empresa metal mecnica tiene los siguientes requerimientos sobre piezas de
aluminio:
Tamao 2.5 3.5 4.5
Demanda 15 20 30
Los tamaos son dados en metros. Las piezas debern ser obtenidas a travs de cortes sobre
piezas de tamao de 12mts. Determine los planes de corte ptimos para el menor desperdicio
de piezas de tamao de 12mts.
11. Un fabricante de lminas metlicas recibe un pedido especial para producir 2000 lminas
de tamao 2x 4 y lminas de tamao 4 x 7. Se dispone de dos rollos de lminas estndar de
tamaos 10x 3000 y 11 x 2000
El personal del departamento de Ingeniera decide que los tres siguientes patrones de corte
son adecuados para satisfacer el pedido






Formule el problema para satisfacer el pedido y minimizar el desperdicio.




Patrn 1 Patrn 2 Patrn 3
2 7
4
2 2 2 2 2 2 2 7
4 4
Prof. Rosa Delgadillo


Problema de Transbordo
12. Una empresa debe transportar 100 unidades de un producto a partir de una localidad 1
para as localidades 2, 3 y 4 en las cantidades de 40, 30 y 30 unidades respectivamente. Las
tarifas areas (en dlares por unidad) entre as localidades son dadas en la siguiente tabla:

Localidad
Localidad 1 2 3 4
1 - 38 60 35
2 38 - 38 80
3 60 38 - 20
4 35 80 20 -

Determine un esquema de expedicin para satisfacer la demanda requerida a un costo de
flete total mnimo. Es permitida la expedicin por puntos intermedios.


13. La red de la figura siguiente muestra las rutas para el traslado de automviles desde 3
plantas (nodos 1, 2, 3) hasta cinco agentes vendedores (nodos del 6 al 10) a travs de dos
centros de distribucin (nodos 4 y 5). Suponga que el costo unitario del traslado del nodo i al
nodo j es .
ij
c Responda:
a) Elabore un modelo de transbordo asociado al problema
b) Reformule el problema suponiendo que se permite el transbordo entre los agentes.

Plantas Centros de Agentes
distribucin

1000 1800



500



1500 750



1000


1200
650




1
6
3
2
5
4
10
9
8
7
Prof. Rosa Delgadillo


Problema de la Ruta Ms Corta
14. Determine la ruta ms corta entre los nodos 1 y 7 de la red de la siguiente figura. La
distancia entre dos nodos es dada en la arista.



1
5 4
5 7 9 2

8
4 6 1
3
5 7
2 3

3





Planeamiento de la produccin

15. Una compaa de artculos electrnicos produce tres lneas de productos: transistores,
micromdulos y circuitos armados. Tiene cuatro reas de proceso:

rea I Produccin de transistores

rea II Ensamblaje de circuitos
rea III Control de transistores y mdulos
rea IV Prueba de circuitos y embalaje

La produccin de un transistor requiere:
0.2 horas-hombre en el rea I
0.6 horas-hombre en el rea II
S/ 80 en costos directos

La produccin de un micromdulo requiere:
0.5 horas-hombre en el rea II
0.6 horas-hombre en el rea III
4 transistores
S/ 60 en costos directos

La produccin de un circuito armado requiere:
0.2 horas-hombre en el rea II
0.6 horas-hombre en el rea IV
2 transistores
4 micromdulos
S/ 30 en costos directos
1 7
3
6
5
4
2
Prof. Rosa Delgadillo


Cualquiera de los tres productos de puede vender en cantidades ilimitadas los precios de
S/.300, S/ 1200 y S/ 3500 respectivamente. Si hay 300 horas-hombre disponibles en cada una
de las cuatro reas de produccin. Formule el problema para obtener una ganancia mxima.

16. Una compaa compra los ensamblajes A y B y produce el reloj C. Cada reloj requiere 2
ensamblajes A 1 ensamblaje A y 2 ensamblajes B. La fbrica tiene una capacidad de
produccin de 8000 relojes por trimestre. La disponibilidad de ensamblajes en el mercado es
variable y los relojes son requeridos en diferentes cantidades cada trimestre.

TRIMESTRE 1 2 3 4
ENSAMBLAJE A 9 000 10 000 8 000 7 000
ENSAMBLAJE B 8 000 13 000 11 000 10 000
RELOJES C 5 000 10 000 7 000 6 000

El almacenaje de relojes es sumamente caro y se debe hacer mnima la cantidad llevada al
inventario de un trimestre a otro. Al comienzo del ao hay 3000 ensamblajes A y 2000
ensamblajes B en inventario; y al menos la mitad de esa cantidad debe ser dejada en
inventario al final del ao. Modelar el problema descrito.

17. Una compaa que ensambla y compra radares al ejercito, se ha comprometido a cumplir
con el siguiente pedido:
Envo Requerimiento Acumulado

1 Abril 300 300
1 Mayo 400 700
1 Junio 300 1000

Por cada radar entregado recibe 500 dlares. Debe cumplir con entregar las 1000 unidades en
total. Si el 1 de alguno de esos meses no ha cumplido con enviar el total acumulado a esa
fecha tiene una penalidad de $ 50 por cada unidad y si por el contrario, produce ms unidades
que el total acumulado a ese momento, no puede enviarlos al ejercito , pues no los recibiran y
deber guardarlos en un almacn a un costo de $10 por unidad.
Un radar requiere de 43 horas de tiempo de ensamble. Un hombre entrenado ( con ms de un
mes de experiencia) produce 172 por mes en un tiempo normal, mientras que un hombre
nuevo (sin experiencia) tiene una eficiencia de 75% y produce el equivalente a 129 horas
estndar por mes.
A los trabajadores se les paga $5 /hora en su tiempo (jornada) normal y $7.5 / hora en sobre
tiempo por mes. A los trabajadores con experiencia se les permite hasta 35 horas de sobre
tiempo por mes, pero a los nuevos no se les permite. Cada hombre tiene garantizado un
ingreso de $860 por mes. Al final del mes, el 5% del personal renuncia, siendo necesario
contratar personal nuevo el 1 de cada mes a un costo de $200 (costo de pruebas)
El 1 de marzo la empresa cuenta con 60 operadores entrenados y si se desea se puede
contratar nuevo personal inmediatamente.
El 1 de junio la empresa desea tener por lo menos 80 operarios, pues tiene comprometido
otro nuevo contrato. Cul es el modelo de optimizacin del funcionamiento de la planta para
cumplir con el pedido?



Prof. Rosa Delgadillo


Programacin de maquinas (clulas de fabricacin flexibles tareas independientes)
18. Una clula de fabricacin flexible consta de 3 maquinas CNC (control numrico
computarizado), las cuales estn programadas para ejecutar 5 tipos de tareas diferentes con
los siguiente tiempos de procesamiento en segundos:
Maquina | Tareas j1 j2 j3 j4 j5
M1 3.0 2.0 2.5 3.2 2.5
M2 3.2 2.5 3.2 3.0 3.2
M3 2.8 3.0 3.2 2.8 3.0

Determine un programa de designacin de maquinas a tareas para atender un lote de tareas
con el menor tiempo posible. Considere el siguiente lote de tareas: j1, j1, j2, j3, j3, j4, j4, j4,
j5, j5.


Programacin de maquinas (clulas de fabricacin flexibles tareas dependientes)
19.Una clula de fabricacin flexible consta de 3 maquinas CNC (control numrico
computarizado) homogneas, las cuales estn programadas para ejecutar 6 tipos de tareas
diferentes con los siguientes tiempos de procesamiento en segundos:
Tareas t1 t2 t3 t4 t5
Tiempos 5 2.3 4 5 6
Considere la siguiente relacin de precedencia entre las tareas:







Determine un programa de designacin de maquinas a tareas para atender un lote de tareas
con el menor tiempo posible. Considere el siguiente lote de tareas: t1, t1, t2, t3, t3, t4, t4, t4,
t5, t5.

t1
t5
t4
t3 t2