# Monge-Kantorovich Transportation Problem

Monge-Kantorovich Transportation Problem

Some homogeneous goods are stocked in storage centers in quantities , , , …, . The goods are required in corresponding consumption centers , , , …, . Knowing the unit transportation costs from each storage center to each consumption center, a plan that uses all the goods (offers) and satisfies all the consumers (requests) is needed.

m

a

1

a

2

a

3

a

m

n

b

1

b

2

b

3

b

n

c

ij

x

ij

i

j

y

y=cx

m

∑

j=1

n

∑

i=1

ij

ij

n

∑

j=1

ij

i

i=1,…,m

m

∑

i=1

ij

j

j=1,…,n

a=a

m

∑

i=1

i

b=b

n

∑

j=1

j

The transportation problem can be solved if . If , we introduce a fictional consumption center with the offer and transportation cost 0. if , we introduce a fictional storage center with the request and transportation cost 0.

a=b

a>b

b-a

a<b

a-b

The problem is shown for . The result shows a matrix whose row and column sums are the and . This matrix shows the quantity that each storage center should ship to each consumption center. If , we can obtain a 4×5 () matrix or a 5×4 () matrix, where the extra row or column corresponds to a fictional center.

m=n=4

a

i

b

j

a≠b

a>b

a<b