problema de transporte

V Congreso de Ingeniería de Organización
Valladolid-Burgos, 4-5 Septiembre 2003

ƒ Índice

Nuevos Algoritmos en el Problema de Transporte

1
1 Doctor Ingeniero Industrial, Departamento Organización de Empresas. E.U.I.T.I.-San Sebastián-UPV. Correo-
e: oeploruf@sc.ehu.es

2
Ingeniero de Organización Industrial, Departamento Organización de Empresas. E.U.I.T.I.-San Sebastián-UPV. Correo-e: oeparlag@sc.ehu.es

RESUMEN
Una vez formulado el modelo matemático del problema de transporte, el siguiente paso es
resolver el modelo, es decir, obtener los mejores valores numéricos para las variables de decisión.
La forma en que se obtengan estos valores depende del tipo específico del modelo matemáticoutilizado. Por tanto, una vez definido el modelo, se podrá elegir un método apropiado para
resolverlo. En el problema de transporte, estos métodos pertenecen a una de estas dos categorías:
1.-Métodos óptimos, que permiten obtener los mejores valores para las variables de decisión, es
decir, aquellos valores que satisfacen simultáneamente todas las restricciones y proporcionan el
mejor valor para la función objetivo.2.-Métodos heurísticos, que permiten obtener valores para las variables de decisión que
satisfacen todas las restricciones. Aunque no necesariamente óptimos, estos valores proporcionan
un valor aceptable para la función objetivo.
En comparación con los métodos óptimos, los métodos heurísticos son computacionalmente más
eficientes y, por tanto, se utilizan cuando la obtención de soluciones óptimas conlleva excesivotiempo o bien es imposible por ser el modelo matemático demasiado complejo. Este artículo
aporta tres nuevos algoritmos para la obtención de soluciones iniciales, basados en los métodos
heurísticos.
Palabras clave: Programación Lineal. Problema del transporte. Algoritmo de Transporte. Métodos
de obtención de una solución inicial. Algoritmo de optimización y mejora.


1. Introducción al problema de transporteUna de las aplicaciones más interesantes de los problemas de programación lineal es el
llamado problema de transporte, que resulta ser un modelo lineal que presenta una estructura
especial. Este problema fue planteado y resuelto por F. L. Hitchcock[1] con anterioridad a la
formulación del concepto general de la programación lineal, siendo debido a G. B. Dantzig[2]la aplicación de la programación lineal a la resolución del problema de transporte mediante el
método general del Simplex.

Los métodos de resolución de este problema pertenece a la clase de los llamados modelos
combinatorios que presentan una gran complejidad computacional y ofrecen un número muy
grande de posibles soluciones, siendo por ello necesario buscar otro tipo de métodos de
solución.V Congreso de Ingeniería de Organización
Valladolid-Burgos, 4-5 Septiembre 2003

En consecuencia, los esfuerzos referentes a la búsqueda de métodos diferentes de resolución
se han dirigido en un primer enfoque hacia los métodos que están basados en la utilización de
algoritmos matemáticos, es decir, que permiten obtener una solución óptima exacta para elproblema combinatorio, mediante la utilización de técnicas que permitan reducir la búsqueda
de soluciones (p.e. el método del Simplex, para la Programación Lineal).

Alternativamente, se han propuesto determinados métodos heurísticos que carecen de una
base matemática formal y que están basados en la intuición. Sin embargo, permiten obtener
una solución inicial próxima a la solución óptima con la ventaja de obtener ahorrosconsiderables en tiempo respecto a los métodos basados en algoritmos matemáticos, por lo
que estos últimos métodos no resultan ser apropiados para su utilización en problemas de gran
tamaño.

Cada una de estas alternativas (métodos basados en algoritmos matemáticos y métodos
heurísticos), presentan ventajas e inconvenientes. El presente artículo aporta tres nuevos...