Material Informativo
Programa de Estudios/Programa INGENIERÍA INDUSTRIAL Sesión N°7
Experiencia Curricular: HERRAMIENTAS PARA LA TOMA DE DECISIONES Semestre 2022-01
Contenido temático: Programación Dinámica
Docente:
Tipo de Material Informativo: Guía de ejercicios
Guía de ejercicios
FACULTAD DE INGENIERIA
ESCUELA PROFESIONAL DE INGENIERIA
INDUSTRIAL
EJERCICIO DE HERRAMIENTAS
GRUPO -05
Integrantes:
RAMOS ROSALES, JUAN
HORNA LINARES, KIMBERLY
ROSAS AVILA ELVIS JAVIER
QUIÑONES CHAVEZ, MELANIE MAIDELY
STEVEN HIDALGO PÉREZ
CHIMBOTE - PERÚ
2022-01
Programación Dinámica
1) El propietario de 3 tiendas ha comprado 5 cestas de fresas, para satisfacer la demanda
en las diferentes tiendas. El propietario desea determinar la forma de distribuir los
canastos, de manera de maximizar el beneficio total. Los retornos (utilidades) en función
del número de canastos distribuidos (se asume vendidos) en las 3 tiendas están dados
en la siguiente tabla:
Formula: Sk-1=Sk-dk; Fk= Rk + F*k-1
Etapa 3
D1 Tienda 3
k1=0 1 2 3 4 5 𝑓3∗ 𝑘3∗
S1 r1= 0 4 6 11 12 13
0 0 - - - - - 0 0
1 0 4 - - - - 4 1
2 0 4 6 - - - 6 2
3 0 4 6 11 - - 11 3
4 0 4 6 11 12 - 12 4
5 0 4 6 11 12 13 13 5
Etapa 2
D2 Tienda 2
K2=0 1 2 3 4 5 𝑓2∗ 𝑘2∗
S2 R2= 0 5 10 11 11 11
0 0 - - - - - 0 0
1 0+4=4 5+0=5 - - - - 5 1
2 0+6=6 5+4=9 10+0=10 - - - 10 2
3 0+11=11 5+6=11 10+4=14 11+0=10 - - 14 2
4 0+12=12 5+11=16 10+6=16 11+4=15 11+0=11 - 16 1o2
5 0+13=13 5+12=17 10+11=21 11+6=17 11+4=15 11+0=11 21 2
Etapa 1
D1 Tienda 1
K3=0 1 2 3 4 5 𝑓1∗ 𝑘1∗
S1 R3= 0 3 7 9 12 13
5 0+21=21 3+16=19 7+14=21 9+10=19 12+5=17 13+0=13 21 0o2
El máximo beneficio es de 21
Tabla resumen
Con la opción de 0 en la etapa 1
Etapas Sk-dk=Sk-1 F*k
1 5-0=5 0
2 5-2=3 10
3 3-3=0 11
Con esta distribución se puede dejar 0 canasto en la tienda 1, 2 canasto en la tienda 2 y 3 canasto
en la tienda 3 para un beneficio máximo de 21
Con la opción de 2 en la etapa 1
Etapas Sk-dk=Sk-1 F*k
1 5-2=3 7
2 3-2=1 10
3 1-1=0 4
Con esta distribución se puede dejar 2 canasto en la tienda 1, 2 canasto en la tienda 2 y 1 canasto
en la tienda 1 para un beneficio máximo de 21
2) SINAI Hospital, se dedica a mejorar la atención médica en los países subdesarrollados
del mundo. Dispone de 5 brigadas médicas para asignarlas a tres de estos países. El
consejo necesita determinar cuántas brigadas debe asignar a cada país (si lo hace) para
maximizar la medida de la eficiencia de las brigadas, la cual será el incremento en el
promedio de vida esperado en años, multiplicado por la población de cada país.
Etapa 3
D1 País 3
k1=0 1 2 3 4 5 𝑓3∗ 𝑘3∗
S1 r1= 0 50 70 80 100 130
0 0 - - - - - 0 0
1 0 50 - - - - 50 1
2 0 50 70 - - - 70 2
3 0 50 70 80 - - 80 3
4 0 50 70 80 100 - 100 4
5 0 50 70 80 100 130 130 5
Etapa 2
D2 País 2
K2=0 1 2 3 4 5 𝑓2∗ 𝑘2∗
S2 R2= 0 20 45 75 110 150
0 0 - - - - - 0 0
1 0+50=50 20+0=20 - - - - 50 1
2 0+70=70 20+50=70 45+0=45 - - - 70 0o1
3 0+80=80 20+70=90 45+50=95 75+0=10 - - 95 2
4 0+100=100 20+80=100 45+70=115 75+50=125 110+0=110 - 125 3
5 0+130=130 20+100=120 45+80=125 75+70=145 110+50=160 150+0=150 160 4
Etapa 1
D1 País 1
K3=0 1 2 3 4 5 𝑓1∗ 𝑘1∗
S1 R3= 0 45 70 90 105 120
5 0+160=160 45+125=170 70+95=165 90+70=160 105+50=155 120+0=120 170 1
El máximo beneficio es de 170
Tabla resumen
Con la opción de 1 en la etapa 1
Etapas Sk-dk=Sk-1 F*k
1 5-1=4 45
2 4-3=3 75
3 1-1=0 50
Para obtener el máximo beneficio se debe asignar 1 brigada en el país 1, 3 brigadas en el
país 2 y 1 brigada en el país 3, lo cual incrementara el promedio de vida esperado
en años, en (170*100 años) 170000 años
3) Problema del Agente Viajero:
cuadro
1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0
Permutación
C1>C2> C3>C4>C1
C1>C2> C4>C3>C1
C1>C4> C2>C3>C1
C1>C4> C3>C2>C1
C1>C3> C4>C2>C1
C1>C3> C2>C4>C1
Total, de permutaciones: 3!
C1>C2> C3>C4>C1 = 10+ 9+12+8=37
C1>C2> C4>C3>C1 = 10+ 10+9+6=35
C1>C4> C2>C3>C1 =20+8+9+6= 43
C1>C4> C3>C2>C1 = 20+9+13+5= 47
C1>C3> C4>C2>C1 =15+12+8+5= 40
C1>C3> C2>C4>C1 = 15+13+10+8= 46
Entonces la ruta mas corta es 1 – 2 – 4 – 3 – 1
4) Problema del agente viajero
C1 C2 C3 C4 C5 C6
C1 0 8 X 3 X 4
C2 8 0 1 5 9 X
C3 X 1 0 7 2 21
C4 3 5 7 0 X 3
C5 X 9 2 X 0 35
C6 4 X 21 3 35 0
5) Un explorador desea ir de A a J en un safari, y quiere viajar de la forma más segura
posible. Tiene los puntos de salida y destino conocidos, pero tiene múltiples opciones
para viajar a través del territorio. Se entera de la posibilidad de adquirir seguro de vida
como pasajero del safari. El costo de la póliza estándar (cij ) se muestra en la sgte. tabla.
Transcripción de los datos
Empezamos con la etapa k=4
Estados x4 Costo DE POLIZ acumulado Decisión optima U*4
F*4
H 3 J
I 4 J
Para la etapa K=3
ESTADOS X4
Estados X2 H I Costo DE POLIZ Decisión optima U*3
acumulado F*3
E 4 8 4 H
F 9 7 7 I
G 6 7 6 H
Para la etapa K=2
ESTADOS X3
Estados X2 E F G Costo DE POLIZ Decisión optima U*2
acumulado F*2
B 11 11 12 11 E. F
C 7 9 10 7 E
D 8 8 11 8 E. F
Finalmente en la etapa K=1
ESTADOS X2
Estados X1 B C D Costo DE POLIZ Decisión optima U*1
acumulado F*1
A 13 11 11 11 C. D
Ruta optima:
A C E H J 4+3+1+3=11
A D E H J 3+4+1+3=11
A D F I J 3+1+3+4=11
El óptimo no coincide con la decisión miope A B F I J 2+4+3+4=13
Para la etapa K=2
Estados X1
Estados X2 A Costo DE POLIZ Decisión optima U*2
acumulado F*2
B 2 2 A
C 4 4 A
D 3 3 A
Para K=3
Estados X2
Estados X3 B C D Costo DE POLIZ Decisión optima U*3
acumulado F*3
E 9 7 7 7 C. D
F 6 6 4 4 D
G 8 8 8 8 B. C. D
Para k=4
Estados X3
Estados X4 E F G Costo DE POLIZ Decisión optima U*4
acumulado F*4
H 8 10 11 8 E
I 11 7 11 7 F
Finalmente para la etapa K=5
Estados X4
Estados X5 H I Costo DE POLIZ Decisión optima U*5
acumulado F*5
J 11 11 11 H. I
Ruta óptima:
J H E C A 3+1+3+4=11
J H E D A 3+1+4+3=11
J I F D A 4+3+1+3=11
6) Suponga que se desea establecer una ruta aérea de costo mínimo desde un aeropuerto
de salida en un País 0 hasta 1 en otro país 4. Para esto, es necesario hacer escalas en
aeropuertos de otros tres países (1,2, 3) y comprar pasajes para cada vuelo. La red de
posibles vuelos (combinaciones aéreas ) se presenta a continuación:
1 1 1
1 2 2 2 1
3 3 3
País 0 País 1 País 2 País 3 País 4
Se conocen los precios de los boletos de pasaje aéreo, que se registran a continuación:
Del país 0 al 1
1 2 3
1 168 175 196
Del país 1 al país 2
1 2 3
1 340 353 309
2 298 364 279
3 315 333 296
Del país 2 al 3
1 2 3
1 158 174 162
2 146 135 124
3 187 205 222
Del país 3 al 4
1
1 340
2 316
3 323
Para
la etapa 4
Estados x4 Costo DE POLIZ acumulado Decisión optima U*4
F*4
1 340 1
2 316 1
3 323 1
Para la etapa 3
Estados x2
Estados x2 1 2 3 Costo DE POLIZ Decisión optima U*3
acumulado F*3
1 498 490 485 485 3
2 486 451 447 447 3
3 527 521 545 521 2
Para la etapa 2
Estados x3
Estados x2 1 2 3 Costo DE POLIZ Decisión optima U*2
acumulado F*2
1 825 800 830 800 2
2 783 811 800 783 1
3 800 780 817 780 2
Para la etapa 1
ESTADOS X2
Estados X1 1 2 3 Costo DE POLIZ Decisión optima U*1
acumulado F*1
1 968 958 973 958 2
Decisión optima:
1 2 1 3 =1
7) Problema de la Diligencia
Este problema está referido a encontrar la ruta óptima (ruta mínima o ruta más confiable),
para viajar desde un punto llamado nodo inicial o fuente hacia otro llamado nodo final o
destino a través de una red de caminos que los conecta dados los retornos (costos beneficios
tiempo, etc), asociados con los arcos o ramas de la red.
En este caso lo primero que hay que reconocer es, que al tomar una decision para decidir que
ruta ,seguir en la forma general para todoel problema ,involucra analizar toda la red estpo hace
que el problema sea complejo ,por cuanto del modo 1 al 14 existen multiples alternativas en las
que se encuentran varias ramas en la ruta en segundo lugar , ver si es posible dividir el problema
en subproblema o etapas de manera que la decision en cada subproblema sea mas facil ,en este
sentido se ha dividido el problema en 5 etapas ,de la 1 a la 5 conforme se aprecia en la parte
inferior de la red .observese que es mas facil tomar una decision en cada etapa pues la decision
sea directa por ejemplo si estamos en la etapa 3 (subproblema 3) al inicio nos podemos los nodos
5 , 6 ó 7 y podemos ir a los nodos 8, 9, 10 ú 11 la decisión es inmediata, pues solo existeencontrar
en una rama en cada alternativa .estas caracteristica es importante reconocer para tomar la
decision de aplicar la metodologia de la programacion dinamica
para n=3
𝑓3∗ (𝑆3 ) = 𝑀𝐼𝑁[𝑅3 (𝐷3 , 𝑆4 ) + 𝑓4 (𝑆4 )]
para n=2
𝑓2∗ (𝑆2 ) = 𝑀𝐼𝑁[𝑅2 (𝐷2 , 𝑆3 ) + 𝑓3 (𝑆3 )]
para n=1
𝑓2∗ (𝑆2 ) = 𝑀𝐼𝑁[𝑅2 (𝐷2 , 𝑆3 ) + 𝑓3 (𝑆3 )]
¿como se obtiene el recorrido mas corto?
esto se logra comenzando desde la etapa 1,de la siguiente manera:
si se esta en el nodo 1 la decision optima es ir al nodo 3,luego se pasa a la etapa 2
si se esta en el nodo 3 la decision optima es ir al nodo 5,luego se pasa a la etapa 3
si se esta en el nodo 5 la decision optima es ir al nodo 9,luego se pasa a la etapa 4
si se esta en el nodo 9 la decision optima es ir al nodo 12,luego se pasa a la etapa 5
si se esta en el nodo 12 la decision optima es ir al nodo 14
la distancia social total se obtiene sumando las distancias de las maneras de las ramas
involucradas en el recorrido en este caso
1-3-5-9-12-14---->2+8+2+3+4=19
8) Problema:
Dada la red de carreteras que se encuentra a continuación, encontrar la ruta mas corta desde
el nodo 1 hasta el nodo 9.
4
6
4
2 7 5
5 2 6
1 5 9
3
3 9
3 7
8
5 6
6
la ruta mas carta desde cada nodo hacia atrás puede ser mas resumidas de la manera siguientes:
ruta:1,2,4,7,9=5+4+6+5=20
ruta:1,3,6,8,9=3+5+6+7=21
ruta:1,2,5,7,9=5+2+6+5=18
ruta:1,3,5,8,9=3+3+9+7=22
podemos determinar que efectivamente la ruta mas corta es:
ruta:1,2,5,7,9=5+2+6+5=18
9) Estrategia para campaña electoral.
Una campaña política se encuentra en su última etapa y las preliminares indican que la elección
está pareja. Uno de los candidatos del cual usted es asesor, tiene suficientes fondos para
comprar tiempo de TV por un total de cinco comerciales en 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 pueden ganar en las diferentes
áreas de difusión según el número de comerciales que se compren. Estas estimaciones se dan
en la siguiente tabla en miles de votos:
Utilice la programación dinámica para diseñar una estrategia respecto a cómo deben distribuirse
los cinco comerciales entre las cuatro áreas con el fin de maximizar el número estimado de votos
ganados.
Número de Área
comerciales 1 2 3 4
0 0 0 0 0
1 4 6 5 3
2 7 8 9 7
3 7 10 11 12
4 12 11 10 14
5 15 12 9 16
funcion recursiva :
𝑓𝑛∗ (𝑆𝑛 ) = 𝑀𝐴𝑋[𝑅𝑛 (𝐷𝑛 , 𝑆𝑛 ) + 𝑓𝑛 (𝑆𝑛 )]
0≤Dn≤5
0≤Sn≤5
para n=4
Para n=3
Para n=2
Para n=1
asignar 1 comercial a la estacion ubicada en el area 2 votos ganados:6
asignar 1 comercial a la estacion ubicada en el area 3 votos ganados:5
asignar 3 comercial a la estacion ubicada en el area 4 votos ganados:12
total de votos que se esperan que ganen 23
10)Una familia va a salir de vacaciones desde su ciudad natal. La familia
desea visitar n ciudades y dispone de un total de M días para hacerlo, conM
<= n. La familia desea saber cuantos días permanecer en cada ciudad de
modo de maximizar la satisfacción total de sus vacaciones sabiendo que para
cada ciudad i existe una función de satisfacción gi que es funcióndel número
de días de permanencia.
Maximización con m < = N.
p= 0.1 0.3 0.6
0.2 0.2 0.5
0.1 0.8 0.4
Existe una función de satisfacción Gi que es una función de dias de permanencia.
19
P= 0.1 0.3 0.8 * 0.1 0.3 0.8 = 33 12
0.2 0.2 0.6 100
0.2 0.2 0.6 100 25
0.2 0.4 0.4 0.2 0.4 0.4 9 17 12
50 50 25
9 3 13
50 10 25
9 12 3 12 13 13
𝑃2 = ∗ + ∗ + ∗ = 0.0864 + 0.1440 + 0.2704 = 0.5008
50 25 10 25 25 25
11) Una empresa dispone de 4 millones de dólares para invertir en tres campos petroleros.
Las utilidades que gana en el sitio i (i=1,2,3) dependen de la cantidad invertida en el,
así:
Si Se supone que la cantidad invertida en cada campo debe ser un múltiplo exacto de 1 millón de
dólares. Determinar con programación dinámica una política de inversiones que eleva al máximo las
utilidades que gana la empresa con sus tres campos petroleros.
PROGRAMACIÓN DINAMICA EN CADA CAMPO
5
3
CAMPO 1:
1
4 7
2 6
3 9
CAMPO 2:
1
8 11
2 10
CAMPO 3:
13
3
1
12 15
2 14
