Archivo del Autor: Aldo Romero

Investigación de Operaciones: El problema de la mochila

Por Aldo Romero

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.

ProductoPeso de un saco
en kilogramos
Ahorro al consumidor
en pesos por saco
Arroz1225
Azúcar1520
Café1030
Frijol1525

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

Investigación de Operaciones: El problema de la dieta

Por Aldo Romero

Introducción

En la entrada anterior hablamos un poco de lo que es la Programación Lineal, de su historia y de cuáles son los tipos de problemas que estudia. Dijimos que un problema de programación lineal es aquel en el que se busca optimizar una función lineal bajo ciertas restricciones lineales. En estas entradas y las siguientes veremos algunos ejemplos conocidos de problemas de programación lineal. Comenzaremos hablando del problema de la dieta.

Ejemplo del problema de la dieta

Consideremos el problema de diseñar un desayuno en una escuela que satisfaga ciertos requisitos de nutrición establecidos por alguna institución de salud que hace recomendaciones con respecto a la dieta de la población.

Supongamos que se tienen cuatro alimentos disponibles: leche, jamón, huevo y pan. El costo de la leche es de \$10 por litro, el del jamón de \$45 por kilogramo, el del huevo de \$13 por kilogramo y el del pan de \$0.60 por pieza.

De acuerdo a las restricciones establecidas por la institución de salud, en cada menú los niños deben ingerir por lo menos, entre otras cosas, 25 unidades de cierto nutriente al que llamaremos N1 y 20 unidades de otro denominado N2. Si quieres puedes pensar en que N1 son proteinas y N2 carbohidratos.

El contenido nutritivo de los alimentos y el costo de éstos se muestra en la siguiente tabla. Debemos diseñar el menú más económico que satisfaga las necesidades nutrimentales mencionadas.

AlimentoCosto por unidad en pesosContenido nutritivo por unidad de alimento
N1N2
Leche$10/lt153
Jamón$45/kg515
Huevo$13/kg88
Pan$0.60/pz14
Necesidades de nutrición2520

Veamos cómo podemos plantear el problema anterior como un problema de programación lineal.

Variables de decisión del problema de la dieta

Puesto que el problema es determinar la cantidad de cada alimento que debemos incluir en el menú, definiremos las siguientes variables:

  • $x_1$ = número de litros de leche a incluir en el menú.
  • $x_2$ = número de kilogramos de jamón a incluir en el menú.
  • $x_3$ = número de kilogramos de huevo a incluir en el menú.
  • $x_4$ = número de piezas de pan a incluir en el menú.

Observemos que un conjunto de asignación de valores a las variables de decisión representa una alternativa de solución para el problema, es decir, un menú.

Restricciones del problema de la dieta

El conjunto de posibles valores de las variables debe representar a todas las alternativas factibles para el problema. En otras palabras, las restricciones que se impongan a los valores de las variables deben garantizar el consumo de nutrientes requerido.

Hagamos de manera detallada el cálculo para el nutriente N1. Notemos que la cantidad de nutriente N1 que tiene un menú se puede desglosar de acuerdo a cuánto contribuye cada tipo de alimento. Así, calculemos las siguientes cantidades:

  • Como tendremos $x_1$ litros de leche y cada litro contribuye con $15$ unidades de nutriente $1$, entonces el número de unidades del nutriente N1 contribuidas por la lecha es $15x_1$.
  • De manera similar, el número de unidades de nutriente N1 contribuidas por los $x_2$ kilogramos de jamón es $5x_2$.
  • Así mismo, el número de unidades de nutriente N1 contribuidas por $x_3$ kilogramos de huevo es $8x_3$.
  • Finalmente, el número de unidades de nutriente N1 contribuidas al menú por las $x_4$ piezas de pan es simplemente $x_4$, pues cada pieza contribuye con sólo una unidad.

Así, en el menú compuesto por $x_1$ litros de leche, $x_2$ kilogramos de jamón, $x_3$ kilogramos de huevo y $x_4$ piezas de pan tenemos un total de

$$15x_1+5x_2+8x_3+x_4$$

unidades de nutriente N1 y esta cantidad deberá ser mayor o igual que $25$.

En resumen, la primera restricción del problema es: $$15x_1+5x_2+8x_3+x_4 \geq 25.$$

Aún no terminamos con todas las restricciones. También debemos considerar al nutriente N2. Afortunadamente, los cálculos son muy similares y nos dicen que la cantidad total de nutriente N2 incluida en un menú compuesto por $x_1$ litros de leche, $x_2$ kilogramos de jamón, $x_3$ kilogramos de huevo y $x_4$ piezas de pan es $$3x_1+15x_2+8x_3+4x_4.$$

De este modo, para cumplir con los requisitos de tener al menos $20$ unidades de N2 se debe cumplir que $$3x_1+15x_2+8x_3+4x_4\geq 20.$$

Finalmente notemos que en un menú no puede haber una cantidad negativa de ingredientes. Por ejemplo, no podemos tener $-5$ piezas de pan. Así, también deben satisfacerse las siguiente restricciones de no-negatividad: $$x_i \geq 0 \quad \text{para $i=1, \ldots , 4$.}$$

Función objetivo del problema de la dieta

La función objetivo de un problema de programación lineal está dada por la cantidad que queremos optimizar. En el problema que tenemos, se pide encontrar el menú más económico. Así, el criterio de evaluación de las alternativas de menú que tenemos es su costo.

Podemos calcular el costo de un menú de manera muy similar a la que calculamos la cantidad de nutrientes. El costo depende de cuántas unidades incluyamos de cada alimento, y esto ya sabemos que está contemplado en las variables $x_1,x_2,x_3,x_4$. Por ejemplo, como cada litro de leche cuesta \$10, entonces tendremos que la leche costará en total $10x_1$ pesos. Haciendo lo mismo para el resto de los alimentos, obtenemos que el costo de un menú compuesto por $x_1$ litros de leche, $x_2$ kilogramos de jamón, $x_3$ kilogramos de huevo y $x_4$ piezas de pan es: $$z=10x_1+45x_2+13x_3+0.6x_4.$$

Esta es la función que queremos optimizar. Más concretamente, es la función que debemos minimizar.

Resumen de formulación del problema de la dieta

En resumen, la versión matemática del problema de programación lineal que nos interesa estudiar es la siguiente:

\begin{align*}
Min \quad z &= 10x_1+45x_2+13x_3+0.6x_4\\
s.a.\\
15x_1&+5x_2+8x_3+x_4 \geq 25\\
3x_1&+15x_2+8x_3+4x_4 \geq 20\\
x_i& \geq 0, \quad i=1, \ldots ,4.\\
\end{align*}

Más adelante…

El problema de la dieta es el primer ejemplo de problema de programación lineal que nos encontramos. En las siguientes entradas veremos otros ejemplos más, como el problema de la mochila, el del transporte y otros.

Hasta ahora sólo hemos hablado de qué tipo de problemas queremos resolver, pero no hemos dicho nada con respecto al cómo los resolveremos. Veremos eso un poco más adelante.

Tarea moral

  • ¡Oh no! La inflación llegó y el precio de los alimentos mencionados en la entrada subió en $10\%$. Realiza nuevamente la formulación del problema de la dieta del ejemplo bajo este supuesto.
  • Formula como un PPL el siguiente ejemplo:
    «Se tienen disponibles 4 tipos de inversión cuyos costos son \$12,000, \$20,000, \$16,000, \$15,000 respectivamente. La inversión 1 tiene un valor presente neto de \$14,000, la 2 de \$25,000, la 3 de \$20,000 y la 4 de \$18,000. Se cuenta con un presupuesto de \$50,000. El objetivo es determinar la combinación de inversiones que aporte el valor presente neto máximo.»
  • Imagina que tenemos un problema de la dieta muy sencillo. Sólo se puede adquirir pan y leche. Cuesta \$1 la pieza de pan y \$10 el litro de leche. El pan da 5 unidades de N1 y 1 de N2. La lecha da 3 unidades de N1 y 10 de N2. Imagina que se deben consumir 25 unidades de N1 y 20 unidades de N2. Se quiere encontrar la dieta más económica. Plantea este problema como un problema de programación lineal.
  • Intenta resolver el problema de programación lineal del inciso anterior con las herramientas con las que cuentes hasta ahora de Cálculo, Álgebra Lineal, etc. ¿Cuál sería el menú más económico?
  • ¿Por qué en el problema de la dieta no tiene sentido preguntarse por la dieta menos económica? Intenta argumentarlo desde el punto de vista práctico, como desde el punto de vista matemático.

Entradas relacionadas

Investigación de Operaciones: Introducción a la programación lineal

Por Aldo Romero

Introducción

En esta entrada comenzaremos a abordar el primer tema de este curso de Investigación de Operaciones: el de la programación lineal. Hablaremos un poco de por qué es importante estudiar esta disciplina. Luego, explicaremos un poco en qué consiste. Finalmente, veremos el tipo de problemas que podremos responder una vez que hayamos desarrollado más teoría.

¿Por qué estudiar programación lineal?

El desarrollo de la programación lineal ha sido clasificado como uno de los avances científicos más importantes de mediados del siglo XX. En la actualidad es una herramienta de uso cotidiano que permite efectuar de manera óptima muchas de las operaciones que realizan individuos, gobiernos, compañías y negocios. Esto ha su vez ha permitido el uso eficiente de los recursos y ahorros prácticamente incalculables.

Además de las ventajas que trae usar la programación lineal, también es notable la facilidad con la que hoy en día se aplican sus métodos. El tipo de matemáticas sobre las cuales está construida la programación lineal es en general teoría bien conocida: resultados básicos de álgebra lineal, teoremas importantes de cálculo, teoría de gráficas y redes. Esto se complementa con que en la actualidad es sencillo llevar esta teoría a la práctica, pues existen varios lenguajes de programación para uso científico que cuentan con bibliotecas dedicadas a la programación lineal.

¿Qué es la programación lineal?

La programación lineal es una rama de la programación matemática que estudia problemas de optimización en los cuales se desea maximizar (o minimizar) una función lineal restringida mediante ecuaciones o desigualdades lineales. En este contexto no hablamos de la palabra «programación» en el sentido usual de crear código para diseñar programas en una computadora. Más bien, nos referimos a «programación» más como en el sentido de «la programación de cierto canal de televisión» o bien como en la frase «programé una cita con mi dentista», es decir, como una manera de tomar decisiones para repartir un recurso (el tiempo de aire en el caso de la televisión y el tiempo del doctor y del paciente en el ejemplo del dentista).

Existe una gran variedad de problemas, en diversos campos, que pueden ser formulados o aproximados como modelos lineales. Una de las ventajas de resolver problemas por métodos de programación lineal es que existen técnicas eficientes, sencillas y bien estudiadas para resolverlos. Además, se tiene la comodidad de que una vez que se haya resuelto un problema, es sencillo hacer una variación de los parámetros originales para tener una buena intuición de la nueva respuesta sin tener que volver a hacer un procedimiento largo (a esto se le llama análisis de postoptimalidad).

Aunque una de sus aplicaciones más frecuentes es la asignación de recursos, la programación lineal tiene muchas otras posibilidades. En realidad, cualquier problema cuyo modelo matemático se ajuste al formato general de un problema de programación lineal, puede ser estudiado mediante las herramientas de la teoría.

Formato general de un problema de programación lineal

A un problema de programación lineal y su modelo lo llamaremos programa lineal. Abreviaremos problema de programación lineal como PPL y programa lineal como PL.

Estos problemas tienen que cumplir con las siguientes condiciones:

  • El criterio para seleccionar el mejor valor de las variables desconocidas involucradas en el problema, llamadas variables de decisión, puede describirse como función lineal de éstas. A esta función se le da el nombre de función objetivo.
  • Las reglas de operación que gobiernan el proceso (que definen las alternativas de solución) pueden expresarse mediante un conjunto de ecuaciones o desigualdades lineales a las cuales se les da el nombre de restricciones del problema.

El planteamiento matemático inicial del problema de programación lineal fue desarrollado por George Bernard Dantzig en 1947 junto con el método de solución simplex. El formato general del un modelo de esta clase es:

\begin{align*}
\text{Maximizar (o Minimizar)}&\\
z = c_1x_1+c_2x_2&+\ldots+c_nx_n\\
\text{s.a. (sujeto a)}\\
a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n \quad &\leq b_1 \quad \text{(o bien $\geq$ o $=$)}\\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n \quad &\leq b_2 \quad \text{(o bien $\geq$ o $=$)}\\
&\vdots\\
a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n \quad &\leq b_m \quad \text{(o bien $\geq$ o $=$)}\\
x_i & \geq 0, i = 1,\ldots,n.
\end{align*}

Este problema de programación lineal PPL puede escribirse en forma matricial:

\begin{align*}
\text{Max. (o Min.)}&\\
z &= c\\
\text{s.a.}\\
Ax \quad &\leq b
\quad \text{(o bien $\geq$ o $=$)}\\
x &\geq 0.
\end{align*}

En esta expresión $c$ es un vector renglón en $\mathbb{R}^n$, llamado vector de costos o de coeficientes en la función objetivo. El vector $x$ es un vector columna (formado por las variables de decisión $x_1,\ldots,x_n$) en $\mathbb{R}^n$. La matriz $A$ es de $m$ renglones y $n$ columnas, llamada la matriz de restricciones. Y finalmente $b$ es un vector columna en $\mathbb{R}^n$, llamado el vector de recursos o lado derecho.

Más adelante…

En esta entrada hablamos un poco de qué es la programación lineal y qué es un PPL, pero nos hemos quedado en términos un poco abstractos. La mejor forma de entender qué es un problema lineal es mediante la presentación de ejemplos. En las siguientes entradas formularemos algunos ejemplos comunes, motivados en aplicaciones prácticas. Hablaremos del problema de la dieta, el problema de la mochila, el problema del transporte, y otros.

Tarea moral

  1. Ve el siguiente video de acerca de George Dantzig. ¿Que te pareció la anécdota de su tiempo de estudiante?
  1. Aún no hemos visto ejemplos de Problemas de Programación Lineal (PPL) pero, ¿crees que es siguiente ejemplo pueda formularse como uno? «Encontrar la ruta más corta entre una ciudad y otra teniendo varias rutas posibles que se cruzan entre sí.»
  2. Investiga un poco más de la historia de la programación lineal. ¿Qué gran evento en el mundo ayudó a que la teoría se desarrollara aceleradamente?

Enlaces