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 almacen 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 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
- 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 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?
- 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éxico | Guadalajara | Tijuana | |
Coatepec | 5 | 6 | 3 |
Orizaba | 3 | 5 | 4 |
- 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
- 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