文档介绍：Transportation problem
Suppose that a number of suppliers (s1,s2,…,sm) are to provide goods for a number of customers (d1,d2,…,dn). The transportation problem is how to meet each customer’s requirement, while not exceeding the capacity of any supplier, at a minimum cost. Costs are known for supplying one unit of the goods along each route. In some cases it may not be possible to supply a particular customer from a particular supplier .
S1
S2
S3
D1
D2
D3
D4
Example:
Manufactured goods are transported from 3 supply points (factures) to 4 demand points (outlet shops)
Objective: minimize cost of transportaiton
assume all routes are feasible
Assumption:
Cost of transportation is linearly related to the amount transported
. 5 units $200
10units $400
Data: 1) Maximum supply at supply nodes
supply point Daily maximum capacity
1 35
2 50
3 40
2) Demand level at Demand points
Demand point Daily demand
1 45
2 20
3 30
4 30
Data: 3) Per unit transportation costs
supply point D1 D2 D3 D4
s1 8 6 10 9
s2 9 12 13 7
s3 14 9 16 5
Notation
Cij = cost of transporting one unit from supply point I to demand point j
Xij = The amount of goods that we will transport form supply point I to demand points j
Objective:
Min z = 8X11 + 6X12 + 10X13 + 9X14 + 9X21 + …. + 5X34
Constraints
Don’t exceed the supply at any supply point
SP1: X11 + X12 + X13 +X14 <= 35
SP2: X21 + X22 + X23 +X24 <= 50
SP3: X31 + X32 + X33 +X34 <= 40
2) Meet the demand at every demand point
DP1: X11 + X21 + X31 >= 45
DP2: X12 + X22 + X32 >= 20
DP3: X13 + X23 + X33 >= 30
DP4: X14 + X24 + X34 >= 30
3) Xij >= 0
8
6
10
9
7
5
16
13
12
9
14
9
S3
S2
S1
D1
D2
D3
D4
35
50
40
45
20
30
30
Transportation tableau form
8
6
10
9
7
5
16
13
12
9
14
9
S3
S2
S1
D1
D2
D3
D4
55
50
40
45
20
30
30
0
0
0
20
Dummy
8
6
10
9
7
5
16
13
12
9
14
9
S3
S2
S1
D1
D2
D3
D4
35
50
40
45
20
30
30
35
10
10
0
40
20
0
20
20
10
10
0