EL PROBLEMA DE TRANSPORTE POR EL CRITERIO DEL COSTO: SOLUCIÓN A TRAVÉS DE MATHCAD

TRANSPORTATION PROBLEM BY THE CRITERIA OF COST: SOLUTION THROUGH MATHCAD

RESUMEN

Los métodos de Programación Lineal encuentran cada vez mayor atención en la economía, la tecnología, el ámbito militar y en otras aplicaciones. El crecimiento exponencial de las computadoras ha permitido un amplio desarrollo de esta especialidad matemática, dando solución a problemas que eran imposibles de resolver en décadas pasadas. Entre las aplicaciones de la Programación Lineal se destaca el denominado Problema de Transporte, que constituye el tema del presente artículo, mostrando destacados avances tecnológicos. Su objetivo radica en el diseño de un modelo matemático (basado en la programación lineal) el cual permite la distribución de un determinado producto (en nuestro caso arena para construcción) de forma óptima y con el mínimo costo.

Palabras claves: El Problema de Transporte, Método Simplex, Programación Lineal

ABSTRACT

Linear Programming methods find increasing attention in economics, technology, the military, and other applications. The exponential growth of computers has allowed a broad development of this mathematical specialty, providing solutions to problems that were impossible to solve in past decades. Among the applications of Linear Programming, the so-called Transportation Problem stands out, which is the subject of this article, showing outstanding technological advances. Its objective lies in the design of a mathematical model (based on linear programming) which allows the distribution of a certain product (in our case construction sand) in an optimal way and with the minimum cost.

Keywords: Linear Programming, Simplex Method, Transportation Problem.

INTRODUCCIÓN

La Programación Lineal, (también llamada Rendimiento Máximo Lineal) es una técnica matemática y de investigación de operaciones que se utiliza en la planificación administrativa y económica para maximizar o minimizar las funciones lineales de un gran número de variables sujetas a determinadas restricciones (Garvin, 2005). El desarrollo de computadoras electrónicas y de técnicas de procesamiento de alta velocidad ha aportado recientemente muchos avances a la Programación Lineal, de forma que ahora esta técnica se utiliza extensamente en operaciones industriales, científicas, tecnológicas y militares (Charnes, Abrahany Cooper, 1961).

Su desarrollo está íntimamente ligado a la toma de decisiones de tipo administrativo, convirtiéndose en una de las técnicas más ampliamente usadas a nivel internacional.

Estos procedimientos eran conocidos desde principios del siglo XIX, pero debido a la gran cantidad de variables y restricciones que se presentaban para el cálculo de la solución de determinados problemas, no era técnicamente posible resolverlos por la enorme cantidad de operaciones que era necesario desarrollar.

Fue en la cuarta década del siglo XX, cuando están disponibles las primeras grandes computadoras electrónicas, entre las que podemos citar la Electronic Numerical Integrator And Computer (ENIAC) que esta ciencia (la programación lineal) comienza su pleno desarrollo, manteniéndose de forma permanente hasta la actualidad (Hollingdale, (2007).

En los últimos años de la Segunda Guerra Mundial, (1944-1945) las técnicas de Programación Lineal, fueron utilizadas fundamentalmente en el traslado de mercancías y pertrechos de guerra por vía marítima (Dantzig, 1963).

En Cuba, la Programación Lineal, comienza su desarrollo en los primeros años de la Revolución Cubana, fue en 1959 cuando el comandante Ernesto Guevara, por esa época Ministro de Industrias, (1961) el que propició la divulgación de esta técnica, impartiendo conferencias a directores de empresas del citado ministerio, en más de una ocasión señaló que “para dominar la ciencia económica hay que saber matemáticas, en especial la Programación Lineal” (Periódico Granma).

Se evidencia la importancia de la utilización de la programación lineal según lo planteado en un informe de la Organización para la Alimentación y la Agricultura F.A.O. (feb. 2017) cuando expresa que: “Se ha estimado, de una manera general, que, si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15 % en tan sólo un año”.

Teniendo presente lo argumentado por la F.A.O. en nuestro país desde la década de los años 70 se desarrollan modelos matemáticos que aplican la programación lineal en ramas tan diversas como la agricultura, comercio, minería y otras especialidades. Por último, debemos destacar que antes de 1947 era inconcebible pensar en la existencia de una herramienta como la programación lineal que permitiese examinar millones de combinaciones.

Y es precisamente uno de los clásicos problemas de la programación lineal, “El problema de transporte” que servirá de ejemplo demostrativo en el presente artículo que tiene como objetivo: diseñar un modelo matemático (basado en la programación lineal) el cual permite la distribución de un determinado producto (en nuestro caso arena para construcción) de forma óptima y con el mínimo costo. Debemos destacar que antes de 1947 era inconcebible pensar en la existencia de una herramienta como la programación lineal que permitiese examinar millones de combinaciones.

DESARROLLO

Apuntes históricos de la Programación Lineal

En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilliy sobre todo, Lagrange, que tanto habían contribuido al desarrollo del Cálculo Infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones.

Posteriormente el matemático francés Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en percatarse, aunque de forma imprecisa, de los métodos de lo que actualmente llamamos Programación Lineal y la potencialidad que de ellos se deriva.

Fue el matemático Gaspar Monge (Francia, 1746-1818), quien en 1776 se interesó por problemas de este género. Pero debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual Programación Lineal (Cajori, 1909).

Por esa época el matemático ruso Leonid V. Kantorovitch (1912-1986) publicó una extensa monografía titulada “Métodos matemáticos de organización y planificación de la producción” en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal (Barsov, 1988).

En 1941-1942 se fórmula por primera vez el Problema de Transporte, (bajo consideraciones teóricas) en correspondencia con las necesidades bélicas relacionadas con la Segunda Guerra Mundial.

Paralelamente a los hechos descritos se desarrollan en los Estados Unidos, las técnicas de computación y los primeros grandes ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando. No es accidental que la Programación Lineal y el computador electrónico se hayan desarrollado al mismo tiempo en la década de los 50.

En 1947, el matemático norteamericano George Dantzig (1914-2005) fórmula, en términos matemáticos muy precisos, el enunciado al que cabe reducir todo problema de programación lineal, creando el Método Simplex, apoyado con ordenadores de la firma International Business Machines (IBM). En relación a las aplicaciones técnicas e industriales de la programación lineal, debemos destacar los aportes de los matemáticos Abrahan Charnesy Williams W. Cooper realizados en la década de los años cincuenta del siglo XX, en especial la creación del método clásico del problema de transporte definiéndolo como: La distribución de cualquier mercancía desde cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se minimicen los costos totales de distribución, que apareció por vez primera en el artículo “The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems -1954- “Este procedimiento permite que una persona que no conozca los métodos generales de la Programación Lineal pueda resolver este tipo de problema (Charnes y Cooper, 1961).

El primer gran ensayo demostrativo para probar la efectividad del Método Simplex aplicado al Modelo de Transporte, fue realizado en el estado de California por la compañía Creole Petroleum (Año 1955), el mismo consistía en la transportación de gasolina en camiones cisternas de diversos tonelajes desde 25 centros de distribución (Orígenes) hacia 115 estaciones de servicio, (Destinos) demostrando con relación a la distribución que se realizaba sistemáticamente, un significativo ahorro monetario por concepto de transportación (Simmonard, 1972).

Es necesario puntualizar una vez más que la obtención de la información para llegar a confeccionar la tabla de datos en múltiples ocasiones es una tarea verdaderamente compleja que requiere la participación de un grupo multidisciplinario. Llegado a este punto la parte computacional no ofrece mayores dificultades (Simmonard, 1972) (Garfinkel, 2003).

Formulación del modelo matemático

Vamos a representar con todo detalle un ejemplo clásico del Problema de Transporte desarrollado en Mathcad (Mathcad, software matemático de amplia utilización internacional).

El PROBLEMA: Hallar el plan de transporte óptimo de arena de construcción desde tres puntos de partida (Orígenes O₁, O₂, O₃) hasta cuatro puntos de llegada (Destinos D₁, D₂, D₃, D₄) para las condiciones definidas en la siguiente tabla.

Aquí representamos los costos de transportación, por ejemplo, para trasladar una tonelada de arena desde el origen O₁ hacia el destino D₁ se establece un costo de $ 72.00 y así sucesivamente.

La columna oferta, representa las disponibilidades en toneladas de arena, las filas demanda muestran las cantidades que se deben recibir. Las variables representadas por x₁….x₁₂ (x_i ≥ 0, i = 1, 2, 3,.. 12) en la tabla No. 2, se indican las toneladas de transportación, que serán calculadas al correr el programa.

Para ofrecer una situación real hemos seleccionado en la provincia de Ciego de Ávila, Cuba la ejemplificación del problema, como se puede observar en el gráfico esquemático adjunto (Fig. No. 2) las areneras están representadas mediante círculos y las obras en forma de rombos, las distancias en kilómetros, también se muestra el tonelaje de transportación y demanda asignada.

La estructura matemática está definida en forma matricial.

Matriz de los Costos:

Costos = \ \left( \begin{matrix} 72 & 198 & 196 \\ \end{matrix}\ \ \ \ \begin{matrix} 144 & 122 & 104 \\ \end{matrix}\ \ \ \ \begin{matrix} 102 & 142 & 142 \\ \end{matrix}\ \ \ \ \begin{matrix} 124 & 18 & 68 \\ \end{matrix}\ \right)

Matriz con oferta-demanda:

Totales = \left( \begin{matrix} 30 & 45 & 25 \\ \end{matrix}\ \ \ \ \begin{matrix} 25 & 15 & 40\ \ \ \ 20 \\ \end{matrix} \right)

De la tabla No. 1 tenemos que:

Cantidad de filas ► Filas = 3

Cantidad de columnas col = \frac{cols(Costos)}{Filas} = 4

CT = {Costos}^{\ T}

Función objetivo:

c(x) = \sum_{j = 1}^{Filas\ .\ \ col}\left( {CT}_{j}\ .\ \ x_{j} \right)

Equilibrio entre Orígenes y Destinos

\sum_{}^{}(Orig) = \sum_{}^{}(Dest)

Esto quiere decir, que la oferta total es igual a la demanda total.

En el caso que no se cumpla la identidad \sum_{}^{}(Orig) > \sum_{}^{}(Dest) se incorporaría un centro (ficticio) de Destino adicional al problema (Luenberger, 1965).

En el ejemplo:

\ Orig = \sum_{K = 1}^{Filas}{\left( {Totales}^{\ T} \right)_{K} = 100}

Dest = \sum_{K = Filas + \ 1}^{Filas + \ col}{\left( {Totales\ }^{T} \right)_{K} = 100}

Como se puede apreciar en la Tabla No. 1, podemos definir las siguientes igualdades.

Por filas:

x_{1} + x_{2} + x_{3} + x_{4} = 30

x_{5} + x_{6} + x_{7} + x_{8} = 45

x_{9} + x_{10} + x_{11} + x_{12} = 25

Por columnas:

x_{1} + x_{5} + x_{9} = 25

x_{2} + x_{5} + x_{10} = 15

x_{3} + x_{7} + x_{11} = 40

x_{4} + x_{8} + x_{12} = 20

Estructura Matricial

M = \left( \begin{matrix} \begin{matrix} 1 & 1 & 1 \\ \end{matrix}\ \ \ \ \begin{matrix} 1 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix} \\ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \ \begin{matrix} 0 & 1 & 1 \\ \end{matrix}\ \ \ \begin{matrix} 1 & 1 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix} \\ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 1 \\ \end{matrix}\ \ \ \ \begin{matrix} 1 & 1 & 1 \\ \end{matrix} \\ \begin{matrix} 1 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 1 & 0 \\ \end{matrix}\ \ \ \ \begin{matrix} 0 & 0 & 1 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix} \\ \begin{matrix} 0 & 1 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 1 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \ \begin{matrix} 1 & 0 & 0 \\ \end{matrix} \\ \begin{matrix} 0 & 0 & 1 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 1 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 1 & 0 \\ \end{matrix} \\ \begin{matrix} 0 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 1 & 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 1 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0 & 0 & 1 \\ \end{matrix} \\ \end{matrix}\ \ \right) x = \ \begin{pmatrix} \begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{matrix} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ x_{10} \\ x_{11} \\ x_{12} \\ \end{pmatrix}

M\ .\ x = \begin{pmatrix} x_{1} + x_{2} + x_{3} + x_{4} \\ x_{5} + x_{6} + x_{7} + x_{8} \\ x_{9} + x_{10} + x_{11} + x_{12} \\ x_{1} + x_{5} + x_{9} \\ x_{2} + x_{6} + x_{10} \\ x_{3} + x_{7} + x_{11} \\ x_{4} + x_{8} + x_{12} \\ \end{pmatrix}

M\ .\ x = {Totales}^{\ T}

\begin{pmatrix} x_{1} + x_{2} + x_{3} + x_{4} \\ x_{5} + x_{6} + x_{7} + x_{8} \\ x_{9} + x_{10} + x_{11} + x_{12} \\ x_{1} + x_{5} + x_{9} \\ x_{2} + x_{6} + x_{10} \\ x_{3} + x_{7} + x_{11} \\ x_{4} + x_{8} + x_{12} \\ \end{pmatrix} = \begin{pmatrix} \begin{matrix} 30 \\ 45 \\ 25 \\ \end{matrix} \\ 25 \\ 15 \\ 40 \\ 20 \\ \end{pmatrix}

Las anteriores igualdades representan las restricciones del problema.

La matriz M, compuesta por 7 filas y 12 columnas, tiene por elementos 0 y 1. En forma general cualquier problema de Transporte con las características del ejemplo tendrá la misma matriz M.

Estructura de cálculo en MathCad

f = Filas\ .\ col

x_{f} = 0

Given

M\ .\ x = {Totales}^{\ T}

x \geq 0

Minimize\ (c,x) = \begin{pmatrix} \begin{matrix} 25 \\ 0 \\ 0 \\ \end{matrix} \\ 5 \\ 0 \\ 15 \\ 15 \\ 15 \\ 0 \\ 0 \\ 25 \\ 0 \\ \end{pmatrix}\begin{pmatrix} \begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{matrix} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ x_{10} \\ x_{11} \\ x_{12} \\ \end{pmatrix}\begin{pmatrix} \begin{matrix} 25 \\ 0 \\ 0 \\ \end{matrix} \\ 5 \\ 0 \\ 15 \\ 15 \\ 15 \\ 0 \\ 0 \\ 25 \\ 0 \\ \end{pmatrix}

Llegamos a la solución buscada, utilizando la función Minimize. Incorporando los resultados en la Tabla No. 1, conformamos la Tabla No. 3 que determina el tonelaje de transportación.

La tabla No. 3 nos indica que se deben transportar desde la arenera No.1, (Chambas) 25 toneladas hacia la obra 1 (Morón) y 5 toneladas a la obra 4. (Violeta) Y así en forma sucesiva como se muestra en la tabla.

Completando de este modo la distribución, equivalente a 100 toneladas.

El costo Óptimo es:

Costo = \sum_{i = 1}^{f}{\left( CT_{i}\ .\ \ x_{i} \right) = 8190}

El costo es igual al costo unitario multiplicado por el número de unidades distribuidas. En el ejemplo $8190.00 representa el costo (mínimo) de transporte.

Nota: Es posible calcular el Costo, aplicando Producto Escalar (implementado en Mathcad) del siguiente modo:

CT^{\ T}.\ \ x = 8190

Como se ha podido observar durante el desarrollo del problema, el procedimiento presenta un acentuado grado de complejidad, pero esto es debido a que, aunque las restricciones sean lineales el hecho de que no se pueden admitir valores negativos (x ≥ 0) de las variables, significa que no se pueden emplear los métodos usuales de resolución de los conjuntos de ecuaciones lineales (Forsythe, 2012).

Debemos puntualizar que la solución mostrada en la tabla No. 3, representa el modo óptimo de transportación, cualquier otra distribución, genera mayor costo, para lo cual se requiere establecer la logística necesaria referente a la flota de camiones que deben estar disponibles en el momento de la distribución de la arena.

La modelación del transporte de carga conlleva la dificultad de buscar técnicas matemáticas para representar adecuadamente a los múltiples factores que determinan los flujos de carga, y sus distintos objetivos, cuando todos estos actores tratan de optimizar sus propios criterios de desempeño simultáneamente, incluso cuando estos objetivos se contrapongan.

CONCLUSIONES

En la solución al Problema del Transporte, se ha utilizado MathCad, pero debemos señalar que en la actualidad existen considerables softwares que permiten llegar a recursos similares a los encontrados. El motivo de seleccionar MathCad fue ante todo para mostrar paso a paso el procedimiento algebraico-matricial que permite llegar a la solución final, pues esta característica no aparece en otros programas. El crecimiento exponencial de las computadoras ha permitido un amplio desarrollo de esta especialidad matemática, dando solución a problemas que eran imposibles de resolver.

REFERENCIAS BIBLIOGRÁFICAS