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=
m
∑
j=1
n
∑
i=1
c
ij
x
ij
n
∑
j=1
x
ij
a
i
i=1,…,m
m
∑
i=1
x
ij
b
j
j=1,…,n
a=
m
∑
i=1
a
i
b=
n
∑
j=1
b
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