Transportation problem. supply chain managementppt

supply chain management

1. .
1
Transportation, Transportation,
Assignment and Assignment and
Transshipment ProblemsTransshipment Problems

2. .
2
DescriptionDescription
A transportation problem basically deals with
the problem, which aims to find the best way to
fulfill the demand of n demand points using the
capacities of m supply points. While trying to
find the best way, generally a variable cost of
shipping the product from one supply point to
a demand point or a similar constraint should
be taken into consideration.

3. .
3
Formulating Transportation Formulating Transportation
ProblemsProblems
Example 1: Powerco has three electric
power plants that supply the electric
needs of four cities.
•The associated supply of each plant and
demand of each city is given in the table 1.
•The cost of sending 1 million kwh of
electricity from a plant to a city depends
on the distance the electricity must travel.

4. .
4
Transportation tableTransportation table
A transportation problem is specified by
the supply, the demand, and the shipping
costs. So the relevant data can be
summarized in a transportation tableau.
The transportation tableau implicitly
expresses the supply and demand
constraints and the shipping cost between
each demand and supply point.

5. .
5
Shipping costs, Supply, and Demand for Shipping costs, Supply, and Demand for
Power co ExamplePower co Example
From To
City 1City 2City 3City 4Supply
(Million kwh)
Plant 1 $8 $6 $10 $9 35
Plant 2 $9 $12$13 $7 50
Plant 3 $14 $9 $16 $5 40
Demand
(Million kwh)
45 20 30 30
Transportation Table

6. .
6
SolutionSolution
1.Decision Variable:
Since we have to determine how much
electricity is sent from each plant to each
city;
X
ij = Amount of electricity produced at plant i
and sent to city j
X
14 = Amount of electricity produced at plant
1 and sent to city 4

7. .
7
Objective functionObjective function
Since we want to minimize the total cost of
shipping from plants to cities;
Minimize Z = 8X
11
+6X
12
+10X
13
+9X
14
+9X
21+12X
22+13X
23+7X
24
+14X
31
+9X
32
+16X
33
+5X
34

8. .
8
Supply ConstraintsSupply Constraints
Since each supply point has a limited production
capacity;
X
11
+X
12
+X
13
+X
14
<= 35
X
21+X
22+X
23+X
24 <= 50
X
31
+X
32
+X
33
+X
34
<= 40

9. .
9
. Demand Constraints. Demand Constraints
Since each supply point has a limited production
capacity;
X
11
+X
21
+X
31
>= 45
X
12+X
22+X
32 >= 20
X
13
+X
23
+X
33
>= 30
X
14
+X
24
+X
34
>= 30

10. .
10
5. Sign Constraints5. Sign Constraints
Since a negative amount of electricity can not be
shipped all Xij’s must be non negative;
Xij >= 0 (i= 1,2,3; j= 1,2,3,4)

11. .
11
LP Formulation of Powerco’s ProblemLP Formulation of Powerco’s Problem
Min Z = 8X
11
+6X
12
+10X
13
+9X
14
+9X
21
+12X
22
+13X
23
+7X
24
+14X
31
+9X
32
+16X
33
+5X
34
S.T.:X
11
+X
12
+X
13
+X
14
<= 35 (Supply Constraints)
X
21
+X
22
+X
23
+X
24
<= 50
X
31
+X
32
+X
33
+X
34
<= 40
X
11
+X
21
+X
31
>= 45 (Demand
Constraints)
X
12+X
22+X
32 >= 20
X
13+X
23+X
33 >= 30
X
14+X
24+X
34 >= 30
Xij >= 0 (i= 1,2,3; j= 1,2,3,4)

12. .
12
General Description of a Transportation General Description of a Transportation
ProblemProblem
1.A set of m supply points from which a good
is shipped. Supply point i can supply at most
s
i
units.
2.A set of n demand points to which the good
is shipped. Demand point j must receive at
least d
i
units of the shipped good.
3.Each unit produced at supply point i and
shipped to demand point j incurs a variable
cost of c
ij.

13. .
13
X
ij
= number of units shipped from supply point i to
demand point j
),...,2,1;,...,2,1(0
),...,2,1(
),...,2,1(..
min
1
1
11
njmiX
njdX
misXts
Xc
ij
mi
i
jij
nj
j
iij
mi
i
nj
j
ijij















14. .
14
Balanced Transportation ProblemBalanced Transportation Problem
If Total supply equals to total demand, the
problem is said to be a balanced
transportation problem:






nj
j
j
mi
i
i ds
11

15. .
15
Balancing a TP if total supply exceeds total Balancing a TP if total supply exceeds total
demanddemand
If total supply exceeds total demand, we
can balance the problem by adding dummy
demand point. Since shipments to the
dummy demand point are not real, they
are assigned a cost of zero.

16. .
16
Balancing a transportation problem if total Balancing a transportation problem if total
supply is less than total demandsupply is less than total demand
If a transportation problem has a total
supply that is strictly less than total
demand the problem has no feasible
solution. There is no doubt that in such a
case one or more of the demand will be
left unmet. Generally in such situations a
penalty cost is often associated with
unmet demand and as one can guess this
time the total penalty cost is desired to be
minimum

17. .
17
Finding Basic Feasible Solution for Finding Basic Feasible Solution for
TPTP
Unlike other Linear Programming
problems, a balanced TP with m supply
points and n demand points is easier to
solve, although it has m + n equality
constraints. The reason for that is, if a set
of decision variables (x
ij
’s) satisfy all but
one constraint, the values for x
ij
’s will
satisfy that remaining constraint
automatically.

18. .
18
Methods to find the bfs for a balanced TPMethods to find the bfs for a balanced TP
There are three basic methods:
1.Northwest Corner Method
2.Minimum Cost Method
3.Vogel’s Method

19. .
19
Northwest Corner MethodNorthwest Corner Method
To find the bfs by the NWC method:
Begin in the upper left (northwest) corner of
the transportation tableau and set x
11 as
large as possible (here the limitations for
setting x
11
to a larger number, will be the
demand of demand point 1 and the supply
of supply point 1. Your x
11
value can not be
greater than minimum of this 2 values).

20. .
20
According to the explanations in the previous slide According to the explanations in the previous slide
we can set xwe can set x
1111=3 (meaning demand of demand =3 (meaning demand of demand
point 1 is satisfied by supply point 1).point 1 is satisfied by supply point 1).
5
6
2
3 5 2 3
3 2
6
2
X 5 2 3

21. .
21
After we check the east and south cells, we saw that After we check the east and south cells, we saw that
we can go east (meaning supply point 1 still has capacity we can go east (meaning supply point 1 still has capacity
to fulfill some demand).to fulfill some demand).
3 2 X
6
2
X 3 2 3
3 2 X
3 3
2
X X 2 3

22. .
22
After applying the same procedure, we saw that we can After applying the same procedure, we saw that we can
go south this time (meaning demand point 2 needs more go south this time (meaning demand point 2 needs more
supply by supply point 2).supply by supply point 2).
3 2 X
3 2 1
2
X X X 3
3 2 X
3 2 1 X
2
X X X 2

23. .
23
Finally, we will have the following bfs, which is:Finally, we will have the following bfs, which is:
x x
1111=3, x=3, x
1212=2, x=2, x
2222=3, x=3, x
2323=2, x=2, x
2424=1, x=1, x
3434=2=2
3 2 X
3 2 1 X
2 X
X X X X

24. .
24
Minimum Cost MethodMinimum Cost Method
The Northwest Corner Method dos not utilize
shipping costs. It can yield an initial bfs easily but
the total shipping cost may be very high. The
minimum cost method uses shipping costs in
order come up with a bfs that has a lower cost. To
begin the minimum cost method, first we find the
decision variable with the smallest shipping cost
(X
ij
). Then assign X
ij
its largest possible value,
which is the minimum of s
i
and d
j

25. .
25
After that, as in the Northwest Corner Method we
should cross out row i and column j and reduce the
supply or demand of the noncrossed-out row or
column by the value of Xij. Then we will choose the
cell with the minimum cost of shipping from the
cells that do not lie in a crossed-out row or column
and we will repeat the procedure.

26. .
26
An example for Minimum Cost MethodAn example for Minimum Cost Method
Step 1: Select the cell with minimum cost.Step 1: Select the cell with minimum cost.
2 3 5 6
2 1 3 5
3 8 4 6
5
10
15
12 8 4 6

27. .
27
Step 2: Cross-out column 2Step 2: Cross-out column 2
2 3 5 6
2 1 3 5
8
3 8 4 6
12 X 4 6
5
2
15

28. .
28
Step 3: Find the new cell with minimum shipping Step 3: Find the new cell with minimum shipping
cost and cross-out row 2cost and cross-out row 2
2 3 5 6
2 1 3 5
2 8
3 8 4 6
5
X
15
10 X 4 6

29. .
29
Step 4: Find the new cell with minimum shipping Step 4: Find the new cell with minimum shipping
cost and cross-out row 1cost and cross-out row 1
2 3 5 6
5
2 1 3 5
2 8
3 8 4 6
X
X
15
5 X 4 6

30. .
30
Step 5: Find the new cell with minimum shipping Step 5: Find the new cell with minimum shipping
cost and cross-out column 1cost and cross-out column 1
2 3 5 6
5
2 1 3 5
2 8
3 8 4 6
5
X
X
10
X X 4 6

31. .
31
Step 6: Find the new cell with minimum shipping Step 6: Find the new cell with minimum shipping
cost and cross-out column 3cost and cross-out column 3
2 3 5 6
5
2 1 3 5
2 8
3 8 4 6
5 4
X
X
6
X X X 6

32. .
32
Step 7: Finally assign 6 to last cell. The bfs is found Step 7: Finally assign 6 to last cell. The bfs is found
as: Xas: X
1111=5, X=5, X
2121=2, X=2, X
2222=8, X=8, X
3131=5, X=5, X
3333=4 and X=4 and X
3434=6=6
2 3 5 6
5
2 1 3 5
2 8
3 8 4 6
5 4 6
X
X
X
X X X X

33. .
33
Vogel’s MethodVogel’s Method
Begin with computing each row and column a
penalty. The penalty will be equal to the difference
between the two smallest shipping costs in the
row or column. Identify the row or column with
the largest penalty. Find the first basic variable
which has the smallest shipping cost in that row
or column. Then assign the highest possible value
to that variable, and cross-out the row or column
as in the previous methods. Compute new
penalties and use the same procedure.

34. .
34
An example for Vogel’s MethodAn example for Vogel’s Method
Step 1: Compute the penalties.Step 1: Compute the penalties.
SupplyRow Penalty
6 7 8
15 80 78
Demand
Column Penalty 15-6=9 80-7=73 78-8=70
7-6=1
78-15=63
15 5 5
10
15

35. .
35
Step 2: Identify the largest penalty and assign the Step 2: Identify the largest penalty and assign the
highest possible value to the variable.highest possible value to the variable.
SupplyRow Penalty
6 7 8
5
15 80 78
Demand
Column Penalty 15-6=9 _ 78-8=70
8-6=2
78-15=63
15 X 5
5
15

36. .
36
Step 3: Identify the largest penalty and assign the Step 3: Identify the largest penalty and assign the
highest possible value to the variable.highest possible value to the variable.
SupplyRow Penalty
6 7 8
5 5
15 80 78
Demand
Column Penalty 15-6=9 _ _
_
_
15 X X
0
15

37. .
37
Step 4: Identify the largest penalty and assign the Step 4: Identify the largest penalty and assign the
highest possible value to the variable.highest possible value to the variable.
SupplyRow Penalty
6 7 8
0 5 5
15 80 78
Demand
Column Penalty _ _ _
_
_
15 X X
X
15

38. .
38
Step 5: Finally the bfs is found as XStep 5: Finally the bfs is found as X
1111=0, X=0, X
1212=5, =5,
XX
1313=5, and X=5, and X
2121=15=15
SupplyRow Penalty
6 7 8
0 5 5
15 80 78
15
Demand
Column Penalty _ _ _
_
_
X X X
X
X

39. .
39
The Transportation Simplex The Transportation Simplex
MethodMethod
In this section we will explain how the simplex
algorithm is used to solve a transportation problem.

40. .
40
How to Pivot a Transportation ProblemHow to Pivot a Transportation Problem
Based on the transportation tableau, the
following steps should be performed.
Step 1. Determine (by a criterion to be
developed shortly, for example northwest corner
method) the variable that should enter the basis.
Step 2. Find the loop (it can be shown that there
is only one loop) involving the entering variable
and some of the basic variables.
Step 3. Counting the cells in the loop, label them
as even cells or odd cells.

41. .
41
Step 4. Find the odd cells whose variable assumes
the smallest value. Call this value . The variable
θ
corresponding to this odd cell will leave the basis.
To perform the pivot, decrease the value of each
odd cell by and increase the value of each even
θ
cell by . The variables that are not in the loop
θ
remain unchanged. The pivot is now complete. If
=0, the entering variable will equal 0, and an odd
θ
variable that has a current value of 0 will leave the
basis. In this case a degenerate bfs existed before
and will result after the pivot. If more than one
odd cell in the loop equals , you may arbitrarily
θ
choose one of these odd cells to leave the basis;
again a degenerate bfs will result

42. .
42
Assignment ProblemsAssignment Problems
Example: Machine has four jobs to be completed.
Each machine must be assigned to complete one
job. The time required to setup each machine for
completing each job is shown in the table below.
Machine wants to minimize the total setup time
needed to complete the four jobs.

43. .
43
Setup times
(Also called the cost matrix)
Time (Hours)
Job1Job2Job3Job4
Machine 114 5 8 7
Machine 22 12 6 5
Machine 37 8 3 9
Machine 42 4 6 10

44. .
44
The ModelThe Model
According to the setup table Machinco’s problem
can be formulated as follows (for i,j=1,2,3,4):
10
1
1
1
1
1
1
1
1..
10629387
5612278514min
44342414
43332313
42322212
41312111
44434241
34333231
24232221
14131211
4443424134333231
2423222114131211











ijijorXX
XXXX
XXXX
XXXX
XXXX
XXXX
XXXX
XXXX
XXXXts
XXXXXXXX
XXXXXXXXZ

45. .
45
For the model on the previous page note that:
X
ij
=1 if machine i is assigned to meet the demands
of job j
X
ij
=0 if machine i is not assigned to meet the
demands of job j
In general an assignment problem is balanced
transportation problem in which all supplies and
demands are equal to 1.

46. .
46
The Assignment ProblemThe Assignment Problem
In general the LP formulation is given as
Minimize
1 1
1
1
1 1
1 1
0
, , ,
, , ,
or 1,
n n
ij ij
i j
n
ij
j
n
ij
i
ij
c x
x i n
x j n
x ij
 


  
  
 





Each supply is 1
Each demand is 1

47. .
47
Comments on the Assignment ProblemComments on the Assignment Problem
The Air Force has used this for assigning
thousands of people to jobs.
This is a classical problem. Research on the
assignment problem predates research on LPs.
Very efficient special purpose solution
techniques exist.
◦10 years ago, Yusin Lee and J. Orlin solved a problem
with 2 million nodes and 40 million arcs in ½ hour.

48. .
48
Although the transportation simplex appears to be
very efficient, there is a certain class of transportation
problems, called assignment problems, for which the
transportation simplex is often very inefficient. For
that reason there is an other method called The
Hungarian Method. The steps of The Hungarian
Method are as listed below:
Step1. Find a bfs. Find the minimum element in each
row of the mxm cost matrix. Construct a new matrix
by subtracting from each cost the minimum cost in its
row. For this new matrix, find the minimum cost in
each column. Construct a new matrix (reduced cost
matrix) by subtracting from each cost the minimum
cost in its column.

49. .
49
Step2. Draw the minimum number of lines
(horizontal and/or vertical) that are needed to
cover all zeros in the reduced cost matrix. If m
lines are required , an optimal solution is available
among the covered zeros in the matrix. If fewer
than m lines are required, proceed to step 3.
Step3. Find the smallest nonzero element (call its
value k) in the reduced cost matrix that is
uncovered by the lines drawn in step 2. Now
subtract k from each uncovered element of the
reduced cost matrix and add k to each element
that is covered by two lines. Return to step2.

50. .
50
Transshipment ProblemsTransshipment Problems
A transportation problem allows only shipments
that go directly from supply points to demand
points. In many situations, shipments are allowed
between supply points or between demand points.
Sometimes there may also be points (called
transshipment points) through which goods can be
transshipped on their journey from a supply point
to a demand point. Fortunately, the optimal
solution to a transshipment problem can be found
by solving a transportation problem.

51. .
51
Transshipment ProblemTransshipment Problem
An extension of a transportation problem
◦More general than the transportation problem in that in
this problem there are intermediate “transshipment
points”. In addition, shipments may be allowed between
supply points and/or between demand points
LP Formulation
◦Supply point: it can send goods to another point but
cannot receive goods from any other point
◦Demand point It can receive goods from other points
but cannot send goods to any other point
◦Transshipment point: It can both receive goods from
other points send goods to other points

52. .
52
The following steps describe how the optimal
solution to a transshipment problem can be found
by solving a transportation problem.
Step1. If necessary, add a dummy demand point
(with a supply of 0 and a demand equal to the
problem’s excess supply) to balance the problem.
Shipments to the dummy and from a point to itself
will be zero. Let s= total available supply.
Step2. Construct a transportation tableau as
follows: A row in the tableau will be needed for
each supply point and transshipment point, and a
column will be needed for each demand point and
transshipment point.

53. .
53
Each supply point will have a supply equal to it’s
original supply, and each demand point will have a
demand to its original demand. Let s= total
available supply. Then each transshipment point will
have a supply equal to (point’s original supply)+s
and a demand equal to (point’s original demand)+s.
This ensures that any transshipment point that is a
net supplier will have a net outflow equal to
point’s original supply and a net demander will
have a net inflow equal to point’s original demand.
Although we don’t know how much will be
shipped through each transshipment point, we can
be sure that the total amount will not exceed s.

54. .
54
Transshipment ExampleTransshipment Example
Example 5: Widgetco manufactures widgets at
two factories, one in Memphis and one in
Denver. The Memphis factory can produce as
150 widgets, and the Denver factory can
produce as many as 200 widgets per day.
Widgets are shipped by air to customers in LA
and Boston. The customers in each city require
130 widgets per day. Because of the
deregulation of airfares, Widgetco believes that
it may be cheaper first fly some widgets to NY
or Chicago and then fly them to their final
destinations. The cost of flying a widget are
shown next. Widgetco wants to minimize the
total cost of shipping the required widgets to
customers.

55. .
55
Transportation Table Associated with Transportation Table Associated with
the Transshipment Examplethe Transshipment Example
 NY Chicago LA Boston Dummy Supply
Memphis $8 $13 $25 $28 $0 150
Denver $15 $12 $26 $25 $0 200
NY $0 $6 $16 $17 $0 350
Chicago $6 $0 $14 $16 $0 350
Demand 350 350 130 130 90
Supply points: Memphis, Denver
Demand Points: LA Boston
Transshipment Points: NY, Chicago
The problem can be solved using the transportation simplex
method

56. .
56
Limitations of Transportation ProblemLimitations of Transportation Problem
One commodity ONLY: any one product
supplied and demanded at multiple locations
◦Merchandise
◦Electricity, water
Invalid for multiple commodities: (UNLESS
transporting any one of the multiple
commodities is completely independent of
transporting any other commodity and hence can
be treated by itself alone)
◦Example: transporting product 1 and product 2 from
the supply points to the demand points where the total
amount (of the two products) transported on a link is
subject to a capacity constraint
◦Example: where economy of scale can be achieved by
transporting the two products on the same link at a
larger total volume and at a lower unit cost of
transportation

57. .
57
Limitations of Transportation ProblemLimitations of Transportation Problem
◦Difficult to generalize the technique to accommodate
(these are generic difficulty for “mathematical
programming,” including linear and non-linear
programming
Economy of scale the per-unit cost of transportation on a link
decreasing with the volume (nonlinear and concave; there is a trick
to convert a “non-linear program with a piecewise linear but
convex objective function to a linear program; no such tricks exists
for a piecewise linear but concave objective function)
Fixed-cost: transportation usually involves fixed charges. For
example, the cost of truck rental (or cost of trucking in general)
consists of a fixed charge that is independent of the mileage and a
mileage charge that is proportional to the total mileage driven. Such
fixed charges render the objective function NON-LINEAR and
CONCAVE and make the problem much more difficult to solve

58. .
58
Presented by Presented by
Future innoversity