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
Supongamos que un estado de la República Mexicana cuenta con un programa social para la venta de ciertos productos de la canasta básica a un precio reducido. Para ello, una camioneta transporta sacos de estos productos y los lleva a varios poblados del estado para venderlos. Si el consumidor adquiere el producto con la camioneta en vez de con otro distribuidor obtiene cierto ahorro.
En la siguiente tabla se indican los productos que se transportarán. Para cada uno de ellos, se muestra el peso en kilogramos de un saco de cada producto. También se muestra el ahorro, en pesos por saco, que obtendrán los consumidores.
| Producto | Peso de un saco en kilogramos | Ahorro al consumidor en pesos por saco |
| Arroz | 12 | 25 |
| Azúcar | 15 | 20 |
| Café | 10 | 30 |
| Frijol | 15 | 25 |
La camioneta puede transportar un máximo de 2 toneladas en carga. Queremos determinar con qué productos se debe cargar la camioneta de manera que se produzca el máximo ahorro al consumidor.
Variables de decisión del problema de la mochila
Puesto que se desea determinar la cargar de la camioneta, definimos las siguientes variables para cada $i=1,2,3,4$:
$x_i$ = número de sacos del producto $i$ que se incluirán en la carga de la camioneta.
Así como en la entrada anterior sobre el problema de la dieta, un conjunto de posibles asignaciones de valores de estas variables corresponden a una alternativa para el problema, es decir, una manera de posible de cargar la camioneta.
Restricciones del problema de la mochila
En este caso la única condición que debe satisfacer una alternativa posible es que su peso total no exceda la capacidad de carga de la camioneta. El peso de una carga posible es: $12x_1+15x_2+10x_3+15x_4$ kilogramos. Las cuentas son muy similares a las del problema de la entrada anterior. Por ejemplo, el término $12x_1$ aparece pues se transportarán $x_1$ sacos de arroz y cada uno de ellos pesa $12$ kilogramos.
El peso de la carga no debe exceder de las $2$ toneladas. Aquí hay que ser cuidadosos pues las unidades son distintas: kilos vs. toneladas. Para plantear correctamente el problema, debemos primero considerar que $2$ toneladas son $2000$ kilogramos. De este modo, la restricción queda escrita como $$12x_1+15x_2+10x_3+15x_4\leq 2000.$$
Por otro lado, dada su definición, las variables deben ser no negativas (pues no podemos transportar una cantidad negativa de sacos) y enteras (pues no podemos transportar sólo una fracción de saco).
Función objetivo del problema de la mochila
El criterio de comparación entre las alternativas es el ahorro total que aporten a los consumidores, de modo que tenemos que diseñar la función objetivo para que represente a éste. El ahorro total que se obtiene es de $$z=25x_1+20x_2+30x_3+25x_4.$$ Esta es la cantidad que se quiere maximizar.
Resumen de formulación del problema de la mochila
El PPL que obtenemos es en resumen:
\begin{align*}
Max \quad z&=25x_1+20x_2+30x_3+25x_4\\
s.a.&\\
12x_1&+15x_2+10x_3+15x_4 \leq 2000\\
x_i &\geq 0,x_i \in \mathbb Z, i=1,\ldots,4.\\
\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.
Un caso particular de este modelo, también difícil de resolver, es el problema binario de la mochila en el cual las variables sólo pueden tomar los valores $0$ o $1$. Esto se traduce, en el caso de la excursión, simplemente a decidir si se incluye o no una lata de alimento $i$.
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 distrubuir 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 moral
- Para entender un poco las dificultades de los PPLE considera el siguiente ejemplo. Imagina que el saco de arroz pesa 5 kilogramos, que el saco de azucar pesa 3 kilogramos, que el primero de ellos da un ahorro de \$12 y que el segundo da un ahorro de \$10. El vehículo que tenemos ahora es un coche que sólo puede cargar 300 kilogramos. ¿Cómo cargarías en este caso el coche para maximizar el ahorro? Plantea el PPLE e intenta resolver el problema con las herramientas con las que cuentes hasta ahora.
- Para entender un poco el problema binario de la mochila, considera el siguiente ejemplo. Se tienen 10 posibles artículos con peso $7,10,12,4,5,9,11$ y con valor correspondiente $23,25,28,17,19,25,26$. Sólo podemos decidir si llevar o no llevar cada artículo, y el peso total que se cargará no puede exceder $40$. ¿Cuáles artículos hay que llevar para maximizar el valor? Plantea el PPLE e intenta resolverlo con las herramientas con las que cuentes hasta ahora.
- Considera el problema ejemplo de la entrada. ¿Qué crees que pase con la respuesta del problema si pasan las siguientes cosas? ¿El ahorro óptimo aumentará o dismunuirá? Considera cada caso por separado, uno por uno.
- El programa compró una mejor camioneta, que ahora puede transportar 2.5 toneladas.
- El café se volvió más caro y ahora cada saco sólo ahorra 25 pesos al consumidor.
- La fábrica de frijol ya cambió las presentaciones de sus productos y ahora sólo vende sacos de 30 kilos, que le dan un ahorro de 50 pesos al comprador.
- Por una nueva política de salud, se quitó el azucar de los productos beneficiados por el programa social.
- ¿Notaste que en la entrada anterior no dimos la formulación general del problema de la dieta, sino sólo un ejemplo? Es tu turno de plantear una versión general. Regresa a la entrada anterior y plantea la versión general del problema de la dieta.
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