Задача о назначениях

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

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

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

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

Решение 3: 72 + 56 + 35 + 45 = 208 миль.

Общая дальность перевозок  для всех трех решений одинакова.

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

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

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

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

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

венгерский метод алгоритм задача назначение

Заключение

Суть венгерского метода состоит в следующем: путем прибавления  определенным образом найденных  чисел к некоторым столбцам и  вычитания из них некоторых чисел  находят систему так называемых независимых нулей. Набор нулей  называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых  нулей равно n, то, приняв соответствующие  им переменные xij равными 1, а все остальные - равными 0, согласно утверждению 2, получим оптимальный план назначения.

Алгоритм венгерского  метода состоит из предварительного шага и не более, чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n) , задача решена. Оптимальный план назначения определится положением независимых нулей на последней итерации.

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

Список литературы

1. Агальцов, В.П. Математические  методы в программировании: учебник.  В.П. Агальцов, И.В. Волдайская. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006 г. - 224 с.: ил.

2. Акулич И. А. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.

3. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. - М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. - 436 с.

4. Грызина, Н.Ю. Математические методы исследования операций / Н. Грызина. Учеб. Пособие. Москва: МЭСИ, 2005.- 12 с.

5. Зайченко Ю.П. Исследование  операций: Учеб. пособие для студентов вузов. - 2-е изд., перераб. и доп. - Киев: Вища школа. Главное изд-во, 1979. 392 с.

6. Наследов, А.Д. Математические методы А. Наследов. - СПб: Речь, 2004. 38 с.

7. Партыка, Т.Л. Математические методы: учебник. / Т.Л. Партыка, И.И.

8. Попов. - 2-е изд., испр. - М.:ФОРУМ: ИНФРА-М, 2009 г. - 464 с.: ил.

9. Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

10. Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.

11. Хазанова Л.Э. Математическое  программирование в экономике:  Учебное пособие. - М.: Издательство  БЕК, 1998. - 141с.

12. Цирель, С. В. Венгерский способ/ С. Цирель. Москва: УРСС, 2007.- 120 с.

13. Шапкин, А.С. Математические  методы / А. Шапкин. Учебник. Москва, 2004.- 104 с.