USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Minimisation Problems

PROBLEMS

Minimisation Problems

Step I. Check if the number of rows is equal to number of columns. If it is equal, the problem is a balanced one. If not, add a dummy column or row to make it a balanced one, by allotting zero values to each element (cell) of dummy row or column as the case is.

Step II. Row subtraction, Subtract the minimum or least value element of each row from all elements of that row.

Step III. Column subtraction. Subtract the minimum or least value element of each column from all elements of that column.

Step IV. Draw minimum number of horizontal and/or vertical lines in such a manner that all zeros are covered. For doing this, follow the procedure as follows:-

(a)             Select a row containing exactly one uncovered zero and draw a vertical line through the column containing this zero and repeat the process till no such row is left

(b)             Select a column containing exactly one uncovered zero and draw a horizontal line through the row containing the zero and repeat the process till no such column is left.

Step V. If the total number of minimum lines covering all zeros is equal to the order of the matrix, then we have got the optimal solution and there is no need to proceed further.

Step VI. If not, subtract the minimum uncovered element from all the uncovered elements and add this element to all the elements at the intersection points of the lines covering zeros.

Step VII. Repeat steps IV, V and VI till minimum number of lines covering all zeros is equal to the order of the matrix.

Step VIII. Now make assignments by selecting a row containing exactly one unmarked zero and put a square ⎕ around it. Also, draw a vertical line through the column containing this zero. Repeat this process till no such row is left Move to the column containing exactly one unmarked zero and put a square ⎕ around it, also, draw a horizontal line through the row containing this zero and repeat this process till no such column is left. If there are more than one zeros in anyone row or column, select anyone arbitrarily and pass two lines horizontally and vertically,

Step IX. Find the optimum value by adding up the values of the final assignments.

Maximisation Problems

Step I. Rewrite the problem as a minimisation problem by subtracting all elements from the largest element.

Step II. Follow the same steps as above from I to IX.