Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 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), после чего производить решение по приведенному выше алгоритму.
Оглавление "Управленческие решения"
|