MODELOS DETERMINÍSTICOS DE DECISIÓN

SEMANA N° 4

Programación Dinámica
Determinística
Edgard Gustavo Solis Vargas
Interés

[Link]
 Interés

¿Cuántas
alternativas tenemos
para ir de la casa a la
universidad?

¿Puedo dividir un
problema grande en
sub problemas?
[Link]
AGENDA

1. Introducción.
2. Elementos de un Problema de Programación
Dinámica (PD).
3. Caso de Aplicación.
 LOGRO DE LA SESIÓN

Al término de la sesión el estudiante encuentra la solución óptima de

diversos problemas de toma de decisiones utilizan el enfoque de la

Programación Dinámica y el uso del cálculo recursivo.

 Descubrimiento

1.- Introducción
Una forma razonable y comúnmente empleada de resolver un problema es definir o caracterizar su
solución en términos de las soluciones de subproblemas del mismo.

La programación dinámica encuentra la solución óptima de un problema con n variables,

descomponiéndolo en n etapas, siendo cada etapa un subproblema de una sola variable.

A diferencia de la programación lineal, el modelado de problemas de programación dinámica no

sigue una forma estándar.

Principio de optimalidad: Dado el estado actual, la decisión óptima para cada una de las etapas
restantes no tiene que depender de los estados ya alcanzados o de las decisiones tomadas
previamente.
 Descubrimiento

1.- Introducción
Caso de análisis:
Deseamos hallar la ruta más corta, partiendo del punto “A” hasta llegar al punto “J”, los valores en
los arcos representan costos, distancias o tiempo entre los diversos nodos.

7
B E
4 1
6 4
2 H
3 3
6
4 2
A C F J
4 3
4
3 I
4 3
1 3
D 5 G
 Descubrimiento

2.- Elementos de un Problema de PD.

Etapas: Decisiones:
Este problema puede En cada etapa se toman
ser dividido en cuatro decisiones o el nodo al
etapas cual ir.
7
B E
Etapa 1 4 1 Etapa 1: Nodos B, C o D.
Etapa 2 6 4 Etapa 2: Nodos E, F o G.
2 H
Etapa 3 Etapa 3: Nodos H, I.
3 3
Etapa 4 6 Etapa 4: Nodo tomar
J.
4 2
A C F J
4 3
4
Estados: 3 I
Cada etapa tiene sus 4 3 Función Recurrente:
1 3 Es el resultado de las
estados o el nodo de D G
5 decisiones.
partida.

Etapa 1: Nodo A.
Etapa 2: Nodos B, C y D.
Etapa 3: Nodos E, F y G.
Etapa 4: Nodos H, I.

Etapa 1 Etapa 2 Etapa 3 Etapa 4

 Descubrimiento

2.- Elementos de un Problema de PD.

7
B E
4 1
6 4 X1=B,C,D X2=E,F,G X3=H,I X4=J
2 H
3 3
6 S1 =A tomar
4 2 S2 S3
A C F J S4 S5
3 1 2 3 4
4 4
3 I B E H
4 3 C F J
1 3 I
D 5 G R1 D R2 G R3 R4

Etapa 1 Etapa 2 Etapa 3 Etapa 4

 Experiencia
ESTRUCTURA PPT

3.- Caso de Aplicación

Caso de análisis:
Deseamos hallar la ruta más corta, partiendo del punto “A” hasta llegar al punto “J”, los valores en
los arcos representan costos, distancias o tiempo entre los diversos nodos.

Si se tomara la decisión de ir por la ruta más barata

en cada etapa, ésta sería: A – B – F – I – J con un B 7
E
costo total asociado de 13. 4 1
6 4
2 H
Note que, si desde el nodo A llegamos al 3 3
6
nodo F mediante D, en lugar de ir por B, 4 2
el costo sería menor. A C F J
4 3
4
Variables de decisión: 3 I
4 3
xn : destino inmediato de la etapa n, 1 3
D 5 G
Estado:
sn : lugar donde se encuentra en la etapa n

Función recursiva: fn(sn , xn)= csnxn + fn+1*(xn)

 Experiencia
ESTRUCTURA PPT

Primera Iteración – Etapa 4

Iniciamos resolviendo la última etapa, el destino final es x4 = J y su estado actual s4 puede ser H o I ,
de manera que su último tramo es desde s4 hacia J. Por lo tanto, f4*(s4) = f4(s4, J) = cs4J
7
B E
4 1
6 4
2 H
3 3
6
4 2
A C F J
4 3
4
3 I
4 3
1 3
D 5 G

Etapa 4
Solución de la Etapa 4
f4(s4 ,x4)= cs4x4 Solución óptima
s4 x4 = J f4*(s4) x4*
H 3 3 J
I 4 4 J
 Experiencia
ESTRUCTURA PPT

Segunda Iteración – Etapa 3

Iniciamos resolviendo la última etapa, el destino final es x4 = J y su estado actual s4 puede ser H o I ,
de manera que su último tramo es desde s4 hacia J. Por lo tanto, f4*(s4) = f4(s4, J) = cs4J

Solución de la Etapa 4 7
B E
4 1
f4(s4 ,x4)= cs4x4 Solución óptima 6 4
2 H
s4 x4 = J f4*(s4) x4* 3 3
6
4 2
H 3 3 J A C F J
4 3
I 4 4 J 4
3 I
4 3
1 3
D 5 G
Solución de la Etapa 3
f3(s3 ,x3)= cs3x3 + f4*(x3) Solución óptima
s3 x3 = H x3 = I f3*(s3) x3* Etapa 3
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
 Experiencia
ESTRUCTURA PPT

Tercera Iteración – Etapa 2

Iniciamos resolviendo la última etapa, el destino final es x4 = J y su estado actual s4 puede ser H o I ,
de manera que su último tramo es desde s4 hacia J. Por lo tanto, f4*(s4) = f4(s4, J) = cs4J

7
Solución de la Etapa 3 B E
4 1
6 4
f3(s3 ,x3)= cs3x3 + f4*(x3) Solución óptima 2 H
3 3
s3 x3 = H x3 = I *
f3 (s3) x3* 6
4 2
E 1+3=4 4+4=8 4 H A C F J
4 3
4
F 6+3=9 3+4=7 7 I 3 I
4 3
G 3+3=6 3+4=7 6 H 1 3
D 5 G

Solución de la Etapa 2
f2(s2 ,x2)= cs2x2 + f3*(x2) Solución óptima Etapa 2
s2 x2 =E x2 =F x2 =G f2*(s2) x2*
B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 EoF
C 3+4= 7 2+7= 9 4 + 6 = 10 7 E
D 4+4= 8 1+7= 8 5 + 6 = 11 8 EoF
 Experiencia
ESTRUCTURA PPT

Cuarta Iteración – Etapa 1

Iniciamos resolviendo la última etapa, el destino final es x4 = J y su estado actual s4 puede ser H o I ,
de manera que su último tramo es desde s4 hacia J. Por lo tanto, f4*(s4) = f4(s4, J) = cs4J

7
Solución de la Etapa 2 B E
4 1
6 4
f2(s2 ,x2)= cs2x2 + f3*(x2) Solución óptima 2 H
3 3
6
s2 x2 =E x2 =F x2 =G f2*(s2) x2* 4 2
A C F J
B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 EoF 4 3
4
C 3+4= 7 2+7= 9 4 + 6 = 10 7 E 3 I
4 3
1 3
D 4+4= 8 1+7= 8 5 + 6 = 11 8 EoF D G
5

Solución de la Etapa 1
Etapa 1
f1(s1 ,x1)= cs1x1 + f2*(x1) Solución óptima
x1 =B x1 =C x1 =D f1*(s1) x1*
s1
A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 CoD
 Experiencia
ESTRUCTURA PPT
Solución Óptima
7
Solución de la Etapa 4 B E
4 1
6 4
f4(s4 ,x4)= cs4x4 Solución óptima 2 H
3 3
s4 x4 = J f4*(s4) x4* 6
4 2
A C F J
H 3 3 J 4 3
4
I 4 4 J 3 I
4 3
1 3
Solución de la Etapa 3 D G
5
f3(s3 ,x3)= cs3x3 + f4*(x3) Solución óptima
s3 x3 = H x3 = I f3*(s3) x3*
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I Costo Total = 11
G 3+3=6 3+4=7 6 H Ruta 1: A – D – F – I – J
3 + 1 + 3 + 4 = 11
Solución de la Etapa 2
f2(s2 ,x2)= cs2x2 + f3*(x2) Solución óptima
x2 =E x2 =F x2 =G f2*(s2) x2*
Costo Total = 11
s2
Ruta 2: A – C – E – H – J
B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 EoF
4 + 3 + 1 + 3 = 11
C 3+4= 7 2+7= 9 4 + 6 = 10 7 E
D 4+4= 8 1+7= 8 5 + 6 = 11 8 EoF El problema tiene
Solución de la Etapa 1 múltiples soluciones
f1(s1 ,x1)= cs1x1 + f2*(x1) Solución óptima
s1 x1 =B x1 =C x1 =D f1*(s1) x1*
A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 CoD
 Aprendizaje
ESTRUCTURA PPTevidenciado

TRABAJO APLICATIVO

Desarrollar los casos propuestos como actividades en la semana actual.

INSTRUMENTO DE EVLUACIÓN

INSTRUMENTO DE EVALUACIÓN
• Al finalizar la sesión de aprendizaje los estudiantes trabajan en grupos y elaboran
una tabla resumen sobre una glándula asignada, mostrando, orden, información
precisa , redacción legible y puntualidad.

CRITERIO DESCRIPCIÓN
NL EP L COMENTARIO PTJE
Trabajo Colaboran entre 3 o 4 estudiantes
0 2 4
colaborativo para el diseño y elaboración de la
propuesta de sesión de clase.
Identificación de
0 3 4
las etapas,
Identifican las etapas, estados de
estados y
cada etapa y las decisiones.
decisiones

Desarrollo de la
Resuelve cada etapa, realizando la 0 2 4
solución en
operación recursiva.
cada iteración

Identificación de
Identifica la o las soluciones 0 2 6
la solución
óptimas.
óptima
La entrega del trabajo cumple con
Puntualidad 0 1 2
los plazos establecidos
 REFERENCIAS

• Hamdy A. Taha, (2016). Investigación de Operaciones Una Introducción.

• Gustavo Solis y Luis Ulfe (2019). Modelamiento matemático usando LINGO.