SESIÓN 5 INVOP2 PROGRAMACIÓN DINÁMICA DETERMINÍSTICA PRESENTACIÓN
Páginas: 5 (1182 palabras)
Publicado: 25 de octubre de 2015
INVESTIGACIÓN DE OPERACIONES 2
Sesión 5: Programación Dinámica Determinística
CASO: RUTA MÁS CORTA
Tomando en cuenta el siguiente sistema de caminos, si se encuentra inicialmente en el
nodo A, encontrar la trayectoria más económica para llegar al nodo J considerando que
los valores que se encuentran en las ramas representan los costos ($) de trasladarse de
un nodo a otro.
7
B
E
4
1
6
42
H
3
3
A
4
6
2
C
J
F
3
4
4
I
3
4
3
1
D
3
5
G
OPINIONES:
•
¿Cómo se puede desarrollar este caso planteado, con recursión progresiva (hacia
adelante)?
CASO 1: VUELO ADICIONAL
Se ha informado a Taca Perú, que podría programar seis vuelos adicionales para este
día que partan desde Lima. El destino de cada vuelo podría ser Trujillo, Tumbes o
Arequipa. En la tabla se presenta lacontribución a la utilidad de la compañía por parte
de los vuelos diarios desde Lima a cada destino posible.
Trujillo
Tumbes
Arequipa
1
80
100
90
2
150
195
180
3
210
275
265
4
260
325
310
5
270
300
350
6
280
250
320
PREGUNTAS:
•
Establezca la cantidad óptima de vuelos que deben partir de Lima a cada destino
para maximizar la utilidad de estos vuelos adicionales.
LOGRO DE LA SESIÓN
•
Losestudiantes al finalizar la sesión
tendrán las competencias para resolver
problemas de decisión organizacional
mediante el uso de programación
dinámica determinística.
1. PROGRAMACIÓN DINÁMICA
•
La programación dinámica es un procedimiento matemático diseñado principalmente
para mejorar la eficiencia de cálculo de problemas de programación matemática
seleccionados, descomponiéndolos ensub-problemas de menor tamaño y más
fáciles de calcular.
•
La PD generalmente resuelve el problema en etapas. Los cálculos en las diferentes
etapas se enlazan a través de cálculos recursivos de manera que se genera una
solución óptima factible a todo el problema
•
Los cálculos se realizan recursivamente donde la solución optima de un subproblema se utiliza como dato de entrada para el siguientesub-problema
•
La solución para todo el problema se obtiene cuando se soluciona el ultimo subproblema.
2. CARACTERÍSTICAS DE PROGRAMACIÓN DINÁMICA
•
Es posible dividir el problema en etapas, y se requiere una decisión en cada etapa.
•
Cada etapa se relaciona con una cierta cantidad de etapas
•
La decisión tomada en cualquier etapa describe el modo en que el estado actual se
transforma en elestado siguiente
•
Dado el estado actual, la decisión optima para cada una de las etapas restantes no
tiene que depender de los estados ya alcanzados o de la decisión ya tomada
previamente
•
Si los estados del problema se clasifican dentro de uno de T etapas, debe haber una
recursión que relacione la etapa t con la etapa t+1; en forma progresiva o regresiva.
3. RECURSIÓN EN PROGRAMACIÓNDINÁMICA
El problema de programación dinámica se puede dividir en T etapas, entonces:
•
•
Un problema de PD utiliza la recursividad hacia adelante (Recursividad Progresiva)
en los cuales los cálculos proceden de la etapa 1 a la etapa T.
El mismo problema de PD puede resolverse por medio de recursividad hacia atrás
(Recursividad Regresiva) comenzando en la etapa T y terminando en la etapa 1.
EJEMPLO:
Alcomienzo del año 0 un granjero posee k ovejas. Al final de cada año decide cuántas
debe vender y cuantas conservar. La ganancia obtenida por la venta de una oveja en el
año i es pi. Las ovejas que conserve duplicara su número en el transcurso del año. El
granjero venderá todas sus ovejas al cabo de n años
4. PROGRAMACIÓN DINÁMICA DETERMINÍSTICA (PDD)
•
La PDD enfoca los problemas en formadeterminística, en los cuales el estado de la
siguiente etapa esta determinado por completo por el estado y la política de decisión
de la etapa actual.
•
La solución se obtiene usando la recursión regresiva o progresiva
5. PDD MEDIANTE RECURSIÓN
•
El objetivo del problema es encontrar los valores de xi, que optimizan el retorno
global.
•
El retorno global casi siempre es la suma de los...
Sesión 5: Programación Dinámica Determinística
CASO: RUTA MÁS CORTA
Tomando en cuenta el siguiente sistema de caminos, si se encuentra inicialmente en el
nodo A, encontrar la trayectoria más económica para llegar al nodo J considerando que
los valores que se encuentran en las ramas representan los costos ($) de trasladarse de
un nodo a otro.
7
B
E
4
1
6
42
H
3
3
A
4
6
2
C
J
F
3
4
4
I
3
4
3
1
D
3
5
G
OPINIONES:
•
¿Cómo se puede desarrollar este caso planteado, con recursión progresiva (hacia
adelante)?
CASO 1: VUELO ADICIONAL
Se ha informado a Taca Perú, que podría programar seis vuelos adicionales para este
día que partan desde Lima. El destino de cada vuelo podría ser Trujillo, Tumbes o
Arequipa. En la tabla se presenta lacontribución a la utilidad de la compañía por parte
de los vuelos diarios desde Lima a cada destino posible.
Trujillo
Tumbes
Arequipa
1
80
100
90
2
150
195
180
3
210
275
265
4
260
325
310
5
270
300
350
6
280
250
320
PREGUNTAS:
•
Establezca la cantidad óptima de vuelos que deben partir de Lima a cada destino
para maximizar la utilidad de estos vuelos adicionales.
LOGRO DE LA SESIÓN
•
Losestudiantes al finalizar la sesión
tendrán las competencias para resolver
problemas de decisión organizacional
mediante el uso de programación
dinámica determinística.
1. PROGRAMACIÓN DINÁMICA
•
La programación dinámica es un procedimiento matemático diseñado principalmente
para mejorar la eficiencia de cálculo de problemas de programación matemática
seleccionados, descomponiéndolos ensub-problemas de menor tamaño y más
fáciles de calcular.
•
La PD generalmente resuelve el problema en etapas. Los cálculos en las diferentes
etapas se enlazan a través de cálculos recursivos de manera que se genera una
solución óptima factible a todo el problema
•
Los cálculos se realizan recursivamente donde la solución optima de un subproblema se utiliza como dato de entrada para el siguientesub-problema
•
La solución para todo el problema se obtiene cuando se soluciona el ultimo subproblema.
2. CARACTERÍSTICAS DE PROGRAMACIÓN DINÁMICA
•
Es posible dividir el problema en etapas, y se requiere una decisión en cada etapa.
•
Cada etapa se relaciona con una cierta cantidad de etapas
•
La decisión tomada en cualquier etapa describe el modo en que el estado actual se
transforma en elestado siguiente
•
Dado el estado actual, la decisión optima para cada una de las etapas restantes no
tiene que depender de los estados ya alcanzados o de la decisión ya tomada
previamente
•
Si los estados del problema se clasifican dentro de uno de T etapas, debe haber una
recursión que relacione la etapa t con la etapa t+1; en forma progresiva o regresiva.
3. RECURSIÓN EN PROGRAMACIÓNDINÁMICA
El problema de programación dinámica se puede dividir en T etapas, entonces:
•
•
Un problema de PD utiliza la recursividad hacia adelante (Recursividad Progresiva)
en los cuales los cálculos proceden de la etapa 1 a la etapa T.
El mismo problema de PD puede resolverse por medio de recursividad hacia atrás
(Recursividad Regresiva) comenzando en la etapa T y terminando en la etapa 1.
EJEMPLO:
Alcomienzo del año 0 un granjero posee k ovejas. Al final de cada año decide cuántas
debe vender y cuantas conservar. La ganancia obtenida por la venta de una oveja en el
año i es pi. Las ovejas que conserve duplicara su número en el transcurso del año. El
granjero venderá todas sus ovejas al cabo de n años
4. PROGRAMACIÓN DINÁMICA DETERMINÍSTICA (PDD)
•
La PDD enfoca los problemas en formadeterminística, en los cuales el estado de la
siguiente etapa esta determinado por completo por el estado y la política de decisión
de la etapa actual.
•
La solución se obtiene usando la recursión regresiva o progresiva
5. PDD MEDIANTE RECURSIÓN
•
El objetivo del problema es encontrar los valores de xi, que optimizan el retorno
global.
•
El retorno global casi siempre es la suma de los...
Leer documento completo
Regístrate para leer el documento completo.