Ejercicios De Investigación De Operaciones

Investigación de Operaciones - I
Ejercicios de Programación Dinámica en variable discreta
|A continuación se presentan 5 ejercicios resueltos de Programación Dinámica en variable discreta, y se dejan otros 5 ejercicios |
|planteados para que Ud. los resuelva. |
|Profesor: Juan Barrios M. ----Ayudantes: Ramón González – Daniela Romero |
|(Consultas sobre esta guía hacerlas a:) |



EJERCICIOS RESUELTOS DE PROGRAMACIÓN DINAMICA


1.- Un Ingeniero Forestal, requiere saber: i)Cuál es el costo mínimo, y ii)Cuál es la ruta con esecosto mínimo, para ir desde su oficina hasta el lugar donde está la cosecha. En su camino debe pasar por 3 sectores o ciudades antes de llegar a su destino, y lugares posibles en esos sectores o ciudades. Las posibles rutas, y el costo asociado por Kms. de distancia y otros en $, se ven en el siguiente esquema:

||
|[pic] |


Solución:
Para ir de 1 a 13 hay 48 rutas posibles. Una posibilidad para encontrar la solución es calcular el valor asociado a cada una y ver cual es la que proporciona el menor costo. ¿Y si fuesen miles de rutas?. Por se descarta esa alternativa y se usa el método de laprogramación Dinámica, donde se resuelve desde el final hacia el inicio, y hay etapas y estados.
Etapas: Son 4. La etapa 1 es decidir ir del estado inicial 1 al estado 2,3,4 o 5 que son los puntos posibles en el sector siguiente. La etapa 2 es decidir ir a 6, 7 u 8. La etapa 3 es decidir ir a 9, 10, 11 o 12. La etapa 4 es decidir a 13.
Estado: Lugar donde se encuentra. La etapa 1 tiene 1 estado:el 1. La etapa 2 tiene 4 estados: 2, 3, 4, 5. La etapa 3 tiene 3 estados: 6,7,8. La etapa 4 tiene 4 estados: 9, 10, 11, 12.

|Cálculos | |n = 4 |S \ X4 |13 |F4* |X4* |
| | | |9 |12 |12 |13 |
| | | |10 |16 |16|13 |
| | | |11 |15 |15 |13 |
| | | |12 |14 |14 |13 |

|n = 3 | S \ X3 |9 |10 |11 |12 |F3* |X3* |
| |6 |3+12=15|2+16=18 |1+15=16 |3+14=17 |15 |9 |
| |7 |4+12=16 |1+16=17 |4+15=19 |6+14=20 |16 |9 |
| |8 |2+12=14 |3+16=19 |6+15=21 |5+14=19 |14 |9 |

|n=2 |S \ X2 |6 |7|8 |F2* |X2* |
| |2 |9+15=24 |4+16=20 |6+14=20 |20 |7 - 8 |
| |3 |5+15=20 |7+16=23 |4+14=18 |18 |8 |
| |4 |9+15=24 |10+16=26 |8+14=22 |22 |8 |
||5 |9+15=24 |10+16=26 |11+14=25 |24 |6 |

|n = 1 |S \ X1 |2 |3 |4 |5 |F1* |X1* |
| |1 |7+20=27 |6+18=24 |5+22=27 |6+24=30 |24 |3 |

Respuesta: El...