Investigacion operativa Programcion dinamica
Enviado por hammersc • 14 de Junio de 2017 • Exámen • 1.985 Palabras (8 Páginas) • 683 Visitas
INVOP2 Programación Dinámica Deterministica
PROBLEMA 1 (Modelo: Volumen de carga)
Un barco de 4 toneladas es cargado con uno o más de tres artículos. La tabla siguiente muestra el peso unitario pn, en toneladas y el ingreso por unidad in , en miles de $, para el artículo n. ¿Cómo se debe cargar el barco para maximizar los ingresos totales?
Artículo n | pn | in |
1 | 2 | 31 |
2 | 3 | 47 |
3 | 1 | 14 |
Tener en cuenta que el barco puede cargar estos artículos en cualquier orden, además, como el peso unitario y el peso permisible son enteros, las variables sólo deben tener valores enteros.
Solución:
Etapa: Cada tipo de artículo hace referencia a una etapa.
Estado: La disponibilidad respecto a la capacidad del barco
Decisión: Cuántas unidades de cada tipo de artículo llevar
Función recursiva: Representa el total de ingreso que se quiere maximizar.
Etapa 3 | |||||||
s3 | f3(s3,x3)=14x3 | Solución óptima | |||||
x3 =0 | x3 =1 | x3 =2 | x3 =3 | x3 =4 | f3*(s3) | x3* | |
0 | 14(0)=0 | - | - | - | - | 0 | 0 |
1 | 14(0)=0 | 14(1)=14 | - | - | - | 14 | 1 |
2 | 14(0)=0 | 14(1)=14 | 14(2)=28 | - | - | 28 | 2 |
3 | 14(0)=0 | 14(1)=14 | 14(2)=28 | 14(3)=42 | - | 42 | 3 |
4 | 14(0)=0 | 14(1)=14 | 14(2)=28 | 14(3)=42 | 14(4)=56 | 56 | 4 |
s3=0; significa que el barco está lleno, disponibilidad cero.
s3=4; significa que el barco está vacío, disponibilidad 4 ton.
Etapa 2 | ||||
s2 | f2(s2,x2)=47x2+f3*(s2-3x2) | Solución óptima | ||
x2 =0 | x2 =1 | f2*(s2) | x2* | |
0 | 47(0)+0=0 | - | 0 | 0 |
1 | 47(0)+14=14 | - | 14 | 0 |
2 | 47(0)+28=28 | - | 28 | 0 |
3 | 47(0)+42=42 | 47(1)+0=47 | 47 | 1 |
4 | 47(0)+56=56 | 47(1)+14=61 | 61 | 1 |
Etapa 1 | |||||
s1 | f1(s1,x1)=31x1+ f2*(s1-2x1) | Solución óptima | |||
x1 =0 | x1 =1 | x1 =2 | f1*(s1) | x1* | |
0 | 31(0)+0=0 | - | - | 0 | 0 |
1 | 31(0)+14=14 | - | - | 14 | 0 |
2 | 31(0)+28=28 | 31(1)+0=31 | - | 31 | 1 |
3 | 31(0)+47=47 | 31(1)+14=45 | - | 47 | 0 |
4 | 31(0)+61=61 | 31(1)+28=59 | 31(2)+0=62 | 62 | 2 |
Para obtener la solución óptima, se observa que el máximo ingreso generado en la etapa 1, es decir $62 mil, se produce cuando se decide llevar 2 unidades del artículo 1.
...