Project Plant 
A 
B 
C 
Plant capacity 
W 
4 56 
8 
8 
56 
X 
17 16 
24 66 
16 
82 
Y 

16 36 
24 41 
77 

72 
102 
41 
215 
Total cost of initial solution
Since the stone squares are 5 as against the nm requirements m+11
3+31 =5
The above solution is non degenerate
Now we proceed to test its optimality by stepping stone method.
We have traced a closed loop or path for each of unused square i.e., opportunity cost of square is determined next
To From 
Project A 
Project B 
Project C 
Plant Capacity 
W 
4 56 
8 
8 
56 
X 
16 16 
24 60 
16 
82 
Y 
8 
16 36 
24 41 
77 
Project Requirement 
72 
102 
41 
215 
On the basis of closed loop
WC =WCWA+XAXB+4I34C
=84+ 1624+ 1624= 12.
Now tracing a closed loop for cell XC
To From 
A 
B 
C 

W 
4 56 
8 
8 
56 
X 
16 16 
24 66 
16 
82 
Y 
8 
16 36 
24 41 
77 

72 
102 
41 
215 
WC = WC WA + XAXB + YB – YC
=84 + 1624 + 16 24 =12.
Now the IInd improved table is as under
To From 
Project A 
Project B 
Project C 

W 
4 56 
8 
8 
56

X 
16 
24 25 
16 41 
82 77 
Y 
8 
16 77 
24 


72 
102 
41 
215 
Associated transportation costs is
56 × 4 + 16 × 16 + 25 × 24 + 41 × 16 + 77 × 16 = 2968.
Closed paths and improvement index, for unused square
WB 8 – 4 + 16 – 24 =4
WC 84+1616=4
YA 8 – 16 + 24 – 16 = 0
YC M16+M16=16
The most –ve opportunity cost is – 4 in the cell WB
The closed path
WB 56 
WB ← + 
16+ 
↓ ↑
25 
To From 
A 
B 
C 
Plant capacity 
W 
4
4 
8
56 
8  56 
X 
16
41 
24
0 
16
41 
82 
Y 
8
31 
16
46 
24
16 
77 

72  102  41  215 
Closed path
WA 48+16+8=4
WC 816+168+168=8
XB 24 – 16 + 8 – 16 = 0
YC 2416+168=16
Total cost of optimal solution
56 × 8+41 × 16+41× 16+31 × 8+46 × 16=2744
The opportunity cost of XB cell is zero it means there exists an alternative solution where shipping assignment will change.
WB 56 × 8 +41 × 24+41× 16 +72 × 8+5 × 16=2744.
Example 5.10. The above problem can also be solved with the help of MODI method.
K_{j} R_{j} 

K_{1} 
K_{2} 
K_{3} 


To From 
A 
B 
C 
Plant capacity 
R_{1} 
W  4
56 
8  8 
56 
R_{2} 
X  16
16 
24
66 
16 
82 
R_{3} 
Y  8  16
36 
24
41 
77 

72  102  41 
215 
For each square we use the following formula to find its cost.
R_{i}+ K_{j}= C_{ij}
R_{i} + K_{1} =4
R_{2} + K_{1} = 16
R_{2}+ K_{2} = 24
R_{3}+ K_{2} = 16
R_{3} + K_{3} = 24
R_{1} =0 then
R_{1} +K_{1} =4
0+ K_{1} =4
K_{1} =4
R_{1} + K_{1} = 16
R_{1}+4 = 16
R_{2} = 12
Similarly R3 + K_{2} = 16
R_{3} + 12 = 16
R_{3} =4
R_{2} + K_{2} = 24
12 + K_{2} = 24
K_{2} = 12
R_{3}+K_{3}=24
4 + K_{3} = 24
K_{3}=20
K_{j} R_{j} 

K_{1}=4 
K_{2}=12 
K_{3}=20 


To From 
Project A 
Project B 
Project C 
Plant capacity 
R_{1}=0 
W  4
56 
8  8 
56 
R_{2}=12 
X  16
16 
24
66 
16 
82 
R_{3}=4 
Y  8  16
36 
24
41 
77 

72  102  41 
215 
Unused squares 
C_{ij}R_{1}K_{1} 
Improvement index 
1 → 2 
C_{12}RK_{2} 8012 
4 
1 → 3 
C_{13}R_{1}K_{3} 8020 
12 
2 → 3 
C_{23}R_{2}K_{3} 161220 
16 
3 → 1 
C_{31} – R_{3} – K_{1} 844 
0 
The value of water square 23 is most ve we draw closed loop through this cell and the new table will be
K_{j} R_{j} 

K_{1}=4 
K_{2}=12 
K_{3}=20 


To From 
Project A 
Project B 
Project C 
Plant capacity 
R_{1}=0 
W  4
56 
8
4 
8
12 
56 
R_{2}=12 
X  16
16 
24
66 
16+
16 
82 
R_{3}=4 
Y  8
0 
16
36 
24
41 
77 

Project requirement  72  102  41 
215 
K_{j} R_{j} 

K_{1}=4 
K_{2}=12 
K_{3}=20 


To From 
Project A 
Project B 
Project C 
Plant capacity 
R_{1}=0 
W  4
56 
8
4 
8
+4 
56 
R_{2}=12 
X  16
16 
24
25 
16
41 
82 
R_{3}=4 
Y  8
0 
16
77 
24
12 
77 

72  102  41 
215 
Calculation of opportunity cost of water squares is as given
Unused squares 
C_{ij}=R_{i}K_{j} 
Improvement index 
1 → 2 
C_{12}R_{1}K_{2} 8012 
4 
1 → 3 
C_{13}R_{1}K_{3} 804 
+4 
3 → 1 
C_{31}R_{3}K_{1} 844 
0 
3 → 3 
C_{33}R_{3}K_{3} 2444 
+ 16 
The opportunity cost of cell I → 2 is –ve
K_{j} R_{j} 

K_{1}=4 
K_{2}=8 
K_{3}=4 


To From 
Project A 
Project B 
Project C 
Plant capacity 
R_{1}=0 
W  4
31 
8
25 
8
+4 
56 
R_{2}=12 
X  16
41 
24
4 
16
41 
82 
R_{3}=8 
Y  8
4 
16
77 
24
12 
77 

72  102  41 
215 
The value of cell 3 → 1 is – ve in the improved solution.
K_{j} R_{j} 

K_{1}=0 
K_{2}=8 
K_{3}=0 


To From 
A 
B 
C 
Plant capacity 
R_{1}=0 
W  4
+4 
8
56 
8
8 
56 
R_{2}=16 
X  16
41 
24
0 
16
41 
82 
R_{3}=8 
Y  8
31 
16
46 
24
16 
77 

72  102  41 
215 
Total cost of optimal solution
Shipping assignment 
Quantities shipped 
Limit cost 
Total cost 
WB XA XC YA YB 
56 41 41 31 46 
8 16 16 8 16 
448 656 656 258 730 



2744 
Example 5.11. A company has 4 different locations in the country and 4 sales agencies in 4 other locations in the country. The cost of production, the sale price, shipping cost in the cells of the matrix, monthly capacities and monthly requirement are given below:
Factory 
1 
2 
3 
4 
Capacity 
Cost of production 
A B C D 
7 3 4 8 
5 5 6 7 
6 4 4 6 
2 2 5 5 
10 15 20 15 
10 15 16 15 
Monthly requirement 
8 
12 
18 
22 


Selling price 
20 
22 
25 
18 


Find the monthly production and distribution schedule which will maximise profits.
Sol. By adding cost of production and shipping cost of each cell, the total cost of matrix is

I 
II 
III 
IV 
A 
17 
15 
16 
14 
B 
18 
20 
19 
17 
C 
20 
22 
20 
21 
D 
23 
22 
21 
20 
By deducting cost of production from sales price of each agency, of we get profit matrix.
Profit matrix

I 
II 
III 
IV 
A B C D 
3 2 0 3 
7 2 0 0 
9 6 5 4 
4 1 3 2 
Let us convert the matrix into a minimization matrix by deducting each element from the maximum profit i.e. Rs. 9.
Sales Factory 
S_{I} 
S_{II} 
S_{III} 
S_{IV} 
Capacity 
F_{A} F_{B} F_{C} F_{D} 
6 7 9 12 
2 7 9 9 
0 3 4 5 
5 8 12 11 
10 15 20 15 
Required 
8 
12 
18 
22 
60 
Initial Feasible Solution
Sales Factory 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
Capacity 
UP_{1} 
UP_{2} 
UP_{3} 
UP_{4} 
F_{A}  6  2
10 
0  5  10  2  –  –  – 
F_{B}  7  7  3  8
15 
15  4  4  0  – 
F_{C}  9
2 
9  4
18 
12  20  5  5
← 
0  0 
F_{D}  12
6 
9
2 
5  11
7 
15  4  4  2  2 
Req.  8  12  18  12  60  
UP_{1}  1  5↑  3  3  
UP_{2}  2  2  1  3  
UP_{3}  2  2  –  3 ↑  
UP_{4}  3 ↑  0  –  – 
The stone squares, are equal to rim requirement.
The stone squares are 7 = Rim requirement 7
The above solution is nondegenerate, we proceed to test its optimality by MODI method.
The optimality by MODI method
K_{j} R_{i} 

K_{1}=12 
K_{2}=9 
K_{3}=7 
K_{4}=11 


Ag Fact 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
Capacity 
K_{1}=7  F_{A}  6
1 
2
10 
0
0 
5
1 
10 
K_{2}=3  F_{B}  7
2 
7
1 
3
1 
8
15 
15 
K_{3}=3  F_{C}  9^{+}
2 
9
3 
4
18 
12
4 
20 
K_{4}=0  F_{D}  12
6 
9
2 
5
+ 2 
11
7 
K_{j} R_{i} 

K_{1}=10 
K_{2}=9 
K_{3}=5 
K_{4}=11 


Ag Fact 
1 
2 
3 
4 
Capacity 
K_{1}=7  A  6
3 
2
10 
0
2 
5
1 
10 
K_{2}=3  B  6
3 
2
10 
0
2 
5
1 
10 
K_{3}=1  C  9
8 
9
1 
4
12 
12
2 
20 
K_{4}=0  D  12
2 
9
2 
5
6 
11
7 
15 
8  12  18  22  60 
The final improved matrix is

S_{1} 
S_{2} 
S_{3} 
S_{4} 
Capacity 
F_{A} 
3  7
10 
9  4 
10 
F_{B} 
2  2  6  1
15 
15 
F_{C} 
0  0  5
12 
3 
20 
F_{D} 
3  0
2 
4
6 
2
7 
15 
Requirement 
8 
12 
18 
22 
60 
The opportunity cost of all water squares is +ve. So the solution is optimum
Factory → 7 Sales Agency = Total profit
F_{A}→S_{2}=7×10 =70
F_{B} →S_{4}=1 × 15 =15
F_{C} → S_{1} = 0 × 8 = 0
F_{D} → S_{3} = 5 × 12 = 60
F_{D}→S_{2} = 0 × 2 = 0
F_{D} →S_{3} = 4 × 4 = 24
F_{D} → S_{4} =2 × 7 =14
Total profit = 155/
Example 5.12 A transport corporation has trucks at 3 garages ABC in a city. The number of trucks available in each garage, the number of trucks required by each customer and the distance from garage to customer’s locations are given below:
Customers 
1 
2 
3 
4 
Availabilities 
Garages A B C 
7 8 10 
6 6 7 
9 7 8 
12 10 12 
12 8 10 
Requirement 
4 
3 
5 
8 

Just before sending the trucks, it is known that road from B to customers 2 is closed for traffic due to road block. How should the trucks be assigned to the customers in order to minimize the total distance to be covered due to road block?
Sol. The problem is unbalanced, we add dummy with 0 transportation cost and assign M prohibited cell
To From 
1 
2 
3 
4 
Dummy 
Capacity 
UP_{1} 
UP_{2} 
UP_{3} 
UP_{4} 
A 
7
4 
6
3 
9
5 
12  0 
12 
6 
1 
1 
2 
B 
8  M  7  10
8 
0 
8 
1 
1 
1 
1 
C 
10  7  8  12  0
10 
10 
7 
– 
– 
– 
Req. 
4 
3 
5 
8 
10 
30 




UP_{1} 
1 
1 
1 
2 
0 





UP_{2} 
1 
M7↑ 
1 
2 
– 





UP_{3} 
1 
– 
1 
– 
– 





UP_{4} 
1 
– 
1 
– 
– 





The stone square = 5
Rim requirement
m+n1
3+51=7
The above problem is of degeneracy
We introduce e at two cells and list its optimality by MODImethod
K_{j} R_{i} 

K_{1}=7 
K_{2}=6 
K_{3}=9 
K_{4}=12 
K_{5}=0 


1  2  3  4  0  cap.  
R_{1}=0 
A 
7
4 
6
3 
9
5 
12
0 
0

Recent Comments