6

Tema 6
El problema de transporte y el
problema de asignaci´on
En este tema se presentan algoritmos para resolver dos problemas lineales particulares: el problema de transporte y el problema de asignaci´on.

6.1 El problema de transporte
El problema de transporte es una de las primeras aplicaciones importantes de
la programaci´on lineal. Se puede representar con un modelo lineal y utilizar elm´etodo simplex para resolverlo. Sin embargo, dada la estructura especial de este
modelo lineal, se puede construir un m´etodo m´as eficaz para su resoluci´on. En
este tema nos ocuparemos del estudio de este m´etodo.
El problema de transporte trata de enviar unidades de un producto desde m
or´ıgenes, O1 , . . . , Om , a n destinos, D1 , . . . , Dn , en las siguientes condiciones.
• Cada origen Oi , i =1, . . . , m, dispone de una oferta ai .
• Cada destino Dj , j = 1, . . . , n, realiza una demanda bj .
• cij , i = 1, . . . , m, j = 1, . . . , n, es el coste de enviar una unidad desde el
origen Oi al destino Dj .
El problema es determinar el n´umero de unidades xij que se deben enviar
desde cada origen Oi hasta cada destino Dj para realizar el transporte a coste
m´ınimo, teniendo en cuenta quehay que satisfacer las restricciones de oferta y
demanda.
167

168

Tema 6. El problema de transporte y el problema de asignaci´on

La formulaci´on lineal de este problema es la siguiente:

m

n

cij xij

min z =
i=1 j=1

sujeto a
n

xij ≤ ai , i = 1, . . . , m
j=1
m

xij ≥ bj , j = 1, . . . , n
i=1

xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n
Las primeras m restricciones est´an asociadas a lasofertas de los or´ıgenes, que
no se deben sobrepasar. Las n siguientes restricciones aseguran que se deben
satisfacer las demandas de los destinos. Las variables no pueden tomar valores
negativos, ya que representan cantidades de producto que se transportan.
La forma est´andar del problema de transporte es la siguiente:
m

n

min z =

cij xij
i=1 j=1

sujeto a
n

xij = ai , i = 1, . . . , m
j=1
mxij = bj , j = 1, . . . , n
i=1

xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n

Ejemplo. Supongamos que una empresa productora de barras de pan tiene
dos almacenes A1 y A2 desde los cuales debe enviar pan a tres panader´ıas P1 , P2
y P3 . Las ofertas, las demandas y los costes de env´ıo se dan en el siguiente grafo.

OpenCourseWare, UPV/EHU

6.1. El problema de transporte

169

P1

1500

P2

2000P3

1000

8
2000

A1

6
10
10 4

2500

A2

9

Para plantear un modelo lineal que represente el problema definimos
xij : cantidad de barras de pan que se env´ıan desde cada origen Ai , i = 1, 2, a
cada destino Pj , j = 1, 2, 3.
El modelo lineal para este problema es el siguiente:
min z = 8x11 +6x12 +10x13 +10x21 +4x22 +9x23
sujeto a
x11 +x12 +x13

= 2000
x21

x11

+x22 +x23 = 2500

+x21
x12

=1500
+x22

x13

= 2000
+x23 = 1000

x11 , x12 , x13 , x21 , x22 , x23 ≥ 0
En este caso las restricciones se pueden escribir con igualdad porque la suma
de ofertas es igual a la suma de demandas.
Para observar la estructura de la matriz A escribimos el modelo de la siguiente
forma:

Investigaci´on Operativa. Programaci´on Lineal

170

Tema 6. El problema de transporte y el problema de asignaci´on







min z = (8, 6, 10, 10, 4, 9) 







x11





x12 


x13 


x21 


x22 

x23

sujeto a


1 1 1


 0 0 0


 1 0 0


 0 1 0

0 0 1

0 0 0
1 1 1
1 0 0
0 1 0
0 0 1



















x11
x12
x13
x21
x22
x23





 
 
 
 
 
=
 
 
 
 



2000





2500 


1500 


2000 

1000

xij ≥ 0, i = 1, 2, j =1, 2, 3
En este ejemplo hay 2 or´ıgenes, m = 2, y 3 destinos, n = 3. La matriz A
tiene 2 + 3 filas y 2 × 3 columnas. Se puede comprobar que el rango de la matriz
es 4.
Por otra parte, todos los vectores columna tienen solamente 2 componentes
iguales a 1 y las dem´as son 0. Si denotamos los vectores columna de la matriz A
con dos sub´ındices, es decir, a11 , a12 , a13 , a21 , a22 , a23 , podemos...