IN RUSH,Operation Research , minimum spanning path, transportation Problem. Plz
ID: 3149458 • Letter: I
Question
IN RUSH,Operation Research , minimum spanning path, transportation Problem. Plz show all your work in a paper!
5. Powerco has three electric power plants that supply the needs of four cities. Each power plant can supply the following numbers of kilowatt-hours (kwh) of electricity plant 1, 30 million; plant 2, 50 million; plant 3, 40 million. The peak power demands in these cities, which occur at the same time (2 PM), are as follows (in kwh): city 1, 40 million, city 2,20 million; city 3, 30 million, city 4, 30 million. The costs of sending 1 million kwh of electricity from plant to city depend on the distance the electricity must travel. The following table summarizes the above information. 0 From City 1 City 2 City 3 Supply (million kwh Plant 1 Plant 2 Plant 3 $8 $9 $14 $6 $12 $9 $10 $13 $16 $9 $7 $5 30 50 40 Demand 40 20 30 30 million kwh Use the NW corner rule to find an initial basic feasible solution. Once the IBF solution has been found, conduct iterations to optimize the solution.Explanation / Answer
5)
Solution of Transportation Problem Using North-West Corner Method
TOTAL no. of supply constraints : 3
TOTAL no. of demand constraints : 4
Problem Table is
Here Total Demand = 110 is less than Total Supply = 120. So We add a dummy demand constraint with 0 unit cost and with allocation 10.
Now, The modified table is
The rim values for S1=30 and D1=40 are compared.
The smaller of the two i.e. min(30,40) = 30 is assigned to S1 D1
This exhausts the capacity of S1 and leaves 40 - 30 = 10 units with D1
Table-1
The rim values for S2=50 and D1=10 are compared.
The smaller of the two i.e. min(50,10) = 10 is assigned to S2 D1
This meets the complete demand of D1 and leaves 50 - 10 = 40 units with S2
Table-2
The rim values for S2=40 and D2=20 are compared.
The smaller of the two i.e. min(40,20) = 20 is assigned to S2 D2
This meets the complete demand of D2 and leaves 40 - 20 = 20 units with S2
Table-3
The rim values for S2=20 and D3=20 are compared.
The smaller of the two i.e. min(20,20) = 20 is assigned to S2 D3
This exhausts the capacity of S2 and leaves 20 - 20 = 0 units with D3
Table-4
The rim values for S3=40 and D3=0 are compared.
The smaller of the two i.e. min(40,0) = 0 is assigned to S3 D3
This meets the complete demand of D3 and leaves 40 - 0 = 40 units with S3
Table-5
The rim values for S3=40 and D4=30 are compared.
The smaller of the two i.e. min(40,30) = 30 is assigned to S3 D4
This meets the complete demand of D4 and leaves 40 - 30 = 10 units with S3
Table-6
The rim values for S3=10 and D5=10 are compared.
The smaller of the two i.e. min(10,10) = 10 is assigned to S3 D5
Table-7
Final Allocation Table is
Here, the number of allocation is equal to m + n - 1 = 3 + 5 - 1 = 7
The solution is feasible.
Total Transportation cost = 8 × 30 + 9 × 10 + 12 × 20 + 13 × 20 + 5 × 30 + 0 × 10 = 980
The minimized total transportation cost = 980
6) Solution of Transportation Problem Using Voggel's Approximation Method
TOTAL no. of supply constraints : 3
TOTAL no. of demand constraints : 4
Problem Table is
Here Demand And Supply are not equals. So Add supply or demand constraint.
Now, TOTAL no. of supply constraints : 3
Now, TOTAL no. of demand constraints : 5
Now, Problem Table is
Table-1
The maximum penalty, 7, occurs in row S2.
Allocate At [2][5] = 10
The minimum Cij in this row is C25 = 0.
The maximum allocation in this cell is 10.
It satisfy demand of D5 and adjust the supply of S2 from 50 to 40 (50 - 10 = 40).
Table-2
The maximum penalty, 4, occurs in row S3.
Allocate At [3][4] = 30
The minimum Cij in this row is C34 = 5.
The maximum allocation in this cell is 30.
It satisfy demand of D4 and adjust the supply of S3 from 40 to 10 (40 - 30 = 10).
Table-3
The maximum penalty, 5, occurs in row S3.
Allocate At [3][2] = 10
The minimum Cij in this row is C32 = 9.
The maximum allocation in this cell is 10.
It satisfy supply of S3 and adjust the demand of D2 from 20 to 10 (20 - 10 = 10).
Table-4
The maximum penalty, 6, occurs in column D2.
Allocate At [1][2] = 10
The minimum Cij in this column is C12 = 6.
The maximum allocation in this cell is 10.
It satisfy demand of D2 and adjust the supply of S1 from 30 to 20 (30 - 10 = 20).
Table-5
The maximum penalty, 4, occurs in row S2.
Allocate At [2][1] = 40
The minimum Cij in this row is C21 = 9.
The maximum allocation in this cell is 40.
It satisfy supply of S2 and adjust the demand of D1 from 40 to 0 (40 - 40 = 0).
Table-6
The maximum penalty, 10, occurs in column D3.
Allocate At [1][3] = 20
The minimum Cij in this column is C13 = 10.
The maximum allocation in this cell is 20.
It satisfy supply of S1 and adjust the demand of D3 from 20 to 0 (20 - 20 = 0).
Final Allocation Table is
Here, the number of allocation is equal to m + n - 1 = 3 + 5 - 1 = 7
The solution is feasible.
Total Transportation cost = 6 × 10 + 10 × 20 + 9 × 40 + 0 × 10 + 9 × 10 + 5 × 30 = 860
The minimized total transportation cost = 860
Now modi method starts....
Find Ui and Vj, Cij = Ui + Vj, for all occupied cells(i,j)
Substituting, U1 = 0, we get
C12 = U1 + V2 Þ 6 = 0 + V2 Þ V2 = 6 - 0 = 6
C32 = U3 + V2 Þ 9 = U3 + 6 Þ U3 = 9 - 6 = 3
C34 = U3 + V4 Þ 5 = 3 + V4 Þ V4 = 5 - 3 = 2
C13 = U1 + V3 Þ 10 = 0 + V3 Þ V3 = 10 - 0 = 10
Find Dij, Dij = Cij - (Ui + Vj), for all unoccupied cells(i,j)
D11 = C11 - (U1 + V1) = 8 - (0 + 0) = 8
D14 = C14 - (U1 + V4) = 9 - (0 + 2) = 7
D15 = C15 - (U1 + V5) = 0 - (0 + 0) = 0
D22 = C22 - (U2 + V2) = 12 - (0 + 6) = 6
D23 = C23 - (U2 + V3) = 13 - (0 + 10) = 3
D24 = C24 - (U2 + V4) = 7 - (0 + 2) = 5
D31 = C31 - (U3 + V1) = 14 - (3 + 0) = 11
D33 = C33 - (U3 + V3) = 16 - (3 + 10) = 3
D35 = C35 - (U3 + V5) = 0 - (3 + 0) = -3
DMinR : 2, DMinC : 4,DMinVal :-3
Now choose the minimum negative value from all Dij (opportunity cost) = D35 = [-3]
and draw a closed path from (S3,D5).
Loop and Plus/Minus Allocation...
Minimum allocated value among all negative position (-) on closed path = -1
Substract -1 from all (-) and Add it to all (+)
Find Ui and Vj, Cij = Ui + Vj, for all occupied cells(i,j)
Substituting, U3 = 0, we get
C32 = U3 + V2 Þ 9 = 0 + V2 Þ V2 = 9 - 0 = 9
C12 = U1 + V2 Þ 6 = U1 + 9 Þ U1 = 6 - 9 = -3
C13 = U1 + V3 Þ 10 = -3 + V3 Þ V3 = 10 - -3 = 13
C34 = U3 + V4 Þ 5 = 0 + V4 Þ V4 = 5 - 0 = 5
C35 = U3 + V5 Þ 0 = 0 + V5 Þ V5 = 0 - 0 = 0
C25 = U2 + V5 Þ 0 = U2 + 0 Þ U2 = 0 - 0 = 0
C21 = U2 + V1 Þ 9 = 0 + V1 Þ V1 = 9 - 0 = 9
Find Dij, Dij = Cij - (Ui + Vj), for all unoccupied cells(i,j)
D11 = C11 - (U1 + V1) = 8 - (-3 + 9) = 2
D14 = C14 - (U1 + V4) = 9 - (-3 + 5) = 7
D15 = C15 - (U1 + V5) = 0 - (-3 + 0) = 3
D22 = C22 - (U2 + V2) = 12 - (0 + 9) = 3
D23 = C23 - (U2 + V3) = 13 - (0 + 13) = 0
D24 = C24 - (U2 + V4) = 7 - (0 + 5) = 2
D31 = C31 - (U3 + V1) = 14 - (0 + 9) = 5
D33 = C33 - (U3 + V3) = 16 - (0 + 13) = 3
Since all Dij>=0. So final solution is arrived.
Here, the number of allocation is equal to m + n - 1 = 3 + 5 - 1 = 7
The solution is feasible.
Total Transportation cost = 6 × 10 + 10 × 20 + 9 × 40 + 0 × 10 + 9 × 10 + 5 × 30 + 0 × -1 = 860
The minimized total transportation cost = 860