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

На данном этапе мы можем осуществить только три нулевых назначения, тогда как требуемое их количество равно четырем. Полученное распределение является недопустимым. Переходим к этапу 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