iUNIT - IV
Assignment Problem
Assignment Problem is a special type of linear programming problem where the objective is
to minimize the cost or time of completing a number of jobs by a number of persons.
For example, suppose an accounts officer has 4 subordinates and 4 tasks. The subordinates
differ in efficiency and take different times to perform each task. If one task is to be assigned
to one person in such a way that the total person hours are minimized, the problem is called
an assignment problem.
Assignment problem Hungarian method example
An assignment problem can be easily solved by applying Hungarian method which consists of
two phases. In the first phase, row reductions and column reductions are carried out. In the
second phase, the solution is optimized on iterative basis.
Phase 1
Step 0: Consider the given matrix.
Step 1: In a given problem, if the number of rows is not equal to the number of columns and vice
versa, then add a dummy row or a dummy column. The assignment costs for dummy cells are
always assigned as zero.
Step 2: Reduce thee matrix by selecting the smallest element in each row and subtract with other
elements in that row.
Phase 2:
Step 3: Reduce the new matrix column-wise using the same method as given in step 2.
Step 4: Draw minimum number of lines to cover all zeros.
Step 5: If Number of lines drawn = order of matrix, then optimally is reached, so proceed to step
7. If optimally is not reached, then go to step 6.
Step 6: Select the smallest element of the whole matrix, which is NOT COVERED by lines.
Subtract this smallest element with all other remaining elements that are NOT COVERED by
lines and add the element at the intersection of lines. Leave the elements covered by single line as
it is. Now go to step 4.
Step 7: Take any row or column which has a single zero and assign by squaring it. Strike off the
remaining zeros, if any, in that row and column (X). Repeat the process until all the assignments
have been made.
Step 8: Write down the assignment results and find the minimum cost/time.
Note: While assigning, if there is no single zero exists in the row or column, choose any one zero
and assign it. Strike off the remaining zeros in that column or row, and repeat the same for other
assignments also. If there is no single zero allocation, it means multiple numbers of solutions
exist. But the cost will remain the same for different sets of allocations.
Example : Assign the four tasks to four operators. The assigning costs are given in Table.
Assignment Problem
Solution:
Step 1: The given matrix is a square matrix and it is not necessary to add a dummy row/column
Step 2: Reduce the matrix by selecting the smallest value in each row and subtracting from other
values in that corresponding row. In row A, the smallest value is 13, row B is 15, row C is 17 and
row D is 12. The row wise reduced matrix is shown in table below.
Row-wise Reduction
Step 3: Reduce the new matrix given in the following table by selecting the smallest value in
each column and subtract from other values in that corresponding column. In column 1, the
smallest value is 0, column 2 is 4, column 3 is 3 and column 4 is 0. The column-wise reduction
matrix is shown in the following table.
Column-wise Reduction Matrix
Step 4: Draw minimum number of lines possible to cover all the zeros in the matrix given in
Table
Matrix with all Zeros Covered
c
The first line is drawn crossing row C covering three zeros, second line is drawn crossing column
4 covering two zeros and third line is drawn crossing column 1 (or row B) covering a single zero.
Step 5: Check whether number of lines drawn is equal to the order of the matrix, i.e., 3 ≠ 4.
Therefore optimally is not reached. Go to step 6.
Step 6: Take the smallest element of the matrix that is not covered by single line, which is 3.
Subtract 3 from all other values that are not covered and add 3 at the intersection of lines. Leave
the values which are covered by single line. The following table shows the details.
Subtracted or Added to Uncovered Values and Intersection Lines Respectively
Step 7: Now, draw minimum number of lines to cover all the zeros and check for optimality.
Here in table minimum number of lines drawn is 4 which are equal to the order of matrix. Hence
optimality is reached.
Optimality Matrix
Step 8: Assign the tasks to the operators. Select a row that has a single zero and assign by
squaring it. Strike off remaining zeros if any in that row or column. Repeat the assignment for
other tasks. The final assignment is shown in table below.
Final Assignment
Therefore, optimal assignment is:
There are five machines and five jobs are to be assigned and
the associated cost matrix is as follows. Find the proper
assignment.
Solution:
In order to find the proper assignment, we apply the
Hungarian method as follows:
Step 1: Row reduction
Step 2: (Column reduction)
Step 3: (Zero Assignment)
From the last table we see that all the zeros are either assigned
or crossed out, but the total number of assignment,i.e., 4<5
(number of jobs to be assigned to machines). Therefore, we
have to follow step 4 and onwards as follows:
Step 4:
Step 5:
Here, the smallest element among the uncovered elements is
2.
(i) Subtract 2 from all those elements which are not
covered.
(ii) Add 2 to those entries which are at the junction of
two lines.
Complete the table as under:
Step 6: using step 3 again
Thus, we have got five assignments as required by the
problem.
The assignment is as follows:
Thus from the cost matrix the minimum cost =
6+1+11+12+5=Rs.35.
Hamiltonian Circuit Problems
Given a graph G = (V, E) we have to find the Hamiltonian Circuit using Backtracking
approach. We start our search from any arbitrary vertex say 'a.' This vertex 'a' becomes the
root of our implicit tree. The first element of our partial solution is the first intermediate
vertex of the Hamiltonian Cycle that is to be constructed. The next adjacent vertex is selected
by alphabetical order. If at any stage any arbitrary vertex makes a cycle with any vertex other
than vertex 'a' then we say that dead end is reached. In this case, we backtrack one step, and
again the search begins by selecting another vertex and backtrack the element from the
partial; solution must be removed. The search using backtracking is successful if a
Hamiltonian Cycle is obtained.
Example: Consider a graph G = (V, E) shown in fig. we have to find a Hamiltonian circuit
using Backtracking method.
Solution: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our
implicit tree.
Next, we choose vertex 'b' adjacent to 'a' as it comes first in lexicographical order (b, c, d).
Next, we select 'c' adjacent to 'b.'
Next, we select 'd' adjacent to 'c.'
Next, we select 'e' adjacent to 'd.'
Next, we select vertex 'f' adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have
already visited. Thus, we get the dead end, and we backtrack one step and remove the vertex
'f' from partial solution.
From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already
been checked, and b, c, d have already visited. So, again we backtrack one step. Now, the
vertex adjacent to d are e, f from which e has already been checked, and adjacent of 'f' are d
and e. If 'e' vertex, revisited them we get a dead state. So again we backtrack one step.
Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a.'
Here, we get the Hamiltonian Cycle as all the vertex other than the start vertex 'a' is visited
only once. (a - b - c - e - f -d - a).
Again Backtrack
Example: Find the Hamiltonian cycle by using the backtracking
approach for a given graph.
Solution:
Solve the sum of subset problems using backtracking algorithmic
strategy for the following data: n = 4 W =(w , w , w , w ) = (11, 13, 24,
1 2 3 4
7) and M = 31.