Archivo de la etiqueta: investigación de operaciones

Investigación de Operaciones: El problema de producción e inventario

Por Aldo Romero

Introducción

Ya hemos visto algunos ejemplos en los que se plantea un problema de programación lineal a partir de un contexto específico. Hemos visto el problema de la dieta, el problema de la mochila y el problema del transporte. Hay algunos problemas que parecen un poco más complicados y que no es tan evidente desde el inicio que se pueden plantear como problemas de programación lineal. En esta ocasión veremos uno de ellos: el problema de producción e inventario.

A grandes rasgos, el problema consiste en modelar una fábrica que necesita tener lista cierta cantidad de inventario de un producto en determinados momentos del año. La fábrica puede producir cierta cantidad de producto que depende de la temporada del año. Quizás haya temporadas en las que puede producir más de lo que necesita, pero si hace eso incurrirá en costos de almacenaje. ¿Cómo puede distribuir su producción, almacenaje y despacho la fábrica para minimizar el costo y cumplir con su compromiso de inventario? Veamos a continuación que esta situación se puede plantear en términos de un problema de programación lineal.

Ejemplo del problema de producción e inventario

Una fábrica de alimento para gatos tiene un contrato para entregar las siguientes cantidades de alimento al final de cada uno de los trimestres indicados.

Trimestre1234
Demanda en
toneladas
100150480350

Debido a la estacionalidad de los ingredientes involucrados en la producción de alimento para gato, la fábrica tiene una capacidad de producción trimestral de 150 toneladas en los semestres 1 y 3; y de 260 toneladas en los trimestres 2 y 4.

El costo de producción de cada tonelada de alimento para gato es de \$50,000. Por otro lado, es posible almacenar el producto de un trimestre a otro incurriendo en un costo de \$8,000 por unidad. También se tiene la opción, con objeto de cumplir el contrato, de comprar a un competidor alimento para gato a \$52,000 la tonelada.

Se desea determinar un plan de producción, inventario y compra que satisfaga el contrato a costo mínimo.

Variables de decisión del problema de producción e inventario

Lo que se puede decidir en este problema es cuánto alimento producir en cada semestre, y cuánto alimento comprar a un competidor en cada semestre. De esta manera, planteamos las variables de decisión como sigue:

  • $x_i$ = cantidad de alimento de gato (en toneladas) a producir en el trimestre $i$ , $i=1, \ldots ,4.$
  • $y_i$ = cantidad de alimento de gato (en toneladas) a comprar al competidor en el trimestre $i$, $i=1, \ldots , 4.$

Restricciones del problema de producción e inventario

Una primera cosa a observar es que el alimento de gato que sobre de un periodo a otro puede ser usado para cubrir la demanda del segundo periodo, claro, con la desventaja de que esto incurrirá en un costo. ¿Cómo podemos determinar la cantidad de alimento que sobra? Por ejemplo, el alimento que sobra del primer al segundo periodo sería $x_1+y_1-100$, pues a lo producido y comprado habrá que quitar lo que sí se vendió. De manera similar podemos calcular otros sobrantes.

Con esto en mente, vamos a plantear primero las restricciones de demanda. Lo que requerimos es que todo el alimento sobrante, producido y comprado de cada periodo sea suficiente para cubrir la demanda. De esta manera, tenemos las siguientes restricciones.

\begin{align}
x_1 + y_1 &\geq 100\\
x_2 + y_2 + (x_1 + y_1 – 100) &\geq 150\\
x_3 + y_3 + (x_2 + y_2 + (x_1 + y_1 – 100) – 150) &\geq 480\\
x_4 + y_4 + (x_3 + y_3 + (x_2 + y_2 + (x_1 + y_1 – 100) – 150) – 480) &\geq 350.\\
\end{align}

Si bien estas desigualdades reflejan correctamente lo requerido, las condiciones anteriores son un poco complicadas de escribir. Por esta razón, vamos a introducir algunas variables auxiliares. Estas serán variables que no se deciden sino que están totalmente determinadas por lo que se produce y compra al competidor. De cualquier forma, es útil introducirlas en el modelo, y para dejar claro que dependen de las variables $x_i$, tendremos que establecer algunas restricciones dadas por igualdades. Hagamos esto. Definamos las siguientes variables.

  • $w_i$ = cantidad de fertilizante (en toneladas) en inventario al final del trimestre $i$, $i=1, \ldots , 4.$

Como comentamos arriba, estas variables dependen de las variables $x_i$ y $y_i$; de hecho, por ejemplo: $$w_1 = x_1 + y_1 – 100.$$

Si reescribimos esta restricción obtenemos

$$x_1 + y_1 – w_1 = 100.$$

Análogamente:

\begin{align*}
x_2 + y_2 + w_1 – w_2 = 150\\
x_3 + y_3 + w_2 – w_3 = 480\\
x_4 + y_4 + w_3 – w_4 = 350.\\
\end{align*}

Tenemos una gran ventaja de usar estas restricciones. Es exactamente lo mismo «que se cubra la demanda en cada periodo» a que «lo que nos sobre en cada periodo sea $\geq 0$». Intenta convencerte de esto intuitivamente y luego verifica esto algebraicamente. Por ejemplo, nota que la primera condición de demanda ($x_1+y_1\geq 100$) es exactamente lo mismo que pedir $w_1=0$, y lo mismo para las demás. De esta manera, las restricciones (1),(2),(3) y (4) pueden cambiarse por pedir que cada $w_i\geq 0$.

Con esto terminamos con las restricciones de demanda. Tenemos otras restricciones dadas por la cantidad de toneladas de alimento que se pueden producir cada mes. Estas quedan expresadas en las siguientes desigualdades:

\begin{align*}
x_i \leq 150, i = 1,3\\
x_i \leq 260, i = 2,4.\\
\end{align*}

Finalmente, hay condiciones de no negatividad. Ya dijimos que $w_i\geq 0$ para $i=1,2,3,4$. Además de esto, claramente necesitamos

\begin{align*}
x_i, y_i,\geq 0 \quad i=1, \ldots , 4.
\end{align*}

Función objetivo del problema de producción e inventario

En cada periodo tenemos ciertas toneladas que se producen, ciertas que se compran y ciertas que se obtuvieron por almacenar de periodos anteriores. Cada una de ellas incurre en un costo.

Como cada tonelada producida cuesta \$50,000, el total de gasto por toneladas de alimento de gato producidas es de $50000(x_1+x_2+x_3+x_4)$. Como cada tonelada comprada a un competidos cuesta \$52,000, el total de gasto por toneladas de alimento de gato adquiridas a un competidor es de $52000(y_1+y_2+y_3+y_4)$. De manera similar, el costo incurrido por almacenar sobrantes es de $8000(w_1+w_2+w_3+w_4)$. Si juntamos todo en notación suma obtenemos que el costo total a minimizar es el siguiente:

\begin{align*}
z = 50000\sum_{i=1}^4 x_i + 52000\sum_{i=1}^4y_i + 8000\sum_{i=1}^4w_i.
\end{align*}

Resumen de formulación del problema de producción e inventario

En resumen, el PPL que obtenemos es:

\begin{align*}
Min \quad z &= 50000\sum_{i=1}^4 x_i + 52000\sum_{i=1}^4y_i + 8000\sum_{i=1}^4w_i.
&\\
s.a.&\\
x_1&+y_1-w_1 &= 100\\
x_2&+y_2+w_1-w_2 &= 150\\
x_3&+y_3+w_2-w_3 &= 480\\
x_4&+y_4+w_3-w_4 &= 350\\
&x_i \leq 150, i =1,3, \quad x_i \leq 260, i = 2,4\\
x_i, &y_i,w_i \geq 0, i=1, 2, 3, 4.\\
\end{align*}

Más adelante…

En este problema introducimos las variables $w_i$, y ese es uno de los trucos para ampliar el tipo de situaciones que se pueden atender con problemas de programación lineal. La siguiente entrada muestra nuestro último ejemplo introductorio: el problema de la ruta más corta. Como veremos, en este problema también es necesario aprovechar la situación del problema de manera creativa para poder llevarlo a un contexto lineal.

Tarea moral

  1. El problema se vuelve mucho más sencillo si únicamente hay un periodo, pues en ese caso no sobra inventario de un periodo a otro. Plantea un problema que refleje esta situación en el caso particular de la entrada y resuélvelo. Es decir, determina en ese (único periodo) cuál es la cantidad correcta de unidades a producir y cuál es la cantidad correcta de unidades a comprar al competidor, para optimizar el costo total.
  2. Cambia el planteamiento dado en la entrada por uno en el que el costo de almacenaje es de \$0. En ese caso, ¿cuál sería el plan de producción, inventario y compra óptimo?
  3. Estudia el planteamiento dado en la entrada y realiza cambios ya sea en las variables o restricciones para reflejar las siguientes situaciones:
    1. No hay ningún competidor al que se le pueda comprar producto para ayudar a cumplir la demanda.
    2. Hay un competidor, pero sólo permite comprarle 100 toneladas por periodo.
  4. En esta entrada dimos la formulación de un caso particular del problema de producción e inventario. Sin embargo, ya tienes todas las herramientas para plantear el problema de manera general. Realiza una formulación general en la que:
    1. Se tengan periodos $p_1, p_2, \ldots, p_n$ con requisitos de contrato $r_1, r_2, \ldots, r_n$ unidades a cubrir.
    2. Se tengan capacidades de producción $c_1, c_2, \ldots, c_n$ unidades en cada periodo.
    3. Se tengan costos $P$, $C$ y $A$ de producir, comprar al competidor y almacenar una unidad de producto, respectivamente.
  5. En un problema general de producción e inventario. ¿Por qué podría ser mala idea producir todo lo que se necesita vender? ¿Por qué podría ser mala idea producir mucho más de lo necesario en las temporadas en las que se puede? ¿Por qué podría ser mala idea cubrir toda la demanda con unidades compradas al competidor? Intenta justificar intuitivamente, y luego encuentra algunos casos particulares del problema que apoyen tus argumentos.

Entradas relacionadas

Investigación de Operaciones: El problema del transporte

Por Aldo Romero

Introducción

En esta entrada abordaremos otro de los problemas conocidos que se pueden plantear en términos de programación lineal: el problema del transporte. A grandes rasgos, el problema del transporte habla de cómo surtir a diferentes destinos de un cierto producto que parte de diferentes orígenes con disponibilidad limitada.

Siendo un poco más concretos, cada origen tiene una cierta cantidad de unidades de producto. Cada destino requiere de una cierta cantidad de unidades de producto. Además, para cada pareja origen-destino se tiene un costo de transporte unitario. El objetivo es determinar cuál es la manera más económica de cumplir con todos los requisitos de oferta y demanda.

Ejemplo del problema del transporte

Supongamos que una compañía que produce electrónicos tiene tres almacenes $A$, $B$ y $C$. La cantidad de computadoras portátiles disponibles en cada uno de los almacenes se encuentra registrada en la siguiente tabla.

OrigenABC
Oferta en unidades200350470

Pensemos que hay dos tiendas de electrónicos $X$ y $Y$ que desean vender computadoras portátiles de dicha compañía. La cantidad de computadoras portátiles que necesita cada tienda está dada en la siguiente tabla.

DestinoXY
Demanda en
unidades
300500

Además de esto sabemos que transportar cada una de las computadoras portátiles tiene un costo que depende del almacen origen y de la tienda destino. El costo unitario de transporte está dado por la siguiente tabla.

ABC
X354042
Y443745

Así, por ejemplo, transportar una computadora portátil del almacen $B$ a la tienda $Y$ tiene un costo de \$37.

Queremos determinar cuántas computadoras portátiles se tienen que enviar de cada origen a cada destino de manera que 1) no se exceda la cantidad disponible en cada origen, 2) a cada tienda llegue la cantidad de computadoras que se deben enviar y 3) se minimice el costo total de envío.

Variables de decisión del problema del transporte

Lo que tenemos que decidir en nuestro problema es cuántas computadoras portátiles se envían de cada origen a cada destino. Por ejemplo, debemos decidir cuánto vale una variable $x_{AX}$ que nos dice cuántas computadoras portátiles enviar del almacén $A$ a la tienda $X$. De manera análoga, debemos decidir valores para variables $x_{AY}$, $x_{BX}$, $x_{BY}$, $x_{CX}$ y $x_{CY}$, las cuales quedan definidas de manera similar.

En este ejemplo en concreto, la cantidad de unidades debe ser un número entero (no podemos enviar $1/2$ de computadora portátil de un almacen a una tienda).

Restricciones del problema del transporte

Hay dos tipos de restricciones que debemos cuidar:

  • Que ninguno de los almacenes exceda la cantidad de computadoras portátiles que tiene disponible.
  • Que cada tienda reciba el número de computadoras portátiles que requiere.

En el caso de la primera restricción, lo que estamos haciendo es limitar a las sumas que involucren a un mismo almacen. Por ejemplo, para no exceder las $200$ unidades que se tienen disponibles en el almacen $A$, se debe cumplir que $x_{AX}+x_{AY}\leq 200$. De manera similar, con el almacen $B$ obtenemos que $x_{BX}+x_{BY}\leq 350$ y con el almacen $C$ obtenemos que $x_{CX}+x_{CY}\leq 470$.

En el caso de la segunda restricción, ahora la desigualdad es opuesta: es una condición que requiere que las computadoras portátiles que lleguen a cada tienda sean al menos un valor dado. Traduciendo estas condiciones en desigualdades, obtenemos respectivamente para la tienda $X$ y $Y$ lo siguiente:

\begin{align*}
x_{AX}+x_{BX}+x_{CX}\geq 300\\
x_{AY}+x_{BY}+x_{CY}\geq 500.
\end{align*}

Función objetivo del problema del transporte

Finalmente, debemos de establecer cuál es la función objetivo que queremos optimizar. Notemos que el costo total que involucrarán las computadoras portátiles enviadas del almacen $A$ a la tienda $X$ es $35x_{AX}$, pues de acuerdo a la tabla de costos de transporte, hay un costo de \$35 para enviar cada computadora portatil. Todas las computadoras que salgan del almacen $A$ tendrán entonces un costo de $35x_{AX}+44x_{AY}$. Si calculamos de manera similar el costo de las computadoras que se salesn de los almacenes $B$ y $C$ obtenemos un costo total dado por la siguiente expresión:

$$35x_{AX}+44x_{AY}+40x_{BX}+37x_{BY}+42x_{CX}+45x_{CY}.$$

Lo que queremos es minimizar este costo total.

Resumen de formulación del problema del transporte

En resumen, el ejemplo de problema de transporte queda resumido en el siguiente PPL.

\begin{align*}
Min \quad z = 35x_{AX}+44x_{AY}+40x_{BX}&+37x_{BY}+42x_{CX}+45x_{CY}.&\\
s.a.&\\
x_{AX}+x_{AY}&\leq 200\\
x_{BX}+x_{BY}&\leq 350\\
x_{CX}+x_{CY}&\leq 470\\
x_{AX}+x_{BX}+x_{CX}&\geq 300\\
x_{AY}+x_{BY}+x_{CY}&\geq 500\\
x_{AX}, x_{AY},x_{BX},x_{BY},&x_{CX},x_{CY} \in \mathbb{Z}^{\geq 0}
\end{align*}

Formulación general del problema del transporte

De manera general, en el problema del transporte se requieren transportar ciertas unidades de un producto desde $m$ centros de oferta (también llamados orígenes), a $n$ centros de demanda, (también denominados destinos). Cada centro de oferta tiene una cierta cantidad de unidades disponibles, y cada centro de demanda tiene una cierta cantidad de unidades que desea recibir.

Llamemos $o_i$ a la oferta del origen $i$ en unidades del producto ($i=1, \ldots , m$) y $d_j$ la demanda del destino $j$ en unidades del producto ($j=1, \ldots, n$). Para cada origen $i$ y cada destino $j$ tiene cierto costo enviar una unidad de producto. Sea $c_{ij}$ el costo unitario de transporte del producto del origen $i$ al destino $j$ ($i = 1, \ldots , m;j=1, \ldots , n$).

Lo que buscamos es determinar para cada origen $i$ y cada destino $j$ cuántas unidades $x_{ij}$ se deben transportar de tal modo que no se exceda la producción de cada origen, se satisfaga la demanda en cada destino y se incurra en el mínimo costo de transporte.

Como lo hemos hecho en entradas anteriores, las condiciones anteriores pueden ser planteadas en términos lineales. Para no exceder la oferta del origen $i$, se debe cumplir que

$$\sum_{j=1}^nx_{ij} \leq o_i,$$

para cada $i=1,\ldots,m$. A estas desigualdades les llamamos las restricciones de oferta.

Para cumplir con la demanda en el destino $j$ se debe cumplir que

$$\sum_{i=1}^{m}x_{ij} \geq d_j,$$

para cada $j=1,\ldots,n$. A estas desigualdades les llamamos las restricciones de demanda.

Agregando las condiciones de positividad y estableciendo que queremos minimizar el costo total, obtenemos el problema planteado de la siguiente manera:

\begin{align*}
Min \quad z &= \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}\\
s.a.&\\
\sum_{j=1}^nx_{ij} &\leq o_i, \quad i=1, \ldots , m \quad \quad (1)\\
\sum_{i=1}^{m}x_{ij} &\geq d_j, \quad j=1, \ldots , n \quad \quad (2)\\
x_{ij} &\geq 0; \quad i=1, \ldots , m; j=1, \ldots , n,\\
\end{align*}

donde $x_{ij}$ es el número de unidades del producto a transportar del origen $i$ al destino $j$, para cada $i=1, \ldots , m$ y cada $j = 1, \ldots , n$.

Las desigualdades en (1) se llaman restricciones de oferta y en (2) restricciones de demanda.

Notemos que cuando modelamos este problema, se obtiene una estructura muy particular. Al plantear las restricciones, obtenemos que los coeficientes de las variables $x_{ij}$ sólo son $0$ o $1$. De hecho, cada variable $x_{ij}$ aparece sólo en dos restricciones: en la $i$-ésima de oferta y en la $j$-ésima de demanda.

Más adelante…

Con este problema contamos ya con tres ejemplos de situaciones que se pueden plantear en términos de programación lineal: el problema de la dieta, el problema de la mochila y el problema del transporte. A continuación veremos dos más: el problema de producción e inventario, y el problema de la ruta más corta.

Tarea moral

  1. Encuentra por lo menos una manera de realizar las asignaciones de variables en el problema de los almacenes de computadoras portátiles y las tiendas. No importa que el costo total que encuentres no sea óptimo, pero sí se deben cumplir las restricciones de oferta y de demanda.
  2. ¿Qué sucede en el problema del transporte si la cantidad total de demanda excede a la cantidad total de oferta? Plantea esta posibilidad en términos de los parámetros $o_i$ y $d_j$ de oferta y demanda, respectivamente.
  3. Imagina que en el ejemplo que planteamos de computadoras portátiles, almacenes y tiendas sucede que el precio de transportar una computadora portatil es de \$30 sin importar el almacen origen o la tienda destino. En este caso, ¿cuál sería una manera óptima de realizar los envíos, y tal que se cumplan las restricciones de oferta y demanda?
  4. Plantea el siguiente problema del transporte como un problema de programación lineal, ayudándote ya sea del ejemplo particular o del caso general planteados en la entrada.
    Supongamos que un productor de café debe transportar el producto desde Coatepec y Orizaba a sus centros de distribución en la Ciudad de México, Guadalajara y Tijuana. La cantidad disponible en Coatepec es de 55 toneladas de café y en Orizaba es de 35 toneladas. La demanda de café en sus centros de distribución es: 40 toneladas en la Ciudad de México, 30 en Guadalajara y 20 en Tijuana. El costo, en cientos de pesos, por transportar una tonelada de café entre las ciudades se indica en la tabla de abajo.
    El productor desea determinar un plan de transporte de costo mínimo tal que se satisfaga la demanda.
Cd. de MéxicoGuadalajaraTijuana
Coatepec563
Orizaba354
  1. Un posible caso particular del problema del transporte sucede cuando hay muchos orígenes y únicamente un destino. Plantea esta posibilidad de manera general. En este caso, ¿cuál sería una buena estrategia para decidir cuáles orígenes deben enviar unidades del producto al destino?

Entradas relacionadas

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

  1. 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.
  2. 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.
  3. 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.
  4. ¿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