Лекция: Шаг 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, значит назначение является полным, а решение оптимальным, то есть
x110 = x220 = x330 = x440 = 1; min L = с11 + с22 + с33 + с44 = 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* | ||
| 3* | 0* | |
| 4* | ||
| bj | – |
Таблица 5.4
| i | j | ai |
| 3* | ||
| 0* | ||
| 0* | ||
| 0* | ||
| 0* | ||
| bj | – |
Контрольные задания