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.

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:

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

• Ir a Investigación de Operaciones
• Entrada anterior del curso: Introducción a la programación lineal
• Entrada siguiente del curso: El problema de la mochila