Решение задачи назначения с помощью электронных таблиц

Решение

Понимание существа проблемы можно в значительной степени облегчить, если перед тем, как применять Венгерский метод, попытаться решить поставленную задачу, используя один из широко известных  методов. Примените метод Вогеля и проследите, насколько он приближает нас к оптимальному решению, которое  мы рассмотрим в конце данного  раздела. Значения общего спроса и общего предложения для всех строк и  столбцов равны единице.

Этап 1 Венгерского метода:

В каждой строке находится наименьший элемент. Наименьший элемент вычитается из всех элементов соответствующей строки 
 

Найденный наименьший элемент вычитается из всех элементов соответствующего столбца.

В соответствии с процедурой, описанной в этапе 2, осуществляются назначения.

Наличие назначения обозначается через

Таблица 13.33. Назначения в  клетки с нулевыми значениями

На данном этапе мы можем осуществить только три нулевых назначения, тогда  как требуемое их количество равно  четырем. Полученное распределение  является недопустимым. Переходим к  этапу 3. Проводим наименьшее число  прямых, проходящих через все нули таблицы.

Таблица 13.34. Проведение прямых через нулевые  элементы

Наименьшим  элементом, через который не проходит ни одна из прямых, является число 2. Скорректируем  таблицу так, как это описано  выше в соответствии с этапом 3, т.е. вычтем 2 из каждого элемента, через  который не проходит ни одна прямая, и добавим 2 ко всем элементам, лежащим  на пересечении двух прямых, оставив  без изменения все прочие элементы, через которые проходит только одна прямая. Теперь перераспределим соответствующие  назначения сбытовых баз и потребителей.

Теперь  требование о размещении четырех  назначений в клетки с нулевой  стоимостью выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы А к потребителю I, с базы В — к потребителю II, с базы С — к потребителю III и с  базы D — к потребителю IV. Хотя данное решение и является оптимальным, однако оно не единственное. Тем  не менее в любом оптимальном  решении должен присутствовать маршрут (С,III), поскольку это единственный элемент с нулевой стоимостью в строке С. Два других оптимальных  распределения назначений представлены ниже.

Минимальную дальность перевозок для каждого  из трех решений можно вычислить  из исходной таблицы:

Решение 1: 68 + 60 + 35 + 45 - 208 миль;

Решение 2: 68 + 63 + 35 + 42 = 208 миль;

Решение 3: 72+56+35 + 45 = 208 миль. 
Общая дальность перевозок для всех трех решений одинакова.

Примечание: в задачах большей размерности, чем задача из примера 1. убедиться в том, что проведенное в соответствии г пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":

1. Выбирается  любая  строка  или  столбец,   содержащие только  один  нулевой элемент.

2. Если  выбрана строка, прямая проводится  через столбец, в котором находился  данный нулевой элемент.

3. Если  выбран столбец, прямая проводится  через строку, содержащую данный  нулевой элемент.

4. Пункты 1-3 повторяются до тех пор, пока  не будут учтены все входящие  в таблицу нули.

  Особые случаи  задачи о назначениях

МАКСИМИЗАЦИЯ  ЦЕЛЕВОЙ ФУНКЦИИ

Алгоритм  решения задачи о назначениях  предполагает минимизацию ее целевой  функции. Если имеется задача о назначениях, целевую функцию которой нужно  максимизировать, то поступают таким  же образом, как и в алгоритме  решения транспортной задачи: после  окончания формирования первой таблицы  все ее элементы умножаются на (— 1).

Пример  2. В распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в табл. 13.38.

Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы  достичь максимального объема продаж?

Решение.

Все элементы исходной таблицы умножаются на (-1);