Этап II. Поиск оптимального решения.

При помощи нулевых значений C попытаемся сконструировать решение, для которого суммарное время потерь (или, в условиях других задач, суммарные затраты) имело бы нулевое значение. Если это возможно, то мы нашли оптимальное решение. В противном случае мы переходим к третьему этапу.

Чтобы найти решение с нулевым значением, рассмотрим сначала ту строку (или те строки), которая содержит наименьшее число нулей; обведем квадратиком один из нулей этой строки, а затем вычеркнем нули, которые находятся в той же строке или в том же столбце, что и обведенный нуль.

Таблица 6.6а

			0,5	0,5	6,5
2	11,5	8,5
3	7,5	7,5
4			5,5	12,5	7,5
5	8,5	1,5

Найдем среди оставшихся строк ту (или те), которая содержит меньше всего нулей, и повторим тот же процесс. Будем поступать так до тех пор, пока мы уже больше не сможем обводить квадратиками новые нули.

В нашем примере мы сначала обвели квадратиком элемент С₂₄, затем С₃₅, затем С₅₃ и, наконец, С₄₁ и вычеркнули С₄₂, хотя можно было бы обвести С₄₂ и вычеркнуть С₄₁. Совершенно ясно, что здесь не получилось решения с нулевым значением; действительно, если бы мы завершили назначения выбором элемента C₁₂, то значение решения было бы 7 + 0 + 0 + 0 + 0 = 7. Следовательно, мы должны переходить к следующему этапу.