Transporte y asignación

5. EL PROBLEMA DE TRANSPORTE
5.1 Introducci´n.
o
5.1.1 Forma matricial para el problema del transporte.
5.1.2 Teoremas.
5.1.3 C´lculo de una soluci´n factible b´sica inicial.
a
o
a
5.1.4 Mejora de una soluci´n factible b´sica.
o
a
5.1.5 Tabla del transporte.
5.1.6 Algoritmo para el problema del transporte.
5.1.7 Soluci´n degenerada.
o

1

5.1. El problema de transporte
Setrata de enviar unidades de un producto desde m
or´
ıgenes, O1 , . . . , Om, a n destinos, D1, . . . , Dn , en las
siguientes condiciones.
• ai: oferta de Oi ,

i = 1, . . . , m.

• bj : demanda de Dj ,

j = 1, . . . , n.

• cij : coste de transporte desde Oi a Dj , i = 1, . . . , m,
j = 1, . . . , n.
Modelo lineal para el problema de transporte.
m

n

min z =

cij xij
i=1 j=1sujeto a
n

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

xij ≥ bj

j = 1, . . . , n

xij ≥ 0

∀i, j

i=1

A˜adiendo variables de holgura se tiene la forma est´ndar.
n
a
m

Si

n

ai =
i=1

bj

entonces se tiene la forma estandar

j=1

sin necesidad de variables de holgura.
2

Ejemplo.
P1

1500

8
2000

A

6

10
P2

10
2500

2000

4

B
9
P31000

• Variables de decisi´n.
o
xij : unidades desde i a Pj , i = A, B, j = 1, 2, 3.
min z = 8xA1 + 6xA2 + 10xA3 + 10xB1 + 4xB2 + 9xB3
sujeto a
xA1

+xA2

+xA3

≤
xB1
+xB1

xA1

+xB2

xA2
xA3

+xB3

2.500
1.500

≥

+xB3

≤
≥

+xB2

2.000

2.000

≥

1.000

xij ≥ 0 i = A, B j = 1, 2, 3

3

Forma matricial.



min z = (8 , 6 , 10 , 10 , 4 ,xA1
xA2




9) 




xA3
xB1
xB2
xB3










sujeto a








1

1

1

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

1

0

0

1

0

0

0

1

0

0

1

xij ≥ 0,





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

xA1
xA2
xA3
xB1
xB2
xB3

i = A, B






 
 
=
 
 
2.000
2.500
1.500
2.000
1.000








j = 1, 2, 3

P1

P2

P3

OF ERT A

A

8

6

10

2.000

B

10

4

9

2.500

DEM AN DA

1.500

2.000

1.000

4

5.2. Forma matricial del problema de transporte.
D1

D2

···

Dn

OF ERT A

O1

c11

c12

···

c1n

a1

O2
.
.
.

c21
.
.
.

c22
.
.
.

···
...

c2n.
.
.

a2
.
.
.

Om

cm1

cm2

···

cmn

am

DEM AN DA

b1

b2

···

bn

n

m

bj , el problema es equilibrado.

ai =

Si
i=1

j=1

m

n

1.

bj . Origen ficticio Om+1 .

ai <
i=1

j=1
n

m

• Oferta: am+1 =

bj −
j=1

i=1

• Costes: cm+1,j = 0,

bj . Destino ficticio Dn+1

ai >
i=1

j = 1, . . . , n

n

m

2.

aij=1
m

n

• Demanda: bn+1 =

ai −
i=1

• Costes: ci,n+1 = 0,

bj
j=1

i = 1, . . . , m
5

5.3. Teoremas.

Teorema 1 Para que el problema de transporte tenga
soluci´n es condici´n necesaria y suficiente que la oferta
o
o
total sea igual a la demanda total.
Teorema 2 El problema de transporte equilibrado tiene
una soluci´n factible.
o
Teorema 3 Todo problema detransporte equilibrado
tiene una soluci´n b´sica factible. Esta soluci´n tiene
o
a
o
como m´ximo m + n − 1 variables no negativas.
a
Observaci´n: rg(A) = m + n − 1
o

6

5.4. C´lculo de una soluci´n factible b´sica inicial.
a
o
a
El m´todo de la esquina noroeste.
e
Dado un problema de transporte equilibrado,
Paso 1. Elegir la esquina noroeste (i, j) de la tabla
(inicialmente i = 1, j =1).
Paso 2. Asignar xij = min{ai, bj }. Actualizar ofertas y demandas.
• Si ai = min{ai, bj }, oferta de Oi es 0, demanda
de Dj es bj − ai.
• Si bj = min{ai , bj }, demanda de Dj es 0, oferta
de Oi es ai − bj .
• Si ai = bj , oferta de Oi y demanda de Dj son 0.
Eliminar de la tabla para c´lculos posteriores la fila
a
y/o columna satisfecha.
Paso 3. Se pueden dar dos casos.
• Si queda...