cultura empresarial

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

6.1 El problema de transporte
El problema de transporte es una de las primeras aplicaciones importantes de
la programaci´ n lineal. Se puede representar con un modelo lineal yutilizar el
o
m´ todo simplex para resolverlo. Sin embargo, dada la estructura especial de este
e
modelo lineal, se puede construir un m´ todo m´ s eficaz para su resoluci´ n. En
e
a
o
este tema nos ocuparemos del estudio de este m´ todo.
e
El problema de transporte trata de enviar unidades de un producto desde m
or´genes, O1 , . . . , Om , a n destinos, D1 , . . . , Dn , en las siguientescondiciones.
ı
• 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´ mero de unidades xij que se deben enviar
u
desde cada origen Oi hasta cada destino Dj para realizar eltransporte a coste
m´nimo, teniendo en cuenta que hay que satisfacer las restricciones de oferta y
ı
demanda.
167

168

Tema 6. El problema de transporte y el problema de asignaci´ n
o

La formulaci´ n lineal de este problema es la siguiente:
o

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´ n asociadas a las ofertas de los or´genes, que
a
ı
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´ ndar del problema de transportees la siguiente:
a
m

n

min z =

cij xij
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

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 costesde env´o se dan en el siguiente grafo.
ı

OpenCourseWare, UPV/EHU

6.1. El problema de transporte

169

P1

1500

P2

2000

P3

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.
Elmodelo 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 laestructura de la matriz A escribimos el modelo de la siguiente
forma:

Investigaci´ n Operativa. Programaci´ n Lineal
o
o

170

Tema 6. El problema de transporte y el problema de asignaci´ n
o









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...