# Degeneracy Assignment Problems

Prof Vinay Pandit

ASSIGNMENT AND TRANSPORTATION THEORY1) What is an Assignment Problem?

•

The assignment problem can be stated as a problem where different jobs are to beassigned to different machines on the basis of the cost of doing these jobs. Theobjective is to minimize the total cost of doing all the jobs on different machines

•

The peculiarity of the assignment problem is only one job can be assigned to onemachine i.e., it should be a one-to-one assignment

•

The cost data is given as a matrix where rows correspond to jobs and columns tomachines and there are as many rows as the number of columns i.e. the number of jobs and number of Machines should be equal

•

This can be compared to demand equals supply condition in a balancedtransportation problem. In the optimal solution there should be only oneassignment in each row and columns of the given assignment table. one canobserve various situations where assignment problem can exist

e.g.,

assignmentof workers to jobs like assigning clerks to different counters in a bank or salesmanto different areas for sales, different contracts to bidders.

•

Assignment becomes a problem because each job requires different skills and thecapacity or efficiency of each person with respect to these jobs can be different.This gives rise to cost differences. If each person is able to do all jobs equallyefficiently then all costs will be the same and each job can be assigned to any person.

•

When assignment is a problem it becomes a typical optimization problem it cantherefore be compared to a transportation problem. The cost elements are givenand is a square matrix and requirement at each destination is one and availabilityat each origin is also one.

OR MMS

*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 requ_{i}res allocations in ** m + n – 1 **independent cells. If the number of allocations is short of the requ

_{i}red 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.

If number of allocations, N ¹ m + n – 1, then degeneracy does exist. Go to Step 4.

**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).

Once an initial solution is obtained, the next step is to test its optimality.

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 u_{1}, u_{2}, …,u_{i} and the column 1, column 2,…, column j are assigned with variables v_{1}, v_{2}, …,v_{j} respectively.

(ii) Initially, assume any one of U Transportation Model i values as zero and compute the values for u_{1}, u_{2}, …,u_{i} and v_{1}, v_{2}, …,v_{j} by applying the formula for occupied cell.

**For occupied cells,**

c_{ij} + u_{i} + v_{j} = 0

(iii) Obtain all the values of c_{ij} 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).

The reduced matrix is shown in Table

**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)

= 500 + 600 + 1050 + 500 + 600 + 300 = Rs. 3550

**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.

The advantage of this method is that it gives an initial solution which is nearer to an optimal solution or the optimal solution itself.

** 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 v

_{j}for rows and columns respectively by applying the formula for occupied cells.

c_{ij}+u_{i}+v_{j} = 0

Then, the opportunity cost for each unoccupied cell is calculated using the formula C ij = c_{ij} + u_{i} + v_{j} 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 u_{i} and v_{j}, using the formula for occupied cells. Assume any one

of u_{i} and v_{j} value as zero (U3 is taken as 0)

c_{ij} + u_{i} + v_{j} = 0

4 + 0 + v_{2} = 0, v_{2} = – 4

5 + v_{2}– 3 = 0, u_{2} = – 2

3 – 2 + v_{1} = 0, v_{1} = – 1

2 – 4 + u_{1} = 0, u_{1} = 2

Calculate the values of C ij , using the formula for unoccupied cells

C ij = c_{ij} + u_{i} + v_{j}

c_{11} = 4+2 –1 = 5

c_{13} = 7+2 –3 = 6

c_{14} = 3+2 –1 = 4

C_{22} = 7–2 – 4 = 1

C_{24} = 8–2 – 1 = 5

C_{31} = 9 +0 –1 = 8

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. 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:**** Step1: **The initial basic feasible solution is found using Vogel’s Approximation Method as shown in Table.

**Initial Basic Feasible Solution Using VAM**

Total transportation cost = (19 × 5) + (10 × 2) + (40 × 7) + (60 × 2) + (8 × 8) +(20 × 10)

= 95 + 20 + 280 + 120 + 64 + 200

= Rs. 779.00

Step 2: To check for degeneracy, verify the number of allocations, N = m+n – 1.

In this problem, number of allocation is 6 which is equal m+n – 1.

∴ N = m + n – 1

6 = 3 + 4 – 1

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.

**Optimality Test Using MODI Method**

Find the values of the dual variables Ui and Vj for occupied cells.

Initially assume Ui = 0,

Cij + Ui + Vj = 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.

The final allocations are shown in Table.

**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

row or dummy column as required and solve.

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**