1.

Una inmobiliaria desea promocionar una nueva urbanización mediante una

campaña publicitaria. Para ello dispone de 5 tipos de anuncios: anuncios en
televisión local al mediodía (tvm), anuncios en televisión local a la noche (tvn),
anuncios en periódico local (per), anuncios en suplemento dominical local (sup) y
anuncios en radio local por la mañana (rad). La empresa ha reunido datos sobre la
cantidad de clientes potenciales a los que se destina cada tipo de anuncio y el coste
de cada anuncio en euros. Además, se ha llevado a cabo una valoración de la
calidad que tiene cada anuncio de acuerdo al medio en el que se expone, en una
escala de 0 a 100 (0 nula, 100 excelente). Los datos se recogen en la siguiente tabla:
Clientes Coste Calidad
Anuncios
Potenciales (euros) exposición
tvm 1000 1500 65
tvn 2000 3000 90
per 1500 400 40
sup 2500 1000 60
rad 300 100 20

El número máximo de anuncios que se pueden emitir es 15, 10, 25, 4 y 30 de tvm,
tvn, per, sup y rad, respectivamente. La inmobiliaria, aconsejada por una agencia de
publicidad, decide utilizar al menos 10 anuncios en la televisión, alcanzar por lo
menos 50000 clientes potenciales, no gastar más de 18000 euros en anuncios en
televisión y si se hacen anuncios en el periódico entonces no hacer anuncios en la
televisión por la noche. El presupuesto máximo para la campaña publicitaria es de
30000 euros. Modelizar, sin resolver, mediante programación lineal entera el
problema de cómo debe planificar la campaña si se desea maximizar la calidad de
la exposición de todos los anuncios de la campaña publicitaria.

2. La directora de un centro educativo debe asignar la docencia de 5 asignaturas, A1,

A2, A3, A4 y A5 a 4 profesores, P1, P2, P3 y P4 teniendo en cuenta las valoraciones
de las encuestas hechas por los alumnos y unas restricciones impuestas por un nuevo
reglamento. En base a las encuestas de años anteriores, se tienen las siguientes
valoraciones promedios (escala: 0 mala, 5 excelente):
 A1 A2 A3 A4 A5
P1 2.7 2.2 3.4 2.8 3.6
P2 2 3.6 3.4 2.8 3.6
P3 3.2 3.8 2.3 1.9 2.6
P4 2.6 2.5 1.8 4.2 3.5

El nuevo reglamento dice que el profesor P3 no puede impartir las asignaturas A1 y

A2. Las asignaturas no se pueden compartir y se han de impartir todas. Ningún
profesor puede quedar sin asignaturas. Al profesor P1 solamente se le debe asignar
una asignatura.
a) Modelizar como un problema de programación lineal entera con el objetivo de
obtener la asignación que maximice la valoración media total.
b) Indicar a qué tabla habría que aplicar el método húngaro para determinar
la asignación óptima.
3. Una empresa de juguetes está considerando la puesta en marcha de tres nuevos
modelos de juguetes (1, 2 y 3) para su posible inclusión en la próxima campaña de
Navidad. La preparación de instalaciones para la fabricación de estos modelos
costaría 25000 €, 35000 € y 30000 € respectivamente, y la ganancia unitaria sería
de 10 €, 15 € y 13 € respectivamente. La empresa dispone de tres plantas de
producción para la elaboración de estos modelos, pero para evitar gastos sólo en
una de ellas se producirían los juguetes, dependiendo la elección de la
maximización de las ganancias.
El número de horas que se precisa para producir cada juguete en cada planta es:

juguete 1 juguete 2 juguete 3

planta 1 5 4 6
planta 2 4 2 2
planta 3 3 3 2

Las plantas disponen al día 500, 600 y 630 horas de producción respectivamente.
La gerencia ha decidido desarrollar al menos uno de los tres juguetes.
a) Modelizar el problema utilizando programación lineal entera para maximizar
el beneficio total.
b) La empresa decide producir únicamente el juguete tipo 3, pero debe tener en
cuenta que si produce más de 50 unidades de este tipo de juguete entonces:

el coste de preparación de instalaciones del juguete tipo 3 es de 40000 €

debe producir en la planta 3
Modelizar el problema, añadiendo esta información, utilizando programación lineal
entera.
4. Se considera el siguiente grafo:
3
2 5
9
1
a
4
2
7
1 4 7

1
4
2
6
3 6
4

a) Si los valores de cada arco representan distancias, hallar

razonadamente cómo debe ser a para que la ruta más corta del nodo 1 al 7 pase
obligatoriamente por el nodo 2. Indicar esta ruta más corta.
b) Si a = 5 y los valores de los arcos representan capacidades de flujo,
calcular el valor del flujo máximo del nodo 1 al 7.
5. Una universidad se encuentra en un proceso de formar una comisión.
Diez personas han sido nominadas: A, B, C, D, E, F, G, H, I y J. El reglamento
obliga a que sean incluidos en dicha comisión al menos una mujer, un hombre, un
estudiante, un administrativo y un profesor. Además, el número de mujeres debe ser
igual que el de hombres y el número de profesores no debe de ser inferior al de
administrativos. La mezcla de los nominados en las siguientes categorías es como
sigue:

Categoría Personas
Mujeres A, B, C, D, E
Hombres F, G, H, I, J
Estudiantes A, B, C, J
Administrativos E, F
Profesores D, G, H, I

Modelizar sin resolver como un problema de programación lineal entera, si se trata

de que la comisión sea lo más reducida posible.
6. Una empresa de transporte dispone de 4 camiones y 4 rutas. Cada camión debe
hacer una ruta y cada ruta debe realizarse exclusivamente por un camión. Los
beneficios de cada transportista para las distintas rutas dependen de las
características del camión y de la ruta escogida y se presentan en la siguiente tabla:

Ruta 1 Ruta 2 Ruta 3 Ruta 4

Camión 1 150 200 300 100
Camión 2 100 220 300 250
Camión 3 250 140 240 240
Camión 4 300 250 100 300

a) Decidir la ruta que debe realizar cada camión para que el beneficio total
obtenido sea máximo.
b) El comercial de la empresa ha conseguido dos nuevas rutas y desea probarlas
durante este año. Los beneficios obtenidos por cada camión son:

Camión 1 Camión 2 Camión 3 Camión 4

Ruta 5 200 300 250 250
Ruta 6 260 280 250 320

i) Construir la tabla a la que aplicaríamos el Método Húngaro sabiendo

que cada camión únicamente puede realizar una ruta y las nuevas
rutas deben realizarse obligatoriamente.
ii) Construir la tabla a la que aplicaríamos el Método Húngaro sabiendo
que se tienen que realizar todas las rutas, cada camión puede realizar
más de una ruta y tienen que utilizarse obligatoriamente todos los
camiones. Además, el camión 1 podrá realizar, como mucho, 450 km
diarios, los camiones 2 y 3 podrán realizar, como mucho, 300 km diarios
y el camión 4, 160 km y las rutas 1, 2, 3, 4, 5, 6 son de 110, 150, 130,
150, 120 y 90 km respectivamente.
7. Una fábrica produce 4 tipos de jabones, para lo cual son necesarios 6
componentes. En la siguiente tabla se muestran las cantidades necesarias para
realizar una pastilla de jabón de cada tipo.

sosa esencia esencia

aceite agua glicerina
cáustica de limón de fresa

J1 250 ml 240 ml 42 g 1g 1 ml 3 ml

J2 200 ml 210 ml 2g 40 g 2 ml 1 ml

J3 230 ml 240 ml 20 g 25 g 3 ml 1 ml

J4 180 ml 200 ml 10g 35 g 1 ml 3 ml

La fábrica dispone de 150000 ml de aceite, 160000 ml de agua, 12 kg de sosa

cáustica, 3 kg de glicerina, 2000 ml de esencia de limón y 3000 ml de esencia de
fresa por día.
Se tiene que producir al menos un tipo de jabón al día y como mucho tres. Además
si se producen jabones del tipo 1 no se podrán producir del tipo 4.
El beneficio por cada pastilla de jabón es de 10, 13, 15 y 11 euros respectivamente
para cada tipo de pastilla de jabón.
La fábrica se está planteando ampliar la planta de producción con un coste de
200000 euros, de forma que si se realiza la ampliación las disponibilidades de los
componentes aumentarán en 50000 ml de aceite, 70000 ml de agua, 4 kg de sosa
cáustica, 4 kg de glicerina, 1000 ml de esencia de limón y 500 ml de esencia de
fresa. Además, en el caso de realizar esta ampliación, si se producen pastillas del
tipo 3, se tendrán que realizar también del tipo 1.
Modelizar el problema de programación lineal entera que maximice el beneficio.

43
8. Con motivo del 5º centenario del nacimiento de un célebre pintor, un importante
museo ha decidido restaurar cinco de sus obras, para lo cual ha contratado tres
equipos de restauración. Cada equipo ha presentado el presupuesto de restauración
para cada una de las obras, como se recoge en el siguiente cuadro, en miles de
euros.

O1 O2 O3 O4 O5
R1 60 -- 90 -- 120
R2 70 90 80 100 80
R3 -- 70 120 90 100
(Donde “--“ significa que dicho equipo no restaurará en ningún caso la obra
correspondiente).

El primer equipo restaurador está compuesto por seis personas, el segundo por
cuatro y el tercero por tres. En la restauración de cada una de las obras son
necesarias dos personas. Cada persona de un equipo sólo restaura una obra.
a) ¿A qué tabla se debe aplicar el Método Húngaro para realizar las cinco
restauraciones, con el menor coste posible, teniendo en cuenta que cada una
de ellas debe ser realizada por un único equipo restaurador, y que los tres
equipos deben participar en dichas restauraciones?
b) Dado que el coste de restauración de las cinco obras es muy elevado, la
directiva del museo decide restaurar únicamente tres, asignando una única obra
a cada equipo. Determinar, aplicando el Método Húngaro, todas las posibles
asignaciones que minimicen el coste total.

10. Dado el siguiente problema de programación lineal entera:

Max (2 x1 + 5 x2 )
2x1 +3x2 ≤ 12 (1)
x ≤ 4
 (2)
s.a  1
 x2 ≤ 3 (3)
 x1 ≥ 0, x2 ≥ 0 y enteras

a) Resolver el problema mediante el método de Ramificación y Acotación.