Monge-Kantorovich Transportation Problem

offers

a

1

40

a

2

45

a

3

10

a

4

30

requests

b

1

35

b

2

70

b

3

10

b

4

10

The minimum cost is 525

20	0	10	10
0	45	0	0
0	10	0	0
15	15	0	0

an optimal plan

cost matrix

c

11

6

c

12

4

c

13

2

c

14

1

c

21

5

c

22

2

c

23

1

c

24

1

c

31

9

c

32

6

c

33

6

c

34

4

c

41

9

c

42

6

c

43

6

c

44

4

Some homogeneous goods are stocked in

m

storage centers in quantities

a

1

,

a

2

,

a

3

, …,

a

m

. The goods are required in

n

corresponding consumption centers

b

1

,

b

2

,

b

3

, …,

b

n

. Knowing the unit transportation costs

c

ij

from each storage center to each consumption center, a plan that uses all the goods (offers) and satisfies all the consumers (requests) is needed.

x

ij

denotes the quantity of goods transported from storage center

i

to consumption center

j

. The following is a mathematical model of the problem, where we try to minimize the total transportation cost

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

is the total offer,

b=

n

∑

j=1

b

j

is the total request.

The transportation problem can be solved if

a=b

. If

a>b

, we introduce a fictional consumption center with the offer

b-a

and transportation cost 0. if

a<b

, we introduce a fictional storage center with the request

a-b

and transportation cost 0.

The problem is shown for

m=n=4

. The result shows a matrix whose row and column sums are the

a

i

and

b

j

. This matrix shows the quantity that each storage center should ship to each consumption center. If

a≠b

, we can obtain a 4×5 (

a>b

) matrix or a 5×4 (

a<b

) matrix, where the extra row or column corresponds to a fictional center.