Degeneracy in transportation problem in Operational Research are explained below Show Step 3: Check for degeneracy In a standard transportation problem with m sources of supply and n demand destinations, the test of optimality of any feasible solution requires allocations in m + n – 1 independent cells. If the number of allocations is short of the required number, then the solution is said to be degenerate. If number of allocations, N = m + n – 1, then degeneracy does not exist. Go to Step 5. Step 4: Resolving degeneracy In order to resolve degeneracy, the conventional method is to allocate an infinitesimally small amount e to one of the independent cells i.e., allocate a small positive quantity e to one or more unoccupied cell that have lowest transportation costs, so as to make m + n – 1 allocations (i.e., to satisfy the condition N = m + n – 1). In other words, the allocation of e should avoid a closed loop and should not have a path. Once this is done, the test of optimality is applied and, if necessary, the solution is improved in the normal was until optimality is reached. The following table shows independent allocations. Independent Allocations  The following Tables 6.10 (a), (b) and (c) show non-independent allocations. Non-Independent Allocations Optimal Solution Step 5: Test for optimality The solution is tested for optimality using the Modified Distribution (MODI) method (also known as U-V method). An optimal solution is one in which there are no other transportation routes that would reduce the total transportation cost, for which we have to evaluate each unoccupied cell in the table in terms of opportunity cost. In this process, if there is no negative opportunity cost, and the solution is an optimal solution. (i) Row 1, row 2,…, row i of the cost matrix are assigned with variables u1, u2, …,ui and the column 1, column 2,…, column j are assigned with variables v1, v2, …,vj respectively. (ii) Initially, assume any one of U Transportation Model i values as zero and compute the values for u1, u2, …,ui and v1, v2, …,vj by applying the formula for occupied cell. For occupied cells, cij + ui + vj = 0
(iii) Obtain all the values of cij for unoccupied cells by applying the formula for unoccupied cell. For unoccupied cells,
Step 6: Procedure for shifting of allocations Select the cell which has the most negative C ij value and introduce a positive quantity called ‘q’ in that cell. To balance that row, allocate a ‘– q’ to that row in occupied cell. Again, to balance that column put a positive ‘q’ in an occupied cell and similarly a ‘-q’ to that row. Connecting all the ‘q’s and ‘-q’s, a closed loop is formed. Two cases are represented in Table In Table if all the q allocations are joined by horizontal and vertical lines, a closed loop is obtained. The set of cells forming a closed loop is CL = {(A, 1), (A, 3), (C, 3), (C, 4), (E, 4), (E, 1), (A, 1)} The loop in Table 6.11(b) is not allowed because the cell (D3) appears twice. Showing Closed Loop
Conditions for forming a loop (i) The start and end points of a loop must be the same. (ii) The lines connecting the cells must be horizontal and vertical. (iii) The turns must be taken at occupied cells only. (iv) Take a shortest path possible (for easy calculations). Remarks on forming a loop (i) Every loop has an even number of cells and at least four cells (ii) Each row or column should have only one ‘+’ and ‘–’ sign. (iii) Closed loop may or may not be square in shape. It can also be a rectangle or a stepped shape. (iv) It doesn’t matter whether the loop is traced in a clockwise or anticlockwise direction. Take the most negative '– q' value, and shift the allocated cells accordingly by adding the value in positive cells and subtracting it in the negative cells. This gives a new improved table. Then go to step 5 to test for optimality. Step 7: Calculate the Total Transportation Cost. Since all the C ij values are positive, optimality is reached and hence the present allocations are the optimum allocations. Calculate the total transportation cost by summing the product of allocated units and unit costs. Example : The cost of transportation per unit from three sources and four destinations are given in the following table Obtain the initial basic feasible solutions using the following methods. (i) North-west corner method (ii) Least cost method (iii) Vogel’s approximation method Transportation Model Solution: The problem given in Table is a balanced one as the total sum of supply is equal to the total sum of demand. The problem can be solved by all the three methods. North-West Corner Method: In the given matrix, select the North-West corner cell. The North-West corner cell is (1,1) and the supply and demand values corresponding to cell (1,1) are 250 and 200 respectively. Allocate the maximum possible value to satisfy the demand from the supply. Here the demand and supply are 200 and 250 respectively. Hence allocate 200 to the cell (1,1) as shown in Table. Conditions for forming a loop (i) The start and end points of a loop must be the same. (ii) The lines connecting the cells must be horizontal and vertical. (iii) The turns must be taken at occupied cells only. (iv) Take a shortest path possible (for easy calculations). Remarks on forming a loop (i) Every loop has an even number of cells and at least four cells (ii) Each row or column should have only one ‘+’ and ‘–’ sign. (iii) Closed loop may or may not be square in shape. It can also be a rectangle or a stepped shape. (iv) It doesn’t matter whether the loop is traced in a clockwise or anticlockwise direction. Take the most negative '– q' value, and shift the allocated cells accordingly by adding the value in positive cells and subtracting it in the negative cells. This gives a new improved table. Then go to step 5 to test for optimality. Allocated 200 to the Cell (1, 1) Now, delete the exhausted column 1 which gives a new reduced table as shown in the following tables. Again repeat the steps. Exhausted Column 1 Deleted Table after deleting Row 1 Exhausted Row 1 Deleted Table after deleting column 2 Exhausted Column 2 Deleted Finally, after deleting Row 2, we have Exhausted Row 2 Deleted Now only source 3 is left. Allocating to destinations 3 and 4 satisfies the supply of 500. The initial basic feasible solution using North-west corner method is shown in the following table Initial Basic Feasible Solution Using NWC Method Transportation cost = (4 × 200) + (2 × 50) + (7 × 350) + (5 × 100) +(2 × 300) + (1 × 300) = 800 + 100 + 2450 + 500 + 600 + 300 = Rs. 4,750.00 Least Cost Method Select the minimum cost cell from the entire table, the least cell is (3,4). The corresponding supply and demand values are 500 and 300 respectively. Allocate the maximum possible units. The allocation is shown in Table. Allocation of Maximum Possible Units From the supply value of 500, the demand value of 300 is satisfied. Subtract 300 from the supply value of 500 and subtract 300 from the demand value of 300. The demand of destination 4 is fully satisfied. Hence, delete the column 4; as a result we get, the table as shown in the following table. Exhausted Column 4 Deleted Now, again take the minimum cost value available in the existing table and allocate it with a value of 250 in the cell (1,2). Exhausted Row 1 Deleted In the reduced table, the minimum value 3 exists in cell (2,1) and (3,3), which is a tie. If there is a tie, it is preferable to select a cell where maximum allocation can be made. In this case, the maximum allocation is 200 in both the cells. Choose a cell arbitrarily and allocate. The cell allocated in (2,1) is shown in Table. The reduced matrix is shown in Table. Reduced Matrix Now, deleting the exhausted demand row 3, we get the matrix as shown in the following table Exhausted Row 3 Deleted The initial basic feasible solution using least cost method is shown in a single table Initial Basic Feasible Solution Using LCM Method Transportation Cost = (2 × 250)+ (3 × 200) + (7 × 150) + (5 × 100)+ ( 3 × 200) +(1 × 300) Vogel’s Approximation Method (VAM): The penalties for each row and column are calculated (steps given on pages 176-77) Choose the row/column, which has the maximum value for allocation. In this case there are five penalties, which have the maximum value 2. The cell with least cost is Row 3 and hence select cell (3,4) for allocation. The supply and demand are 500 and 300 respectively and hence allocate 300 in cell (3,4) as shown in Table Penalty Calculation for each Row and Column Since the demand is satisfied for destination 4, delete column 4. Now again calculate the penalties for the remaining rows and columns. Exhausted Column 4 Deleted In the following table shown, there are four maximum penalties of values which is 2. Selecting the least cost cell, (1,2) which has the least unit transportation cost 2. The cell (1, 2) is selected for allocation as shown in the previous table. The following table shows the reduced table after deleting row l. Row 1 Deleted After deleting column 1 we get the table as shown in the table below. Column 1 Deleted Finally we get the reduced table as shown in the following table. Final Reduced Table The initial basic feasible solution is shown in the following table. Initial Basic Feasible Solution Transportation cost = (2 × 250) + (3 × 200) + (5 × 250) + (4 × 150) + (3 × 50) +(1 × 300) = 500 + 600 + 1250 + 600 + 150 + 300 = Rs. 3,400.00 Example : Find the initial basic solution for the transportation problem and hence solve it. Transportation Problem Solution: Vogel’s Approximation Method (VAM) is preferred to find initial feasible solution. Step 1: The given transportation problem is a balanced one as the sum of supply equals to sum of demand. Step 2: The initial basic solution is found by applying the Vogel’s Approximation method and the result is shown in the following table. Initial Basic Solution Found by Applying VAM Step 3: Calculate the Total Transportation Cost. Initial Transportation cost = (2 × 250) + (3 × 200) + (5 × 250) + (4 × 150) + (3 × 50) + (1 × 300) = 500 + 600 + 1250 + 600 + 150 + 300 = Rs. 3,400 Step 4: Check for degeneracy. For this, verify the condition, Number of allocations, N= m + n – 1 6 = 3 + 4 – 1 6 = 6 Since the condition is satisfied, degeneracy does not exist. Step 5: Test for optimality using modified distribution method. Compute the values of U i and vj for rows and columns respectively by applying the formula for occupied cells. cij+ui+vj = 0 Then, the opportunity cost for each unoccupied cell is calculated using the formula C ij = cij + ui + vj and denoted at the left hand bottom corner of each unoccupied cell. The computed valued of uj and vi and are shown in the table below. Calculation of the Opportunity Cost Calculate the values of ui and vj, using the formula for occupied cells. Assume any one cij + ui + vj = 0 Calculate the values of C ij , using the formula for unoccupied cells C ij = cij + ui + vj Since all the opportunity cost, C ij values are positive the solution is optimum. Total transportation cost = (2 × 25) + (3 × 200) + (5 × 250) + (4 × 150) + (3 × 50)+ (1 × 300) = 50 + 600 +1250 + 600 + 150 + 300 = Rs 2,950/- Example : Find the initial basic feasible solution for the transportation problem given in Table. Transportation Problem Solution : The initial basic feasible solution using VAM is shown in table below. Initial Basic Feasible Solution Using VAM Check for degeneracy, The number of allocations, N must be equal to m + n – 1. i.e., N = m+n – 1 5 = 3+3 – 1 since 4 ≠5, therefore degeneracy exists. To overcome degeneracy, the condition N = m + n – 1 is satisfied by allocating a very small quantity, close to zero in an occupied independent cell. (i.e., it should not form a closed loop) or the cell having the lowest transportation cost. This quantity is denoted by e. This quantity would not affect the total cost as well as the supply and demand values. How to Resolve Degeneracy in Transportation Problem ?Table shows the resolved degenerate table. Resolved Degenerate Table Total transportation cost = (50 × 1)+ (90 × 3) + (200 × 2) + (50 × 2) + (250 × e) = 50 + 270 + 400 + 100 + 250 e = 820 + 250 e = Rs. 820 since e ® 0 Example : Obtain an optimal solution for the transportation problem by MODI method given in Table. Transportation Problem Solution: Non Degenerate basic feasible Solution in Transportation ProblemInitial Basic Feasible Solution Using VAM 6 = 6 therefore degeneracy does not exist. Step 3: Test for optimality using MODI method. In Table 6.36 the values of Ui and Vj are calculated by applying the formula Cij + Ui + Vj = 0 for occupied cells. Transportation Problem Modi method degeneracyOptimality Test Using MODI Method Find the values of the dual variables Ui and Vj for occupied cells. Initially assume Ui = 0, 19 + 0 + V i = 0, V1 = – 19 10 + 0 + V4 = 0, V4 = – 10 60 + U2 – 10 = 0, U2 = – 50 20 + U3 – 10 = 0, U3 = – 10 8 – 10 + V2 = 0, V2 = 2 40 – 50 + V3 = 0, V3 = 10 C12 = 30 + 0 + 2 = 32 C13 = 50 + 0 + 10 = 60 C21 = 70 – 50 – 19 = 1 C22 = 30 – 50 + 2 = –18 C31 = 40 – 10 – 19 = 11 C33 = 70 – 10 + 10 = 70 In Table the cell (2,2) has the most negative opportunity cost. This negative cost has to be converted to a positive cost without altering the supply and demand value. Step 4: Construct a closed loop . Introduce a quantity + q in the most negative cell (S2, D2 ) and a put – q in cell (S3, D2 ) in order to balance the column D2. Now, take a right angle turn and locate an occupied cell in column D4. The occupied cell is (S3, D4) and put a + q in that cell. Now, put a – q in cell (S2, D4 ) to balance the column D4. Join all the cells to have a complete closed path. The closed path is shown in Figure. Closed Path Now, identify the – q values, which are 2 and 8. Take the minimum value, 2 which is the allocating value. This value is then added to cells (S2, D2 ) and (S3, D4 ) which have ‘+’signs and subtract from cells (S2, D4 ) and (S3, D2 ) which have ‘–’ signs. The process is shown in Figure. Closed Path The table after reallocation is shown in Table below. After Reallocation Now, again check for degeneracy. Here allocation number is 6. Verify whether number of allocations, N = m + n – 1 6 = 3 + 4 – 1 6 = 6 therefore degeneracy does not exits. Again find the values of Ui, Vj and cij for the Table 6.39 shown earlier. For occupied cells, Cij + Ui + Vj = 0 19 + 0 + V1 = 0, V1 = – 19 10 + 0 + V4 = 0, V4 = – 10 20 + U3 – 10 = 0, U3 = – 10 8 – 10 + V2 = 0, V2 = 2 30 + U2 + 2 = 0, U2 = – 32 40 – 50 + V3 = 0, V3 = – 10 C12 = 30 + 0 + 20 = 50 C13 = 50 + 0 – 8 = 42 C21 = 70 – 32 – 19 = 19 C24 = 60 – 32 – 10 = 18 C31 = 40 – 10 – 19 = 11 C33 = 70 – 10 – 8 = 52 The values of the opportunity cost cij are positive. Hence the optimality is reached. Final Allocation V1 = – 19 V2 = 2 V3 = – 8 V4 = – 10 Total transportation cost = (19 × 5) + (10 × 2) + (30 × 2) + (40 × 7) + (8 × 6) + (20 × 12) = 95 + 20 + 60 + 280 + 48 + 240 = Rs. 743 Example : Solve the transportation problem The problem is unbalanced if S ai = S bj, that is, when the total supply is not equal to the total demand. Convert the unbalanced problem into a balanced one by adding a dummy Here the supply does not meet the demand and is short of 2 units. To convert it to a balanced transportation problem add a dummy row and assume the unit cost for the dummy cells as zero as shown in Table and solve. Dummy Row Added to TP |
When the total allocations in a transportation model of M N size is not equals to M N 1 the situation is known as?
Related Posts
Copyright © 2024 SignalDuo Inc.
