Ejercicios Programacion Lineal Entera, Binaria y Mixta

lez Brevis
Pablo Gonza
Cristian Palma Infante
Daniel Contesse Strauss
Matas Vaccarezza Sevilla

1. Mini-Market. Un mini-market atiende 24 horas continuas y tiene los siguientes requerimientos mnimos de n
umero de cajeros.
Hora

03:00-7:00

07:00-11:00

11:00-15:00

15:00-19:00

19:00-23:00

23:00-03:00

Cajeros

20

14

20

10

El primer periodo sigue inmediatamente despues del u

ltimo periodo. Un cajero trabaja
ocho horas consecutivas, comenzado al principio de uno de los seis periodos. Formule
un modelo que permita determinar la cantidad de cajeros que deben comenzar en cada
periodo de modo minimizar la cantidad de cajeros contratados.
2. Autos. Una empresa automotriz esta considerando producir tres tipos de auto: compacto,
mediano y grande. Los recursos requeridos y el beneficio esperado por cada tipo de auto
son
Tipo de auto
Compacto Mediano Grande

Item
Acero requerido (ton)
Mano obra requerida (hr)
Beneficio (US$)

1,5
30
2

3
25
3

5
40
4

Actualmente existen 6.000 toneladas de acero disponible y se cuenta con una capacidad
maxima de 60.000 horas de mano de obra. Para que la produccion de un tipo de auto
sea economicamente factible, al menos 1.000 unidades de ese tipo de auto deben ser
producidas. Formule un modelo que permita decidir que tipo de auto y cuantas unidades
producir de modo de maximizar el beneficio.
n. Sin Inc., una productora de television, el proximo a
3. Productora de Televisio
no
ofrecera tres tipos de comerciales. La gerencia quiere determinar cuales seran las inversiones para el proximo a
no, cuales seran las cantidades de comerciales a producir con la
nueva tecnologa y cuales seran las utilidades que se generaran.
Para realizar cada comercial se debe pasar por tres etapas. La primera es la etapa creativa, en donde se idea la tematica del comercial y se realiza el guion. La segunda etapa
consiste en realizar distintas tomas de escenas para luego pasar a la tercera etapa, la postproduccion y edicion. En el siguiente cuadro se muestran los tiempos promedio requeridos
en cada una de las etapas, los ingresos percibidos por cada tipo de comercial en libras
esterlinas, y la disponibilidad de horas para cada etapa.

Etapa
Creativa (hr)
Grabacion (hr)
Post-Produccion (hr)
Beneficios ()

Tipo de Comercial
A
B
C
2
3
3

5
4
3

800 700

4
6
5
950

Disponibilidad
(horas)
70
86
78

La empresa esta considerando la posibilidad de aumentar la disponibilidad de tiempo,

invirtiendo en equipos mas eficientes para cada proceso. Para ello, se pueden llevar a
cabo algunas de las posibilidades indicadas en el siguiente cuadro.
Etapa
Incremento (hr)
Inversion ()

Creativa
10
1600

15
1700

Grabacion

Post-Produccion

8
1700

9
1600

12
1800

13
1900

A lo sumo se puede realizar un tipo de incremento para cada etapa. Gracias a un estudio
de mercado se conocen tanto la demanda mnima como la maxima de estos comerciales,
las que se aprecian en el cuadro adjunto.
Comerciales

Mnima

Maxima

A
B
C

6
3
7

17
8
20

Ademas, se sabe que la inversion total no puede exceder los 4.200. Modele el problema
que enfrenta Sin Inc. utilizando programacion lineal entera.
ctricas. Se tienen n centrales electricas que pueden abastecer de energa
4. Centrales Ele
a m ciudades. Se conoce la demanda por electricidad en un periodo y el problema consiste
en decidir que centrales operar en ese periodo para satisfacer la demanda. Asuma que la
demanda de cada ciudad pueden ser abastecida por una o mas centrales.
Si se decide operar la central i, se incurre en un costo de puesta en marcha de ki . Sea
dj la demanda en la ciudad j, ei la capacidad de generacion de la central i y cij el costo
unitario de transmision de energa electrica desde la central i a la ciudad j.
Utilize programacion lineal entera para modelar esta situacion. Asuma que el costo de
operacion es igual en todas las centrales y por lo tanto no es relevante en la decision.
n de Ma
quinas. Se tiene la posibilidad de comprar hasta I 0 de un total de
5. Adquisicio
I maquinas disponibles para procesar J trabajos. El costo ($) de procesar el trabajo j en
la maquina i es cij y el consumo de tiempo (hr) asociado es aij . El tiempo (hr) disponible
de maquina i para el perodo en estudio es bi . Formule un modelo que permita decidir la
compra de maquinas y la asignacion de trabajos a ellas a mnimo costo sabiendo que fi
es el costo ($) de compra de la maquina i.
n de Archivos. Usted ha sido asignado para ordenar los archivos de datos
6. Clasificacio
de una compa
nia en dos sistemas de almacenamiento. El peso en megabytes (MB) y tipo
clasificacion de archivo se encuentran en la siguiente tabla

Archivo

Tipo

Peso (MB)

1
2
3
4
5
6
7
8

Fotos
Videos
Fotos
Videos
Fotos
Videos
Otros
Fotos/Video

4
5
3
2
4
3
5
4

Se le pide que el contenido de cada dispositivo de almacenamiento cumpla con las siguientes condiciones
(a) Cada dispositivo debe tener dos archivos de fotos
(b) El primer dispositivo debe al menos tener tres archivos de video
(c) Ya sea el archivo 5 o el 6 tiene que ir en el primer dispositivo
(d) Si los archivos 2 y 4 estan en el primer dispositivo, entonces el archivo 5 tiene que ir
en el segundo dispositivo.
(e) Cada dispositivo debe tener entre 14 y 16 megabytes.
Formule el problema como uno de programacion lineal entera.
n de Plantas y Bodegas. Una compa
7. Locacio
na dispone de U posibles ubicaciones
para sus plantas de produccion y de B posibles ubicaciones para sus bodegas de almacenamiento. La compa
na produce un u
nico producto que debe distribuir a sus C clientes,
cuya demanda mnima se debe satisfacer a mnimo costo. Toda la produccion debe pasar
por una bodega de almacenaje antes de ser distribuida a los clientes. Instalar una planta
en la ubicacion i cuesta CIPi y una bodega en la ubicacion j cuesta CIBj , mientras que
producir una unidad de producto en una planta en la ubicacion i cuesta CP Pi y almacenar
una unidad de producto en la bodega j cuesta CABj . Adicionalmente, el costo unitario de
transporte desde una planta i a una bodega j es F P Bij , y el costo unitario de transporte
entre una bodega j y un cliente k es F BCjk . La capacidad de produccion maxima de una
planta en la ubicacion i es CAP Pi y la capacidad de almacenamiento maximo de una
bodega en j es CAP Bj . Por lo tanto, el problema de decisiones consiste en seleccionar la
ubicacion de la(s) planta(s) de produccion, la ubicacion de la(s) bodega(s) y determinar
los flujos de su produccion a ser enviados entre cada planta y las bodegas, y entre cada
bodega y los clientes a los que se debe abastecer. Formule un modelo que resuelva el problema, definiendo claramente sus parametros, coeficientes y variables de decision. Indique
claramente que hace cada restriccion del modelo.
n de Calendario. Una institucion de educacion superior desea progra8. Programacio
mar el calendario de certamenes para lo cual destinara un total de M das, cada uno
dividido en K modulos horarios. El problema consiste en determinar el da y modulo horario en que se realizara el certamen de cada uno de los I cursos dictados. Cada certamen
requiere solo un modulo horario y por simplicidad asumiremos que cada certamen requiere solo una sala para su aplicacion. Se dispone de R salas. El calendario propuesto debe
asegurar a los estudiantes que van al da en sus cursos (y eventualmente a los que van
ligeramente atrasados) que sus certamenes no seran programados en el mismo horario,
3

para lo cual se dispone de un coeficiente (no variable) binario bij que vale 1 si el curso i
no se puede programar en el mismo horario que el curso j. En el caso de alumnos que van
mas atrasados puede darse que dos de sus certamenes se topen en horario, pero el objetivo
de la programacion es que el n
umero de estudiantes en esta condicion sea mnimo. Para
ello se sabe que aij es la cantidad de alumnos que estan inscritos en los cursos i y j.
(a) Formule un modelo de optimizacion que permita programar los certamenes de modo
de minimizar el n
umero de topones de horario.
(b) Como puede modificar su modelo para exigir que los certamenes de los cursos i y j
tales que bij = 1 no solo no se realicen en el mismo horario sino que en das distintos?
(c) Si se dictan 50 cursos, se han definido 4 modulos horarios para realizar certamenes
en el da, se espera programar los certamenes en un perodo de 6 das y se cuenta con
5 salas. Indique el n
umero de variables de decision que tiene su modelo.
9. Fletes. Una empresa de mudanzas dispone de M camiones cada uno con una capacidad
de carga Vm . Para un da determinado esta empresa ha sido contratada por N clientes
distintos que deben transportar una carga Rn cada uno. Cada mudanza debe realizarse
mediante un u
nico flete y en cada flete no puede llevarse mas de una mudanza. Un mismo
camion puede hacer varios fletes en el da, siendo Lm el n
umero maximo de fletes diarios
que puede hacer el camion m. Si el camion m hace la mudanza del cliente n, el beneficio
es Bmn . Debe tomarse en cuenta en la programacion de los fletes que los clientes s y t
deben ser atendidos por camiones diferentes y los clientes v y w deben ser atendidos por
el mismo camion (por supuesto en viajes diferentes). Por u
ltimo debe considerarse que si
el camion m no fuera asignado a mudanza alguna en este da entonces puede contratarse
para el un flete interurbano si conviene, cuyo destino puede ser Yumbel, Lota o Chillan. El
beneficio de un camion m por contratar este u
nico flete del da esta dado por la expresion
+ Di , donde y son constantes y Di es la distancia de viaje a la ciudad i (i =
Yumbel, Lota, Chillan). Construya un modelo matematico que asegure atender a todos
los clientes y que maximice el beneficio diario de esta empresa.
n a Grupos. De un grupo de 30 personas se pretende crear 10 grupos de
10. Asignacio
tres personas (exactamente 3 personas en cada grupo). Considere que la variable xij es la
variable binaria que denota si la persona i esta en el mismo grupo que la persona j. Escriba
las restricciones del modelo que permiten hacer la asignacion. Utilice notacion indexada
de ser posible. (Ayuda: Considere el hecho que para que el modelo no de respuestas
absurdas. Las asignaciones deben ser simetricas, es decir que si por ejemplo x23 = 1
entonces x32 = 1. Considere ademas que las asignaciones deben ser transitivas, es decir
que si por ejemplo x12 = 1 y x23 = 1 entonces x13 = 1).
n. Usted administra la planta UNPRODUCTO. En esta planta, solo se pro11. Produccio
duce un tipo de producto, el que se puede producir en distintas ventanas de tiempo
(periodos), desde el periodo 1 hasta la n. En cada periodo se puede producir o no. Si se
decide producir, se incurre en un costo de puesta en marcha ft , ademas de un costo variable de pt por unidad. La produccion de periodos anteriores puede ser acumulada en una
bodega a un costo de ht por unidad durante el periodo t. Considere que inicia el proceso
sin producto acumulado. Suponga que la demanda es conocida y se define como dt en
el periodo t. Formule un modelo de programacion lineal entera que permita planificar la
produccion del producto minimizando el costo total.
n de Pagos. J.C. Nickles recibe pagos de tarjeta de credito desde cuatro
12. Percepcio
regiones del pas (Oeste, Oeste medio, Este y Sur). El valor promedio diario de pagos que
4

envan por correo los clientes desde cada region es como se indica: Oeste, 70.000 dolares;
Oeste medio, 50.000 dolares; Este, 60.000 dolares; Sur, 40.000 dolares. Nickles tiene que
decidir donde por correo los clientes deben enviar sus pagos. Como Nickles puede ganar
20 % de interes si invierte estos ingresos, le gustara recibir los pagos tan rapido como sea
posible. Cada da que un dolar esta retenido, Nickles deja de ganar un 20 % de interes
de ese monto. Nickles piensa iniciar un sistema de percepcion de pagos para procesar los

pagos tan rapido como sea posible en cuatro ciudades distintas: Los Angeles,
Chicago,
Nueva York y Atlanta. La cantidad promedio de das (desde el momento que el pago se
enva) hasta que es aprobado el cheque y Nickles puede depositar el dinero, depende de
la cuidad a la cual se enva el pago, seg
un se muestra en la siguiente tabla:
De
A

Los Angeles

Chicago

Nueva York

Atlanta

Oeste
Medio Oeste
Este
Sur

2
6
8
8

6
2
5
5

8
5
2
5

8
5
5
2

Por ejemplo si se enva un cheque desde el Oeste hasta Atlanta, se requieren 8 das
promedio antes que Nickles pueda ganar intereses con el cheque. El costo anual de financiar
un sistema de percepcion de pagos en cualquier ciudad es 50.000 dolares.
Plantee un modelo de programacion entera binaria que permita a Nickles minimizar la
suma de los costos debido al interes perdido y las operaciones del sistema de percepcion
de pagos. Suponga que cada region debe enviar todo su dinero a una sola ciudad y que
no hay lmite en cuanto a la cantidad de dinero que puede manejar cada sistema de
percepcion de pagos. El modelo debe resolver donde opera el sistema de percepcion de
pagos y a que cuidad enva cada region.
13. Almacenamiento. El jefe del Departamento de Informatica de la Universidad desea tener acceso a cinco archivos distintos. Estos archivos estan copiados en 10 discos portatiles
seg
un se indica en la tabla siguiente

Archivo

1
2
3
4
5

X
X

Disco
5 6

10

X
X

X
X

X
X
X

X
X

La cantidad de almacenamiento de cada disco es

Disco

10

Capacidad (Terabytes)

El jefe del departamento esta en un plan de orden, y solo desea conservar la menor cantidad
de discos posibles para as formatear el resto y maximizar la capacidad de almacenaje.
Es por esto que formatearan los discos que no le sirven y solo dejara los que necesita.
(a) Formule un modelo de programacion lineal entera que determine el conjunto de discos
a conservar de modo que la cantidad de almacenamiento total medida en Terabytes
sea la mnima posible. Considere que si un disco se mantiene, todos los archivos seran
conservados.
(b) Modifique el modelo anterior, de tal manera que si se conserva el disco 3 o el disco 5,
entonces el disco 2 tambien se tiene que conservar (solo escriba la o las restricciones
extras necesarias).
14. Proyectos. Una empresa esta considerando cinco proyectos. Cada proyecto aprobado
sera ejecutado sobre un periodo de tres a
nos. Los rendimientos esperados y los gastos
anuales para cada proyecto, junto con los fondos anuales disponibles en miles de euros,
se muestran en la siguiente tabla

Proyecto

Gasto(Me)
A
no 1 A
no 2 A
no 3

1
2
3
4
5

5
4
3
7
8

1
7
9
4
6

8
10
2
1
10

Recursos (Me)

25

25

25

Rendimientos (Me)
20
40
20
15
30

La empresa, teniendo en cuenta su capital disponible, debe elegir los proyectos con el
objetivo de maximizar los rendimientos totales. Ademas se dispone de la siguiente informacion:
(a) El proyecto 3 no se hace si se hace el 5.
(b) Los proyectos 1 y 2 se hacen de forma conjunta solo si no se hacen ni el 4 ni el proyecto
5.
(c) La empresa debe reducir en uno de los tres a
nos sus fondos disponibles en 5 mil euros
y debe decidir en que a
no hacerlo.
Defina un modelo de programacion lineal entera para este caso.
n del Lote Econo
mico con Tiempos de Configuracio
n. La com15. Programacio
pa
na PAINTME produce y comercializa tarros de pintura de diferentes colores. La demanda estimada por tarro de pintura de color j en el periodo t es definida como Djt .
Esta demanda se puede satisfacer de dos formas. La primera es con tarros producidos
en el mismo periodo. La segunda es con tarros en inventario al comienzo del periodo. La
empresa no permite utilizar produccion para satisfacer ordenes no satisfechas en periodos
anteriores (no existe backlog).
El costo de produccion de un tarro de pintura de color j en el periodo t es de cjt y el
costo de inventario en el periodo t y por tarro de pintura se denota ht y se paga por el
6

inventario que se tiene al inicio del periodo, siendo el mismo costo para cualquier color
(todos los tarros son de 5 galones).
Los tarros de pintura son elaborados por una maquina u
nica que puede funcionar hasta
Ct horas por periodo. Considere que si mas de un color es producido en un mismo periodo,
la maquina debe configurarse y por lo tanto no se puede utilizar mientras dure el proceso
de configuracion.
El n
umero de horas que la maquina se detiene depende u
nica y exclusivamente del color j
que se va a producir y esta representado por bj . Una vez que la maquina esta configurada,
cada tarro de pintura de color j, demora aj horas en ser elaborado. El costo de configurar
la maquina en cada periodo depende del color a configurar y es representado con fj . La
produccion se realiza en lotes por lo que todos los tarros de un mismo color se fabrican
juntos para el mismo periodo (se paga el costo de configuracion por color una sola vez
por periodo).
Para simplificar la notacion, considere N = {1, . . . , n} y P = {1, . . . , p} como los conjuntos de colores y periodos considerados en el estudio respectivamente.
Suponga que no existe inventario inicial y que el inventario final (al inicio del periodo
p + 1) debe ser 0 para todos los colores. Suponga ademas que al comienzo de todos los
periodos la maquina no esta configurada en ning
un color.
Formule el problema como uno de programacion lineal entera.
Sugerencia: defina dos tipos de variables enteras y un tipo de variable binaria siendo una
de las variables enteras la de inventario. Ayuda: en su modelo al menos debe considerar las
restricciones de capacidad de la maquina y balance de produccion, demanda e inventario.
n y Transporte. Una compa
16. Localizacio
na puede elegir entre P potenciales ubicaciones para operar una o varias plantas manufactureras y as satisfacer la demanda
mnima de N ciudades. Cada ubicacion potencial de las plantas tiene un costo fijo cfi de
operacion, y un costo de transporte asociado al envo del producto hacia cada ciudad ctij .
Cada posible planta tiene una capacidad de produccion que no puede ser excedida, ki .
El objetivo consiste en localizar optimamente las plantas manufactureras de modo de
satisfacer la demanda de todas las ciudades (dj ) a mnimo costo. Formule un modelo que
resuelva el problema.
n de helico
pteros, MinMax. Para enfrentar de mejor manera la proxi17. Localizacio
ma temporada de incendios forestales, se desea ubicar en forma optima dos centros de
operacion para los dos helicopteros de control de incendios que cubriran las emergencias
en las regiones del sur del pas.
Para abordar el problema se han dividido las zonas boscosas en S sectores y se ha determinado U posibles ubicaciones para los dos centros de operacion. Cada sector tiene
un area As (ha) y se ha estimado que el tiempo que tarda un helicoptero en llegar desde
un posible centro de operaciones al punto medio de cada sector es Tus (minutos). Con
esta informacion, el problema de decision consiste en seleccionar la ubicacion de los dos
centros de operacion y decidir que centro de operacion atendera a que sector en caso
de un incendio (un sector es asignado a solo un centro de operacion, pero un centro de
operacion puede ser asignado a mas de un sector).
Por otro lado, el costo de las operaciones esta dado por un costo fijo de instalacion del
centro de operaciones, Ku (US$), y por un costo variable que depende del tiempo de viaje
del helicoptero entre el centro de operaciones y el punto medio del sector, C (US$/min)

y de la superficie de los sectores que se atenderan desde el centro de operaciones Fus

(US$/ha). Considere que el presupuesto maximo disponible es de P (US$).
Formule un modelo lineal que minimice el tiempo maximo de respuesta en caso de incendio, esto es, minimice el tiempo que tardara un helicoptero en llegar desde su centro de
operaciones al sector mas alejado.
quinas. La decision de usar o no una maquina en particular es repre18. Binarias - Ma
sentada por una variable binaria xj , siendo igual a 1, si la maquina j es utilizada y 0, en
otro caso. Formule las siguientes condiciones mediante el uso de restricciones enteras.
(a) Si la maquina A es utilizada, entonces la maquina B tambien tiene que utilizarse.
(b) Si la maquina C es utilizada, no podemos utilizar ni la maquina D ni la B.
(c) Si la maquina D es utilizada, debemos utilizar al menos la maquina A o B.
19. Binarias - Planes. Una firma tiene un n
umero de posibles planes de produccion, marketing y financieros. La decision de seguir un determinado plan pueden ser incorporadas
a un modelo binario con variables 0 1. Formule las siguientes condiciones mediante el
uso de restricciones enteras.
(a) El plan de produccion 1 es imposible de hacerse si el plan de marketing 2 es adoptado
y el plan de marketing 1 no es adoptado.
(b) El plan de produccion 2 no se puede realizar si el plan de marketing 1 y el plan
financiero 2 son adoptados y al mismo tiempo el plan de marketing 2 y el plan
financiero 1 no son adoptados.
(c) Al menos uno de los cuatro planes de marketing debe ser utilizado.
(d) Solo un plan puede ser implementado por la firma. Si mas de un plan es requerido este lo debe implementar una agencia externa que cobrara c por cada plan que
implementen.
20. (?) Binarias - Procesos. Un proceso de produccion puede usar exactamente uno de
dos metodos alternativos, A y B
(a) Si el metodo A es utilizado, entonces las dos variables continuas asociadas al proceso,
x1 y x2 , deben satisfacer las restricciones 0 x1 2 y 0 x2 3. Si el metodo B
es utilizado, x1 y x2 , deben satisfacer las restricciones x1 x2 , x2 1 y x1 + x2 5.
Muestre como se pueden incluir estas condiciones en un modelo de programacion
lineal entera.
(b) Asuma que el costo de produccion utilizando el metodo A es 6x1 + 4x2 y que el costo
utilizando el metodo B es de 5x1 + 5x2 . Muestre como el modelo de la parte (a) puede
ser extendido para incluir estos costos.
21. Binarias - Mezclas. Suponga que las variables xi representan la proporcion del componente Ci en una mezcla. Si la proporcion de C1 excede 0.3, entonces la proporcion de C2
debe ser al menos 0.1 y la proporcion de C3 no debe superar 0.2. Muestre como modelar
estas condiciones utilizando variables binaria.
22. (?) Binarias - K entre N Restricciones. Suponga un modelo que tiene m restricciones lineales del tipo g(x) b y k restricciones lineales del tipo h(x) c . Considere que a
lo mas m
restricciones del primer tipo se deben cumplir (con m > m)
y que exactamente
8

 Modele esto utilizando

k restricciones del segundo tipo se deben cumplir (con k > k).
variables binarias. Defina claramente las variables y cualquier parametro requerido para
expresar estas condiciones.
23. Fertilizantes. Una planta de fertilizantes produce kilogramos de un determinado producto utilizando en su fabricacion t procesos distintos. Los costos de operacion por kilogramo de producto en el proceso i son representados por ci . Se tiene un contrato firmado
que obliga a producir D kilogramos del producto. Se tiene ademas una cantidad limitada
de horas maquina y horas hombre, siendo la primera M horas y la segunda H horas. El
proceso i utiliza hhi horas hombre y hmi horas maquina por cada kilogramo de producto.
Los costos fijos de los procesos son fi . Se quiere establecer un plan de produccion que
minimice costos, considerando que:
Si se usa el proceso 1, deben ser usados el 2 y el 3.
Se ha establecido que un proceso sera utilizado s y solo si produce al menos 50
unidades.
La gerencia de la empresa ha manifestado que podra entregar a cero costo mas mano
de obra o mas horas maquinas pero no las dos (suponga que el aumento puede ser
ilimitado).
Formule un modelo de programacion matematica para representar esta situacion.
n de Flota. Suponga que usted es el ingeniero de logstica de la tienda
24. Asignacio
retail RIPARISELLA y debe resolver el problema de asignar los n camiones de reparto
disponibles esta ma
nana, para entregar k pedidos que estan pendientes. Naturalmente,
usted busca hacer la entrega lo antes posible, por que quisiera una solucion que implique
la menor distancia total recorrida.
La distancia extra marginal del camion j por repartir el pedido i se denomina dij . La
capacidad maxima de carga de cada camion se denomina cj . La carga de cada pedido se
denomina pi .
(a) Plantee un problema de programacion binaria para modelar matematicamente este
problema.
(b) Suponga que al hacer un poco mas de analisis, usted se da cuenta que existen algunas
relaciones de dependencia y de exclusion:
(i) Si el camion 1 reparte el paquete 4, entonces el mismo camion debe repartir el
paquete 7.
(ii) Si el camion 2 reparte el paquete 6, entonces debe ser liberado de todos los
demas paquetes.
(iii) Si el camion 3 es asignado a repartir el paquete 4, entonces tambien debera recoger el 5 y el 7.
A
nada las restricciones que permitan modelar cada uno de estos casos.
25. (?) Secuenciamiento. Considere que n diferentes piezas tienen que ser procesadas por
m maquinas. Cada pieza debe ser procesada primero en la maquina 1, luego la maquina
hasta ser procesada finalmente por la maquina m. La secuencia de las piezas puede
2, asA
diferir en cada maquina. Asuma que el tiempo requerido para realizar el trabajo de la
pieza i por la maquina j, se denota tij y es conocido y entero. Tenga en cuenta que
una maquina no puede procesar dos piezas al mismo tiempo y una pieza no puede ser
9

procesada por una maquina si no ha sido terminada por la maquina anterior. El objetivo
es minimizar el tiempo total necesario para procesar todos las piezas.
Formule el problema como uno de programacion entera. (Ayuda: defina xij como el tiempo
de partida para procesar la pieza i en la maquina j).
n de Sitios. Usted esta a cargo de la exploracion de sitios para la extraccion
26. Exploracio
de petroleo. Debe determinar la seleccion de menor costo de k sitios de un total de
m candidatos. Los sitios se etiquetan como S1 , S2 , . . . , Sm , y los costos de exploracion
asociados son C1 , C2 , . . . , Cm .
Usted debe considerar las siguientes restricciones:
a) Evaluar los sitios S1 y S7 le impiden evaluar el sitio S8 .
b) Evaluar los sitios S3 o S4 le impiden evaluar el sitio S5 .
c) Del grupo S5 , S6 , S7 y S8 solo dos deben ser evaluados.
d ) Para evaluar el sitio S9 , se debe haber evaluado antes el sitio S4 .
Defina un modelo de programacion binaria que permita minimizar los costos de exploracion cumpliendo con las restricciones planteadas.
n de Consultorios. Considere el problema de la localizacion de consul27. Localizacio
torios de atencion primaria en una ciudad con varias comunas. Asuma que la poblacion
esta repartida en C comunas y que la comuna i tiene pi habitantes. Un analisis preliminar
ha limitado la cantidad de consultorios a K sitios. Se define dij 0 como la distancia
desde el centro de la comuna i al sitio j.
Dada la concentracion urbana en torno a las comunas 1, 2, 3 y 4, se estima necesario ya
sea abrir los consultorios 1 y 2, 3 y 4 o 1 y 4 (una de las tres combinaciones).
La inversion en dinero por consultorio es funcion de la cantidad de gente atendida por ese
consultorio (pj ) y se denota fj (pj ). El presupuesto total de construccion asignado es B.
La idea es poder hacer una seleccion de los mejores sitios para construir consultorios y
hacer la asignacion de estos a la atencion de las comunas (cada comuna es asignada por
completo a un consultorio, pero un consultorio puede atender mas de una comuna).
Plantee un modelo de programacion matematica que permita optimizar esta asignacion,
cumpliendo las restriccion de presupuesto y otras que usted estime conveniente. Considere
que se le pide minimizar la maxima distancia entre una comuna y su consultorio asignado
(medido desde el centro de la comuna).
28. Call Center. La compa
na YOLOATIENDO es una administradora del call center que
recibe llamadas de reclamos del Transantiago desde toda la ciudad de Santiago. Se debe
hacer un estudio para decidir la cantidad de call centers a instalar, el lugar donde hacerlo
y la proporcion de llamadas de cada zona de la ciudad que recibira cada call center.
Por ejemplo, se puede definir que el call center 3 atendera el 40 % de las llamadas de la
zona 1. Existen n posibles ubicaciones para los call center y m zonas distintas de donde
provienen los llamados. Las personas que llaman desde una zona i son derivadas a un
call center j de acuerdo a la planificacion que se haga de esto. Cada call center puede
entonces recibir llamadas de las m diferentes zonas de Santiago. Dependiendo de la zona
de origen de la llamada y el call center en que se atiende, el costo de la llamada que paga
la compa
na YOLOATIENDO vara. Este costo se parametriza como cij por unidad de
llamada, siendo i la zona de origen y j el call center de destino, es decir i = 1, . . . , m;
j = 1, . . . , n. Cada call center tiene un costo fijo fj si es que se decide abrir. La cantidad de
10

llamadas esperadas es un parametro que se estima a traves de un estudio de mercado. Se

define entonces di como la demanda esperada en llamadas desde la zona i en unidades de
llamadas telefonicas. Dada la cantidad de operadores contratados, se estima que cada call
center tiene una capacidad maxima de atencion que se parametriza por uj (en unidades de
llamadas telefonicas). Usted debe entonces construir un modelo de Programacion Lineal
Entera que permita decidir que call center instalar, y que proporcion de las llamadas
de cada zona atendera cada call center. Para esto se solicita que defina claramente las
variables de decision y que defina un modelo.
29. En el proceso de planificacion de estudio para los examenes, usted tiene disponible T
horas para N examenes. Usted ha hecho una estimacion de que nota obtendra en cada
uno de los N examenes en funcion de la cantidad de horas asignadas a cada uno. Se
define entonces gij como la nota estimada en el examen del ramo i al asignarle j horas
de estudio. Su objetivo es aprobar los N cursos, maximizando la suma de las N notas de
los examenes. En cada ramo i usted debe obtener al menos una nota Mi para aprobar.
Modele esta situacion a traves de un problema de programacion binaria.

11