Programaci N Din Mica Donar
Páginas: 4 (761 palabras)
Publicado: 24 de abril de 2015
Programación Dinámica
La programación dinámica es una técnica matemática útil para la
toma de decisiones secuenciales interrelacionadas. Proporciona
un procedimiento sistemático para determinar lacombinación
óptima de decisiones.
En contraste con la programación lineal, no cuenta con una
formulación
matemática
estándar
“del”
problema
de
programación dinámica, sino que se trata de un enfoque detipo
general para solucionar problemas; además, las ecuaciones
específicas que se usan deben ajustarse a la situación particular.
Por tanto, es necesario cierto grado de creatividad y un buenconocimiento de la estructura general de los problemas de
programación dinámica para reconocer cuando y como un
problema puede ser resuelto por medio de estos procedimientos.
El problema de Diligencia
Uncazafortunas de Missouri que decide ir al Oeste a la fiebre del
oro en California tiene que hacer un viaje de diligencia a través de
territorios sin ley desde el punto i (Missouri) hasta el destino j(California), el hombre prudente preocupado de su seguridad busca
la ruta más segura y con el menor costo total CTij. El costo de la
póliza estándar del viaje en diligencia, del estado i al estado jse
denota como cij. A continuación se representan los estados y las
rutas posibles en figura 1;
FIGURA 1
Sistema de caminos y
costos del problema de la
diligencia.
El problema de Diligencia
A
B
2C
4
D
3
B
E
7
F
4
G
6
E
H
1
I
4
H
J
3
C
3
2
4
F
6
3
I
4
La pregunta se centrará, ¿Cuál esDla ruta
que
minimiza
el 3costo3 total de la póliza?
4
1
5
G
Solución del problema
Observeprimero que el procedimiento poco inteligente de elegir la ruta más barata en cada
etapa sucesiva no conduce a una decisión óptima global. En caso de adoptar esta estrategia,
se obtiene la ruta A → B→ F → I → J, con un costo total de 13.
La programación dinámica proporciona una solución con mucho menos esfuerzo que la
enumeración exhaustiva, la solución óptima obvia de este problema reducido...
La programación dinámica es una técnica matemática útil para la
toma de decisiones secuenciales interrelacionadas. Proporciona
un procedimiento sistemático para determinar lacombinación
óptima de decisiones.
En contraste con la programación lineal, no cuenta con una
formulación
matemática
estándar
“del”
problema
de
programación dinámica, sino que se trata de un enfoque detipo
general para solucionar problemas; además, las ecuaciones
específicas que se usan deben ajustarse a la situación particular.
Por tanto, es necesario cierto grado de creatividad y un buenconocimiento de la estructura general de los problemas de
programación dinámica para reconocer cuando y como un
problema puede ser resuelto por medio de estos procedimientos.
El problema de Diligencia
Uncazafortunas de Missouri que decide ir al Oeste a la fiebre del
oro en California tiene que hacer un viaje de diligencia a través de
territorios sin ley desde el punto i (Missouri) hasta el destino j(California), el hombre prudente preocupado de su seguridad busca
la ruta más segura y con el menor costo total CTij. El costo de la
póliza estándar del viaje en diligencia, del estado i al estado jse
denota como cij. A continuación se representan los estados y las
rutas posibles en figura 1;
FIGURA 1
Sistema de caminos y
costos del problema de la
diligencia.
El problema de Diligencia
A
B
2C
4
D
3
B
E
7
F
4
G
6
E
H
1
I
4
H
J
3
C
3
2
4
F
6
3
I
4
La pregunta se centrará, ¿Cuál esDla ruta
que
minimiza
el 3costo3 total de la póliza?
4
1
5
G
Solución del problema
Observeprimero que el procedimiento poco inteligente de elegir la ruta más barata en cada
etapa sucesiva no conduce a una decisión óptima global. En caso de adoptar esta estrategia,
se obtiene la ruta A → B→ F → I → J, con un costo total de 13.
La programación dinámica proporciona una solución con mucho menos esfuerzo que la
enumeración exhaustiva, la solución óptima obvia de este problema reducido...
Leer documento completo
Regístrate para leer el documento completo.