DESCARGAR DOCUMENTO:
https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BxUD2st9AdUCMjYzZGI4MzktNWQ4My00MDM2LTk2MDEtODlhYzAyMjM1M2Zl&hl=en_US
https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BxUD2st9AdUCMjYzZGI4MzktNWQ4My00MDM2LTk2MDEtODlhYzAyMjM1M2Zl&hl=en_US
INTRODUCCIÓN.
PROGRAMACIÓN DINÁMICA.
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.
RUTA MÁS CORTA.
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Planteamiento.
La secretaria de salud pública tiene disponibles cuatro brigadas formadas para distribuir vacunas en 4 regiones del estado de México a niños mayores de 3 años.
El Mtro. Salomón Chertorivski Woldenber secretario de la institución puede repartir estas brigadas en cuatro regiones diferentes para así aplicar más eficazmente las vacunas.
En la tabla se presentan las miles de vacunas distribuidas en cada una de las cuatro regiones, dependiendo del número de brigadas asignadas. Las brigadas no pueden ser divididas por lo que se deben asignar números enteros a cada región.
El Mtro. Salomón Chertorivski Woldenber desea saber…
¿Cuántas brigadas debe asignar a cada región de manera que maximice la cantidad de vacunas aplicadas?
Número de brigadas | Miles de Vacunas distribuidas en la región | |||
1 | 2 | 3 | 4 | |
0 | 0 | 0 | 0 | 0 |
1 | 4 | 6 | 2 | 5 |
2 | 5 | 8 | 7 | 6 |
3 | 9 | 9 | 14 | 12 |
4 | 11 | 10 | 15 | 13 |
Aplicación del método de solución
Programación Dinámica
*Red
ð - El nodo representa el número de brigadas disponibles.
ð - El arco contiene las miles de vacunas distribuidas.
ð Objetivo: maximizar la aplicación de vacunas en las cuatro regiones.
bjj
Información de la red
Tablas
Resultado gráfico
Con este resultado se puede interpretar lo siguiente:
A continuación se planteara el modelo de una forma diferente, interpretando el mismo.
Ruta más corta, mediante: Cambio de variable.
Se desea utilizar el algoritmo de Dijkstra para solucionar el problema de ruta más corta entre dos nodos, los extremos, pero este no funciona muy bien con maximización ya que puede etiquetar a destiempo, entonces se recurrirá al siguiente cambio de variable para cada valor Cij se modifique por una penalización de tal forma que se busque minimizar con un valor Cij*
Se aplicara el siguiente algoritmo:
ð Primero se obtendrá el valor de A donde A= máx {Cij}.
En nuestra red A=15.
bbð Se obtendrá cada nuevo valor C*ij donde C*ij = A - Cij ∀ i,j.
C*ij = 15 - Cij ∀ i,j.
Ejemplo:
Y así para toda la red.
ð Se aplicara el algoritmo de Dijkstra buscando minimizar la penalización.
Nueva red
El algoritmo de Dijkstra para esta red utiliza más de 10 iteraciones por lo tanto se decidió solo poner algunas y el resultado final.
Debemos de tomar en cuenta el cambio de variable y regresarlo a los valores originales:
èPara el número de vacunas totales distribuidas utilizamos la siguiente formula:
No.de vacunas.distribuidas=(No.de arcos utilizados)*A-Penalizacion total
No.de vacunas distribuidas=4*15-40=20
èY para obtener el número de vacunas distribuidas en cada región:
No.de vacunas distribuidas por región: Cij =A-Cij*
Conclusión
Nos podemos dar cuenta por lo anterior que aunque veamos un problema de distinta manera y utilicemos dos métodos diferentes tanto en objetivo y forma de abordar el mismo, se llegara a un resultado equivalente, si tomamos todas las consideraciones de forma correcta.
==Bibliografía
“Ejercicios Programación dinámica.”
Diciembre-2011
No hay comentarios:
Publicar un comentario