Предварительный этап. На этом этапе осуществляются два последовательных преобразования матрицы С. Сначала находится максимальный элемент в каждом столбце: в первом столбце максимальный элемент равен 5, во втором - 4, в третьем - 6, в четвертом - 5, в пятом - 5. Из максимального элемента вычитаются элементы этого столбца. Получается неотрицательная матрица, в каждом столбце которой есть хотя бы один нуль. Затем из каждой строки полученной матрицы вычитаем минимальный элемент этой строки. В результате подготовительного этапа осуществлен переход к неотрицательной матрице, в каждом столбце и каждой строке которой имеется хотя бы один нуль.

В первом столбце матрицы отмечаем звездочкой нуль, расположенный в четвертой строке, во втором столбце - нуль во второй строке. В третьем столбце единственный нуль находится в четвертой строке, в которой уже имеется 0*, поэтому нуль в третьем столбце звездочкой не отмечается. Аналогично не отмечаются звездочкой нули в четвертом столбце, так как они находятся во второй и четвертой строках, где уже имеются выделенные нули. В пятом столбце отмечаем звездочкой нуль в первой строке. В результате получается три независимых нуля, следовательно, для решения задачи необходимо проведение двух итераций.

Итерация 1

Этап 1. Выделяем знаком «+» первый, второй и пятый столбцы матрицы, содержащие нули со звездочкой. Просматриваем невыделенные нули матрицы, начиная с третьего столбца. Отмечаем штрихом нуль эгого столбца, расположенный в четвертой строке. Поскольку в этой строке имеется 0*, то строка подлежит выделению (ставим знак «+» справа or четвертой строки). Одновременно уничтожается (обводится рамкой) знак выделения над первым столбцом, содержащим 0* в четвертой строке (случай (а)).