Инструкция
1
Решайте задачу о назначениях аналогично любой транспортной задаче и формализуйте ее в виде транспортной таблицы, в строках которой отражаются назначения, а в столбцах – расстояния до потребителей. В каждом столбце таблицы найдите минимальное значение и вычтите его из каждого элемента данной строки, затем проделайте эту же операцию для столбцов. Получается, что теперь в каждом столбце и каждой строке вы имеете, по крайней мере, по одному нулевому значению.
2
Найдите строку, которая содержит только одно нулевое значение стоимости, и поместите в эту ячейку один элемент. Если нет такой строки, то допускается начать решение задачи о назначении с любой ячейки, имеющей нулевую стоимость.
3
Зачеркните оставшиеся нулевые значения в ячейках данного столбца и повторите два последних действия до тех пор, пока продолжать их станет уже невозможно.
4
В том случае, если в строках останутся нулевые ячейки, оставшиеся незачеркнутыми, которым не будут соответствовать назначения, то найдите столбец с единственным нулевым значением и поместите в соответствующую ячейку один элемент. Оставшиеся в данной строке нулевые значения стоимости зачеркните. Повторите последние два действия до тех пор, пока это возможно.
5
Если все элементы распределены в ячейки, которым соответствует нулевая стоимость, то данное решение о назначениях является оптимальным. В том случае, если оно оказалось недопустимым, проведите минимальное количество вертикальных и горизонтальных прямых через столбцы и строки таблицы таким образом, чтобы они прошли через все ячейки с нулевой стоимостью.
6
Определите минимальный элемент среди тех, через которые не прошли прямые. Прибавьте этот элемент ко всем значениям элементов матрицы, которые лежат на пересечении проведенных прямых. Те значения элементов, в которых нет пересечения прямых, оставьте без изменений. После данного преобразования у вас в таблице появится, по крайней мере, еще одно нулевое значение. Вернитесь к шагу 2 и повторите оптимизацию, пока не получите нужный результат.