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