570 11 Programación dinámica11.2-3. Considere la siguiente red de proyecto cuando se aplica PERT/CPM como se describe en el capíruJo 10, donde el número sobre el nodo es el tiempo requerido para la actividad correspondiente. Considere el problema a) <Cuáles son las etapas y los estados para la formulación de programación dinámica de este problema? b) Use programación dinámica para resolver este proble- ma, pero en lugar de emplear las tablas usuales, mues- tre su trabajo en una gráfica. En particular, encuentre los valores de las distintas /,* ( s,.) junto a los nodos co- rrespondientes y el arco óptimo que debe tomarse al salir de cada nodo dibujando una cabeza de flecha cer- ca del inicio del arco. Después identifique la trayecto- ria óptima (la trayectoria más larga) que siguen estas cabezas de flecha desde el nodo inicio hasta el término. Si existe más de una trayectoria óptima, identiflquelas. e) Utilice programación dinámica para resolver el pro- blema con las tablas usuales para n = 4, n = 3, n = 2 y n=l. 11.2-4. Considere las siguientes afirmaciones sobre la solución de problemas de programación dinámica. Eti- quete cada una como falsa o verdadera y después jus- tifique su respuesta haciendo referencia a afirmaciones es- pecíficas (con la cita de la página) dentro del capíruJo. a) El procedimiento de solución utiliza una relación re- cursiva que permita obtener la política óptima para La etapa (n + 1) dada la política óptima para la etapa n. b) Después de completar el procedimiento de solución, si se toma por error una decisión no óptima en alguna etapa, deberá aplicarse de nuevo el procedimiento para determinar las nuevas decisiones óptimas (dada esta decisión no óptima) en las etapas subsecuentes. de encontrar la trayeeturia más larga (el mayor tiempo to- tal) a través de esta red desde el inicio hasta el término, ya que la trayectoria más larga es la ruta crítica. 1 e) U na vez que se ha encontrado una política óptima para todo el problema, la información necesaria para espe- cificar la decisión óptima en una etapa en particular es el estado en esa etapa y las decisiones tomadas en las etapas antenores. 11.3-1. * El propietario de una cadena de tres supermer- cados compró cinco cargas de fresas frescas. La distribu- ción de probabilidad estimada para las ventas potenciales de las fresas antes de que se echen a perder difiere entre los tres supermercados. El propietario quiere saber cómo debe asignar las cinco cargas a las tiendas para maximizar la ganancia esperada. Por razones administrativas, no quiere dividir las car- gas entre las tiendas. Sin embargo, está de acuerdo en asignar cero cargas a cualquiera de ellas. La siguiente tabla proporciona la ganancia estimada en cada tienda al asignar distintas cantidades de cargas: Tienda Número de cargas l 3 o o o o 1 S 6 .. 2 9 11 9 3 1-4 IS 13 "' 17 19 18 S 21 22 20 Problemas del capítulo 1 1 Utilice programación dinámica para determinar cuán- tas cargas deben asignarse a cada tienda para maximizar la ganancia toral esperada. 11.3-2. Una estudiante universitaria cuenta con siete días para preparar los exámenes finales de cuatro cursos y quiere asignar su tiempo de estudio de la manera más efi- ciente posible. Necesita por lo menos un día para cada curso y quiere concentrarse sólo en un curso cada dfa por lo que quiere asignar uno, dos, tres o cuatro días a cada curso. Como hace poco tomó un curso de investigación de operaciones, decide aplicar programación dinámica para hacer estas asignaciones que maximicen el total de puntos obtenidos en los cuatro cursos. Estima que las dis- tintas opciones .en días de estudio le redituarán puntos de según la siguiente tabla: Puntos de calificación estimados Curso Número de dias 2 3 4 1 3 5 2 6 2 S 5 4 7 3 6 6 7 9 .. 7 9 8 9 Resuelva este problema con programación dinámica. 11.3-3. Una compañía está planeando una estrategia de publicidad durante el año próximo para sus tres produc- tos más imponantes. Como los tres son bastante diferen- tes, cada esfuerzo de publicidad estará dedicado a un solo producto. En unidades de millones de dólares se dispone de un total de 6 para esta campaña de publicidad y se su- pone que el gasto en cada producto deberá ser un número entero mayor o igual a l . El vicepresidente de mercado- tecnia ha establecido el objetivo como sigue: determinar cuánto gastar en cada producto a fin de maximizar las ven- tas totales. La siguiente tabla da el incremento estimado en ventas (en las unidades apropiadas) para los diferentes gastos en publicidad: Producto Gasto en publicidad 2 3 1 7 4 6 2 10 8 9 3 14 11 13 4 17 14 15 Utilice programación dinámica para resolver el problema. 571 11.3-4. Una campaña política se encuentra en su última etapa y las preliminares indican que la elección está pareja. Uno de los candidatos tiene suficientes fondos para com- prar tiempo de TV por un total de cinco comerciales en las horas de mayor audiencia en estaciones localizadas en cuatro áreas diferentes. Con base en la información de las preliminares se hizo una estimación del número de vo- tos adicionales que se pueden ganar en las áreas difu- sión según el número de comerciales que se contraten. Estas estimaciones se dan en la tabla en miles de votos: Área Comerciales 1 l 3 4 o o o o o 1 4 6 S 3 2 7 8 9 7 3 9 10 11 12 .. 12 11 JO 14 5 15 12 9 16 Utilice programación dinámica para determinar cómo deben distribuirse los cinco comerciales entre las· cuatro áreas con el fin de maximizar el número estimado de votos ganados. 11.3-5. La presidenta de un partido político en un con- dado planea las próximas elecciones presidenciales. Cuen- ta con la colaboración de seis voluntarios para trabajar en los distritos electorales y los quiere asignar a cuatro distri- tos de manera que se maximice su efectividad. EUa piensa que sería ineficiente asignar un voluntario a más de un dis- tritO pero está dispuesta a no asignar a nadie a cualquiera de ellos si pueden lograr más en otro distrito. La siguiente tabla da el aumento estimado en el núme- ro de votos para el candidato del partido en cada distrito si se asignan distintos números de voluntarios: Distrito Voluntarios 2 3 4 o o o o o 1 <4 7 S 6 2 9 11 10 11 3 IS 16 15 1<4 <4 18 18 18 16 S 22 20 21 17 6 24 21 22 18 Este problema tiene varias soluciones óptimas acerca de cuántos voluntarios deben asignarse a cada distrito para maximizar el incremento total estimado en la popularidad 572 1 1 Programación dinámica del candidaro del partido. Utilice programación dinámica para encontrar todas las soluciones óptimas, para que la presidenta del partido pueda hacer una selección toman- do en cuenta otros factores. 11.3-6. Utilice programación dinámica para resolver el problema de programación de la producción de Northern Airplane Co. presentado en la sección 8.1 (vea la tabla 8.7). Suponga que las cantidades producidas deben ser enteros múltiplos de cinco. 11.3-7. Reconsidere el problema 8.1-9 de la Build- Em-Fase. UtÍÍice programación dinámica para resolverlo. 11.3-8. * Una compañía está por introducir un nuevo producto a un mercado muy competido y planea su estra- tegia de comercialización. Se ha tomado la decisión de in- t roducir el producto en tres fases. La fase 1 incluye ofertas especiales de introducción a precio reducido para atraer a los compradores de primera vez. La fase 2 es una campaña intensiva de comerciales y anuncios para persuadir a estos compradores de primera vez. a que continúen comprando el producto a precio normal. Se sabe que otra compañía introducirá otro nuevo producto competitivo más o me- nos al terminar la fase 2. La fase 3, entonces, incluye una campaña de seguimiento y promoción para tratar de evi- tar que los clientes regulares se vayan a la competencia. Se cuenta con un presupuesto total de $4 millones de dólares para esta campaña. El problema consiste en deter- minar cómo asignar este dinero de la manera más efectiva a Las tres fases. Sea m el porcentaje de mercado inicial (ex- presado como porcentaje) que se logra en la fase l; f 2 la fracción de este mercado que se retiene en la fase 2 y f 3 la fracción restante del porcentaje de mercado que se retie- ne en La fase 3. Con los datos de la siguiente tabla, aplique programación dinámica para determinar la asignación de $4 millones para maximizar el porcentaje fmal del merca- do para el nuevo producto, es decir, maximizar mflfl. a) Suponga que el dinero se debe gastar en cantidades en- teras múltiplos de $1 mil1ón en cada fase y que el míni- mo permisible es 1 para la fase 1 y O para las fases 2 y 3. La siguiente tabla proporciona el efecto estimado de los gastos en cada fase: Efecto sobre el Millones de porcentaje de mercado dólares gastados m fl fl o 0.2 0.3 1 20 0.4 o.s 2 30 O .S 0.6 3 -40 0.6 0.7 .. so b) Suponga que se puede gastar cualquier cantidad del presupuesto en cada fase, y que el efecto estimado al gastar x; (millones de dólares) en la fasei(i = 1, 2, 3) es m= 10x 1 - xf f2 = 0.40 + 0.10X2 f 1 = 0.60 + 0.07 x 3 . [Sugerencia: después de obtener analíticamente las fun- ciones¡.; (s) y !3* (s), obtenga xr gráficamente.] 11.3-9. El gerente de una compañía estudia tres nuevos productos posibles de la línea de productos del año próxi- mo. Debe tomar una decisión en cuanto a qué productos comercializar y a qué niveles de producción. La preparación de la producción requerirá un costo fijo sustancial, como se ve en el primer renglón de la tabla que sigue. El segundo renglón muestra el ingreso neto por cada unidad producida, una vez que la producción está en marcha. El tercero contiene el porcentaje de la ca- pacidad disponible que usará cada unidad producida. Productos 1 2 J Costo fijo 3 2 o Ingreso marginal neto 2 3 1 Capacidad usada por unidad, % 20 40 -20 Sólo se pueden vender 3 unidades del producto 1, mientras que es posible la venta de todas las unidades que se fabriquen de los otros dos productos. El objetivo es de- terminar el número de unidades a fabricar de cada pro- ducto para maximizar la ganancia total (ingreso neto total menos costos fijos). a) Suponga <:¡_ue las cantidades de producción deben ser enteros, use programación dinámica para resolver el problema. b) Considere el caso en el que se cumple la suposición de divisibilidad, de manera que las variables que repre- sentan las cantidades de producción se manejan como variables continuas. Suponga que se cumple la propor- cionalidad para los ingresos netos y para las capacida- des usadas; use programación dinámica para resolver este problema. 11.3-10. Considere un sistema electrónico con cuatro componentes, cada uno de los cuales debe trabajar para que el sistema funcione. La confiabilidad de éste se puede mejorar si se instalan varias unidades paralelas en una o más de las componentes. La siguiente tabla muestra la probabilidad de que las respectivas componentes funcio- nen si constan de una, dos o tres unidades paralelas: