UNIDAD I: PROGRAMACION DINAMICA

1. Considere la siguiente red en la que cada número junto a la flecha representa la distancia real entre el par de nodos que conecta. El objetivo es encontrar la ruta mas corta del origen al destino.

[pic]

Cuales son las etapas y los estados para la formulación de programación dinámica de este problema? Utilice P.D. para resolver este problema.

2. El gerente de ventas de una editorial de libros de texto universitarios tiene seis agentes de ventas que puede asignar a tres regiones distintas del país. Ha decidido que cada región debe tener por lo menos un agente y que cada uno de estos debe quedar restringido a una de estas regiones, pero ahora quiere determinar cuantos agentes debe asignar …ver más…

[pic]

La probabilidad de que el sistema funcione es el producto de la probabilidades de que los componentes respectivos funcionen

[pic]

a) Suponga que el dinero se debe gastar en cantidades enteras múltiples de $1 millón en cada fase y que el mínimo permisible es 1 para la fase 1 y 0 para las fases 2 y 3. En la siguiente tabla se proporciona el efecto estimado de los gastos en cada fase:

[pic]

b) Suponga que se puede gastar cualquier cantidad del presupuesto en cada fase, y que el efecto estimado al gastar una cantidad xi (en unidades de millones de dólares) en la fase i (i = 1, 2, 3) es

[pic]

7. La presidenta de un partido político de un estado planea las próximas elecciones presidenciales. Cuenta con la colaboración de seis voluntarios para trabajar en los distritos electorales y los quiere asignar a cuatro distritos de manera que se maximice su eficacia. Ella piensa que seria ineficiente asignar un voluntario a mas de un distrito, pero esta dispuesta a no asignar a nadie a cualquiera de ellos si pueden lograr mas en otro distrito.

En la siguiente tabla se presenta el aumento estimado del número de votos para el candidato del partido en cada distrito si se asigna distintos números de voluntarios:[pic]

El problema tiene varias soluciones óptimas para determinar cuantos voluntarios debe asignarse a cada distrito para maximizar el incremento total estimado de la popularidad del candidato del