UNIVERSIDAD DE GUAYAQUIL
FACULTAD INGENIERÍA INDUSTRIAL
INGENIERÍA TELEINFORMÁTICA
INVESTIGACIÓN DE OPERACIONES II
TEMA:
PROGRAMACIÓN DINÁMICA
DOCENTE:
ING. DENNIS ZAMBRANO SILVA
INTEGRANTES:
REINA VERA KAREN ALEJANDRA
ACOSTA VITE ALVARO RAUL
PROAÑO CALAURANO MICHAEL ANDRES
VELASCO MURILLO CECIBEL ROXANA
WILCHES FILIAN DANIELA MELINA
PARALELO:
7Mo 1
AÑO LECTIVO:
2020 – 2021 CII
ÍNDICE
EJERCICIOS DE PROGRAMACIÓN DINÁMICA .................................................................... 3
Ejercicio 10.2-2. ............................................................................................................................. 3
Ejercicio 10.3-2. ............................................................................................................................. 6
Ejercicio 10.3-3 .............................................................................................................................. 8
Ejercicio 10.3-4. ........................................................................................................................... 11
Ejercicio 10.3-5. ........................................................................................................................... 16
EJERCICIOS DE PROGRAMACIÓN DINÁMICA
Ejercicio 10.2-2.
Programación dinámica determinística
El gerente de ventas de una editorial de libros de texto universitarios tiene seis agentes de
ventas que puede asignar a tres regiones distintas del país. Ha decidido que cada región debe
tener por lo menos un agente y que cada uno de éstos debe quedar restringido a una de estas
regiones, pero ahora quiere determinar cuántos agentes debe asignar a las respectivas
regiones con el fin de maximizar las ventas.
La tabla de la parte superior de la siguiente columna da el incremento estimado de las ventas
en cada región (en las unidades apropiadas) si se le asignan diferentes cantidades de agentes:
a) Utilice programación dinámica para resolver este problema. En lugar de usar las tablas
normales, muestre su trabajo con una gráfica de una red similar a la del problema 10.2-1.
Haga lo mismo que en el problema 10.2-1b para obtener 𝑓𝑛∗ (𝑆𝑛 ) de cada nodo (excepto el
nodo terminal) y escriba sus valores al lado. Dibuje una punta de flecha para indicar la ruta
óptima (o rutas en el caso de empates) que debe tomarse al salir de cada nodo. Por último,
identifique la ruta (o rutas) óptima(s) que obtuvo a través de la red y la solución (o soluciones)
óptima(s) correspondiente.
b) Utilice programación dinámica para resolver este problema; elabore las tablas normales
con n = 3, n = 2 y n = 1.
a)
2 3
Etapa: 1
0 0
0 0 0
24 X3∗ = 1
47 32
1 0
1
46
78 24 X2∗ = 2 63
2 0
2
47 24
99
63 47 70
54 3 3
0
24
X1∗ = 1
40 84
78
4 4
Estado: 4
0 0
119
b)
n=3 𝐒𝟑 𝒇∗𝟑 (𝐒𝟑 ) 𝐗 ∗𝟑
: 0 0 0
1 32 1
2 46 2
3 70 3
4 84 4
𝐗𝟐 𝑓2 = (𝑆2 , 𝑋2 ) = 𝑃2 (𝑋2 ) + 𝑓3∗ (𝑆2 −𝑋2 )
n=2 𝐒𝟐 3 𝑓2∗ (𝑆2 ) 𝑋2∗
0 1 2 4
: 0 0 0 0
1 32 24 32 0
2 46 56 47 56 1
3 70 70 79 63 79 2
4 84 94 93 95 78 95 3
𝐗𝟏 𝑓1 = (𝑆1 , 𝑋1 ) = 𝑃1 (𝑋1 ) + 𝑓2∗ (𝑆1 −𝑋1 )
n=1 𝐒𝟏 0 1 2 3 4 𝑓1∗ (𝑆1 ) 𝑋1∗
:
4 95 119 110 110 99 119 1
Ejercicio 10.3-2. Programación dinámica determinística (creo)
El propietario de una cadena de tres supermercados compró cinco cargas de fresas frescas.
La distribución de probabilidad estimada de las ventas potenciales de las fresas antes de que
se echen a perder difiere entre los tres supermercados.
El propietario quiere saber cómo debe asignar las cinco cargas a las tiendas para maximizar
la ganancia esperada.
Por razones administrativas, no quiere dividir las cargas entre las tiendas. Sim embargo, está
de acuerdo en asignar cero cargas a cualquiera de ellas.
En la siguiente tabla se proporciona la ganancia estimada de cada tienda al asignar distintas
cantidades de cargas:
tienda 1 tienda 2 tienda 3
0
0 0
0
6
4
1 1
11 9
2 2
21 17
14 15(0,1 Y 2)
5 9 13 0
5
3 3
0
20
18
4 4
5 5 20
24(4,3,2)
S3 F3*(S3) X3*
0 0 0
1 4 1
2 9 2
3 13 3
4 18 4
5 20 5
X2 F2(S2, X2) F2*(S2) X2*
S2 0 1 2 3 4 5
0 0 --- ---- --- --- - 0 0
-
1 6 1
4 6 -- --- --- -
2 - 11 2
3 9 10 11 --- --- - 15 1,2,3
--
4 20 2
13 15 15 15 -- -
5 24 1,2,3
-
18 19 20 19 19 -
-
20 24 24 24 23 22
F1(S1, X1) F1*(S1) X1*
X1 0 1 2 3 4
5
S1
5 24 25 24 25 23 25 1,3
21
Solución optima X1* X2* X3*
1 1 2 2
2 3 2 0
Ejercicio 10.3-3
Una estudiante universitaria cuenta con siete días para preparar los exámenes finales de
cuatro cursos y quiere asignar su tiempo de estudio de la manera más eficiente posible.
Necesita por lo menos un día para cada curso y quiere concentrarse sólo en un curso cada día
por lo que quiere asignar uno, dos, tres o cuatro días a cada curso. Como hace poco tomó un
curso de investigación de operaciones, decide aplicar programación dinámica para hacer
estas asignaciones que maximicen el total de puntos obtenidos en los cuatro cursos. Estima
que las distintas asignaciones en días de estudio le redituarán puntos de calificación según la
siguiente tabla: Programación dinámica
5 2 6
1 1 1 0
5 6 7
2 5 2 2 2
1
6 7 9
5 6
7 6 7
3
5 3 3
2
5 9 6 4
8
5
7 4 4 4
3 5 2
Sea 𝑥𝑛 el número de días de estudio asignados 𝑛, 𝑝𝑛 (𝑥𝑛 ) sea el número de puntos de grado
esperados cuando 𝑥𝑛 días asignados al curso 𝑛 y 𝑠𝑛 es el número de días de estudio que
quedan por asignar a los cursos 𝑘 ≥ 𝑛. Entonces:
𝑓𝑛 (𝑠𝑛 ) = max [𝑝𝑛 (𝑥𝑛 ) + 𝑓𝑛+1 (𝑠𝑛 − 𝑥𝑛 )]
1≤𝑥𝑛 ≤min(𝑠𝑛 ,4)
Número de etapas: 4
𝒔𝟒 𝒇𝟒 (𝒔𝟒 ) 𝒙𝟒
1 4 1
2 4 2
3 5 3
4 8 4
𝒔𝟒 𝒇𝟑 (𝒔𝟑 , 𝒙𝟑 )
𝒔𝟑 1 2 3 4 𝑓𝟑 (𝑠𝟑 ) 𝑥3
2 8 --- --- --- 8 1
2 4 10 --- --- 10 2
3 5 10 11 --- 11 3
4 8 11 11 13 13 4
𝒇𝟑 (𝒔𝟑 , 𝒙𝟑 )
𝒔𝟑 1 2 3 4 𝑓𝟑 (𝑠𝟑 ) 𝑥3
2 8 --- --- --- 8 1
2 4 10 --- --- 10 2
3 5 10 11 --- 11 3
4 8 11 11 13 13 4
𝒇𝟏 (𝒔𝟏 , 𝒙𝟏 )
𝒔𝟏 1 2 3 4 𝑓1 (𝑠1 ) 𝑥1
7 19 19 21 21 21 3,4
Solución Óptima 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
1 3 1 2 1
2 4 1 1 1
Ejercicio 10.3-4. Programación dinámica determinística
Una campaña política se encuentra en su última etapa y las preliminares indican que las
preferencias electorales se encuentran sumamente cerradas. Uno de los candidatos tiene
suficientes fondos para comprar tiempo de TV por un total de cinco comerciales en las horas
de mayor audiencia en estaciones localizadas en cuatro áreas diferentes. Con base en la
información de las preliminares se hizo una estimación del número de votos adicionales que
se puede ganar en las áreas de difusión según el número de comerciales que se contrate. Estas
estimaciones se dan en la tabla en miles de votos:
Utilice programación dinámica para determinar cómo deben distribuirse los cinco
comerciales entre las cuatro áreas con el fin de maximizar el número estimado de votos
ganados.
En el problema están presentes los siguientes elementos:
Etapas: se tienen 5 etapas que son las de difusión
Estados: están conformados por el número de comerciales
Decisión: El número de comerciales usados en cada área de difusión.
∗
Fórmula recursiva: 𝑓𝑡 (𝑖, 𝑗) = 𝑑𝑖𝑗 + 𝑓𝑡+1 (𝑖)
Principio de optimalidad: 𝑓𝑡∗ (𝑖) = 𝑚á𝑥 𝑓 ∗ (𝑖, 𝑗)
Condición de la frontera: 𝑓5∗ (𝑖) = 0
Etapa 4
T= 4 F4 (i, j) = dij + f ∗ 5(i)
i/j 0 𝐟 ∗ 𝟒(𝐢) 𝑿𝐭
5 16 16 5
4 14 14 4
3 12 12 3
2 7 7 2
1 3 3 1
0 0 0 0
Etapa 3
T= 3 F3 (i, j) = dij + f ∗ 4(i)
i/j 5 4 3 2 1 0 𝐟 ∗ 𝟑(𝐢) 𝑿𝐭
5 16 19 21 18 13 9 21 2
4 --- 14 17 16 14 10 17 1
3 --- --- 12 12 12 11 12 (0, 1, 2)
2 --- --- --- 7 8 9 9 2
1 --- --- --- --- 3 5 5 1
0 --- --- --- --- --- 0 0 0
Etapa 2
T= 2 F2 (i, j) = dij + f ∗ 3(i)
i/j 5 4 3 2 1 0 𝐟 ∗ 𝟑(𝐢) 𝑿𝐭
5 21 23 20 19 16 12 23 1
4 --- 17 18 17 15 11 18 1
3 --- --- 12 15 13 10 15 1
2 --- --- --- 9 11 8 11 1
1 --- --- --- --- 5 6 6 1
0 --- --- --- --- --- 0 0 0
Etapa 1
T= 1 F1 (i, j) = dij + f ∗ 2(i)
i/j 5 4 3 2 1 0 𝐟 ∗ 𝟑(𝐢) 𝑿𝐭
5 23 22 22 20 18 15 23 0
El resultado de este problema se planteará en una tabla que contará con la cantidad de áreas
y comerciales asignados:
Áreas Comerciales asignados
1 0
2 1
3 1
4 3
Al área 1 no se le asignará ningún comercial.
Al área 2 se le asignará 1 comercial al igual que al área 3.
Por último, al área 4 se le asignará 3 comerciales.
Resultado: El candidato obtendrá 23 mil votos, con lo que tiene asegurado ganar la campaña.
Ejercicio 10.3-5.
La presidenta de un partido político de un estado planea las próximas elecciones
presidenciales. Cuenta con la colaboración de seis voluntarios para trabajar en los distritos
electorales y los quiere asignar a cuatro distritos de manera que se maximice su eficacia. Ella
piensa que sería ineficiente asignar un voluntario a más de un distrito, pero está dispuesta a
no asignar a nadie a cualquiera de ellos si pueden lograr más en otro distrito.
En la siguiente tabla se presenta el aumento estimado del número de votos para el candidato
del partido en cada distrito si se asigna distintos números de voluntarios:
Este problema tiene varias soluciones óptimas para determinar cuántos voluntarios deben
asignarse a cada distrito para maximizar el incremento total estimado de la popularidad del
candidato del partido.
Utilice programación dinámica para encontrar todas las soluciones óptimas para que la
presidenta del partido pueda hacer una selección basada en otros factores.
Etapa: 3
1 2 4
0 0 0 0 0
0 0
24 7 5 6
0 0
1 1 1 11
5 10
22 7 16 15
11 20
18 10
0 0
2 2 2
7 10
11 18
11 14
16 15 18 10
18 5
3 3
0 3 0
7 5
15 18
16
18 16
18 15
18 15
4 21 4
4 0 0
11
10
9 16 11 17
20 21
7 1 5
5 5 5
0 0
4 7
10 5
18
21 22
Estado: 6 6 6 6
0 0 0
S4 f4*(S4) X4*
0 0 0
1 6 1
2 11 2
3 14 3
4 15 4
5 17 5
6 18 6
X3 f3(S3, X3)
S3 0 1 2 3 4 5 6 f3*(S3) X3*
0 0 …. …. …. …. …. …. 0 0
1 6 5 …. …. …. …. …. 6 0
2 11 11 10 …. …. …. …. 11 0.1
3 14 16 16 15 …. …. …. 16 1.2
4 16 19 21 21 18 …. …. 21 2.3
5 17 21 24 26 24 21 …. 26 3
6 18 22 26 29 29 27 22 29 3.4
X2 f2(S2, X2)
S2 0 1 2 3 4 5 6 f2*(S2) X2*
0 0 …. …. …. …. …. …. 0 0
1 6 7 …. …. …. …. …. 7 1
2 11 13 11 …. …. …. …. 13 1
3 16 18 17 16 …. …. …. 18 1
4 21 23 22 22 18 …. …. 23 1
5 26 28 27 27 24 20 …. 28 1
6 29 33 32 32 29 26 21 33 1
X1 f1(S1, X1)
S1 0 1 2 3 4 5 6 f1*(S1) X1*
6 33 32 32 33 31 29 24 33 0.3
Solución X1* X2* X3* X4*
opcional
1 0 1 3 2
2 3 1 0 2
3 3 1 1 1
