Ejercicios

• Un navegante solitario dispone en su barco de 5 metros cúbicos para almacenar cuatro objetos. El objeto A tiene un volumen de 2 m3 y reporta al navegante 3 unidades de beneficio (ub). Los objetos B, C, y D ocupan respectivamente 4,3 y 2 m3 y el beneficio respectivo es de 5,1 y 1 ub.

a) Determinar mediante un algoritmo de programación dinámica cuales son los objetos que debe llevar el navegante.

b) ¿Qué ocurrirá si la capacidad del barco fuese respectivamente de 4, 3, 2 o 1 metros cúbicos?

Ordenamos los siguientes datos del enunciado:

Objeto	Volumen	UB
A	2m3	3
B	4m3	5
C	3m3	1
D	2m3	1

En Caso de 5m³

Usando el algoritmo de programación dinámica obtenemos la siguiente tabla con los valores máximos.

Siguiendo las instrucciones del algoritmo, podemos deducir que el objeto a almacenar cuando se tienen 5m³ disponibles será el objeto número 2 con un espacio en el barco de 4m³ con 5 unidades de beneficio.

En Caso de 4m³

Usando el algoritmo de programación dinámica obtenemos la siguiente tabla con los valores máximos.

Siguiendo las instrucciones del algoritmo, podemos deducir que el objeto a almacenar cuando se tienen 4m³ disponibles será el objeto número 2 con un espacio en el barco de 4m³ con 5 unidades de beneficio.

En Caso de 3m³ 

Usando el algoritmo de programación dinámica obtenemos el siguiente recuadro con los valores máximos.

 

Siguiendo las instrucciones del algoritmo, podemos deducir que el objeto a almacenar cuando se tienen 3m³ disponibles será el objeto número 1 con un espacio en el barco de 2m³ con 3 unidades de beneficio.

En Caso de 2m³ 

Usando el algoritmo de programación dinámica obtenemos el siguiente recuadro con los valores máximos. 

 

Siguiendo las instrucciones del algoritmo, podemos deducir que el objeto a almacenar cuando se tienen 2m³ disponibles será el objeto número 1 con un espacio en el barco de 2m³ con 3 unidades de beneficio.

En Caso de 1m³ 

Usando el algoritmo de programación dinámica obtenemos el siguiente recuadro con los valores máximos. 

 

Como se puede observar, con un espacio de 1m³ no se podría almacenar ninguno de los objetos.

• Un camión puede transportar un total de 10 toneladas de productos. Hay tres clases de productos para transportar, cuyo peso y valor se muestran en la siguiente tabla. Suponiendo que por lo menos se debe transportar un artículo de cada clase, determinar el cargamento que maximiza el valor total.

Clase	Valor (miles de euros)	Peso (tn)
A	2	1
B	5	2
C	6	2

Usando el algoritmo de programación dinámica obtenemos el siguiente recuadro con los valores máximos:

De aquí podemos obtener que de transportar por lo menos un artículo de cada clase tenemos un peso de 5 toneladas con un valor de 13 mil euros. Todavía hay 5 toneladas que pueden disponerse, por esto se deben incluir 2 artículos de la clase C con un peso total de 4 toneladas y valor de 12 mil euros, además 1 artículo de la clase A con un peso total de 1 tonelada y valor de 2 mil euros.

Por lo que para maximizar el valor total del transporte se deben incluir: 2 artículos de la clase A, 1 artículo de la clase B y 3 artículos de la clase C, dando un total de valor de 27 mil euros con un peso al transporte de 10 toneladas.