INVESTIGACION OPERATIVA II - MAT 353 16 DE SPTIEMBRE DE 2015

PROBLEMAS CLASEDocente:Ing. MSc. Mariano Saucedo EliasTEMA: PROGRAMACIÓN DINAMICA

Problema Nr. 1

Considérese el gráfico que contempla las rutas posibles para ir desde la ciudad 1 hasta la ciudad 10. Cada nodo representa una ciudad y los arcos la infraestructura vial disponible. La tabla recoge el costo asociado al desplazamiento entre cada par de nodos para cada una de las etapas. Supondremos que todos los desplazamientos tienen la misma duración, y que el viaje ha de realizarse en cuatro etapas. Cada una de ellas se corresponde con un único desplazamiento entre un par de nodos del grafo, así al finalizar la primera etapa estaremos en una de las ciudades 2, 3 ó 4. La segunda etapa finalizará en la ciudad 5, la número 6 ó la número 7. La tercera jornada nos llevará a la ciudad 8 o a la número 9. La cuarta etapa permite finalizar el viaje en la ciudad 10.

2 5

8

1 3 6 10

9

4 7

2 3 4

1 2 3 4

5 6 7

2 7 4 6

3 3 2 4

4 4 1 5

8 9 10

5 1 4 8 3

6 6 3 9 4

7 3 3

Problema No. 2.-Un Centro Médico de Salud se dedica a mejorar la situación médica del mundo, dispone de 5 brigadas para asignarlas a 3 países. El centro necesita determinar el numero de brigadas por país que debe asignar para maximizar la eficiencia. La medida de eficiencia es el de años de vida por persona.Para un país especifico esta medida es igual al incremento de vida esperado de años multiplicado por su población.En la tabla se dan las estimaciones en múltiplos de un millón, además del numero posible de brigadas asignadas.Que asignación de brigadas se puede dar a cada país para maximizar la eficiencia ?

Número de Brigadas

País1 2 3

0 0 0 01 45 20 502 70 45 704 90 75 804 105 110 1005 120 150 170

Problema No. 3.- Problema de Presupuestación de CapitalSe considera un problema simplificado de presupuestación de capital donde existen 3 fabricas, cada una de ellas considera posibles expansiones. El monto total de capital disponible al proyecto completo es C. Las fabricas 1, 2 y 3 tienen tres, cinco y tres planes alternativos para su expansión, respectivamente. Los costos esperados adicionales y las correspondientes utilidades para el plan j de la fabrica i están dados por cij y rij, respectivamente. El primer plan (j = 1) para cada fabrica, i, se asume que significa la posibilidad de no expansión de manera que c i1 = ri1 = 0 para i = 1, 2, 3. El objetivo de la decisión del problema es seleccionar un plan j para cada fabrica i que maximice la utilidad total. El costo del conjunto de planes seleccionados no debe exceder el capital total disponible, C.

mi i = 1 i = 2 i = 3R1m1 C1m1 R2m2 C2m2 R3m3 C3m3

1 0 0 0 0 0 02 6 3 9 5 4 23 7 4 10 6 6 44 - - 11 7 - -5 - - 12 8 - -

Capital disponible C = 12

Problema No. 4.-En un pueblo se requiere entregar 5 ambulancias a 3 centros asistenciales, se ha determinado la respuesta en el tiempo promedio de llegada a un punto de socorro el contar con 1, 2 y 3 ambulancias

Cantidad Centro 1 Centro 2 Centro 31 8 10 122 6 5 63 3 4 5

se ha considerado el reparto de ambulancias a que al menos 1 vehículo deberá tocar a cada centro asistencial, y la pregunta es ¿cómo se realizará la asignación?

a) Formular el modelo de Programación Dinámica.b) Hallar la solución.

Problema No. 5.- Una estudiante universitaria tiene siete días para preparar los exámenes finales de cuatro cursos y quiere asignar el tiempo que tiene para estudiar de la manera más eficiente posible. Necesita por lo menos un día para cada curso y quiere concentrarse sólo en un curso cada día por lo que quiere asignar uno, dos, tres o cuatro días a cada curso.

Como hace poco tomo un curso de investigación de operaciones, ha decidido aplicar programación dinámica para hacer estas asignaciones, maximizando el total de puntos obtenidos en los cuatro cursos. Estima que las distintas opciones en días de estudio le redituaran puntos de calificación según la siguiente tabla:

Número de Días

Puntos de Calificación EstimadosCurso

1 2 3 4

1 3 5 2 62 5 5 4 73 6 6 7 94 7 9 8 9

Resuelva este problema aplicando la Programación Dinámica. Problema No. 6.-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 comprar tiempo de TV por un total de cinco comerciales en horas de mayor audiencia en estaciones localizadas en cuatro áreas diferentes. Con base a la información de las preliminares se hizo una estimación del número de votos adicionales que se pueden ganar en las diferentes áreas de difusión según el número de comerciales que se compren. Estas estimaciones se dan en la siguiente tabla en miles de votos:

No. de comerciales

Area1 2 3 4

0 0 0 0 01 4 6 5 32 7 8 9 73 9 10 11 124 12 11 10 145 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.

Problema No. 7.-El gerente de ventas de una editorial de libros de textos 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 agente individual debe quedar restringido a una de estas regiones, pero ahora quiere determinar cuantos agentes debe asignar a las respectivas regiones con el fin de maximizar las ventas.La siguiente tabla da el incremento estimado en las ventas de cada región (en las unidades apropiadas) si se le asignan diferentes cantidades de agentes.

Número de Región agentes 1 2 3 ----------------- ---- ----------------------------------------- 1 35 21 28 2 48 42 41 3 70 56 63 4 89 70 75 ------------------------------------------------------------------Utilice programación dinámica para determinar la asignación óptima de agentes a cada una de las tres regiones.

Problema Nr. 8.-

La carga de un avión se distribuye con el propósito de maximizar el ingreso total. Se consideran 5 elementos y sólo se necesita uno de cada uno. La compañía gana 5.000 u.m. por elemento más una bonificación por elemento. El avión puede transportar 2.000 libras.

Elemento Peso,lb

Volumen, pies3

Valorbonificación

1 1000 70 7002 1100 100 8003 700 100 11004 800 80 10005 500 50 700

a) ¿Cuáles elementos deben transportarse?b) Si se considera un volumen máximo de 200 pies cúbicos.

¿cuáles elementos deben transportarse?

Problema Nr. 9.-

La tabla muestra los datos del siguiente problema de producción e inventario: la demanda para los meses de enero, febrero, marzo y abril es de 4, 5, 3 y 4 unidades, respectivamente. Las capacidades de producción son de 6, 4, 7, y 5 unidades; las capacidades de

almacenaje son 4, 3, 2 y 4 unidades respectivamente. Los costos de preparación varían de un mes a otro y son: 500, 450, 500 y 600 u.m. para enero, febrero, marzo y abril.

Mes Costos Demanda Capacidad deproducción

Capacidad deAlmacenamiento

Enero 500 4 6 4Febrero 450 5 4 3Marzo 500 3 7 2Abril 600 4 5 4

Determinar un programa de producción con el fin de minimizar los costos totales relacionados.