a1 pd determinista se 2
DESCRIPTION
PD DETERMINISTICATRANSCRIPT
![Page 1: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/1.jpg)
INVESTIGACIÓN DE OPERACIONES II
Programación DinámicaINVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 2: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/2.jpg)
¿Como les fue con los acertijos?
Quien pasa al frente a explicar como los resolvió?
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 3: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/3.jpg)
Dos Acertijos para entender la PD
Acertijo de las cerillos: Suponga que hay 30 cerillos sobre una
mesa. Yo empiezo eligiendo 1, 2 ó 3 cerillos. Luego mi contrincante debe tomar 1, 2 ó 3 cerillos. Así continuamos hasta que alguno de los jugadores toma el última cerillo. Este jugador es el que pierde. ¿Cómo puedo yo (el primer jugador) estar seguro de ganar el juego?
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 4: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/4.jpg)
Dos Acertijos para entender la PD
Acertijo de las tazas de leche Tengo una taza de 9 onzas y otra de 4
onzas. Mi madre me pidió traer a casa exactamente 6 onzas de leche. ¿Cómo puedo cumplir lo pedido?
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 5: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/5.jpg)
SOLUCION (cerillos)…
Si puedo tener la certeza que le tocará el turno a mi oponente cuando quede una cerilla, claro que ganaré. Es decir, al yo estar seguro que queden 5 cerillos cuando sea el turno de mi oponente, GANARE!!!
Que les dice esto:5, 9, 13, 17, 21, 25, ò 29
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 6: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/6.jpg)
SOLUCION (tazas)…
Si puedo poner una onza de leche en la taza de cuatro onzas, luego lleno la taza de 9 onzas y vierto 3 onzas de leche en la taza de 9 onzas en la taza parcialmente llena de 4 onzas.
Taza de 9 onzas
Taza de 4 onzas
6 0
6 4
9 1
0 1
1 0
1 4
5 0
5 4
9 0
0 0INVESTIGACION DE
OPERACIONES IIIng. Juan Manuel Luna
Valle
![Page 7: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/7.jpg)
Naturaleza recursiva de la PD Los cálculos de programación dinámica se
hacen en forma recursiva, ya que la solución óptima de un subproblema se usa como dato para el siguiente subproblema.
Para cuando se resuelve el último subproblema queda a la mano la solución óptima de todo el problema.
La forma en la que se hacen los cálculos recursivos dependen de cómo se descomponga el problema original.
En particular, los subproblemas se vinculan normalmente mediante restricciones comunes.
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 8: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/8.jpg)
Un problema de redes…
Joe Cougar vive en Nueva York, pero quiere viajar en su automóvil hasta Los Ángeles en busca de fama y fortuna. Los fondos de Joe son limitados, así que decide pasar cada noche de su viaje en la casa de un amigo. Joe tiene amigos en cada ciudad.
Joe sabe que puede viajar un día a la vez y avanzar por etapas.
Luego de 4 días de manejar Joe puede llegar finalmente a Los Ángeles.
Para minimizar la cantidad de millas recorridas, ¿dónde debe Joe pasar cada noche del viaje?
INVESTIGACION DE
OPERACIONES IIIng. Juan Manuel Luna
Valle
![Page 9: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/9.jpg)
Nueva York
1
Omaha
6
Kansas City
5
Lousville
4
Nashville
3
Columbus
2
Dallas
7
San Antonio
9
Denver
8
Los Ángeles
10
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 10: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/10.jpg)
Solución con programación dinámica
Se determinará yendo hacia atrás (Recursividad)
Primero clasificamos todas las ciudades en la que Joe puede estar al principio del n-ésimo día de su viaje como ciudades de la etapa n.
Etapa 1: Nueva York Etapa 2: Columbus, Nashville, Louisville Etapa 3: Kansas City, Omaha, Dallas Etapa 4: Denver, San Antonio Etapa 5: Los Ángeles
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 11: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/11.jpg)
Los Ángeles
10
Nueva York
1
Omaha
6
Kansas City
5
Lousville
4
Nashville
3
Columbus
2
Dallas
7
San Antonio
9
Denver
8550
900 760
770
580
680
660
830
700
510
790
1050
270
790
540
940
610
790
1030
1390 Etapa 5
Etapa 4
Etapa 3
Etapa 2
Etapa 1
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 12: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/12.jpg)
Algoritmo para Recursividad
La idea de trabajar hacia atrás implica que debemos empezar por resolver un problema fácil que con el tiempo nos servirá para resolver uno más complejo.
Empezamos por determinar la trayectoria más corta a Los Ángeles desde cada ciudad de dónde hay sólo un día de viaje en automóvil (ciudades de la etapa 4).
Luego usamos esta información para encontrar el camino más corto hasta Los Ángeles desde cada ciudad donde hay 2 días de manejo (ciudades de la etapa 3).
Con esta información ya somos capaces de hallar el camino más corto desde cada ciudad que esté a 3 días de viaje (ciudades de la etapa 2).
Encontramos, por último, la trayectoria más corta a Los Ángeles desde cada ciudad que está a 4 días de viaje (hay sólo una: Nueva York).
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 13: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/13.jpg)
Criterios básicos
Con el fin de simplificar la exposición usamos los números 1, 2, 3,…, 10 dados en la figura para nombrar las 10 ciudades.
Definimos también cij como las millas entre la ciudad i y la ciudad j. Por ejemplo, c35 = 580 son las millas entre Nashville y Kansas City.
Hacemos ft(i) la distancia del camino más corto desde la ciudad i hasta Los Ángeles, dado que la ciudad i es una ciudad de la etapa t.
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 14: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/14.jpg)
Nueva York
1
Omaha
6
Kansas City
5
Lousville
4
Nashville
3
Columbus
2
Dallas
7
San Antonio
9
Denver
8
Los Ángeles
10
550
900 760
770
580
680
660
830
700
510
790
1050
270
790
540
940
610
790
1030
1390 Etapa 5
Etapa 4
Etapa 3
Etapa 2
Etapa 1
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 15: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/15.jpg)
Cálculos de la Etapa 4
Determinamos el camino más corto desde cada ciudad de la etapa 4 hasta L. A.
Como hay un solo camino desde cada ciudad, observamos que: f4(8) = 1030 f4(9) = 1390
San Antonio
9
Denver
8
Los Ángeles
10
1030
1390 Etapa 5
Etapa 4
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 16: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/16.jpg)
Cálculos de la Etapa 3
Determinamos el camino más corto desde cada ciudad de la etapa 3 hasta L. A.
Determinar f3(5) C58 + f4(8) = 610 + 1030 = 1640 * (5-8-10)
C59 + f4(9) = 790 + 1390 = 2180
Determinar f3(6) C68 + f4(8) = 540 + 1030 = 1570 * (6-8-10)
C69 + f4(9) = 940 + 1390 = 2330
Determinar f3(7) C78 + f4(8) = 790 + 1030 = 1820
C79 + f4(9) = 270 + 1390 = 1660 * (7-9-10)
Omaha
6
Kansas City
5
Dallas
7
San Antonio
9
Denver
8
Los Ángele
s
10
270
790
540
940
610
790
1030
1390 E 5
E 4
E 3INVESTIGACION DE
OPERACIONES IIIng. Juan Manuel Luna
Valle
![Page 17: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/17.jpg)
Cálculos de la Etapa 2
Determinamos el camino más corto desde cada ciudad de la etapa 2 hasta L. A.
Determinar f2(2) C25 + f3(5) = 680 + 1640 = 2320* (2-5-8-10) C26 + f3(6) = 790 + 1570 = 2360 C27 + f3(7) = 1050 + 1660 = 2710
Determinar f2(3) C35 + f3(5) = 580 + 1640 = 2220* (3-5-8-10) C36 + f3(6) = 750 + 1570 = 2330 C37 + f3(7) = 660 + 1660 = 2320
Determinar f2(4) C45 + f4(5) = 510 + 1640 = 2150* (4-5-8-10) C46 + f4(6) = 700 + 1570 = 2270 C47 + f4(7) = 830 + 1660 = 2490
6
5
4
3
2
7
9
8
10760
580
680
660
830
700
510
790
1050 27
0
790
540
940
610
790
1030
1390
E5
E4
E3E2
Ing. Juan Manuel Luna Valle
![Page 18: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/18.jpg)
Cálculos de la Etapa 1
Como ya conocemos f2(2), f2(3) y f2(4), podemos ir hacia atrás una etapa más para determinar f1(1) y, por lo tanto, el camino más corto de la ciudad 1 a la 10.
Obsérvese que el camino más corto desde la c1 a la c10 debe empezar por ir a la ciudad 2, 3 ó a la 4.
Esto significa que el camino más corto desde la c1 hasta la c10 tiene que ser uno de los siguientes: Camino 1. Ir desde la 1 hasta la 2, luego seguir el
camino más corto desde la 2 hasta la 10. [C12 + f2(2) ] Camino 2. Ir desde la 1 hasta la 3, luego seguir el
camino más corto desde la 3 hasta la 10. [C13 + f2(3) ] Camino 3. Ir desde la 1 hasta la 4, luego seguir el
camino más corto desde la 4 hasta la 10. [C14 + f2(4) ]INVESTIGACION DE
OPERACIONES IIIng. Juan Manuel Luna
Valle
![Page 19: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/19.jpg)
Continuación…
Determinar f1(1): C12 + f2(2) = 550 + 2320 = 2870 C13 + f2(3) = 900 + 2220 = 3120 C14 + f2(4) = 770 + 2150 = 2920
Camino óptimo: 1-2-5-8-10 Desde Nueva York hasta Los Ángeles pasará por:
Nueva York, Columbus, Kansas City, Denver y Los Ángeles.
Este camino tiene una distancia de f1(1) = 2780 millas
INVESTIGACION DE OPERACIONES II
Ing. Juan Manuel Luna Valle
![Page 20: a1 Pd Determinista Se 2](https://reader036.vdocumento.com/reader036/viewer/2022082400/5532a0b24a795994618b463f/html5/thumbnails/20.jpg)
16
5
4
3
2
7
9
8
10
2
4 2
3
3
6
4
5
1
3
4
6
3
3
6
3
1
3
3
4