Programacion Lineal.

Problemas de Transporte

CAPITULO 6: PROBLEMAS DE TRANSPORTE

Comúnmente se han considerado como un caso particular de los problemas
lineales los problemas de transporte y de asignación. Pero hemos de notar que se trata
en realidad de problemas de programación entera, dado que las variables que aparecen
en estos problemas son variables que han de tomar valores enteros.
Este tipo deproblemas los vamos a tratar como problemas especiales de
programación lineal, dado que su estructura especial ha hecho que se desarrollen
algoritmos específicos para este tipo de problemas, más eficientes que el método
simplex. No obstante, estamos más interesados en plantear su estructura que en su
resolución particular. Para ello recurriremos al uso del algoritmo de simplex, aunque
indicaremosdiferentes programas de software donde encontrar los algoritmos
particulares para este tipo de problemas.

6.1 ANTECEDENTES DEL PROBLEMA

La primera referencia escrita de este problema se remonta a 1781, cuando el
matemático francés Gaspard Monge describe el problema de la construcción y
abastecimiento de fortificaciones militares de los ejércitos de Napoleon. Monge era
entonces general delos ejércitos napoleónicos. Para resolver este problema usó el
método de “cortar y llenar”, es decir, ir abasteciendo las diferentes trincheras desde los
depósitos de material existentes.
Formalmente, este problema aparece en 1941 cuando F.L. Hitchcock publica una
solución analítica para este problema, aunque su desarrollo se produce a finales de los
años 40, cuando Koopmans (un jovenholandés) realiza su tesis doctoral sobre los
problemas de embarque de la marina holandesa.

Ramon Sala Garrido

149

Modelización y Optimización

A partir de ese momento el campo de aplicación del problema del transporte
empieza a crecer de una forma muy rápida, no solo en aplicaciones militares, sino
también en el campo de la producción, la distribución, las finanzas, etc.

6.2MODELIZACION DEL PROBLEMA: HIPOTESIS BASICAS.

Se trata de uno de los primeros problemas que se formularon como problemas de
programación entera. El problema consiste en lo siguiente:
Supongamos que tenemos m orígenes (almacenes) que tienen que suministrar a n
destinos (centros de consumo) un cierto producto. La capacidad de oferta de cada origen
i (i= 1,...m) es ai (ai>0), mientras que la demanda decada destino j (j=1,...n) es bj ,
(bj>0).
El coste de enviar una unidad de producto del origen i al destino j es cij.
El problema consiste en determinar cuantas unidades de producto deben enviarse
desde el origen i al destino j, de forma que se minimice el coste de envío, y por
descontado, garantizando la demanda de los destinos y no excediendo de la capacidad
de los orígenes.
A lasvariables de decisión xijrepresentan la cantidad enviada desde el almacén
i al centro de consumo j, estas variables de decisión han de ser no negativas y enteras.
En lo sucesivo, y para el planteamiento formal del problema vamos a obviar la
condición de integridad de las variables, ya que bajo determinadas condiciones
podemos garantizar la existencia de una solución entera para el problemaresolviéndolo
como un problema lineal.
Este problema se puede comprender mejor con la ayuda del gráfico siguiente, en
donde se han representado los orígenes y los destinos:

150

Ramon Sala Garrido

Problemas de Transporte

Origen 1
a1

Destino 1
b1

Origen 2
a2

Destino 2
b2

Xij
Origen i
ai

Destino j
bj

Origen m
am

Destino n
bn

Ramon Sala Garrido

151Modelización y Optimización

Por tanto, el problema se puede plantear matemáticamente como:

m

Min

n

∑ ∑ cijxij
==
i1 j1

s.a:
n

∑x
j =1

ij

≤ ai

i=1,2,...m

ij

≥ bj

j=1,2,...n

m

∑x
i =1

xij≥ 0

i=1,2,...m

j=1,2,...n

n

En este problema, el primer conjunto de restricciones ( ∑ xij ≤ ai ) nos esta
j =1

indicando que los envíos totales de...