Introducción

El problema tipo mochila es uno de los planteamientos que más hemos trabajado durante el semestre, un tipo de problema que debido a sus características es bastante dinámico, capaz de ser resuelto por una gran variedad de métodos entre las cuales se encuentra el método de ramificación y acotamiento para binarios, además de esto por su estructura se le puede aplicar otro sub-algoritmo al método para facilitar más los cálculos, el método o algoritmo de inspección para el problema tipo mochila.

Este problema hace referencia a la asignación de distintos elementos en un espacio determinado, “La mochila”, intentando obtener la mayor ganancia posible, esto se presta a distintos modelos para la representación del problema, pero en el caso que se va a tratar en este documento nos limitaremos a un problema tipo mochila sencillo, donde únicamente se busca maximizar la ganancia de los elementos y se limita a tomar un elemento de cada tipo, esto le da al problema una estructura que se apega a un modelo binario.

Problema

Bob es un vendedor primerizo y desea llevar sus productos al mercado de su comunidad, pero se encontró con un problema, la mochila en la que tiene planeado llevar todo únicamente puede cargar 15 kg y los productos que va a vender exceden esta capacidad, así que tiene que seleccionar los productos que le permitan obtener una mayor ganancia sin exceder la capacidad de la mochila, los precios de venta y los pesos de los objetos se muestran en la siguiente imagen.

Sabias que:

• “La aparición más conocida del problema tipo mochila fue junto con otros 21 problemas NP-completos en una lista publicada por Richard Karp en 1987”

-Richard M. Karp. (1987). Reducibility among combinatorial problems. Diciembre 26, 2019, de University of California Sitio web: https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf

Planteamiento

xi = {1 Se toma el elemento i, 0 No se toma el elemento i }

Max Z = 12x1+7x2+3x3+10x4+19x5

s.a.

7x1+3x2+2x3+5x4+10x5 <=15

xi {0,1} xi>=0

Planteamiento con explicación

Como se puede observar a simple vista es un planteamiento sencillo, únicamente con una restricción, maximizado y binario.

Las variables

xi = {1 Se toma el elemento i, 0 No se toma el elemento i }

Esto hace referencia a el hecho de que si se lleva un elemento en la mochila o no se toma.

La función objetivo

Max Z = 12x1+7x2+3x3+10x4+19x5

La función objetivo enlista los objetos con sus costos y es maximizada debido a que se quiere obtener la mayor ganancia.

La restricción

7x1+3x2+2x3+5x4+10x5<=15

Aquí es donde se comienzan a detallar cómo es que se encuentra limitado nuestro problema en este caso por se limita por la capacidad de la mochila y los coeficientes de las variables son los pesos.

Resolución del modelo

Método de ramificación y acotamiento para problemas binarios

En esta ocasión se utilizará el método de ramificación y acotamiento para problemas binarios, este método suele sugerir que resolvamos el modelo relajado con restricciones nuevas, pero gracias a que este problema cumple con las características podemos utilizar el método de inspección para problemas tipo mochila para obtener las soluciones parciales.

Primero obtenemos cocientes del valor del elemento sobre su peso

x1= 127 = 1.71 x2 =73=2.33 x3 =32=1.5 x4=105=2 x5=1910=1.9

Así es como se ordenarán los productos para hacer la evaluación

x2-> x4-> x5 -> x1-> x3

De aquí comenzamos a “ingresar” elementos a la mochila y viendo sus repercusiones en la capacidad y en el valor.

Al final resulta en otra posibilidad con aún mayor ganancia, así que tomaremos esto como nuestra respuesta final.

Interpretación

Este es el resultado final, lo que Bob va a llevar al mercado a vender son los elementos x5 y x2 del problema que son las cajas gris y azul y al venderlo tendrá como ganancia un total de 30 unidades monetarias.

Este tipo de planteamientos se pueden ver en el dia a dia y a escalas mucho mayores, es uno de los planteamientos más útiles de todos.