It develops at the iteration stage . This happens when the selection of entering variables results in simultaneous drive to zero of two or more current ( pre-iteration) basic variables .
(MODI METHOD) – Transportation Algorithms
A feasible solution has to be found always. Rather than determining a first approximation by a direct application of the simplex method, it is more efficient to the work with the transportation table . The transportation algorithm is the simplex method specialised to the format of the table involving the following steps:-
Finding an initial basic feasible solution.
Testing the solution for optimality.
Improving the solution , when it is not optimal
Repeating steps (i) and (iii) until the optimal solution is obtained.
Solution to the transportation problem is obtained in 2 stages-
In first stage we find the basic feasible solution using any of the following method –
North – west corner rule.
Matrix minima method or least cost method.
Vogel’s approximation method.
In second stage, we test the babis feasible solution for the optimality by MODI METHOD.
Q.4 a. Explain the steps involved in Hungarian method of solving Assignment problems.
b. What do you mean by unbalanced assignment problem? How do you overcome it?
Hungarian Method Algorithm:- is based on the concept of opportunity cost and is more efficient in solving assignment problem.
Steps to solve the problem are as follows-
Prepare row ruled matrix by selecting the minimum values for eah row and subtract it from the other elements of the row .
Prepare column-reduced matrix by subtracting minimum value of the column from the other values of the column.
Assign zero row-wise if there is only one zero in the row and cross(X) or cancel other zeros in that column.
Assign column wise if there is only one zero in that column and cross other zeros in that row.
Repeat steps 3 and 4 till all zero are either assigned or crossed. If the number of assignments is equal to the number of row present, you have arrived at an optimal solution, if not , proceed to step 6 .
Mark (√) the unassigned row. Look for crossed zero in that row. Mark the column containing the crossed zero .Look the assigned zero in that column. Mark the row containing the assigned zero .Repeat this process till all the markings are done.
Draw a straight line through unmarked rows and marked column. The number of straight line drawn will be equal to the assignment made.
Examine the uncovered elements. Select minimum.(责任编辑：BUG)