For this transportation problem, we need to make the supply and
demand table first for easy interpretation of the data.
First we use Vogels Approximation Method then we use MODI method
for the optimal solution.
From this solution you can easily fill the table you have
uploaded.
D. Solution: TOTAL number of supply constraints : 2 TOTAL number of demand constraints : 4 Problem Table is D. D2 D CLIFTON SPRINGS 32 34 32 40 DANVILLE 34 30 28 38 Demand 2000 5000 3000 2000 Supply 5000 3000 D, D Here Total Demand = 12000 is greater than Total Supply = 8000. So We add a dummy supply constraint with 0 unit cost and with allocation 4000 Now, The modified table is D. D. Supply CLIFTON SPRINGS 32 34 32 40 5000 DANVILLE 34 30 28 38 3000 0 0 0 0 Demand 2000 5000 3000 2000 Sdn 4000 Problem is Maximization, so convert it to minimization by subtracting all the elements from max element (40) D. D2 D: D: Supply CLIFTON SPRINGS 8 6 8 0 5000 DANVILLE 6 10 12 2 3000 durny 40 40 4000 Demand 2000 5000 3000 2000 S
Table-1 D D2 D. D. CLIFTON SPRINGS 8 6 8 0 Supply Row Penalty 5000 6 = 6 - 0 3000 4= 6-2 DANVILLE 6 10 12 2 Saumoତ 40 40 40 4000 0 = 40 - 40 40 2000 Demand 5000 3000 2000 Column Penalty 2 = 8 -6 4 = 10 -6 4 = 12 - 8 2 = 2 - 0 The maximum penalty, 6, occurs in row CLIFTON SPRINGS. The minimum e; in this row is C14 = 0. The maximum allocation in this cell is min(5000,2000) = 2000. It satisfy demand of D. and adjust the supply of CLIFTON SPRINGS from 5000 to 3000 (5000 - 2000 = 3000). Table-2 D D2 D 8 6 8 CLIFTON SPRINGS DANVILLE 24 Supply Row Penalty 0(2000) 3000 2 = 8 - 6 3000 4 = 10 - 6 40 4000 0 = 40 - 40 6 10 12 Sdum 40 40 40 Demand 2000 5000 3000 0 Column Penalty 2 = 8 - 6 4 = 10 - 6 4 = 12 - 8 The maximum penalty, 4, occurs in column Dz. The minimum c; in this column is C12 = 6. The maximum allocation in this cell is min (3000,5000) = 3000. It satisfy supply of CLIFTON SPRINGS and adjust the demand of D, from 5000 to 2000 (5000 - 3000 = 2000).
Table-3 D. D3 24 D2 643000) Supply Row Penalty 0 CLIFTON SPRINGS 8 8 942400) 2 DANVILLE 6 10 12 3000 4 = 10-6 Scuong 40 40 40 4000 0 = 40 - 40 45 0 2000 2000 3000 Demand Column Penalty 34 = 40 - 6 30 = 40 - 10 28 = 40 - 12 The maximum penalty, 34, occurs in column D. The minimum cj in this column is C21 = 6. The maximum allocation in this cell is min(3000,2000) = 2000. It satisfy demand of D, and adjust the supply of DANVILLE from 3000 to 1000 (3000 - 2000 = 1000). Table-4 0. D D 613000) 10 04 0124001 CLIFTON SPRINGS 요. Supply Row Penalty 0 1000 2 = 12 - 10 DANVILLE 6(2000) 12 2 Sammy 4p 40 40 40 4000 0 = 40 - 40 Demand 0 2000 3000 0 Column Penalty 30 = 40 - 10 28 = 40 - 12 The maximum penalty, 30, occurs in column D2 The minimum c,; in this column is c22 = 10. The maximum allocation in this cell is min(1000,2000) = 1000. It satisfy supply of DANVILLE and adjust the demand of D, from 2000 to 1000 (2000 - 1000 = 1000).
Table-5 Supply Row Penalty CLIFTON SPRINGS 0424007 0 DANVILLE : D2 D 673000) 8 6120001 10110001 12 4 40 40 1000 3000 0 Sduomeny 40 4000 0 = 40 - 40 0 Demand Column Penalty 40 40 The maximum penalty, 40, occurs in column D. The minimum cj in this column is C33 = 40. The maximum allocation in this cell is min(4000,3000) = 3000. It satisfy demand of D, and adjust the supply of Sa from 4000 to 1000 (4000 - 3000 = 1000). dummy Table-6 0. D2 23 De Supply Row Penalty CLIFTON SPRINGS 9424001 0 DANVILLE 613000) 6124001 1010001 40 40 12 0 Samo 40(3000) 40 1000 40 Demand 0 1000 0 0 Column Penalty 40 The maximum penalty, 40, occurs in rows dummy The minimum c, in this row is C32 = 40.
The maximum allocation in this cell is min(1000,1000) = 1000. It satisfy supply of Saummy and demand of Dz. D Supply 0(2000) 5000 2 3000 Row Penalty 6|2|--I--I--I-- 44|4|2|--I- 0 0 0 0 0 401 40 4000 Initial feasible solution is D D2 D: CLIFTON SPRINGS 8 6(3000) 8 DANVILLE 6(2000) 10(1000) 12 dummy 40 40(1000) 40(3000) Demand 2000 5000 3000 2 4 4 4 4 Column 34 30 28 Penalty 30 28 40 40 40 2000 ITTIIN Allocations in the original problem D. D2 D D Supply CLIFTON SPRINGS 32 34 (3000) 32 40 (2000) 5000 DANVILLE 34 (2000) 30 (1000) 28 38 3000 Sd duty 0 0 (1000) O (3000) O 4000 Demand 2000 5000 3000 2000 The maximum profit = 34 x 3000 + 40 x 2000 - 34 x 2000 – 30 1000 + 0 x 1000 - 0x 3000 = 280000 Here, the number of allocated cells = 6 is equal to m+n-1 = 3+4 -1 = 6 : This solution is non-degenerate
Optimality test using modi method... Allocation Table is D. D2 D: DA Supply CLIFTON SPRINGS 8 6 (3000) 8 0 (2000) 5000 DANVILLE 6 (2000) 10 (1000) 12 2 3000 Salemty 40 40 (1000) 40 (3000) 40 4000 Demand 2000 5000 3000 2000 Iteration-1 of optimality test 1. Find u and v, for all occupied cells(i)), where y = u; + v; 1. Substituting, v, - 0, we get 2.C12 = 4 + 12 = U = C12-v2 = 4 = 6-0 = u = 6 3.C14 = 4y + 14 = 14 = C14 - 4 = 4 = 0 - 6 = 14 = -6 4.C22 = U2 + 12 = U2 = C22 - 12 = 12 = 10 - 0 = uz = 10 5.621 = uz + v, = =C21 - uz = v= 6 - 10 = v= .4 6.632 = Uz + 12 = 43 = C32 - 12 = uz = 40 -0 = uz = 40 7.653 = Uz + V3 = vz = C33 - 4; v; = 40 - 40 = v = 0 D D2 D: DA Supply u CLIFTON SPRINGS 8 6 (3000) 8 0 (2000) 5000 DANVILLE 6 (2000) 10 (1000) 12 2 3000 Sd duary 40 40 (1000) 40 (3000) 40 4000 u; = 40 2 = 10 Demand 2000 5000 3000 2000 = V1 - 4 12 = 0 V = -6
2. Find dig for all unoccupied cells(is), where dy = 65-(4-vj) 1.2.1 = C11-(27+ v) = 8 - (6 - 4) = 6 2.0,3 = C13- (u + vz) = 8 -(6-0) = 2 3.0,3 = C23 - (uz + v3 ) = 12 - (10+C) = 2 4.034 = C24 - (uz +v4) = 2 -(10 - 6) = -2 5. ds1 = C31-(uz + V .- (uz + v :) = 40 - (40 - 4) = 4 6. d34 = 634 - (uz +va) = 40 - (40 - 6) = 6 D. D2 D D. Supply u; CLIFTON SPRINGS 8 [6] 6 (3000) 8 [2] 0 (2000) 5000 DANVILLE 6 (2000) 10 (1000) 12 [2] 2 [-2] 3000 40 [4] = 40 40 (1000) 40 (3000) 40 [6] 4000 Demand 2000 5000 3000 2000 = 10 Sawy =- .4 930 V4 6 3. Now choose the minimum negative value from all d; (opportunity cost) = 224 = [-2] and draw a closed path from DANVILLED Closed path is DANVILLEDA DANVILLED, - CLIFTON SPRINGSD, CLIFTON SPRINGSD
Closed path and plus/minus sign allocation.... D D2 D D. Supply 4: CLIFTON SPRINGS 8 [6] 6 (3000) (+) 8 [2] 0 (2000) (-) 5000 DANVILLE 6 (2000) 10 (1000) (-) 12 [2] 2 [-2] (+) 3000 40 [4] 40 (1000) 40 (3000) 40 [6] 4000 = 40 Demand 2000 5000 3000 2000 U2 = 10 S dorty us D: 4. Minimum allocated value among all negative position (-) on closed path = 1000 Substract 1000 from all (-) and Add it to all (+) D. D2 D Supply CLIFTON SPRINGS 8 6 (4000) 8 0 (1000) 5000 DANVILLE 6 (2000) 10 12 2 (1000) 3000 40 40 (1000) 40 (3000) 40 4000 Demand 5000 3000 2000 Saumor 2000 5. Repeat the step 1 to 4, until an optimal solution is obtained. Iteration-2 of optimality test 1. Find u and v, for all occupied cells(i)), where cn = u; + v; 1. Substituting, uy = 0, we get 2. Cl2 = 2+ = + = 12 - 4 = v = 6 - 0 = = 6 3.C32 = Uz + 12 = 3 = C32 - 12 uz = 40 - 6 = uz = 34 4.C33 = 4; + V3 = 13 = 33 - 4; v; = 40 - 34 = va = 6
5.C14 = 4 + 14 = V4 = C14 - 4, = V4 = 0 - 0 = V4 = 0 6.674 = uz+v4 = uz = C24 - 14 = uz = 2-0 = uy = 2 7.C21 = uz + V1 - C21 - U2 = v= 6-2 = x = 4 =0 D. D2 D D. Supply u CLIFTON SPRINGS 8 6 (4000) 8 0 (1000) 5000 DANVILLE 6 (2000) 10 12 2 (1000) 3000 40 40 (1000) 40 (3000) 40 4000 Demand 2000 5000 3000 2000 222 Sdummy 43 = 34 Vj 7 = 4 VA = 0 2. Find dy for all unoccupied cells(i.), where dy=y- (+ vj) 1.0.1 =C11-(2, + v1) = 8 - (0 + 4) = 4 2.0,3 = C13-(x + v) = 8 - (0 - 6) = 2 3.0,2 = C22 - (uz + v2) = 10 - (2 + 6) = 2 4. 0,3 = 623-(uz + v) - 12 - (2 + 6) = 4 5. ds= 031-(uz + x) = 40 - (34 + 4) = 2 6. d4 = 34 - - (uz +v4) = 40 - (34+0) = 6
y = 0 D. D2 D D. Supply u CLIFTON SPRINGS 8 [4] 6 (4000) 8 [2] 0 (1000) 5000 DANVILLE 6 (2000) 10 [2] 12 (4) 2 (1000) 3000 40 (1000) 40 (3000) 40 [6] 4000 43 = 34 Demand 2000 5000 3000 2000 42 = 2 SNE 40 [2] *1 = 4 = Since all do 20. So final optimal solution is arrived. D. D2 D: D. Supply CLIFTON SPRINGS 8 6 (4000) 8 0 (1000) 5000 DANVILLE 6 (2000) 10 12 2 (1000) 3000 dury 40 40 (1000) 40 (3000) 40 4000 Demand 2000 5000 3000 2000 D2 Allocations in the original problem D. D: D Supply CLIFTON SPRINGS 32 34 (4000) 32 40 (1000) 5000 DANVILLE 34 (2000) 30 28 38 (1000) 3000 0 0 (1000) O (3000) 0 4000 Demand 2000 5000 3000 2000 Sdumne The maximum profit = 34 x 4000 + 40 x 1000 - 34 x 2000 - 38 x 1000 + 0 x 1000 - 0x 3000 = 282000