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.

El problema de la dieta fue uno de los primeros problemas sobre optimización. George Joseph Stigler fue quien lo planteo a finales de la década de los años 30. El problema de régimen alimenticio óptimo para tratar de satisfacer la necesidad del ejército americano por hallar la manera más económica de alimentar a sus tropas, asegurándose de satisfacer al mismo tiempo unos determinados requerimientos nutricionales.

Análisis e interpretación

En este tipo de problemas, nos van a dar una cierta cantidad de alimentos diferentes, digamos $m$ alimentos, y cada alimento va a contener una cantidad finita de nutrientes de interés, digamos $n$ nutrientes. Entonces la cantidad de nutrientes j que va a tener el alimento i por unidad va a quedar representado por una constante dada, digamos $a_{i,j}$.

——	Nutriente 1	Nutriente 2	$\ldots$	Nutriente $n-1$	Nutriente $n$	Costo del alimento
Alimento 1	$a_{1,1}$	$a_{1,2}$	$\ldots$	$a_{1,n-1}$	$a_{1,n}$	$c_1$
Alimento 2	$a_{2,1}$	$a_{2,2}$	$\ldots$	$a_{2,n-1}$	$a_{2,n}$	$c_2$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
Alimento m-1	$a_{m-1,1}$	$a_{m-1,2}$	$\ldots$	$a_{m-1,n-1}$	$a_{m-1,n}$	$c_{m-1}$
Alimento m	$a_{m,1}$	$a_{m,2}$	$\ldots$	$a_{m,n-1}$	$a_{m,n}$	$c_m$
Nutrientes requeridos	$b_1$	$b_2$	$\ldots$	$b_{n-1}$	$b_n$	——

Cada individuo (ya sea persona u otro ser vivo) tiene el mismo requerimiento mínimo de cada uno de estos nutrientes, digamos $b_j, \quad \forall \ j \in {1, \ldots, n}$.

Sea $x_i$ = el número de unidades del alimento i que vamos a asignar a cada individuo

Entonces vamos a tener la restricción de que cada individuo tiene que recibir los nutrientes requeridos por los alimentos que le son dados. Esto se representa de la siguiente manera:

(Alimento 1: cantidad de nutriente j)(Unidades de alimento 1) + (Alimento 2: cantidad de nutriente j)(Unidades de alimento 2) + $\ldots$ + (Alimento m: cantidad de nutriente j) (Unidades de alimento m)$\geq$ Nutriente j requerido

Usando la notación de la tabla y las variables que creamos, se escribiría:

$a_{1,j}x_1 + a_{2,j}x_2 + \ldots + a_{m,j}x_m \geq b_j$ para cualquiera de los n nutrientes.

Cada alimento va a tener un coste dado por unidad, digamos $c_i$.

Como se mencionó, se busca la manera más económica de alcanzar los nutrimentos requeridos de los alimentos asignados a cada individuo, entonces, el problema busca minimizar el costo de los alimentos que elijamos. Esto se traduce como:

Minimizar z = (Costo alimento 1)(Unidades de alimento 1) + (Costo de alimento 2)(Unidades de alimento 2) + $\ldots$ + (Costo de alimento m)(Unidades de alimento m)

Usando la notación de la tabla y las variables que creamos, se escribiría:

$Min \quad z = c_1x_1 + c_2x_2 + \ldots + c_mx_m$

Como la cantidad de alimentos que vamos a asignar es a lo menos cero, nuestras variables $x_i$ van a ser mayores o iguales a cero.

Entonces, en términos generales, el problema quedaría de esta forma:

\begin{align*}
Min \quad z = c_1&x_1 + c_2x_2 + \ldots + c_mx_m\\
sujeto \quad a \quad &(s. a)\\
&a_{1,1}x_1 + a_{2,1}x_2 + \ldots + a_{m,1}x_m \geq b_1\\
&a_{1,2}x_1 + a_{2,2}x_2 + \ldots + a_{m,2}x_m \geq b_2\\
\vdots\\
&a_{1,n}x_1 + a_{2,n}x_2 + \ldots + a_{m,n}x_m \geq b_n\\
&x_i \geq 0\\
\end{align*}

Ejemplo del problema de la dieta

Vamos a citar el ejemplo que se encuentra en la sección 1.2.1 del libro «Introducción a la programación lineal» de María del Carmen Hernández Ayuso. El problema dice así:

Consideremos el problema de diseñar un desayuno en una escuela que satisfaga ciertos requisitos de nutrició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 \$13 por kilogramo y la pieza de pan cuesta \$0.60.

Cada día 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.

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 mencionadas.

Veamos cómo podemos plantear el problema anterior como un problema de programación lineal usando el análisis que hicimos anteriormente.

Vayamos paso por paso, primero identifiquemos que una unidad de cada alimento se va a referir a un litro, kilo o pieza del alimento según corresponda.

Sea $x_1$ los litros de leche, $x_2$ los kilos de jamón, $x_3$ los kilos de huevo y $x_4$ las piezas de pan que vamos a hacer parte del desayuno. En la tabla nos indican los costos de estos por lo que ya tenemos nuestra función objetivo a minimizar:

$Min \quad z = 10x_1 + 45x_2 + 13x_3 + .6x_4$

Luego, tenemos que considerar las restricciones de los nutrientes que son requeridos por cada individuo. Solo tenemos dos nutrientes a considerar entonces tenemos las siguientes restricciones:

(Alimento 1: cantidad de nutriente 1)(Unidades de alimento 1) +
(Alimento 2: cantidad de nutriente 1)(Unidades de alimento 2) +
(Alimento 3: cantidad de nutriente 1)(Unidades de alimento 3) +
(Alimento 4: cantidad de nutriente 1) (Unidades de alimento 4) $\geq$
Nutriente 1 requerido

(Alimento 1: cantidad de nutriente 2)(Unidades de alimento 1) +
(Alimento 2: cantidad de nutriente 2)(Unidades de alimento 2) +
(Alimento 3: cantidad de nutriente 2)(Unidades de alimento 3) +
(Alimento 4: cantidad de nutriente 2) (Unidades de alimento 4) $\geq$
Nutriente 2 requerido

Escrito en la notación general descrita:

\begin{align*}
&a_{1,1}x_1 + a_{2,1}x_2 + a_{3,1}x_3 + a_{4,1}x_4 \geq b_1\\
&a_{1,2}x_1 + a_{2,2}x_2 + a_{3,2}x_3 + a_{4,2}x_4 \geq b_2\\
\end{align*}

Y usando los valores de el problema, tenemos:

\begin{align*}
&15x_1 + 5x_2 + 8x_3 + x_4 \geq 25\\
&3x_1 + 15x_2 + 8x_3 + 4x_4 \geq 20\\
\end{align*}

Y por último solo cabe mencionar que las unidades de alimento que vamos a considerar es un número mayor o igual a cero. Por lo que el planteamiento del problema quedaría de la siguiente manera:

\begin{align*}
Min \quad z = 10&x_1 + 45x_2 + 13x_3 + .6x_4\\
s.a&\\
15&x_1 + 5x_2 + 8x_3 + x_4 \geq 25\\
3&x_1 + 15x_2 + 8x_3 + 4x_4 \geq 20\\
&x_1, x_2, x_3, x_4 \geq 0\\
\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