Archivo de la etiqueta: variables de decisión

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.

Origen	A	B	C
Oferta en unidades	200	350	470

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.

Destino	X	Y
Demanda en unidades	300	500

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

	A	B	C
X	35	40	42
Y	44	37	45

Así, por ejemplo, transportar una computadora portátil del almacén $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 no se exceda la cantidad disponible en cada origen, a cada tienda llegue la cantidad de computadoras que se deben enviar y se minimice el costo total de envío.

Variables de decisión

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$. Así, las variables se definen de la siguiente manera:

$x_{ij}$ = número de computadoras a transportar del almacén $i$ al destino $j$. $i \in \{A, B, C\}, j \in \{X, Y\}$.

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 almacén a una tienda).

Función objetivo

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 almacén $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 portátil. Todas las computadoras que salgan del almacén $A$ tendrán entonces un costo de $35x_{AX}+44x_{AY}$. Si calculamos de manera similar el costo de las computadoras que se salen de los almacenes $B$ y $C$ obtenemos el total. Entonces la función objetivo será la siguiente expresión:

$$Min \quad z = 35x_{AX}+44x_{AY}+40x_{BX}+37x_{BY}+42x_{CX}+45x_{CY}.$$

Restricciones

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 almacén. Por ejemplo, para no exceder las $200$ unidades que se tienen disponibles en el almacén $A$, se debe cumplir que $x_{AX}+x_{AY}\leq 200$. De manera similar, con el almacén $B$ obtenemos que $x_{BX}+x_{BY}\leq 350$ y con el almacén $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. Entonces, para la tienda $X$ se tiene que cumplir $x_{AX}+x_{BX}+x_{CX}\geq 300$ y para la tienda $Y$ se tiene que cumplir $x_{AY}+x_{BY}+x_{CY}\geq 500$.

Entonces, juntando todas las restricciones, tenemos:

\begin{align*}
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_{ij} \in \mathbb N, i \in \{A, B, C\}, j \in \{X, Y\}\\
\end{align*}

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_{ij} \in \mathbb N, i \in \{A, B, C\}, j \in \{X, Y\}\\
\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.

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

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.
¿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.
Imagina que en el ejemplo que planteamos de computadoras portátiles, almacenes y tiendas sucede que el precio de transportar una computadora portátil es de \$30 sin importar el almacén 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?
Se presenta la siguiente situación:

Una empresa coreana fabrica y luego distribuye sus pantallas a diferentes vendedores. En este momentos tienen pantallas de 4 diferentes tamaños: 43″, 50″, 55″ y 65″. Los países a donde distribuyen sus productos son Japón, China y Estados Unidos. En la siguiente tabla se muestra el costo de exportación en miles de dólares por cada 1000 televisores de cada modelo.

	43″	50″	55″	65″	Demanda este año
Japón	\$50k	\$60k	\$65k	\$70k	100k
China	\$60k	\$70k	\$75k	\$80k	300k
Estados Unidos	\$80k	\$90k	\$95k	\$100k	350k
Disponibilidad	250k	220k	180k	150k	——

También se señaló en la tabla anterior cual es la demanda de cada país para este año y las pantallas que fueron fabricadas este año por cada modelo.

Plantea este problema como un problema del transporte como se hizo anteriormente.

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?

Respuestas

1.- (Respuesta a criterio del lector)

2.- Si la demanda supera a la oferta, por lo menos uno de los destinos del problema va a cumplir que $\sum_{i=1}^{m}x_{ij} < d_j$, por lo que no cumplirá una de las restricciones de nuestro problema y el problema ya no será factible.

3.- En este caso, sería indistinto de donde elijamos enviar nuestras computadoras con tal de que se satisfaga la demanda, y solamente se parará de enviar computadoras cuando se satisfaga esta demanda de 800 computadoras, que en cualquier caso nos dará un costo total de envío de $24000.

4.- Nuestra variable de decisión va a ser la siguiente: $x_{ij}$ = miles de televisores del tamaño $i$ que van a ser exportados al país $j$, $i \in \{1 (\textrm{43″}), 2 (\textrm{50″}), 3 (\textrm{55″}), 4 (\textrm{65″})\}$, $j \in \{1 (\textrm{Japón}), 2 (\textrm{China}), 3 (\textrm{Estados Unidos})\}$

Si seguimos los pasos como lo hemos venido haciendo, el problema debería quedar planteado de la siguiente manera:

\begin{align*}
Min \quad z = &50x_{11} + 60 x_{12} + 80x{13} + 60 x_{21} + 70 x_{22} + 90x_{23}\\
+ &65x_{31} + 75x_{32} + 95x_{33} + 70x_{41} + 80x_{42} + 100x_{43}\\
&s.a\\
&x_{11} + x_{21} + x_{31} + x_{41} \geq 100\\
&x_{12} + x_{22} + x_{32} + x_{42} \geq 300\\
&x_{13} + x_{23} + x_{33} + x_{43} \geq 350\\
&x_{11} + x_{12} + x_{13} \leq 250\\
&x_{21} + x_{22} + x_{23} \leq 220\\
&x_{31} + x_{32} + x_{33} \leq 180\\
&x_{41} + x_{42} + x_{43} \leq 150\\
&x_{ij} \in \mathbb{N}\\
\end{align*}

5.- Como solamente habría un destino, la variable de decisión sería la siguiente:
$x_i$ = unidades de producto que vamos a enviar del origen $i$ a nuestro destino, $i \in \{1, \ldots, m\}$

Sea $d$ la demanda de nuestro único destino.

El planteamiento general sería el siguiente:

\begin{align*}
Min \quad z &= \sum_{i=1}^{m} c_{i}x_{i}\\
s.a.&\\
x_i &\leq o_i, \quad i \in \{1, \ldots , m\}\\
\sum_{i=1}^{m}x_i &\geq d\\
x_i &\geq 0 \quad i \in \{1, \ldots , m\}\\
\end{align*}

Una buena estrategia para resolver el problema simplemente sería ir agotando las unidades que nos puede proporcionar cada origen empezando por los que nos dan el menor costo de transporte por unidad, y parar justo cuando se haya cumplido la demanda de este único destino.

Entradas relacionadas

Ir a Investigación de Operaciones
Entrada anterior del curso: El problema de la mochila
Entrada siguiente del curso: El problema de producción e inventario

Investigación de Operaciones: El problema de la mochila

Por Aldo Romero

Deja un comentario

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

Cesar es un fabricante de botanas que vende 3 de sus productos a varios distribuidores dentro de su localidad. Cada caja de sus productos tiene un peso diferente y generan diferentes ganancias al ser vendidas. Esta información está reflejada en la siguiente tabla:

—	Peso por caja en kilogramos	Ganancia en pesos por caja vendida
Producto 1	10	150
Producto 2	12	200
Producto 3	15	300

Cesar tiene una camioneta que aguanta hasta 800 kilos de carga sin contar al conductor. Cesar quiere saber cuales son los productos que debe llevar con tal de maximizar sus ganancias.

Variables de decisión

Nuestra variable de decisión es bastante intuitiva.

$x_i$ = número de cajas del producto $i$ que Cesar va a llevar en su camioneta. $i \in \{1, 2, 3\}$

Función objetivo

Como el objetivo de Cesar es maximizar las ganancias, la función objetivo va a ser:

$$Max \quad z = 150x_1 + 200x_2 + 300x_3$$

Restricciones

En este problema, la única condición que nos dan es que el peso total de las cajas a llevar no exceda la capacidad de carga de la camioneta. Es decir:

\begin{align*}
10x_1 + 12x_2 + 15x_3 \leq 800\\
x_i \geq 0, i \in \{1, 2, 3\}\\
\end{align*}

Resumen

El PPL que obtenemos es en resumen:

\begin{align*}
Max \quad z= 150x_1&+ 200x_2 + 300x_3\\
s.a.&\\
10x_1&+12x_2+15x_3 \leq 800\\
x_i& \geq 0,i \in \{1, 2, 3\}\\
\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.

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 distribuir 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

Imagina el siguiente escenario:
Cesar ahora solo vende los productos 1 y 2. El producto 1 ahora pesa 8 kilogramos y el producto 2 ahora pesa 10 kilogramos, que el primero de ellos da una ganancia de \$120 y que el segundo da una ganancia de \$155. El vehículo que tenemos ahora es un coche que sólo puede cargar 392 kilogramos. ¿Cómo cargarías en este caso el coche para maximizar las ganancias? 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 7 posibles artículos con pesos de 7, 10, 12, 4, 5, 9, 11 kilos y con valor de 23, 25, 28, 17, 19, 25, 26 respectivamente. Sólo podemos decidir si llevar o no llevar cada artículo, y el peso total que se cargará no puede exceder 40 kilos. ¿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 original de esta entrada de blog. ¿Qué pasaría con la respuesta del problema si ocurrieran los siguientes escenarios? ¿Las ganancias aumentarán o disminuirán?
- Cesar compró una mejor camioneta, que ahora puede transportar 1.5 toneladas.
- El producto 3 se volvió más caro y ahora Cesar solo gana 250 pesos por caja vendida.
- El tipo de envoltura y material de la caja cambio, por lo que ahora los pesos de los productos son 12, 17, 25 kilos para los productos 1, 2 y 3 respectivamente.

Respuestas

1.- Podríamos calcular cual es el producto que nos da más ganancias por kilo con una simple división. El producto 1 nos da 120/8 = 15 pesos por kilo del producto y el producto 2 nos da 155/10 = 15.5 pesos por kilo. El producto 2 es el que más ganancias nos va a dar por lo que vamos a llenar el carro con la mayor cantidad de productos 1 que se pueda.
Lo máximo que podemos meter dentro del carro son 39 unidades del producto 2, teniendo una ganancia de 6045 pesos, pero nos sobrarían 2 kilos para llegar al límite de peso. Entonces vamos a tratar de considerar las opciones donde incluyamos algunas unidades del producto 1 y a ver si podemos mejoran las ganancias.
Si tomamos 38 unidades del producto 2, nos quedan 12 kilos de capacidad y solamente podemos solamente agregar una unidad del producto 1, teniendo en total una ganancia de 6010 pesos. Esta opción no mejora las ganancias.
Si tomamos 37 unidades del producto 2 nos quedan 22 kilos de capacidad y solamente podemos agregar dos unidades del producto 1, teniendo una ganancia de 5975 pesos. Esta opción tampoco mejora las ganancias.
Ahora, si tomamos 36 unidades del producto 2, nos quedan 32 kilos de capacidad y ahora podemos agregar 4 unidades del producto 1, teniendo ahora una ganancia de 6060 pesos. En este caso SI conseguimos una mejora en nuestras ganancias.
Y si somos observadores, nos daremos cuenta que si seguimos agregando unidades del producto 1, ahora las ganancias solo van a ir disminuyendo, por lo que nos quedaremos con esta última solución para nuestro problema.

2.- La variable de decisión sería como el visto en esta entrada, con la siguiente variante: $x_i$ = 1 si el articulo i se va a llevar o 0 si el articulo i no se va a llevar.

La función objetivo simplemente va a ser la que maximice el valor total de los artículos a llevar:

$$Max z = 23x_1 + 25x_2 + 28x_3 + 17x_4 + 19x_5 + 25x_6 + 26x_7$$

Y la única restricción es:

$$7x_1 + 10x_2 + 12x_3 + 4x_4 + 5x_5 + 9x_6 + 11x_7 \leq 40$$

Entonces, el problema planteado sería:

\begin{align*}
Max z = &23x_1 + 25x_2 + 28x_3 + 17x_4 + 19x_5 + 25x_6 + 26x_7\\
&s.a\\
&7x_1 + 10x_2 + 12x_3 + 4x_4 + 5x_5 + 9x_6 + 11x_7 \leq 40\\
&x_i \geq 0, i \in {1, \ldots, 7}\\
\end{align*}

Y el modo de resolverlo es muy similar al anterior, solo hay que considerar los cocientes de los artículos que dan más valor por cada kilo que pesan, tomar los mejores y si sobra capacidad de peso, probar combinaciones de tal manera que el se elimine esa capacidad restante y evaluar si el valor sube en efecto o hasta baja.

3.- $\bullet$ La solución va a ser similar a el problema 1, se va a llenar la camioneta con el producto que ofrezca la mayor ganancia/kilo (el producto 3) y si sobra capacidad de carga se va a intentar introducir algunos los productos de menor peso, hasta encontrar la solución que nos de las mayores ganancias. La diferencia solo va a ser en el número de unidades que van a entrar en la camioneta y por tanto, la solución aunque sea análoga, va a ser diferente.

$\bullet$ Como la ganancia del producto de mayor ganancia/kilo cambió, ahora hay que comparar este nuevo valor con el de los otros productos y nos daremos cuenta que ahora tendremos la misma ganancia/kilo entre este producto y el producto número 2, entonces lo que se intentará es llenar la camioneta entre estos dos productos de tal manera que no quede capacidad de carga sobrante.

$\bullet$ Hay que calcular la nueva ganancia/kilo de cada producto y resulta ahora que al cambiar los pesos de las cajas, el producto 1 es el que mayor ganancia/kilo tiene, entonces vamos a tratar de incluir la mayor cantidad de unidades de este producto que sea posible y si sobra capacidad tratar de combinar con algunas unidades de los otros productos con tal de tener la ganancia más grande.

Entradas relacionadas

Ir a Investigación de Operaciones
Entrada anterior del curso: El problema de la dieta
Entrada siguiente del curso: El problema del transporte

Investigación de Operaciones: El problema de la dieta

Por Aldo Romero

Deja un comentario

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

Consideremos el siguiente problema:

Un estudiante de la facultad de ciencias asiste a clases los 5 días de la semana. En su hora de comida tiene 3 opciones preferidas: Ir al comedor, comprar una torta o comprar unos tacos de canasta. Cada opción tiene un aporte nutritivo distinto que está representado en la siguiente tabla, así como el costo por merienda de cada opción

	Costo por merienda en pesos	Contenido nutritivo por unidad de alimento
	Costo por merienda en pesos	N1	N2
Comedor	$35	14	10
Torta	$28	10	7
Tacos de canasta	$20	6	4
Necesidades de nutrición a la semana		45	35

El estudiante busca cumplir sus necesidades nutricionales semanales y aparte gastar lo menos posible ya que la beca no da para tanto tristemente. Plantea como un problema de programación lineal.

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

Sea $x_1$ las meriendas en el comedor por semana, $x_2$ las meriendas con torta por semana y $x_3$ las meriendas con tacos de canasta. En la tabla nos indican los costos de estas por lo que ya tenemos nuestra función objetivo a minimizar:

$Min \quad z = 35x_1 + 28x_2 + 20x_3$

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

(Merienda 1: cantidad de nutriente 1)(Meriendas 1 por semana) +
(Merienda 2: cantidad de nutriente 1)(Meriendas 2 por semana) +
(Merienda 3: cantidad de nutriente 1)(Meriendas 3 por semana) $\geq$
Nutriente 1 requerido

(Merienda 1: cantidad de nutriente 2)(Meriendas 1 por semana) +
(Merienda 2: cantidad de nutriente 2)(Meriendas 2 por semana) +
(Merienda 3: cantidad de nutriente 2)(Meriendas 3 por semana) $\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 \geq b_1\\
&a_{1,2}x_1 + a_{2,2}x_2 + a_{3,2}x_3 \geq b_2\\
\end{align*}

Y usando los valores de el problema, tenemos:

\begin{align*}
&14x_1 + 10x_2 + 6x_3 \geq 45\\
&10x_1 + 7x_2 + 4x_3 \geq 35\\
\end{align*}

Y por último solo cabe mencionar que las meriendas del 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 = 35&x_1 + 28x_2 + 20x_3\\
s.a&\\
14&x_1 + 10x_2 + 6x_3 \geq 45\\
10&x_1 + 7x_2 + 4x_3 \geq 35\\
&x_1, x_2, x_3 \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

¡Oh no! La inflación llegó y el precio de las meriendas mencionadas subió un $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 más sencillo. Sólo se pueden elegir entre tortas y tacos. Cuestan \$30 las tortas y \$20 los tacos. La torta da 12 unidades de N1 y 8 de N2. Los tacos dan 9 unidades de N1 y 6 de N2. Imagina que se deben consumir 50 unidades de N1 y 35 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 plan de meriendas semanal 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.

Respuestas

$\bullet$ \begin{align*}
Min \quad z = 38.5&x_1 + 30.8x_2 + 22x_3\\
s.a&\\
14&x_1 + 10x_2 + 6x_3 \geq 45\\
10&x_1 + 7x_2 + 4x_3 \geq 35\\
&x_1, x_2, x_3 \geq 0\\
\end{align*}

$\bullet$ Nuestra variable de decisión es la siguiente:

$x_i$ = Se hace el tipo de inversión $i$ con $i \in \{1, 2, 3, 4\}$, $x_i \in \{0, 1\}$

Observemos que si se hace el tipo de inversión $i$, las ganancias son: valor presente neto – costo de la inversión. Como eventualmente lo que se busca es maximizar las ganancias, nuestra función objetivo sería la siguiente:

$$Max \quad z = 2000x_1 + 5000x_2 + 4000x_3 + 3000x_4$$

La única restricción es el presupuesto con el que se cuenta para realizar las inversiones. Entonces, la restricción será:

$$12,000x_1 + 20,000x_2 + 16,000x_3 + 15,000x_4 \leq 50,000$$

Y como las variables solo toman valor 0 o 1, también se satisface la no negatividad.

Entonces, el problema quedaría planteado de la siguiente forma:

\begin{align*}
Max \quad z = &2000x_1 + 5000x_2 + 4000x_3 + 3000x_4\\
&s.a\\
&12,000x_1 + 20,000x_2 + 16,000x_3 + 15,000x_4 \leq 50,000\\
&x_1 \in {0, 1}, i \in {1, 2, 3, 4}\\
\end{align*}

$bullet$ El cambio es muy simple, solo hay que cambiar las variables de decisión a $x_1$ las meriendas con torta por semana y $x_2$ las meriendas con tacos de canasta por semana. Entonces, con los cambios aplicados:

\begin{align*}
Min \quad z = 30&x_1 + 20x_2\\
s.a&\\
12&x_1 + 9x_2 \geq 50\\
8&x_1 + 6x_2 \geq 35\\
&x_1, x_2 \geq 0\\
\end{align*}

$bullet$ Una idea sería considerar solamente todos los valores posibles a elegir en la semana, revisar que cumplan con las necesidades de nutrición y calcular el gasto que conllevaría cada plan. Vamos a representar esos resultados en la siguiente tabla:

Combinación alimentaria	N1 $\geq$ 50	N2 \geq 35	Costo del plan
5 días torta	60	45	150
4 días torta, 1 día taco	56	42	140
3 días torta, 2 días tacos	52	39
2 días torta, 3 días tacos	48	36
1 día torta, 4 días tacos	44	33	110
5 días tacos	40	30	100

Las filas que tienen una casilla roja no cumplen la necesidad nutricional de su respectiva columna.

Entonces, nuestra solución va a ser el plan de alimentación que tenga el menor costo y que tenga las dos casillas de necesidades nutricionales en verde. Esta solución es la de combinar 3 días con merienda de torta y dos días con merienda de tacos de canasta.

$\bullet$ Podría tal vez argumentarse es que la finalidad de resolver este tipo de problema es economizar los gastos de el o los individuos, entonces al tomar planes de dieta más caros, estamos haciendo lo opuesto a lo propuesto por la función objetivo.

Texto de la cabecera

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

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

Por Aldo Romero

Deja un comentario

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

Ve el siguiente video de acerca de George Dantzig. ¿Que te pareció la anécdota de su tiempo de estudiante?

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í.»
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?

Entradas relacionadas

Ir a Investigación de Operaciones
Entrada siguiente del curso: El problema de la dieta