10

Revista de Dirección y Administración de Empresas. Número 10, diciembre 2002
Enpresen Zuzendaritza eta Administraziorako Aldizkaria. 10. zenbakia, 2002 abendua

págs. 159-173
159-173 orr.

NUEVOS METODOS PARA LA OBTENCION DE
SOLUCIONES INICIALES EN EL PROBLEMA DE
TRANSPORTE

FRANCISCO LÓPEZ RUIZ
Departamento Organización de Empresas. E.U.I.T.I.-San Sebastián-UPV-EHU

RESUMEN
Una vez formulado elmodelo matemático del problema de transporte, el
siguiente paso consiste en resolver el modelo, es decir, en 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 el modelo, se podrá elegir un método
apropiado para resolverlo. En el problema detransport 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 lasrestricciones. 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 excesivo tiempo o bien es imposible por
ser el modelo matemático demasiado complejo. Este artículoaporta tres

160

FRANCISCO LÓPEZ RUIZ

nuevos métodos para la resolución del problema de transporte, basados en los
métodos heurísticos.
Palabras clave: Investigación Operativa. Optimización. Programación
Lineal. Problema del transporte. Métodos de resolución. Técnicas heurísticas.
Método del Simplex. Algoritmo de Transporte. Métodos de obtención de una
solución inicial. Algoritmo de optimización ymejora. Soluciones degeneradas.

1. INTRODUCCION AL PROBLEMA DE TRANSPORTE
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 laprogramació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 necesariobuscar otro tipo de métodos de solución.
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 que permitan reducir labú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
los métodos basados enalgoritmos 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 segunda alternativa....