Tema_2_ProgramaciónDinámica_2_2018-II

Vista previa del material en texto

1
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de esfuerzo
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
7. Problemas de programación no lineal
8. Problemas de renovación de equipamiento
2Investigación de Operaciones 2
Emplee Programación Dinámica para resolver el
siguiente problema de Programación No Lineal.
𝑀𝑎𝑥 𝑍 = 4𝑥1
2 + 2𝑥2
2 + 3𝑥3
2
s.a: 2𝑥1 + 𝑥2 + 3𝑥3  9
𝑥1; 𝑥2; 𝑥3  0 ; enteros
PROBLEMA
3Investigación de Operaciones 2
Hay que decidir qué valor asignar a 𝑥1, 𝑥2 y 𝑥3. Por tanto, las variables son 
las etapas (tres), y sus valores, las variables de decisión
Asociaremos 𝑥1 a la etapa 1, 𝑥2 a la etapa 2 y 𝑥3 a la etapa 3, 
como se ilustra en la siguiente figura
4Investigación de Operaciones 2
𝑀𝑎𝑥 𝑍 = 4𝑥1
2 + 2𝑥2
2 + 3𝑥3
2
s.a: 2𝑥1 + 𝑥2 + 3𝑥3  9
Al lado derecho de la restricción, al
número 9, lo podemos interpretar
como la cantidad total de recurso
que se puede repartir entre las
variables, tal que satisfagan esa
restricción.
𝑠3 = 9 𝑠2 = 𝑠3 − 3𝑥3
Al inicio de la etapa 3,
cuando no se ha tomado aún
ninguna decisión, se tiene la
totalidad del recurso,
Al inicio de la etapa 2 ya
se conoce el valor que
podría tomar 𝑥3
𝑠1 = 9 − 3𝑥3 − 𝑥2
= 𝑠3 − 𝑥2
𝑠0 = 9 − 3𝑥3 − 𝑥2 − 2𝑥1
= 𝑠1 − 2𝑥1
5Investigación de Operaciones 2
Etapa 3: 𝑥3 Etapa 2: 𝑥2 Etapa 1: 𝑥1
6
9
0
3
9
𝑠3 𝑠2 𝑠1 𝑠0
Como las variables son 
enteras, los estados 
posibles serán los que se 
obtienen asignando los 
valores de 𝑥3 tales que 
permiten que 
𝑠2 = 9 − 3𝑥3 ≥ 0.
𝑥3 𝑠2 = 9 − 3𝑥3
0 9
1 6
2 3
3 0𝑥3 = 0
6Investigación de Operaciones 2
Etapa 3: 𝑥3 Etapa 2: 𝑥2 Etapa 1: 𝑥1
4
5
6
7
8
9
0
1
2
3
6
9
0
3
9
𝑠3 𝑠2 𝑠1 𝑠0
Para cada valor de 𝑠2 se van 
combinando los valores de 
𝑥2 tales que
𝑠1 = 𝑠2 − 𝑥2 ≥ 0:
𝑠2 𝑥2 𝑠1 = 𝑠2 − 𝑥2
9 0 9
9 1 8
9 2 7
9 3 6
9 4 5
9 5 4
9 6 3
9 7 2
9 8 1
9 9 0
6 0 6
6 1 5
6 2 4
6 3 3
6 4 2
6 5 1
6 6 0
3 0 3
3 1 2
3 2 1
3 3 0
0 0 0
7Investigación de Operaciones 2
Etapa 3: 𝑥3 Etapa 2: 𝑥2 Etapa 1: 𝑥1
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
6
9
0
3
9
𝑠3 𝑠2 𝑠1 𝑠0
8Investigación de Operaciones 2
Etapa 1
En esta etapa, la función objetivo es 𝑓1 𝑠1, 𝑥1 = 4𝑥
1
2
.
ETAPA 1 𝑥1
𝑠1 0 1 2 3 4 f1* x1*
0 0 0 0
1 0 0 0
2 0 4 4 1
3 0 4 4 1
4 0 4 16 16 2
5 0 4 16 16 2
6 0 4 16 36 36 3
7 0 4 16 36 36 3
8 0 4 16 36 64 64 4
9 0 4 16 36 64 64 4
Los cálculos de cada celda son muy simples. Simplemente son 4𝑥1
2
para aquellas celdas que cumplen que 𝑠0 = 𝑠1 − 2𝑥1 ≥ 0
9Investigación de Operaciones 2
ETAPA 2
En esta etapa, la función objetivo es 𝑓2 𝑠2, 𝑥2 = 2𝑥2
2 + 𝑓1
∗(𝑠1)
ETAPA 2 x2
s2 0 1 2 3 4 5 6 7 8 9 f 2* X2* s1*
0 0 0 0 0
3 4 6 8 18 18 3 0
6 36 18 24 22 36 50 72 72 6 0
9 64 66 44 54 48 66 76 102 128 162 162 9 0
Por ejemplo, el cálculo de la celda 𝑠2 = 6, 𝑥2 = 4 (celda en amarillo) es
𝑓2 6,4 = 2 × 4
2 + 𝑓1
∗ 6 − 4 = 32 + 𝑓1
∗ 2 = 32 + 4 = 36
10Investigación de Operaciones 2
ETAPA 3
En esta etapa, la función objetivo es )𝑓3 𝑠3, 𝑥3 = 3𝑥3
3 + 𝑓2
∗(𝑠2
ETAPA 3 x3
s3 0 1 2 3 f3* x3* s2*
9 162 9 42 81 162 0 9
El óptimo es, por tanto, 𝑥1 = 0, 𝑥2 = 9, 𝑥3 = 0 y se alcanza un valor 
de 𝑍 = 162
11
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de esfuerzo
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
7. Problemas de programación no lineal
8. Problemas de renovación de equipamiento
12Investigación de Operaciones 2
PROBLEMA
Un taller especializado en mecánica de automóviles dispone de un analizador
de motores recién adquirido. El precio de un analizador nuevo es de 1000
dólares. Al final de cada año se puede decidir si continuar con él un año
adicional, o darlo como parte del pago de uno nuevo, que funcionaría desde el
inicio del siguiente año.
El taller podría conservar el analizador un máximo de tres años. Es decir, al
finalizar el tercer año de uso el equipo siempre se renueva.
El coste del mantenimiento del analizador es de 40 dólares durante el primer
año, 50 dólares durante el segundo y 70 dólares durante el tercero. El valor de
reventa del analizador después de un año de uso es de 700 dólares; tras el
segundo año, su valor es de 600 dólares, y tras el tercer año de 400 dólares.
Utilizando programación dinámica, determina una estrategia óptima para la
adquisición y mantenimiento del analizador para los próximos 4 años. Al
finalizar el cuarto año el equipo se revende sea cual fuera su antigüedad.
13Investigación de Operaciones 2
La variable de decisión es:
𝑥𝑛 = conservar (0) o renovar (1) el analizador al final del año n.
Las etapas son los años, y serán cuatro. La variable de estado 𝑠𝑛 es la antigüedad 
del equipo al inicio del año de la etapa 𝑛
• La decisión se toma al final de cada año. 
• Si estamos en el año de la etapa 𝑛, con variable de estado de valor 𝑠𝑛 y a fin de 
año elegimos 𝑥𝑛 = 0, conservaremos el equipo durante el año siguiente, y 
tendremos que el estado del año siguiente será 𝑠𝑛−1 = 𝑠𝑛 + 1. 
• Si, por el contrario, elegimos 𝑥𝑛 = 1, comenzaremos el nuevo año con equipo 
nuevo; es decir, 𝑠𝑛−1 = 0. 
• Si como mínimo se renueva el equipo a los tres años, el valor máximo de la 
variable de estado es 𝑠𝑛 = 2, que se tendrá al inicio del año tercero desde su 
adquisición. 
14Investigación de Operaciones 2
Etapa 4
Año 1
Etapa 3
Año 2
Etapa 2
Año 3
Etapa 1
Año 4
0 0 0 0 FIN
1 1 1
2 2
Al finalizar el año 4 (etapa 1) simplemente hay que calcular el valor de
reventa del equipo y contabilizar los costes de mantenimiento. No se
adquiere un nuevo equipo
15Investigación de Operaciones 2
ETAPA 1-Mes 4 x1
s1 conservar=0 renovar=1 f1* x1*
0 660 660 renovar
1 550 550 renovar
2 330 330 renovar
En las celdas contabilizaremos el ingreso relacionado con dicha decisión.
Por ejemplo, la 𝑠1 = 1, 𝑥1 = 1 (renovar): Como el analizador tiene un año, tendremos
que pagar el mantenimiento del segundo año, que son 50. Como decidimos renovar,
ingresaremos el coste de reventa, que será el de su segundo año: 600. El ingreso neto
es
𝑓1 1,1 = 600 − 50 = 550.
16Investigación de Operaciones 2
ETAPA 2-Mes 3 x2
s2 conservar=0 renovar=1 f2* x2* s1*
0 510 320 510 conservar 1
1 280 210 280 conservar 2
2 -10 -10 renovar 0
Vamos a ver el detalle del cálculo de la celda 𝑠2 = 2, 𝑥2 = 1 (renovar). La función 
objetivo es
𝑓2 2,1 = 𝐼21 + 𝑓1
∗(𝑠1)
Al inicio de esta etapa, el equipo tiene dos años, y en esta etapa estará en su 
tercer año. El ingreso (negativo si es coste) que se genera es:
𝐼21 = -coste mantenimiento del tercer año-coste adquisición nuevo equipo+precio
de reventa de un equipo en su tercer año
𝐼21 = −70 − 1000 + 400 = −670.
Al final de la etapa 2 el equipo será nuevo, es decir 𝑠1 = 0, por lo que el ingreso 
de la etapa 1 será 660. Se tiene entonces que 
𝑓2 2,1 = 𝐼21 + 𝑓1
∗ 𝑠1 = −670 + 660 = −10
17Investigación de Operaciones 2
ETAPA 3-Mes 2 x3
s3 conservar=0 renovar=1 f3* x3* s2*
0 240 170 240 conservar 1
1 -60 60 60 renovar 0
2 -160 -160 renovar 0
Lo cálculos de, por ejemplo, la celda 𝑠3 = 1, 𝑥3 = 0 (conservar) son los
siguientes. La función objetivo de esa celda es
𝑓3 1,0 = 𝐼1,0 + 𝑓2
∗(𝑠2)
Como 𝑠3 = 1, el aparato tiene un año al inicio de esta etapa. Se decide
conservar, por lo que no se va a vender al final del año. Los costes en los que
incurre son los de mantenimiento del segundo año, que son 50. Por tanto,
𝐼1,0 = −50. Como no se renueva, en el mes siguiente se tendrá un estado 𝑠2 =
2, por lo que 𝑓2
∗ 𝑠2 = −10. Por tanto
𝑓3 1,0 = 𝐼1,0 + 𝑓2
∗ 𝑠2 = −50 − 10 = −60
18Investigación de Operaciones 2
ETAPA 4-Mes 1 x4
s4 conservar=0 renovar=1f4* x4* s3*
0 20 -100 20 conservar 1
En el óptimo, se reciben unos ingresos de 20. Si le restamos los 1000
dólares de la compra del equipo la primera vez se tienen unos costes de
980. El óptimo es
• Conservar el equipo dos años
• Renovarlo al inicio del año 3
• Conservarlo los años 3 y 4
• Al final del año 4 se vende por su valor residual