Transcript Transportation Problem

Learning Outcomes
• Mahasiswa dapat menghitung
solusi model transportasi dengan
menggunakan program komputer..
Outline Materi:
• Masalah Transportasi
• Pembuatan program komputer
• Contoh & Penyelesaian..
Transportation Problem
• The transportation problem seeks to minimize
the total shipping costs of transporting goods
from m origins (each with a supply si) to n
destinations (each with a demand dj), when
the unit shipping cost from an origin, i, to a
destination, j, is cij.
• The network representation for a
transportation problem with two sources and
three destinations is given on the next slide.
Transportation Problem
• Network Representation
c11
c12
1
s1
c13
c21
c22
s2
2
c23
SOURCES
1
d1
2
d2
3
d3
DESTINATIONS
Transportation Problem
• LP Formulation
The LP formulation in terms of the amounts
shipped from the origins to the destinations, xij , can be
written as:
Min cijxij
ij
s.t.
xij < si for each origin i
j
xij = dj for each destination j
i
xij > 0 for all i and j
Transportation Problem
• LP Formulation Special Cases
The following special-case modifications to the linear
programming formulation can be made:
– Minimum shipping guarantee from i to j:
xij > Lij
– Maximum route capacity from i to j:
xij < Lij
– Unacceptable route:
Remove the corresponding decision variable.
Example: BBC
Building Brick Company (BBC) has orders for 80
tons of bricks at three suburban locations as follows:
Northwood -- 25 tons, Westwood -- 45 tons, and
Eastwood -- 10 tons. BBC has two plants, each of
which can produce 50 tons per week. Delivery cost
per ton from each plant to each suburban location is
shown on the next slide.
How should end of week shipments be made to
fill the above orders?
Example: BBC

Delivery Cost Per Ton
Northwood
Plant 1
24
Plant 2
30
Westwood
30
40
Eastwood
40
42
Example: BBC

Partial Spreadsheet Showing Problem Data
A
B
1
2 Constraint
X11
3
#1
1
4
#2
5
#3
1
6
#4
7
#5
8 Obj.Coefficients 24
C
D
E
F
G
H
X22
X23
RHS
LHS Coefficients
X12
X13
1
1
X21
50
1
1
1
1
1
25
1
1
30
40
30
50
40
45
1
10
42
30
Example: BBC

Partial Spreadsheet Showing Optimal Solution
A
B
C
D
10
X11
X12
X13
11 Dec.Var.Values
5
45
0
12
Minimized Total Shipping Cost
13
14
LHS
Constraints
15
P1.Cap.
50
16
P2.Cap.
30
17
N.Dem.
25
18
W.Dem.
45
19
E.Dem.
10
E
X21
20
2490
<=
<=
=
=
=
F
X22
0
RHS
50
50
25
45
10
G
X23
10
Example: BBC

Optimal Solution
From
To
Amount Cost
Plant 1 Northwood
5
120
Plant 1 Westwood
45
1,350
Plant 2 Northwood
20
600
Plant 2 Eastwood
10
420
Total Cost = $2,490
Example: BBC

Partial Sensitivity Report (first half)
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value
Cost
Coefficient Increase Decrease
$C$12 X11
5
0
24
4
4
$D$12 X12
45
0
30
4
1E+30
$E$12 X13
0
4
40
1E+30
4
$F$12 X21
20
0
30
4
4
$G$12 X22
0
4
40
1E+30
4
$H$12 X23 10.000
0.000
42
4
1E+30
Example: BBC

Partial Sensitivity Report (second half)
Constraints
Cell
$E$17
$E$18
$E$19
$E$20
$E$16
Name
P2.Cap
N.Dem
W.Dem
E.Dem
P1.Cap
Final Shadow Constraint Allowable Allowable
Value
Price
R.H. Side
Increase Decrease
30.0
0.0
50
1E+30
20
25.0
30.0
25
20
20
45.0
36.0
45
5
20
10.0
42.0
10
20
10
50.0
-6.0
50
20
5