SESIÓN 4

INVESTIGACIÓN DE OPERACIONES 2
Sesión 4.1: Introducción a la Programación Dinámica Determinística

7

B

E

4

1

6

4

2

H
3

3

A

4

6
2

C

J

F
3

4

4

I

3
4

3
1

D

3
5

G

CASO: ACERTIJO DE LAS BOLILLAS
Suponga que hay 20 bolillas en un vaso
Comienzo tomando 1, 2 o 3 bolillas. Entonces mi oponente debe tomar 1, 2 o 3 bolillas.
Continuamos de este modo hasta que se toma la últimabolilla. El perdedor es el jugador
que toma la última bolilla.
¿Cómo puedo estar seguro de ganar el juego? Si mi turno es el primero.

5 – 9 – 13 – 17 – 21 – 25 – 29 – …

OPINIONES:
•

¿Cuál ha sido la lógica de solucionar el caso?

CASO: ACERTIJO DE AGUA
Tengo una taza de 9 onzas y una taza de 4 onzas.
Usando ambas tazas, quiero medir exactamente 6 onzas de agua.

¿Cómo puedo medir esta cantidad?
9onzas
6
6
9
0
1
1
5
5
9
0

OPINIONES:
•

¿Cuál ha sido la lógica de solucionar el caso?

4 onzas
0
4
1
1
0
4
0
4
0
0

CASO 1: 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 trasladarsede
un nodo a otro.
7

B

E

4

1

6

4

2

H
3

3

A

4

6
2

C

J

F
3

4

4

I

3
4

3
1

D

3
5

G

PREGUNTAS:
•

¿Cómo se puede desarrollar este caso planteado?

LOGRO DE LA SESIÓN

•

Los estudiantes 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
•

Una formarazonable y comúnmente empleada de resolver un problema es definir o
caracterizar su solución en términos de las soluciones de sub-problemas 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 sub-problema de
una sola variable.

•

A diferencia de la programación lineal, el modelado de problemas deprogramació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.

1. PROGRAMACIÓN DINÁMICA

ETAPA 1

ETAPA 2

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.

ETAPA 3
7

B

4

ETAPA 4

E

6

1

4

H

2

3

A

4

2

C

J

F
3

4

4

I

3

4

3

1

D

3

6

3

5

G

1. PROGRAMACIÓN DINÁMICA
•

Los cálculos de programación dinámica se hacen en forma recursiva, ya que la
soluciónóptima de un sub-problema se usa como dato para el siguiente subproblema. Para cuando se resuelve el último sub-problema se obtiene la solución
óptima de todo el problema.

•

Al pasar de un sub-problema al siguiente se debe mantener la factibilidad de esas
restricciones comunes.

•

Se usa la recursión en avance, cuando los cálculos se hacen de la primera etapa a la
última etapa; y se usa larecursión en reversa, cuando los cálculos se hacen de la
última etapa a la primera etapa. Con las recursiones en avance y en reversa se
obtiene la misma solución. Se usa la recursión en reversa porque, en general, es
más eficiente desde el punto de vista computacional.
Función recursiva: fi ( xi ) = min { d (xi , xi+1 ) + fi+1 (xi+1) }
Donde:
fi ( xi ) : distancia más corta al nodo xi en la etapa i.
d (xi, xi+1 ) : distancia del nodo xi al nodo xi+1.

CASO 1: RUTA MÁS CORTA
7

B

E

4

1

6

4

2

H
3

3

A

4

6
2

C

J

F
3

4

4

I

3
4

3
1

D

f1

f2

3
5

G

f3

Costo Total = ??

Ruta : ??

f4

f5

CASO 1: RUTA MÁS CORTA
7

B

E

4

1

6

4

2

H
3

3

A

4

6
2

C

J

F
3

4

4

I

3
4

3
1

D

f1

f2

3
5

G

f3

f4

f5

Función recursiva: fi ( xi ) = min { d (xi , xi+1 ) + fi+1...