Programacion determinista
Páginas: 36 (8775 palabras)
Publicado: 17 de noviembre de 2010
PROGRAMACIÓN DINÁMICA
DETERMINÍSTICA
10.1 INTRODUCCIÓN
La programación dinámica (PD) determina la solución óptima de un problema de n variables descomponiéndola en n etapas, con cada etapa incluyendo un subproblema de una sola variable. La ventaja en el aspecto de los cálculos es que optimizaremos una sola variable, en vez de subproblemas de n variables. La principal contribución de la PDes el principio de optimalidad, un marco de referencia para descomponer el problema en etapas. Debido a que la naturaleza de la etapa difiere, dependiendo del problema de optimización, la PD no proporciona los detalles de los cálculos para optimizar cada etapa. Quien resuelve el problema improvisa y diseña esos detalles.
10.2 NATURALEZA RECURSIVA DE LOS CÁLCULOS EN LA PD
Los cálculos en laPD se hacen recursivamente, en el sentido de que la solución óptima de un subproblema se utiliza como una entrada para el siguiente subproblema. Para el momento en que resolvamos el último subproblema, tendremos a la mano la solución óptima para todo el problema. La forma en la cual se hacen los cálculos recursivos depende de la forma en la cual descomponemos el problema original. En particular,los subproblemas por lo común se unen por medio de algunas restricciones comunes. A medida que avanzamos de un subproblema a otro, debemos dar razón de la viabilidad de estas restricciones.
Ejemplo 10.2-1 (PROBLEMA DE LA RUTA MÁS CORTA.)
Supongamos que usted quiere seleccionar la ruta de carretera más corta entre dos ciudades. La red en la figura 10- 1 proporciona las rutas posibles entre laciudad inicial en el nodo 1 y la ciudad de destino en el nodo 7. Las rutas atraviesan ciudades intermedias, designadas por los nodos 2 al 6.
Fig. 10-1
Podemos resolver este problema enumerando en forma exhaustiva todas las rutas entre los nodos 1 y 7 (hay cinco de esas rutas). Sin embargo, en una red más grande, le enumeración exhau tiva no es eficiente desde el punto de vista de loscálculos.
Para resolver el problema por medio de la PQ primero lo descomponemos en etapa& Las líneas verticales (de guiones) en la figura 10-2 delinean las tres etapas del problema. Después, hacemos los cálculos para cada etapa por separado.
Figura 10-2
La idea general es calcular las distancias (acumulativas) más cortas hacia todos los nodos terminales de una etapa y después utilizar esasdistancias como datos de entrada para la etapa inmediata siguiente. Considerando los nodos asociados con la etapa 1, podemos ver que los nodos 2,3 y 4 están conectados cada uno con el nodo inicial 1 por un solo arco (véase la figura 10-2). Por consiguiente, para la etapa 1 tenemos
Etapa 1 resumen de resultados
Distancia más corta al nodo 2 = 7 millas (desde el nodo 1)
Distancia más corta al nodo 3= 8 millas (desde el nodo 1)
Distancia más corta al nodo 4 = 5 millas (desde el nodo 1)
Después, avanzamos a la etapa 2 para determinar las distancias (acumulativas) más cortas a los nodos 5 y 6. Considerando primero el nodo 5, vemos por la figura 10-2 que hay tres rutas posibles para llegar al nodo 5, es decir (2,5),(3,5) y (4,5). Esta información, junto con las distancias más cortas a losnodos 2,3 y 4 determinan la distancia (acumulativa) más corta al nodo 5 como
Distancia más = min Distancia más + (Distancia desde el)
corta al nodo 5 i=2,3,4 corta al nodo i nodo i al nodo 5
7 + 12 = 19
= min 8 + 8 = 16 12 (desde el nodo 4)
1 5 + 7 = 12
De manera similar, para el nodo 6 tenemosDistancia más = min Distancias más + (Distancia desde el)
corta al nodo 6 i-3,4 corta al nodo i nodo i al nodo 6
= min 8 + 9 = 17 = 17 (desde el nodo 3)
5 + 13 = 18
Etapa 2 Resumen de resultados
Distancia más corta al nodo 5 = 12 millas (desde el nodo 4)
Distancia más corta al nodo 6 = 17 millas (desde el nodo 3)
El último paso es considerar la etapa 3. Se...
DETERMINÍSTICA
10.1 INTRODUCCIÓN
La programación dinámica (PD) determina la solución óptima de un problema de n variables descomponiéndola en n etapas, con cada etapa incluyendo un subproblema de una sola variable. La ventaja en el aspecto de los cálculos es que optimizaremos una sola variable, en vez de subproblemas de n variables. La principal contribución de la PDes el principio de optimalidad, un marco de referencia para descomponer el problema en etapas. Debido a que la naturaleza de la etapa difiere, dependiendo del problema de optimización, la PD no proporciona los detalles de los cálculos para optimizar cada etapa. Quien resuelve el problema improvisa y diseña esos detalles.
10.2 NATURALEZA RECURSIVA DE LOS CÁLCULOS EN LA PD
Los cálculos en laPD se hacen recursivamente, en el sentido de que la solución óptima de un subproblema se utiliza como una entrada para el siguiente subproblema. Para el momento en que resolvamos el último subproblema, tendremos a la mano la solución óptima para todo el problema. La forma en la cual se hacen los cálculos recursivos depende de la forma en la cual descomponemos el problema original. En particular,los subproblemas por lo común se unen por medio de algunas restricciones comunes. A medida que avanzamos de un subproblema a otro, debemos dar razón de la viabilidad de estas restricciones.
Ejemplo 10.2-1 (PROBLEMA DE LA RUTA MÁS CORTA.)
Supongamos que usted quiere seleccionar la ruta de carretera más corta entre dos ciudades. La red en la figura 10- 1 proporciona las rutas posibles entre laciudad inicial en el nodo 1 y la ciudad de destino en el nodo 7. Las rutas atraviesan ciudades intermedias, designadas por los nodos 2 al 6.
Fig. 10-1
Podemos resolver este problema enumerando en forma exhaustiva todas las rutas entre los nodos 1 y 7 (hay cinco de esas rutas). Sin embargo, en una red más grande, le enumeración exhau tiva no es eficiente desde el punto de vista de loscálculos.
Para resolver el problema por medio de la PQ primero lo descomponemos en etapa& Las líneas verticales (de guiones) en la figura 10-2 delinean las tres etapas del problema. Después, hacemos los cálculos para cada etapa por separado.
Figura 10-2
La idea general es calcular las distancias (acumulativas) más cortas hacia todos los nodos terminales de una etapa y después utilizar esasdistancias como datos de entrada para la etapa inmediata siguiente. Considerando los nodos asociados con la etapa 1, podemos ver que los nodos 2,3 y 4 están conectados cada uno con el nodo inicial 1 por un solo arco (véase la figura 10-2). Por consiguiente, para la etapa 1 tenemos
Etapa 1 resumen de resultados
Distancia más corta al nodo 2 = 7 millas (desde el nodo 1)
Distancia más corta al nodo 3= 8 millas (desde el nodo 1)
Distancia más corta al nodo 4 = 5 millas (desde el nodo 1)
Después, avanzamos a la etapa 2 para determinar las distancias (acumulativas) más cortas a los nodos 5 y 6. Considerando primero el nodo 5, vemos por la figura 10-2 que hay tres rutas posibles para llegar al nodo 5, es decir (2,5),(3,5) y (4,5). Esta información, junto con las distancias más cortas a losnodos 2,3 y 4 determinan la distancia (acumulativa) más corta al nodo 5 como
Distancia más = min Distancia más + (Distancia desde el)
corta al nodo 5 i=2,3,4 corta al nodo i nodo i al nodo 5
7 + 12 = 19
= min 8 + 8 = 16 12 (desde el nodo 4)
1 5 + 7 = 12
De manera similar, para el nodo 6 tenemosDistancia más = min Distancias más + (Distancia desde el)
corta al nodo 6 i-3,4 corta al nodo i nodo i al nodo 6
= min 8 + 9 = 17 = 17 (desde el nodo 3)
5 + 13 = 18
Etapa 2 Resumen de resultados
Distancia más corta al nodo 5 = 12 millas (desde el nodo 4)
Distancia más corta al nodo 6 = 17 millas (desde el nodo 3)
El último paso es considerar la etapa 3. Se...
Leer documento completo
Regístrate para leer el documento completo.