Vogel

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

ƒ Índice
Nuevos Algoritmos en el Problema de Transporte
Francisco López Ruiz , Germán Arana Landín
1 1

2

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

Ingeniero de Organización Industrial, Departamento Organización deEmpresas. E.U.I.T.I.-San SebastiánUPV. 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ático utilizado. Por tanto, una vez definido elmodelo, 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 detransporte Una 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 laprogramació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íade 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 el problema combinatorio, mediante la utilización de técnicas quepermitan 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 ahorros considerables en tiempo respecto a losmé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 métodos para la resolución del problema de transporte basados en la...