Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1.
Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов:
1 этап:
1 Формализация проблемы в виде транспортной таблицы
2 В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки
3 Повторить ту же процедуру для столбцов
Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью. Оптимальное значение целевой функции в этом случае равно нулю.
2 этап:
1 Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки.
2 Зачеркнуть оставшиеся нулевые значения данного столбца
3 Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным
Если окажется, что имеется несколько нулей, которым не соответствуют назначения, и которые остались незачеркнутыми, необходимо:
4 Найти столбец, содержащий только одно нулевое значение, в его клетку помещается один элемент.
5 Зачеркнуть оставшиеся нули в данной строке
6 Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным
Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6
Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3.
3 этап: (Если решение является недопустимым)
1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице
2 Найти наименьший из элементов, через которые не проходит ни одна прямая
3 Вычесть его из всех элементов, через которые не проходят прямые
4 Прибавить его ко всем элементам, лежащим на пересечении прямых
5 Элементы, через которые проходит только одна прямая, оставить неизменными
В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново.
Пример решения задачи
Компания имеет 4 сбытовых базы и 4 заказа, которые необходимо доставить потребителям. Складские помещения каждой из баз достаточны для размещения любого из этих заказов.
Составим транспортную таблицу.
База
| Потребитель
| Потребитель
| Потребитель
| Потребитель
|
| 1
| 2
| 3
| 4
| A
| 68
| 72
| 75
| 83
| B
| 56
| 60
| 58
| 63
| C
| 38
| 40
| 35
| 45
| D
| 47
| 42
| 40
| 45
|
Вычтем минимальные элементы по строкам (выделены полужирным), получим новую таблицу:
| 1
| 2
| 3
| 4
| A
| 0
| 4
| 7
| 15
| B
| 0
| 4
| 2
| 7
| C
| 3
| 5
| 0
| 10
| D
| 7
| 2
| 0
| 5
|
Повторим ту же процедуру для столбцов:
| 1
| 2
| 3
| 4
| A
| 0
| 2
| 7
| 10
| B
| 0
| 2
| 2
| 2
| C
| 3
| 3
| 0
| 5
| D
| 7
| 0
| 0
| 0
|
На рисунке ниже приведено окончательное решение задачи.
В результате в начальной таблице суммируются клетки, соответствующие выбранным элементам итоговой таблицы (по диагонали - 68+60+35+45=208), это и будет минимальное решение данной задачи. Для решения такой же задачи на максимум необходимо первоначальные значения умножить на (-1), после чего производить решение по приведенному выше алгоритму.
Оглавление "Управленческие решения"
|
