Archivo de la etiqueta: función objetivo

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