Introducción

En la entrada anterior hablamos del problema de la dieta, en donde queríamos cumplir ciertas restricciones alimenticias creando un menú de bajo costo. En esta entrada veremos otro ejemplo conocido de PPL: el problema de la mochila. La idea general es que queremos transportar ciertos bienes mediante un contenedor que tiene cierta capacidad. Este contenedor puede ser algo tan sencillo como una mochila, o algo tan complicado como un tren. A continuación veremos un ejemplo intermedio.

Ejemplo del problema de la mochila

Cesar es un fabricante de botanas que vende 3 de sus productos a varios distribuidores dentro de su localidad. Cada caja de sus productos tiene un peso diferente y generan diferentes ganancias al ser vendidas. Esta información está reflejada en la siguiente tabla:

—	Peso por caja en kilogramos	Ganancia en pesos por caja vendida
Producto 1	10	150
Producto 2	12	200
Producto 3	15	300

Cesar tiene una camioneta que aguanta hasta 800 kilos de carga sin contar al conductor. Cesar quiere saber cuales son los productos que debe llevar con tal de maximizar sus ganancias.

Variables de decisión

Nuestra variable de decisión es bastante intuitiva.

$x_i$ = número de cajas del producto $i$ que Cesar va a llevar en su camioneta. $i \in \{1, 2, 3\}$

Función objetivo

Como el objetivo de Cesar es maximizar las ganancias, la función objetivo va a ser:

$$Max \quad z = 150x_1 + 200x_2 + 300x_3$$

Restricciones

En este problema, la única condición que nos dan es que el peso total de las cajas a llevar no exceda la capacidad de carga de la camioneta. Es decir:

\begin{align*}
10x_1 + 12x_2 + 15x_3 \leq 800\\
x_i \geq 0, i \in \{1, 2, 3\}\\
\end{align*}

Resumen

El PPL que obtenemos es en resumen:

\begin{align*}
Max \quad z= 150x_1&+ 200x_2 + 300x_3\\
s.a.&\\
10x_1&+12x_2+15x_3 \leq 800\\
x_i& \geq 0,i \in \{1, 2, 3\}\\
\end{align*}

Formulación general del problema de la mochila

Un modelo como el anterior recibe el nombre de problema de la mochila pues originalmente fue formulado del siguiente modo: un excursionista desea determinar la cantidad de latas de ciertos comestibles que llevará en su mochila. Las latas tienen cierto peso $p_i$, cierto valor $v_i$ para el excursionista y su mochila tiene capacidad $P$. Si hay $n$ alimentos disponibles y usamos como variables de decisión a $x_1,\ldots,x_n$, donde $x_i$ es el número de latas de alimento $i$ que el excursionista llevarán, entonces el problema de la mochila es:

\begin{align*}
Max \quad z &= \sum_{n}^{i=1} v_ix_i\\
s.a.&\\
\sum_{n}^{i=1} p_ix_i &\leq P\\
x_i &\geq 0, x_i \in \mathbb Z, i=1, \ldots, n.\\
\end{align*}

Este es un problema de programación lineal, pero más específicamente se le conoce como un problema de programación lineal entera (PPLE), o bien un modelo lineal entero, pues las variables $x_i$ están sujetas a tomar sólo valores en los números enteros. Sorpresivamente, aunque los problemas de programación entera parezcan «más fáciles» dado que sus posibilidades están más restringidas, esto no es así. Han sido objeto de mucho estudio pues agregar la condición de integralidad (que las variables sean enteras) crea complicaciones adicionales y hacen que los métodos generales no funcionen tan bien. Los problemas de programación lineal entera son difíciles incluso en términos de una noción computacional muy precisa del tiempo requerido para obtener la mejor solución.

Más adelante…

Aún tenemos algunos problemas conocidos por explorar. El siguiente que veremos es el problema del transporte, en donde queremos saber cómo distribuir productos a través distintas posibilidades de transporte para economizar costos.

En algunas entradas más también hablaremos de cómo llevar cualquier PPL a una forma estándar, que nos permitirá desarrollar la teoría general necesaria para resolverlo.

Tarea

1. Imagina el siguiente escenario:
   Cesar ahora solo vende los productos 1 y 2. El producto 1 ahora pesa 8 kilogramos y el producto 2 ahora pesa 10 kilogramos, que el primero de ellos da una ganancia de \$120 y que el segundo da una ganancia de \$155. El vehículo que tenemos ahora es un coche que sólo puede cargar 392 kilogramos. ¿Cómo cargarías en este caso el coche para maximizar las ganancias? Plantea el PPL e intenta resolver el problema con las herramientas con las que cuentes hasta ahora.
2. Para entender un poco el problema binario de la mochila, considera el siguiente ejemplo. Se tienen 7 posibles artículos con pesos de 7, 10, 12, 4, 5, 9, 11 kilos y con valor de 23, 25, 28, 17, 19, 25, 26 respectivamente. Sólo podemos decidir si llevar o no llevar cada artículo, y el peso total que se cargará no puede exceder 40 kilos. ¿Cuáles artículos hay que llevar para maximizar el valor? Plantea el PPL e intenta resolverlo con las herramientas con las que cuentes hasta ahora.
3. Considera el problema ejemplo original de esta entrada de blog. ¿Qué pasaría con la respuesta del problema si ocurrieran los siguientes escenarios? ¿Las ganancias aumentarán o disminuirán?
   • Cesar compró una mejor camioneta, que ahora puede transportar 1.5 toneladas.
   • El producto 3 se volvió más caro y ahora Cesar solo gana 250 pesos por caja vendida.
   • El tipo de envoltura y material de la caja cambio, por lo que ahora los pesos de los productos son 12, 17, 25 kilos para los productos 1, 2 y 3 respectivamente.

Entradas relacionadas

• Ir a Investigación de Operaciones
• Entrada anterior del curso: El problema de la dieta
• Entrada siguiente del curso: El problema del transporte