Шаг 3. Поиск минимального набора строк и столбцов, содержащих нули

3.1. Отмечают звездочкой:

все строки, в которых нет ни одного отмеченного звездочкой нуля (строка 4, табл. 5.3);

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

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

3.2. Шаги 3.1. b) и 3.1. c) повторяют поочередно до тех пор, пока есть что отмечать.

3.3. После этого зачеркивают каждую непомеченную строку и каждый помеченный столбец (строки 1, 2 и столбец 3, табл. 5.3) с целью провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.

Шаг 4. Перестановка некоторых нулей.

4.1. Определяют наименьшее число из тех клеток, через которые не проведены прямые (не зачеркнуты), то есть число 2 в табл. 5.3.

Это число вычитают из каждого числа невычеркнутых столбцов и прибавляют к каждому числу вычеркнутых строк с получением табл. 5.4.

Если эти операции не приводят к оптимальному решению, то цикл повторяется, начиная с шага 2 до получения оптимума.

В данном случае число нулей, отмеченных точкой, оказалось равным 4, значит назначение является полным, а решение оптимальным, то есть

x ₁₁⁰ = x ₂₂⁰ = x ₃₃⁰ = x ₄₄⁰ = 1; min L = с₁₁ + с₂₂ + с_{33 +} с₄₄ = 3 + 4 + 2 + 8 = 17.

Таблица 5.2

i	с ij	ai
	0 = (3–3)	4 = (7–3)
bj					–
di

Таблица 5.3

i	с ij	ai
		3*
	0*
	0	0*		0
3*			0*
4*			0
bj					–

Таблица 5.4

i	j	ai
		3*
	0*
	0	0*		0
	0		0*
		0	0	0*
bj					–

Контрольные задания