INSTITUTO POLITÉCNICO NACIONAL

ESCUELA SUPERIOR DE ECONOMÍA

OPTIMIZACIÓN DINÁMICA

YAÑEZ JIMENÉZ CARLOS ALBERTO

4.5. ACTIVIDAD DE INTRODUCCIÓN A LA

PROGRAMACIÓN DINÁMICA.

GARCIA MANZANO YESENIA ELOISA

CARRANZA GALICIA JOSE RAFAEL

2EM19

02 DE JUNIO DEL 2022

1
 .................................................................................................................................... 3

......................................................................................................................... 4

.............................................................................................................................. 6

........................................................................................................................... 25

EJERCICIO 6.1 ................................................................................................................................ 25

EJERCICIO 6.2 ................................................................................................................................ 27
EJERCICIO 6.4 ................................................................................................................................ 30
Ejercicio 6.5 ................................................................................................................................... 32
Ejercicio 6.6 ................................................................................................................................... 34
Ejercicio 6.7 ................................................................................................................................... 36
....................................................................................................................... 39

..................................................................................................................... 40

2
Los alumnos deberán crear un panorama mas complejo acerca de las aplicaciones
de la programación dinámica, para qué, de esta forma sea accesible para
estudiantes de la licenciatura, tratando así los elementos básicos de la teoría para
su comprensión. Utilizando el problema básico de control optimo discreto, para
identificar y formular su solución mediante la técnica de programación dinámica de
Bellman e identificar los casos que se presentan para proceder a su
planteamiento y la solución del problema.

3
Para el planteamiento del problema de control optimo discreto, se tiene un
sistema dinámico formulado en tiempo discreto, para un número dado N de etapas
o períodos, donde la situación inicial viene dada por el vector n.-dimensional 𝑥0 , y
que evoluciona en el tiempo. Dicha evolución depende del valor que se dé a cierta
variable nombrada variable de control, que permiten influir en el sistema. Donde
𝑢(𝑘), será el vector m-dimensional de las variables de control en la etapa o periodo
k, para 𝑘 ∈ (0,1, … , 𝑁 − 1).Representado por 𝑥(𝑘), para cada 𝑘 ∈ (0,1, … . , 𝑁 −
1),el vector n-dimensional llamado variable de estado, que nos indicará la
situación del sistema en la etapa o periodo k.

Esto quiere decir, que el sistema dinámico parte del estado inicial 𝑥0 .En el periodo
o etapa 1 (que corresponde a 𝑘 = 0), donde se elige un control 𝑛(0) ∈ Ω(0), en
dicho periodo o etapa se realiza una aportación al funcional objetivo dada por F
[𝑥(0), 𝑢(0),0] y se inicia el periodo o etapa 2 (que corresponde a 𝑘 = 1) con un
valor de vector de estado: 𝑥(1) = 𝑓(𝑥(0), 𝑢(0), 0).

En dicha etapa se tendrá que elegir un control 𝑢(1) ∈ Ω(1). Además se realiza una
aportación al funcional objetivo dada por 𝐹 [𝑥, (1), 𝑢(1), 1]y se inicia el período o
etapa 3 (que corresponde a 𝑘 = 2)con un vector de valor de estado:𝑥(2) =
𝑓(𝑥(1), 𝑢(1), 1).

Se continua de esta manera hasta que por último comienza el período o etapa N
(que corresponde a 𝑘 = 𝑁 − 1)con un estado inicial 𝑥, y hay que elegir un control
𝑢(𝑁 − 1) ∈ Ω(𝑁 − 1), donde se realizara una aportación al funcional objetivo dada
por 𝐹[𝑥(𝑁 − 1), 𝑢 (𝑁 − 1), (𝑁 − 1], alcanzando el sistema en un estado final 𝑥(𝑁) =
𝑓(𝑥(𝑁 − 1), 𝑢(𝑁 − 1), 𝑁 − 1). Al terminar en dicho estado, se realiza una
aportación al funcional objetivo dado por 𝑆[𝑥(𝑁)].

Un control optimo es definido por un control 𝑢(𝑘) ∈ Ω (𝑘)∁ℝ𝑚 , 𝑝𝑎𝑟𝑎 𝑘 = 0,1, … , 𝑁 −

1,(por tanto, admisible), que maximice el funcional objetivo.

4
La programación dinámica, introducida por Bellman (1957), fue creada para
resolver problemas formulados en tiempo discreto, aunque posteriormente sería
adaptada para la resolución de problemas en tiempo continuo. Puesto que la
programación dinámica busca resolver un problema de N etapas o períodos,
mediante la resolución de N problemas de etapas o períodos.

Al igual que en el caso de control óptimo, el funcional objetivo a maximizarse

constituye la suma de las utilidades futuras de la sociedad descontadas por el
factor β. Por otro lado, en este modelo en particular, no se asume depreciación y
la producción en un período determinado (∅(𝑘𝑡 )) se destina tanto a consumo
(𝐶𝑡 ) como al stock de capital del siguiente período (𝑘𝑡 + 1).

Una variación al problema consistiría en introducir shocks estocásticos a la

función de producción (∅(𝑘𝑡 )), tal como se establece en el modelo de crecimiento
estocástico desarrollado por Brock y Mirman. En dicho caso, la variación de la

producción no se encuentra asociada exclusivamente a cambios en el stock de

capital en la economía, sino que además intervienen un conjunto de elementos
aleatorios o no anticipados que pueden resumirse en una variable estocástica ℇ𝑡 .

En este sentido, asumiendo la función de producción ∅(ℇ𝑡 , 𝑘𝑡 ) el objetivo del

planificador social vendría a ser la maximización del valor esperado (o promedio)
del funcional objetivo condicionado a la información del período inicial 𝑡 = 0.

Mientras que en la ecuación de Bellman ecuación es una relación recursiva

fundamental que traduce matemáticamente el principio Básico de la
Programación Dinámica llamado el principio de Optimalidad de Bellman, que
coloquialmente dice que el valor máximo que se puede obtener desde el estado
𝑊𝑤𝑡 es el valor máximo desde el estado siguiente más el valor máximo de 𝑓 una
vez optimizada con respecto a la variable de control para el periodo 𝑡.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
EJERCICIO 6.1
Se trata de construir una autopista entre dos ciudades Ay K, existiendo varias
ciudades por las que puede pasar la autopista, tal como se indica el siguiente
grafo, pudiendo clasificarse estas ciudades en grupos o fases habiéndose
asignado a los arcos del grafo, el importe de los costes totales en cientos de
millones de pesetas (costes de realización, costes de expropiación, etc.

Determinar, utilizando programación dinámica, a la autopista de coste mínimo que

une las ciudades A y K.

ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4

25
 SOLUCIÓN

Etapa 4 Etapa 3 Etapa 2 Etapa 1

𝐺 − 𝐾 = 30 𝐸 − 𝐺 = 40 + 30 = 70 𝐵 − 𝐸 = 50 + 70 = 120 𝐴 − 𝐵 = 15 + 80 = 95
𝑀 − 𝐾 = 25 𝐵 − 𝐸 = 50 + 60 = 110 𝐴 − 𝐶 = 20 + 80 =
𝐼 − 𝐾 = 20 𝐸 − 𝑀 = 35 + 25 = 60 𝐵 − 𝐸 = 50 + 60 = 110 100
𝐽 − 𝐾 = 35 𝐹 − 𝑀 = 45 + 25 = 70 𝐶 − 𝐸 = 20 + 70 = 90 𝐴 − 𝐷 = 30 + 75 = 105
𝐶 − 𝐸 = 20 + 60 = 80
𝐹 − 𝐼 = 30 + 20 = 50 𝐶 − 𝐸 = 20 + 60 = 80

𝐸 − 𝐽 = 25 + 35 = 60 𝐵 − 𝐹 = 30 + 50 = 80
𝐹 − 𝐽 = 40 + 35 = 75 𝐵 − 𝐹 = 30 + 60 =
90
𝐵 − 𝐹 = 30 + 60 = 90
𝐶 − 𝐹 = 40 + 60 = 100
𝐶 − 𝐹 = 40 + 50 = 90
𝐶 − 𝐹 = 40 + 60 = 100
𝐷 − 𝐹 = 25 + 60 = 85
𝐷 − 𝐹 = 25 + 50 = 75
𝐷 − 𝐹 = 25 + 60 = 85

RUTA DE SOLUCIÓN

𝐴 − 𝐵 − 𝐹 − 𝐼 − 𝐾 = 95

26
EJERCICIO 6.2
Resolver el siguiente problema de control, utilizando la programación dinámica:

𝑚𝑖𝑛[𝑥(1) − 10]2 + [𝑥(2) − 15]2 + 𝑢(0) + 𝑢(1) + 𝑢(2)

𝑢(0), 𝑢(1), 𝑢(2)

Sujeto a: 𝑥(𝑘 + 1) = 2𝑥(𝑘) + 𝑢(𝑘), 𝑝𝑎𝑟𝑎 𝑘 = 0,1,2

𝑐𝑜𝑛: 𝑥(0) = 6, 𝑥(3) = 20

𝑥(1)𝑘=0 = 2𝑥(0) + 𝑢(0) → 2(16) + 𝑢(0)

𝑥(1)𝑘=0 = 12 + 𝑢(0) … 𝐸𝑐𝑢. 1

𝑥(2)𝑘=1 = 2𝑥(1) + 𝑢(1) … . 𝐸𝑐𝑢. 2

𝑥(3)𝑘=2 = 2𝑥 (2) + 𝑢(2) … . 𝐸𝑐𝑢. 3

Despejar u

𝑢(0) = 𝑥(1) − 12 … 𝐸𝑐𝑢. 4

𝑢(1) = 𝑥(12) − 2𝑥 (1) … 𝐸𝑐𝑢. 5

𝑢(2) = 𝑥(3) − 2𝑥(2) … 𝐸𝑐𝑢. 6

Etapa 3

𝐽 ∗3 [𝑥(3)] = ∫[𝑥(3)] = 𝑥(3) = 20

27
Etapa 2

𝐽 ∗2 [𝑥(2)] = 𝑚í𝑛 [𝑢(2) + 𝐽 ∗3 [𝑥(3)] … 𝑆𝑢𝑠. 𝐸𝑐𝑢. 3

𝐽 ∗2 [𝑥(2)] = 𝑚í𝑛 [𝑢(2) + 𝐽 ∗3 [2𝑥(2) + 𝑢(2)]]

Etapa 1

𝐽 ∗1 [𝑥(1)] = 𝑚í[[2𝑥(1) + 𝑢(1) − 15]2 + 𝑢(1) + 𝐽 ∗2 [𝑥(2)]] … 𝑆𝑢𝑠. 2

𝐽 ∗1 [𝑥(1)] = 𝑚í𝑛[[2𝑥(1) + 𝑢(1) − 15]2 + 𝑢(1) + 𝐽 ∗2 [2𝑥(1) + 𝑢(1)]

Etapa 0

𝐽 ∗0 [𝑥(0)] = 𝑚í𝑛[𝑢(0) + [𝑢(0) + 2]2 + 𝐽 ∗1 [𝑥(1)] … 𝑆𝑢𝑠. 𝐸𝑐𝑢. 1

𝐽 ∗0 [𝑥(0)] = 𝑚í𝑛[𝑢(0) + [𝑢(0) + 2]2 + 𝐽 ∗1 [2𝑥(0) + 𝑢(0)]]

Resuelve el siguiente problema de programación:

𝐽 ∗0 [𝑥(0)] = [𝑢(0) + [𝑢(0) + 2]2 + 𝐶

Aplico condiciones de optimalidad:

𝐽 ∗0 [𝑥(0)] = [1 + 2[𝑢(0) + 2]

1 + 2(𝑢(0) + 2) = 0

2(𝑢(0) + 2) = −1

𝑢(0) + 2 = −0.5

𝑢(0) = −2.5

Sustituir en Ecu. 1

𝑥(1) = 12 − 2.5

𝑥(1) = 9.5

Etapa 1:

𝐽 ∗1 [𝑥(1)] = 𝑚í𝑛 [[2𝑥(1) + 𝑢(1) − 15]2 + 𝑢(1) + 𝐽 ∗1 [2𝑥(1) + 𝑢(1)]]

28
Sustituir x(1)

𝐽 ∗1 [𝑥(1)] = [2[𝑢(1) + 4] + 1]

2[𝑢(1) + 4] + 1 = 0

2[𝑢(1) + 4] = −1

𝑢(1) + 4 = −0.5

𝑢(1) = −4.5

Sustituir en Ecu. 2

𝑥(2) = 2(9.5) + (−4.5)

𝑥(2) = 14.5

Sustituyendo los parámetros de x(2) y x(3)

𝑥(3)𝑘=2 = 2𝑥(2) + 𝑢(2)

𝑢(2) = 20 − 2(14.5) = −9

𝑥(3)𝑘=2 = 2(14.5) − 9 = 20

t X*(t) U*(t)
0 6 -2.5
1 9.5 -4.5
2 14.5 -9
3 20

29
EJERCICIO 6.4
Un científico vive en una ciudad B y tiene que estar en la ciudad A el próximo
domingo. En cada uno de los días Jueves, Viernes y Sábados, puede dar una
conferencia en alguna de las ciudades A,B,C, con la excepción de que no puede
ser en C jueves. Se le ofrecen 20 unidades monetarias por conferencia en A, 22
en B y 25 en C, más gastos de estancia para una noche en la ciudad en la que
ha dado la charla.

Utilizar programación dinámica para obtener donde debería pasar los 3 días y
noches finales por las conferencias, menos los costos de transporte entre
ciudades.

Los costos de transporte son:

30
31
RUTA DE SOLUCIÓN:

𝐵 − 𝐵 − 𝐵 − 𝐵 − 𝐴 = 60
𝐵 − 𝐵 − 𝐶 − 𝐶 − 𝐴 = 60

Ejercicio 6.5
El servicio de compras de una empresa debe aprovisionar todos los meses cierta
materia prima. El precio de compra y la demanda de dicha materia vienen datos
para los próximos 6 meses por la tabla siguiente:
Mes 1 2 3 4 5 6
Demanda de 5 8 2 4 7 5
toneladas
Precio de 11 13 18 17 10 20
compra

La capacidad de almacenaje se limita a 9 toneladas por mes. El stock inicial es

igual a 2 y el final debe ser nulo. ¿Qué cantidades se debe comprar al principio de
cada mes para que las compras supongan un gasto mínimo?

ETAPA 5
Demanda Precio Total
2 20 2 40
3 20 3 60
4 20 4 80
5 20 5 100
6 20 6 120
7 20 7 140
8 20 8 160
9 20 9 180

Una demanda de 5 unidades y pagar el precio de $100

ETAPA 4
Capacidad Capacidad anterior Pago
4 5 10 4 40
5 4 10 5 50
6 3 10 6 60
7 2 10 7 70
8 1 10 8 80
9 0 10 9 90

32
Una demanda de 7 unidades y pagar el precio de $70
ETAPA 3
Capacidad Capacidad anterior Pago
4 5 17 4 68
5 4 17 5 85
6 3 17 6 102
7 2 17 7 119
8 1 17 8 136
9 0 17 9 153

Una demanda de 4 unidades y pagar el precio de $68

ETAPA 2
Capacidad Capacidad anterior Pago
2 7 18 2 36
3 6 18 3 54
4 5 18 4 72
5 4 18 5 90
6 3 18 6 108
7 2 18 7 126
8 1 18 8 144
9 0 18 9 162

Una demanda de 2 unidades y pagar el precio de $36

ETAPA 1
Capacidad Capacidad anterior Pago
2 7 13 2 26
3 6 13 3 39
4 5 13 4 52
5 4 13 5 65
6 3 13 6 78
7 2 13 7 91
8 1 13 8 104
9 0 13 9 117

Una demanda de 8 unidades y pagar el precio de $104

33
 PRECIO
$104
$36
$68
$70
$100
TOTAL= $378

Se obtiene que el gasto mínimo para el servicio de compras será de $378 el cual
cubrirá la demanda

Ejercicio 6.6
La responsable de ventas de una editorial de libros de textos universitarios tiene 6 jóvenes
vendedores a los que tiene que asignar a 3 diferentes áreas en que ha dividido el país. Ha
decidió que cada área tiene que designar al menos un vendedor, y cada vendedor individual
tiene que tener restringido su campo de actuación a una sola área. Ahora quiere determinar
cuántos vendedores tiene que nombrar para cada una de las áreas y maximizar las ventas.
La siguiente tabla da una estimación del incremento de ventas (en unidades apropiadas)
en cada área se asigna determinando el número de vendedores:
N° Vendedores/área 1 2 3
1 32 20 28
2 48 42 41
3 70 56 63
4 89 70 75

Valores que pueden tener

X(6) 4,3,2,1,0
X(5) 4,3,2,1,0
X(4) 4,3,2,1,0
X(3) 3,2,1,0
X(2) 2,1,0
X(1) 1,0
X(0) 0

ETAPA 3

𝑿(𝟑) 𝑱∗𝟑 𝑼∗𝟑

6 75 4
5 75 4
4 75 4
3 63 3
2 41 2

34
 1 28 1
0 0 0

ETAPA 2

x(2)/u(2) 4 3 2 1 0

6 70+41 111 56+63 119 42+75 117 20+75 95 0+75 75

5 70+28 98 56+41 97 42+63 105 20+75 95 0+75 75

4 70+0 70 56+28 84 42+41 81 20+63 83 0+75 75

3 56+0 56 42+28 70 20+41 61 0+63 63

2 42+0 42 20+28 48 0+41 41

1 20+0 20 0+28 28

0 0+0 0

𝑿(𝟐) 𝑱∗𝟐 𝑼∗𝟑

6 119 3
5 105 2
4 84 3
3 70 2
2 48 1
1 28 0
0 0 0

ETAPA 1

x(1)/u(1) 4 3 2 1 0
6 89+48 137 70+70 140 48+84 132 32+105 137 0+119 119

𝑿(𝟏) 𝑱∗𝟏 𝑼∗𝟏

6 140 3

𝑈1∗ = 3 𝒙∗ (𝟏) = 𝟔
𝑈2∗ = 2 𝒙∗ (𝟐) = 𝟑
𝑈3∗ = 1 𝒙∗ (𝟑) = 𝟏

35
La decisión optima es determinar 1 vendedor en área 3, 2 vendedores en área 2 y 3
vendedores en área 1 para tener un máximo de ventas que es de 140

Ejercicio 6.7
El ayuntamiento de una ciudad ha recibido 5 millones de euros del gobierno autonómico,
que debe gastar totalmente en las áreas de Juventus, cultura, medio ambiente.
El equipo de análisis del ayuntamiento ha obtenido la siguiente estimación de los niveles
de satisfacción de los ciudadanos, en función de la partida presupuestaria destinada a cada
área (que siempre debe ser múltiplo de millón):

Área/dinero 0 1 2 3 4 5
Juventud 0 5 5 6 7 11
Cultura 0 3 6 6 8 10
Medio 0 5 6 8 9 14
Ambiente
Determinar usando programación dinámica, la manera en que sea de repartir los 5 millones
de euros si el ayuntamiento quiere maximizar el nivel de satisfacción ciudadana.

Valores que pueden obtener

X(0) 5
X(1) 5,4,3,2,1,
X(2) 5,4,3,2,1
X(3) 0

x(2) u(2) 𝐽2∗ (𝑥(2))

5 5 14
4 4 9
3 3 8
2 2 6
1 1 5
0 0 0

36
x(1) u(1) 𝒃𝟏 [𝒖(𝟏)] + [𝒙(𝟏) − 𝒖(𝟏)] total
5 5 10 0 10
4 8 5 13
3 6 6 12
2 6 8 14
1 3 9 12
0 0 14 14
4 4 8 0 8
3 6 5 11
2 6 6 12
1 3 8 11
0 0 9 9
3 3 6 0 6
2 6 5 11
1 3 6 9
0 0 8 8
2 2 6 0 6
1 3 5 8
0 0 6 6
1 1 3 0 3
0 0 5 5
0 0 0 0 0

𝑱∗𝟏 (𝒙(𝟏))
x(1) u(1)
5 2,0 14
4 2 12
3 2 11
2 1 8
1 0 5
0 0 0

x(1) u(1) 𝒃𝟎 [𝒖(𝟎)] + [𝒙(𝟎) − 𝒖(𝟎)] total

5 5 11 0 11
4 7 5 12
3 6 8 14
2 5 11 16
1 5 12 17
0 0 14 14

37
 U(0)=1 𝒙∗ (𝟏) = 𝟒
U(1)=2 𝒙∗ (𝟐) = 𝟐
U(2)=2 𝒙∗ (𝟑) = 𝟎

Se concluye que se debe asignar una unidad a la juventud, dos unidades a la cultura y
dos al medio ambiente para utilizar los 5 unidades o millones de dinero y así tener un
máximo de satisfacción que es igual a 17

38
En aquellos problemas en los cuales se considera el tiempo continuo y variables
determinísticas, usualmente se emplea la técnica de control optimo; mientras que
aquellos en los cuales se consideran el tiempo discreto y variables estocásticas
(es decir, variables que tienen un comportamiento aleatorio), se emplea la técnica
de programación dinámica.

A partir de las condiciones de primer orden del problema de programación

dinámica se obtienen características cualitativas acerca del proceso de
optimización Intertemporal que enfrentan los agentes. se pueden obtener
soluciones analíticas simples para el problema. En caso contrario, las trayectorias
de las variables de control y de estado se obtienen a través de métodos numéricos
o de computación.

Las variables de control optimas en programación dinámica son de circuito

cerrado, es decir, dependen tanto de la variable de estado (𝑥𝑡 ) como del tiempo
(𝑡).

En un problema como el que nos ocupa, en el conjunto de controles admisibles

es discreto, conviene calcular el conjunto de valores que puede tomar las
variables de estado de cada periodo, antes de realizar el estudio de cada periodo
y aplicar la ecuación de Bellman. Teniendo en cuenta la condición inicial 𝑥(0), el
conjunto de controles admisibles y las ecuaciones de estado.

39
• Pdf, E. D. (2022, 1 januari). Optimización Dinámica

de Emilio Cerdá. Economía Digital. Geraadpleegd op 30

april 2022, van

https://economiadigitals.blogspot.com/2014/11/descargar

optimizacion-dinamica-de.html

40