PROGRAMACIÓN DINÁMICA DETERMINÍSTICA (PDD - Mochila)
Ever PadillaPráctica o problema12 de Mayo de 2020
585 Palabras (3 Páginas)535 Visitas
[pic 1]
PROGRAMACIÓN DINÁMICA DETERMINÍSTICA (PDD - Mochila)
- Un barco de 4 toneladas puede cargarse con uno o más de tres artículos. La siguiente tabla da el peso unitario, wi, en toneladas y el ingreso unitario en miles de dólares, ri, para el artículo i. El objetivo es determinar la cantidad de unidades de cada artículo que maximizará el rendimiento total.
[pic 2]
Como el peso unitario wi y el peso máximo W son enteros, el estado xi asume sólo valores enteros.
SOLUCIÓN:
- Trabajaremos con 3 etapas, las cuales son los tres artículos
ETAPA 3 | |||||
F3(x3) = MAX (80M3), MAX(M3) = 4 / 3 = 1 | |||||
VALORES: 0, 1 | |||||
X3 | 0 | 1 | M3 | F3(X3) | |
0 | 0 | - | 0 | 0 | |
1 | 0 | - | 0 | 0 | |
2 | 0 | - | 0 | 0 | |
3 | 0 | 80 | 1 | 80 | |
4 | 0 | 80 | 1 | 80 |
ETAPA 2 | ||||||
F2(x2) = MAX (60M2) + f3(x2 - 2m2), MAX(M2) = 4 /2 = 2 | ||||||
VALORES: 0, 1, 2 | ||||||
X2 | 0 | 1 | 2 | M2 | F2(X3) | |
0 | 0 | - | - | 0 | 0 | |
1 | 0 | - | - | 0 | 0 | |
2 | 0 | 60 | - | 1 | 60 | |
3 | 80 | 60 | - | 0 | 80 | |
4 | 80 | 60 | 120 | 2 | 120 |
ETAPA 1 | ||||||||
F1(x1) = MAX (30M1) + f2(x1 - 2m1), MAX(M1) = 4 /1 =42 | ||||||||
VALORES: 0, 1, 2, 3 , 4 | ||||||||
X1 | 0 | 1 | 2 | 3 | 4 | M1 | F1(X1) | |
0 | 0 | - | - | - | - | 0 | 0 | |
1 | 0 | 30 | - | - | - | 1 | 30 | |
2 | 60 | 30 | 60 | - | - | 2 | 60 | |
3 | 80 | 90 | 60 | 90 | - | 3 | 90 | |
4 | 120 | 110 | 120 | 90 | 120 | 4 | 120 |
La etapa 1 necesita interacciones
m1 | x1 = | 4 |
| m1 | x1 = | 3 |
| m1 | x1 = | 2 |
| ||
| 30(m1) + | F2[x1 - 2(m1)] |
| 30(m1) + | F2[x1 - 2(m1)] |
| 30(m1) + | F2[x1 - 2(m1)] | |||||
0 | 0 | 4 | 120 | 0 | 0 | 3 | 80 | 0 | 0 | 2 | 60 | ||
1 | 30 | 3 | 110 | 1 | 30 | 2 | 90 | 1 | 30 | 1 | 30 | ||
2 | 60 | 2 | 120 | 2 | 60 | 1 | 60 | 2 | 60 | 0 | 60 | ||
3 | 90 | 1 | 90 | 3 | 90 | 0 | 90 | 3 | 90 | -1 | - | ||
4 | 120 | 0 | 120 | 4 | 120 | -1 | - | 4 | 120 | -2 | - |
m1 | x1 = | 1 |
| m1 | x1 = | 0 |
| |
| 30(m1) + | F2[x1 - 2(m1)] |
| 30(m1) + | F2[x1 - 2(m1)] | |||
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
1 | 30 | 0 | 30 | 1 | 30 | -1 | - | |
2 | 60 | -1 | - | 2 | 60 | -2 | - | |
3 | 90 | -2 | - | 3 | 90 | -3 | - | |
4 | 120 | -3 | - | 4 | 120 | -4 | - |
LA SOLUCIÓN PARA MAXIMIZAR GANANCIAS ES 4 UNIDADES DEL ARTÍCULO 3
...