Ejercicios Programación dinámica.

1. La policía antinarcóticos tiene disponibles seis brigadas formadas por elementos

especialmente entrenados para combatir el narcotráfico y quemar plantíos de

enervantes. El comandante de la policía puede repartir estas brigadas en cuatro

regiones diferentes para así combatir más eficazmente el narcotráfico. En la tabla

se presentan las toneladas de enervantes destruidas en cada una de las cuatro

regiones, dependiendo del número de brigadas asignadas. Las brigadas no pueden

ser divididas por lo que se deben asignar números enteros a cada región.

El comandante desea saber ¿Cuántas brigadas debe asignar a cada región de manera

que maximice la cantidad de toneladas de enervantes destruidas?

Número de

brigadas

antinarcóticos

Toneladas de enervantes destruidas en la región

1 2 3 4

0 0 0 0 0

1 4 6 2 5

2 5 8 7 6

3 9 9 14 12

4 11 10 15 13

5 15 11 17 14

6 16 13 18 16

2. Fútbol Tamsa es una empresa que administra cuatro equipos de fútbol de primera

división y los quiere reforzar con tres jugadores de fama internacional que acaba de

contratar para así mejorar las probabilidades de ganar el campeonato.

En la siguiente tabla se tienen las probabilidades de que cada equipo gane el

campeonato dependiendo de la asignación de jugadores contratados para

reforzarlos.

Número de jugadores

asignados

Probabilidad de ganar el campeonato por el

equipo

1 2 3 4

0 0.40 0.30 0.60 0.70

1 0.50 0.50 0.70 0.90

2 0.70 0.60 0.80 0.90

3 0.80 0.65 0.90 0.95

En las condiciones actuales, la probabilidad total de que la empresa gane el

campeonato es: 0.40 x 0.30 x 0.60 x 0.70 = 0.0504.

¿Cómo deben asignarse los jugadores para maximizar la probabilidad de que Fútbol

Tamsa gane el campeonato de liga?

3. Un navegante solitario dispone en su barco de 5 metros cúbicos para almacenar

cuatro objetos. El objeto A tiene un volumen de 2 m3 y reporta al navegante 3

unidades de beneficio. Los objetos B,C, y D ocupan respectivamente 4,3 y 2 m3 y el

beneficio respectivo es de 5, 1 y 1. Determinar mediante un algoritmo de

programación dinámica cuales son los objetos que debe llevar el navegante.

4. Un alumno debe seleccionar en total 10 cursos opcionales de cuatro departamentos

distintos, y al menos un curso de cada departamento. Los 10 cursos se asignan a los

cuatro departamentos en una forma que maximiza el "conocimiento". El alumno

mide el conocimiento en una escala de 100 puntos, y llega a la tabla siguiente:

NUMERO DE CURSOS

DEPTO. 1 2 3 4 5 6 7

I 25 50 60 80 100 100 100

II 20 70 90 100 100 100 100

III 40 60 80 100 100 100 100

IV 10 20 30 40 50 60 70

¿Cómo debe seleccionar los cursos el alumno?

5. Tengo un pequeño jardín en mi traspatio que mide 10 X 20 pies. Esta primavera

deseo sembrar tres verduras: tomates, ejotes y maíz. El huerto se organiza en

surcos de 10 pies. Los surcos con tomate y maíz tienen 2 pies de ancho, y los de

ejotes son de 3 pies de ancho. Lo que más me gusta son los tomates, y los ejotes

casi no me gustan; en una escala de 1 a 10 calificaría con 10 a los tomates, 7 al maíz

y 3 a los ejotes. Independientemente de mis gustos, mi esposa insiste en sembrar al

menos un surco de ejotes y no más de dos surcos de tomates. ¿Cuántos surcos de

cada planta debo sembrar?

6. Habitat for Humanity es una maravillosa organización caritativa que construye casas

para familias necesitadas, usando trabajo voluntario. Una familia elegible puede

escoger entre tres tamaños de vivienda: de 1000, 1100 y 1200 pies cuadrados. Cada

tamaño de casa requiere cierta cantidad de voluntarios. El capítulo de Fayetteville

ha recibido cinco solicitudes para los próximos 6 meses. El comité a cargo asigna

una calificación a cada solicitud, con base en varios factores. Una calificación más

alta indica más necesidad. El capítulo de Fayetteville cuenta con un máximo de 23

voluntarios. Los datos que siguen resumen las calificaciones para las solicitudes, y la

cantidad necesaria de voluntarios.

Aplicación Tamaño de la

vivienda

(pies2)

Calificación Número de

voluntarios

requeridos

1 1200 78 7

2 1000 64 4

3 1100 68 6

4 1000 62 5

5 1200 85 8

¿Cuáles solicitudes debe aprobar el comité?

7. El alcalde Bassam se desea reelegir por el condado de Washington. Los fondos

disponibles para su campaña son de $10,000. Aunque al comité de reelección le

gustaría la campaña en los cinco barrios del condado, pero no lo permiten los

fondos limitados. La tabla siguiente muestra la población de electores y la cantidad

de fondos necesarios para lanzar una buena campaña en cada barrio.

Barrio Población Fondos

requeridos

($)

1 3100 3500

2 2600 2500

3 3500 4000

4 2800 3000

5 2400 2000

La opción en cada barrio es recibir todos los fondos asignados o no recibir nada.

¿Cómo se deben asignar los fondos? Un dispositivo electrónico tiene tres

componentes. Esos componentes están en serie, por lo que la falla de uno causa la

falla del dispositivo. La confiabilidad (probabilidad de que no haya falla) del

dispositivo se puede mejorar instalando una o dos unidades de reserva en cada

componente.

8. En la tabla siguiente se ve la confiabilidad r y el costo c.

Número de Componente 1 Componente 2 Componente 3

unidades

en paralelo R1 C1($) R2 C2($) R3 C3($)

1 0.6 1000 0.7 3000 0.5 2000

2 0.8 2000 0.8 5000 0.7 4000

3 0.9 3000 0.9 6000 0.9 5000

El capital total disponible para la fabricación del dispositivo es de $10,000. ¿Cómo se

debe fabricar el dispositivo? (Sugerencia: el objetivo es maximizar la confiabilidad,

del dispositivo. Eso significa que la descomposición de la función objetivo es

multiplicativa, y no aditiva.)