Задача о назначении. Метод Вогеля. Венгерский метод

     Федеральное агентство по образованию

     Кафедра высшей математики и информационных технологий. 
 
 
 
 
 
 
 
 
 
 
 
 

     КУРСОВОЙ  ПРОЕКТ 

     по  курсу: «Экономико-математическое моделирование» 

     на  тему: «Задача о назначении. Метод Вогеля. Венгерский метод » 
 
 
 
 
 
 
 
 
 
 
 
 

                                                      Выполнила студентка

                                                      3 курса очного  отделения

                                                      спец. «Финансы и  кредит»

                                                      Подпись студента 

                                                      Проверил преподаватель: 
 
 
 

     Чебоксары

     2010 г.

Содержание

Введение ………………………………………………………………………..3

1. Задача о назначениях и алгоритм ее решения. Венгерский метод. Метод Вогеля ………………….…………………………………………………….....4

   1.1 Задача о назначениях. Понятие Венгерского метода………………...4

      1.2. Алгоритм решения задачи о назначениях …………………...............4

2.Применение  задачи о назначениях на практике……………………………7

Заключение……………………………………………………………………..12

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

Введение

Частным случаем транспортной задачи является задача о назначениях, в которой  число пунктов производства равно  числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода. 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.Задача о назначениях и алгоритм ее решения. Венгерский метод

1. Задача о назначениях. Понятие Венгерского метода

Частным случаем транспортной задачи является задача о назначениях, в которой  число пунктов производства равно  числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время .Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари).

1.2Алгоритм решения задачи о назначениях

Этот  алгоритм состоит из трех этапов.

Этап 1:

1. Формализация  проблемы в виде транспортной  таблицы по аналогии с решением  транспортной задачи.

2. В  каждой строке таблицы найти  наименьший элемент и вычесть его из всех элементов данной строки.

3. Повторить  ту же самую процедуру для  столбцов.

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

Этап 2.

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

1. Найти  строку, содержащую только одно  нулевое значение стоимости, и  в клетку, соответствующую данному  значению, поместить один элемент.  Если такие строки отсутствуют,  допустимо начать с любого  нулевого значения стоимости.

2. Зачеркнуть  оставшиеся нулевые значения  данного столбца.

3. Пункты 1 и 2 повторять до тех пор,  пока продолжение описанной процедуры  окажется невозможным.

Если  на данном этапе окажется, что есть несколько нулей, которым не соответствуют  назначения и которые являются незачеркнутыми, то необходимо:

4. Найти  столбец, содержащий только одно  нулевое значение, и в соответствующую  клетку поместить один элемент.

5. Зачеркнуть  оставшиеся нули в данной строке.

6. Повторять  пункты 4 и 5 до тех пор, пока  дальнейшая их реализация окажется невозможной.

Если  окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение  является допустимым, т.е. все элементы распределены в клетки, которым соответствует  нулевая стоимость, то полученное решение  одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3.

Этап 3.

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

2. Найти  наименьший среди элементов, через  которые не проходит ни одна  из проведенных прямых.

3. Вычесть  его из всех элементов, через  которые не проходят прямые.

4. Прибавить  найденный элемент ко всем  элементам таблицы, которые лежат  на пересечении проведенных ранее  прямых

5. Все  элементы матрицы, через которые  проходит только одна прямая, оставить без изменения.

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

2.Применение  задачи о назначениях на практике.

Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В таблице 1 содержится информация о расстоянии между каждой базой и каждым потребителем. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной?

Табл.1

Расстояние от сбытовых баз до потребителей

Решение

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

Этап 1 Венгерского метода: В каждой строке находится наименьший элемент.

Табл.2

Выявление наименьших элементов по строкам

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

Табл.3

Вычитание наименьшего элемента по строкам и выявление наименьшего элемента по столбцам

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

Табл.4

Вычитание наименьшего элемента по столбцам

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

Табл.5

Назначения в клетки с нулевыми значениями

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

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

Табл.6

Проведение прямых через нулевые элементы

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

Табл.7

Скорректированная таблица с назначениями для нулевых клеток

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

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

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

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

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

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

Минимальную дальность перевозок можно вычислить  из исходной таблицы: 35+55+50+23=163км.

      Следует заметить, что если на последнем  шаге оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.   
 

Заключение

В заключении можно сделать вывод о проделанной  работе:

Задача  о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства=1. 
Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов.

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

Минимальная дальность перевозок равна: 35+55+50+23=163км.

Задача  решена, цель достигнута 
 
 
 
 
 
 
 
 
 
 

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

1)Волков, И. К., Загоруйко Е. А.: Математика в техническом университете. Выпуск XX. Исследование операций-М.: МГТУ им. Н. Э. Баумана, 2004 436с.  

2)Красс,  М.С.,  Чупрынов, Б.П.: Основы математики и ее приложения в экономическом образовании- М.: Дело, : 2008 464с.

3)Невежин, В.П., Кружилов,С.И.: Сборник задач по курсу "Экономико-математическое моделирование": Учебное пособие для вузов-М:Городец,: 2005  320 с.

4) Фролькис ,В .С.:Введение в теорию и методы оптимизации для экономистов. 2-е изд. /. - СПб: Питер, 2002. - 320 с.

5) www.vslovar.org.ru

6)www.sider.home.nov.ru