Mudanza - Participación

Me voy a cambiar de casa desde Querétaro a la CDMX, he rentado un camión que puede cargar hasta 1,100 pies cúbicos de muebles. El volumen y el valor de cada objeto que estoy pensando en transportar en el camión se proporciona en la tabla siguiente:

¿Qué objetos debo llevar?

PLANTEAMIENTO

Modelaremos el problema como un problema tipo mochila, en donde la función objetivo pretende maximizar el valor total de los artículos en la mudanza y la restricción hace referencia a la capacidad máxima del camión que transportará los muebles. Cuando la variable de decisión toma el valor de 1 nos indica que debemos llevar el artículo representado por esa variable, sucede lo contrario cuando la variable toma el valor de 0.

SOLUCIÓN

Resolveremos este problema con el método de Ramificación y Acotamiento (P. Tipo Mochila).

El primer paso es realizar el cociente entre el beneficio y el peso de cada artículo y ordenar esta cociente de mayor a menor.

Notamos que los artículos quedaron en el siguiente orden: 2 - 4 - 1 - 5 - 3

Esto quiere decir que el artículo en la posición inicial 2 (Comedor) es el que mayor valor monetario tiene, por su parte, el artículo en la posición inicial 3 (Aparato electrofónico) es el de menor valor monetario.

Posteriormente comenzamos con el algoritmo en el cual podemos suponer que se coloca en el camión el artículo i al mismo tiempo que se observa el valor que agrega éste y el volumen que ocupa en el camión.

Por ejemplo, para la primer iteración tenemos lo siguiente:

En caso de que la capacidad se convierta en un valor negativo, procedemos a realizar el cociente de la capacidad anterior entre la capacidad que necesita el artículo.

El siguiente es el árbol de ramificación para este problema:

Con lo que podemos concluir que la solución final indica que deberá subir al camión los artículos 2 (comedor) y 4 (sofá), con un valor total de $79.00.