TRANSPORTATION METHOD
TESTING FOR DEGENERACY
TESTING FOR OPTIMALITY
IMPROVING THE SOLUTION USING MODI METHOD
OBTAINING THE INITIAL SOLUTION
• WE HAVE DISCUSSED 3 METHODS OF
OBTAINING THE INITIAL SOLUTION
• NWC, LCM, VAM
• TO RECAPITULATE THE INITIAL SOLUTION
USING EACH OF THE ABOVE METHODS WAS
OBTAINED
• IT WAS OBSERVED THAT THE TRANSPORT
SCHEDULE AND THE ASSOCIATED COST WERE
DIFFERENT UNDER EACH METHOD
STEP 2
IT HAS TO BE PERFORMED BEFORE TESTING OPTIMALITY
MUST BE REPEATED AFTER EVERY ITERATION
TESTING FOR DEGENERACY
TESTING DEGENERACY
• FOR A TRANSPORTATION PROBLEM WITH ‘m’
ROWS AND ‘n’ COLUMNS;
– THE NUMBER OF OCCUPIED CELLS SHOULD NOT
BE LESS THAN (m + n) -1
– OCCUPIED CELLS MEAN THOSE CELLS IN THE GRID
WHERE SOME QUANTITY HAS BEEN ASSIGNED
FOR TRANSPORTATION
– IN CASE THE ABOVE CONDITION IS SATISFIED THE
SOLUTION IS SAID TO BE ‘NOT DEGENERATE’
NORTH WEST CORNER METHOD
TO
P Q R S SUPPLY
FROM
[180] [150] [170] []
A 12 10 12 13 500
[] [] [180] [120]
B 7 11 8 14 300
[] [] [] [200]
C 6 16 11 7 200
DEMAND 180 150 350 320 1000
TOTAL COST = 12x180 + 10x150 + 12x170 + 8x180 + 14x120 + 7x200 = Rs 10,220
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-P; A-Q; A-R; B-R; B-S; AND C-S
THUS, THE SOLUTION IS NOT DEGENERATE
LEAST COST METHOD
TO
P Q R S SUPPLY
FROM
[] [150] [50] [300]
A 12 10 12 13 500
[] [] [300] []
B 7 11 8 14 300
[180] [] [] [20]
C 6 16 11 7 200
DEMAND 180 150 350 320 1000
TOTAL COST = 10x150 + 12x50 + 13x300 + 8x300 + 6x180 + 7x20 = Rs 9,620
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-Q; AR; A-S; BR; BS; AND C-P
THUS, THE SOLUTION IS NOT DEGENERATE
VOGEL’S APPROXIMATION METHOD
TO
P Q R S SUPPLY
FROM
[] [150] [230] [120]
A 12 10 12 13 500
[180] [] [120] []
B 7 11 8 14 300
[] [] [] [200]
C 6 16 11 7 200
DEMAND 180 150 350 320 1000
TOTAL COST = 10x150 + 12x230 + 13x120 + 7x180 + 8x120 + 7x200 = Rs 9,440
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-Q; A-R; A-S; B-P; B-R; AND C-S
THUS, THE SOLUTION IS NOT DEGENERATE
STEP 3: NWC
MODIFIED DISTRIBUTION METHOD
TO CHECK IF LOWERING OF COST IS POSSIBLE
TESTING OPTIMALITY
TESTING OPTIMALITY
• ONLY MODIFIED DISTRIBUTION METHOD TO BE USED
• USES OCCUPIED CELLS TO DETERMINE THE
OPPORTUNITY COSTS
• CALCULATE FOR EACH ROW A Ui VALUE, AND FOR
EACH COLUMN A Vj VALUE
• AS A DEFAULT, Ui VALUE OF THE FIRST ROW IS
ASSUMED TO BE ZERO
• THE OTHER VALUES CAN BE CALCULATED AS:
Cij = Ui + Vj
WHERE,
Cij IS THE TRANPORTATION COST OF AN OCCUPIED CELL
Ui & Vj ARE THE RESPECTIVE OPPORTUNITY COST
NORTH WEST CORNER METHOD
TO
P Q R S SUPPLY Ui
FROM
[180] [150] [170] []
A 12 10 12 13 500 0
[] [] [180] [120]
B 7 11 8 14 300 -4
[] [] [] [200]
C 6 16 11 7 200 - 11
DEMAND 180 150 350 320 1000
Vj
12 10 12 18
TESTING OPTIMALITY
• AFTER DETERMINING THE Ui AND Vj VALUES, CALCULATE
FOR EVERY EMPTY CELL THE OPPORTUNITY COST OF NOT
USING THAT PARTICULAR ROUTE AS:
Δij = Ui + Vj – Cij
WHERE,
Cij IS THE TRANPORTATION COST OF THE UNOCCUPIED CELL
Ui & Vj ARE THE RESPECTIVE OPPORTUNITY COST
• IF Δij FOR ALL EMPTY CELLS IS EITHER ZERO OR NEGATIVE,
THE SOLUTION IS OPTIMAL
• IF Δij FOR ONE OR MORE EMPTY CELL(S) IS POSITIVE, THE
SOLUTION IS NOT OPTIMAL
TESTING OPTIMALITY
EMPTY CELL Ui Vj Cij Δij = Ui + Vj – Cij
AS 0 18 13 5
BP -4 12 7 1
BQ -4 10 11 -5
CP - 11 12 6 -5
CQ - 11 10 16 -17
CR - 11 12 11 -10
SINCE Δij FOR A-S AND B-P IS POSITIVE, THE SOLUTION IS NOT OPTIMAL
THE LARGEST OPPORTUNITY COST OCCURS IN CELL A-S (5)
IMPROVEMENT IN SOLUTION WILL BE MADE USING A CLOSED LOOP
THE CLOSED LOOP WILL BEGIN FROM CELL A-S
CLOSED LOOP
• A CLOSED LOOP IS DRAWN STARTING WITH AN
EMPTY CELL AND MOVING CLOCKWISE, TURNING
AT RIGHT ANGLES EITHER
HORIZONTALLY/VERTICALLY, TILL WE REACH BACK
TO THE STARTING CELL
• EXCEPT THE STARTING CELL, ALL OTHER CELLS IN
A CLOSED LOOP MUST BE OCCUPIED CELLS
• THE CELLS IN THE CLOSED LOOP ARE MARKED
ALTERNATELY WITH ‘+’ AND ‘-’ SIGNS WHICH
DEPICT ADDITION/DELETION OF QUANTITY
TRACING THE CLOSED LOOP
TO
P Q R S SUPPLY
FROM
[180] [150] [170] []
A 12 10 12 13 500
- +
[] [] [180] [120]
B 7 11 8 14 300
+ -
[] [] [] [200]
C 6 16 11 7 200
DEMAND 180 150 350 320 1000
RULES TO TRACE A CLOSED LOOP
• THE LOOP IS STARTED FROM THE EMPTY CELL WHICH
NEEDS IMPROVEMENT (HIGHEST POSITIVE Δij )
• THE NUMBER OF CELLS IN THE LOOP ARE ALWAYS EVEN
AND THE MINIMUM NUMBER OF CELLS IN THE LOOP IS 4
• ALL THE CELLS IN THE CLOSED LOOP ARE OCCUPIED
CELLS EXCEPT THE STARTING CELL
• THE MOVEMENT IN THE LOOP IS CLOCKWISE AND THE
TURNS ARE MADE AT RIGHT ANGLES HORIZONTALLY AOR
VERTICALLY
RULES TO TRACE A CLOSED LOOP
• PLUS(+) AND MINUS(-) SIGNS ARE PLACED ALTERNATELY
IN EACH CELL OF THE LOOP, STARTING WITH A PLUS SIGN
IN THE STARTING CELL
• THE LOOP TERMINATES ONLY WHEN THE STARTING CELL
IS REACHED AFTER TRACING THE LOOP
• THE OBJECTIVE OF THIS CLOSED LOOP IS TO ALLOCATE
SOME QUANTITY IN THE STARTING CELL
• THE QUANTITY ALLOCATED WILL BE THE LEAST
QUANTITY IN ANY OF THE OCCUPIED CELLS WITH A
NEGATIVE SIGN
CLOSED LOOP DRAWN
• THE CLOSED LOOP TRACED IS:
A-S B-S B-R A-R
THUS, THE SIGNS ARE PLACED AS:
A-S (+ ); B-S ( - ); B-R (+); A-R (- )
AND THE QUANTITY THAT WILL BE ALLOCATED IN
A-S IS 120 UNITS
EFFECTIVELY THE IMPROVED ALLOCATION WILL BE
AS SHOWN IN THE NEXT SLIDE
IMPROVED SOLUTION
TO
P Q R S SUPPLY Ui
FROM
[180] [150] [50] [120]
A 12 10 12 13 500 0
[] [] [300] []
B 7 11 8 14 300 -4
[] [] [] [200]
C 6 16 11 7 200 -6
DEMAND 180 150 350 320 1000
Vj 12 10 12 13
TOTAL COST = 12x180 + 10x150 + 12x50 + 13x120 + 8x300 + 7x200 = Rs 9,620
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-P; A-Q; A-R; B-R; B-S; AND C-S
THUS, THE OBTAINED SOLUTION IS NOT DEGENERATE
TESTING OPTIMALITY
EMPTY CELL Ui Vj Cij Δij = Ui + Vj – Cij
BP -4 12 7 1
BQ -4 10 11 -5
BS -4 13 14 -5
CP -6 12 6 0
CQ -6 10 16 -12
CR -6 12 11 -5
SINCE Δij FOR B-P IS POSITIVE, THE SOLUTION IS NOT OPTIMAL
THE LARGEST OPPORTUNITY COST OCCURS IN CELL B-P (1)
IMPROVEMENT IN SOLUTION WILL BE MADE USING A CLOSED LOOP
THE CLOSED LOOP WILL BEGIN FROM CELL B-P
TRACING THE CLOSED LOOP
TO
P Q R S SUPPLY Ui
FROM
[180] [150] [50] [120]
A 12 10 12 13 500 0
- +
[] [] [300] []
B 7 11 8 14 300 -4
+ -
[] [] [] [200]
C 6 16 11 7 200 -6
DEMAND 180 150 350 320 1000
Vj 12 10 12 13
CLOSED LOOP DRAWN
• THE CLOSED LOOP TRACED IS:
B-P A-P A-R B-R
THUS, THE SIGNS ARE PLACED AS:
B-P (+ ); A-P ( - ); A-R (+); B-R (- )
AND THE QUANTITY THAT WILL BE ALLOCATED IN
B-P IS 180 UNITS
EFFECTIVELY THE IMPROVED ALLOCATION WILL BE
AS SHOWN IN THE NEXT SLIDE
IMPROVED SOLUTION
TO
P Q R S SUPPLY Ui
FROM
[] [150] [230] [120]
A 12 10 12 13 500 0
[180] [] [120] []
B 7 11 8 14 300 -4
[] [] [] [200]
C 6 16 11 7 200 -6
DEMAND 180 150 350 320 1000
Vj 11 10 12 13
TOTAL COST = 10x150 + 12x230 + 13x120 + 7x180 + 8x120 + 7x200 = Rs 9,440
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-P; A-Q; A-R; B-R; B-S; AND C-S
THUS, THE OBTAINED SOLUTION IS NOT DEGENERATE
TESTING OPTIMALITY
EMPTY CELL Ui Vj Cij Δij = Ui + Vj – Cij
AP 0 11 12 -1
BQ -4 10 11 -5
BS -4 13 14 -5
CP -6 11 6 -1
CQ -6 10 16 -12
CR -6 12 11 -5
SINCE Δij FOR ALL EMPTY CELLS IS NEGATIVE, THE SOLUTION IS OPTIMAL
OPTIMAL SOLUTION
• OPTIMAL TRANSPORTATION COST IS Rs 9,440
• OPTIMAL TRANSPORTATION SCHEDULE IS
FROM TO QUANTITY COST PER UNIT TOTAL
A Q 150 10 1,500
A R 230 12 2,760
A S 120 13 1,560
B P 180 7 1,260
B R 120 8 960
C S 200 7 1,400
TOTAL 9,440
STEP 3: LCM
MODIFIED DISTRIBUTION METHOD
TO CHECK IF LOWERING OF COST IS POSSIBLE
TESTING OPTIMALITY
LEAST COST METHOD
TO
P Q R S SUPPLY Ui
FROM
[] [150] [50] [300]
A 12 10 12 13 500 0
+ -
[] [] [300] []
B 7 11 8 14 300 -4
+ -
[180] [] [] [20]
C 6 16 11 7 200 -6
- +
DEMAND 180 150 350 320 1000
Vj 12 10 12 13
TOTAL COST = 10x150 + 12x50 + 13x300 + 8x300 + 6x180 + 7x20 = Rs 9,620
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-Q; AR; A-S; BR; BS; AND C-P
THUS, THE SOLUTION IS NOT DEGENERATE
TESTING OPTIMALITY
EMPTY CELL Ui Vj Cij Δij = Ui + Vj – Cij
AP 0 12 12 0
BP -4 12 7 1
BQ -4 10 11 -5
BS -4 13 14 -5
CQ -6 10 16 -12
CR -6 12 11 -5
SINCE Δij FOR B-P IS POSITIVE, THE SOLUTION IS NOT OPTIMAL
THE LARGEST OPPORTUNITY COST OCCURS IN CELL B-P (1)
IMPROVEMENT IN SOLUTION WILL BE MADE USING A CLOSED LOOP
THE CLOSED LOOP WILL BEGIN FROM CELL B-P
IMPROVED SOLUTION
TO
P Q R S SUPPLY Ui
FROM
[] [150] [230] [120]
A 12 10 12 13 500 0
[180] [] [120] []
B 7 11 8 14 300 -4
[] [] [] [200]
C 6 16 11 7 200 -6
DEMAND 180 150 350 320 1000
Vj 11 10 12 13
TOTAL COST = 10x150 + 12x230 + 13x120 + 7x180 + 8x120 + 7x200 = Rs 9,440
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-P; A-Q; A-R; B-R; B-S; AND C-S
THUS, THE OBTAINED SOLUTION IS NOT DEGENERATE
TESTING OPTIMALITY
EMPTY CELL Ui Vj Cij Δij = Ui + Vj – Cij
AP 0 11 12 -1
BQ -4 10 11 -5
BS -4 13 14 -5
CP -6 11 6 -1
CQ -6 10 16 -12
CR -6 12 11 -5
SINCE Δij FOR ALL EMPTY CELLS IS NEGATIVE, THE SOLUTION IS OPTIMAL
OPTIMAL SOLUTION
• OPTIMAL TRANSPORTATION COST IS Rs 9,440
• OPTIMAL TRANSPORTATION SCHEDULE IS
FROM TO QUANTITY COST PER UNIT TOTAL
A Q 150 10 1,500
A R 230 12 2,760
A S 120 13 1,560
B P 180 7 1,260
B R 120 8 960
C S 200 7 1,400
TOTAL 9,440
STEP 3: VAM
MODIFIED DISTRIBUTION METHOD
TO CHECK IF LOWERING OF COST IS POSSIBLE
TESTING OPTIMALITY
VOGEL’S APPROXIMATION METHOD
TO
P Q R S SUPPLY Ui
FROM
[] [150] [230] [120]
A 12 10 12 13 500 0
[180] [] [120] []
B 7 11 8 14 300 -4
[] [] [] [200]
C 6 16 11 7 200 -6
DEMAND 180 150 350 320 1000
Vj 11 10 12 13
TOTAL COST = 10x150 + 12x230 + 13x120 + 7x180 + 8x120 + 7x200 = Rs 9,440
m = 3; n = 4. THUS, (m + n) -1 = 6.
ALSO, THE 6 OCCUPIED CELLS ARE A-Q; AR; A-S; B-P; B-R; AND C-S
THUS, THE SOLUTION IS NOT DEGENERATE
TESTING OPTIMALITY
EMPTY CELL Ui Vj Cij Δij = Ui + Vj – Cij
AP 0 11 12 -1
BQ -4 10 11 -5
BS -4 13 14 -5
CP -6 11 6 -1
CQ -6 10 16 -12
CR -6 12 11 -5
SINCE Δij FOR ALL EMPTY CELLS IS NEGATIVE, THE SOLUTION IS OPTIMAL AND UNIQUE
OPTIMAL SOLUTION
• OPTIMAL TRANSPORTATION COST IS Rs 9,440
• OPTIMAL TRANSPORTATION SCHEDULE IS
FROM TO QUANTITY COST PER UNIT TOTAL
A Q 150 10 1,500
A R 230 12 2,760
A S 120 13 1,560
B P 180 7 1,260
B R 120 8 960
C S 200 7 1,400
TOTAL 9,440
