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

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

5. 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

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?

2. 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í.»
3. 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

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