Ejercicios De Programación Dinámica

1.- Un Ingeniero Forestal, requiere saber: I) Cuál es el costo mínimo, y II)Cuál es la ruta con ese costo 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 elsiguiente esquema:

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 óptimo es: 24La solución óptima es: X1 = 3 ; X2 = 8 ; X3= 9 ; X4= 13.
La ruta óptima es: | 1 | | 3 | | 8 | | 9 | | 13 |

Respuesta al problema planteado:
-------------------------------------------------
El Ingeniero Forestal tiene un costo mínimo de $24 para ir desde su oficina al lugar de cosecha, y ese mínimo lo puede lograr yendo desde su oficina al lugar 3 luego al lugar 8 luego al lugar 9 yde ahí al lugar 13, que es donde está la cosecha.

2.-Un Técnico Forestal, debe revisar 3 faenas: Poda, Raleo y Cosecha, y dispone de 4 días. Según la dedicación en días que le dé a cada faena, éstas tendrán una probabilidad de fracasar, y con ello fracasar la faena total, por lo que puede ser despedido. Por ello, dicho Técnico desea minimizar la probabilidad de ser despedido minimizando laprobabilidad de que las 3 tareas fracasen al mismo tiempo.
Dedicación \ Faenas | Poda | Raleo | Cosecha |
0 día | 0.50 | 0.60 | 0.40 |
1 día | 0.42 | 0.51 | 0.35 |
2 días | 0.36 | 0.41 | 0.21 |
3 días | 0.25 | 0.36 | 0.18 |
Un día no asignado a una faena no tiene valor asociado. A lo más se puede asignar 3 días a una misma faena.

Solución:

n = 3 | S \ X3 | 0 | 1 | 2 | 3 | F3* |X3* |
| 0 | 0.4*1=0.40 | - | - | - | 0.40 | 0 |
| 1 | 0.4*1=0.40 | 0.35*1=0.35 | - | - | 0.35 | 1 |
| 2 | 0.4*1=0.40 | 0.35*1=0.35 | 0.21 | - | 0.21 | 2 |
| 3 | 0.4*1=0.40 | 0.35*1=0.35 | 0.21 | 0.18 | 0.18 | 3 |
| 4 | 0.4*1=0.40 | 0.35*1=0.35 | 0.21 | 0.18 | 0.18 | 3 |

n=2
S\X2 | 0 | 1 | 2 | 3 | F2* | X2* |
1 | 0.6*0.35=0.210 | 0.51*0.40=0.2040 | - | - | 0.2040 | 1 |
2 |0.6*0.21=0.126 | 0.51*0.35=0.1785 | 0.41*0.40=0.1640 | - | 0.1260 | 0 |
3 | 0.6*0.18=0.108 | 0.51*0.21=0.1071 | 0.41*0.35=0.1435 | 0.36*0.40=0.144 | 0.1071 | 1 |
4 | 0.6*0.18=0.108 | 0.51*0.18=0.0918 | 0.41*0.21=0.0861 | 0.36*0.35=0.1260 | 0.0861 | 2 |

n=1
S\X1 | 0 | 1 | 2 | 3 | F1* | X1* |
4 | 0.5*0.0861= 0,04305 | 0.42*0.1071= 0,044982 | 0.36*0.1260= 0,04536 | 0.25*0.2040= 0,051 |0.04305 | 0 |

Respuesta:

Óptimo = 0.04305 ( un 4,3% ).
La solución óptima es: X1 = 0 ; X2 = 2 ; X3= 2
La ruta óptima es: | 4 | | 4 | | 2 | | 2 |

-------------------------------------------------
Respuesta al problema planteado: La probabilidad mínima de ser despedido es 0.04305 , es decir de un 4,3%, y la asignación óptima de días es: 0 días a la Poda, 2 días al Raleo, 2 Díasa la Cosecha.

3.- Un aserradero debe enviar 4 o 5 cargamentos a cuatro destinos. La máxima asignación para cada destino es de cuatro cargamentos. En la tabla siguiente se indica g(xi) como los ingresos en MM$ obtenidos por cada una de las decisiones posibles. Se desea maximizar el ingreso del aserradero por estos envíos.
Además al destino 2 no se puede asignar 4 sino que máximo 3...