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

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

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

Венгерский метод является одним из интереснейших и наиболее распространенных методов решения транспортных задач.

Рассмотрим основные идеи венгерского метода на примере решения задачи выбора (задачи о назначениях), которая является частным случаем Т-задачи, а затем обобщим этот метод для произвольной Т-задачи.

Постановка задачи. Предположим, что имеется различных работ и механизмов, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы обозначим, и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы

чтобы сумма была максимальна и при этом из каждой строки и столбца С был выбран только один элемент.

Введем следующие понятия.

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

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

Метод представляет собой процедуру, состоящую из следующих шагов:

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

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

3.Ищется минимальное множество строк и столбцов, содержащие нули. Далее вне этого множества находим минимальный элемент и вычитаем его из всех элементов приведенной матрицы. Затем преобразуем матрицу таким образом, чтобы не было отрицательных элементов. Эта процедура эквивалентна следующей: минимальный элемент вычитаем из элементов, не содержащих нулевые строки и столбцы. На пересечении этих вычеркнутых строк и столбцов, содержащих нулевые элементы, этот минимальный элемент прибавляется элементам приведенной матрицы, а остальные элементы вычеркнутых столбцов и строк берутся без изменения.

III.Практическая часть. Задача о назначениях.

Решение венгерским методом

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

Для нахождения оптимального решения воспользоваться «венгерским методом».

Строим матрицу:

Решим ее венгерским методом.

1. Найдем в каждой строке минимальное значение и вычтем его из каждого элемента данной строки,(отмечены полужирным курсивом).

68 72 74 83 0 4 6 15

56 60 58 63 Получим 0 4 2 7

38 40 35 45матрицу: 3 5 0 10

47 42 40 45 7 2 0 5

2.Выберем в каждом столбце матрицы минимальный элемент и вычтем его из каждого элемента данного столбца: (отмечены полужирным курсивом).

0 4 6 15 0 2 6 10

3 5 0 10 3 3 0 5

7 2 0 5 7 0 0 0

3.Определяем число нулей в каждой строке: 1-1, 2-1, 3-1, 4-3и в каждом столбце: 1-2, 2-1, 3-2, 4-1. Максимальное число нулей (3) содержит 4-я строка и 1-й и 3-й столбец. Минимальным числом прямых вычеркнем все нули в матрице. Среди не вычеркнутых элементов выберем минимальный (выделен полужирным курсивом и подчеркнут – 2).

0 2 6 10

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

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

Вычеркнем из матрицы ненужные нули:

0 0 7 8

0 0 2 0

3 1 0 3

9 0 2 0

Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы 1-к потребителю 1, с базы 2- к потребителю 2, с базы 3 – к потребителю 3 и с базы 4 – к потребителю 4. В результате в начальной таблице суммируются клетки, соответствующие выбранным элементам итоговой таблицы(по диагонали – 68+60+35+45=208), это и будет минимальное решение данной задачи.

Ответ: заказы по сбытовым базам распределены оптимально, общая дальность минимальна – 208 км.

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

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

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

3. Ашманов С.А. «Линейное программирование»,- М.: 2011г.

4. Балдин.К.В. «Математическое программирование»/ К.В.Балдин – М: Издательство «Дашков и К», 2009.

5. Васильев Ф.П., «Линейное программирование»/ Ф.П., Васильев, А.Ю. Иваницкий,2009.

6. Вершик А.М. «О Л.В. Канторовиче и линейном программировании»,2010г

7. Глебова Н.В. «Применение методов линейного программирования для решения экономических задач»: учебно –методическое пособие для студентов 3 курса ВВАГС, 2001 г.

8. Карасев А.Н. «Математические методы в экономике»/ А.Н.Карасев,Н.Ш.Кремер,Т.Н.Савельева,2010.

9. Лищенко А.В., «Линейное и нелинейное программирование»,2011.

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

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

12. Шапкин, А.С. «Математические методы» / А. Шапкин. Учебник. Москва, 2010 г.

Вершик А.М. «О Л.В. Канторовиче и линейном программировании»,2010г.,с.45

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

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

Ашманов С.А. «Линейное программирование»,- М.: 2011г,с.235

Балдин.К.В. «Математическое программирование»/ К.В.Балдин – М: Издательство «Дашков и К», 2009.с.67

Васильев Ф.П., «Линейное программирование»/ Ф.П., Васильев, А.Ю. Иваницкий,2009,с.76

Шапкин, А.С. «Математические методы» / А. Шапкин. Учебник. Москва, 2010- 100 с

Лищенко А.В., «Линейное и нелинейное программирование»,2011.С.84

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

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

Карасев А.Н. «Математические методы в экономике»/ А.Н.Карасев,Н.Ш.Кремер,Т.Н.Савельева,2010.с.35

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

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

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

Глебова Н.В. «Применение методов линейного программирования для решения экономических задач»: учебно –методическое пособие для студентов 3 курса ВВАГС, 2001.,с.53

Содержательная постановка задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Q i тонн груза (i = 1,2,…, n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве R j тонн в месяц (j = 1,2,…, n).
Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составляется матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут.

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

Алгоритм венгерского метода .

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

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

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

Предварительный этап .

Шаг 1 . При максимизации целевой функции С найти максимальный элемент и каждый элемент этого столбца вычесть из максимального. При минимизации целевой функции (суммы показателей эффективности назначений) в каждом столбце матрицы С найти минимальный элемент и вычесть его из каждого элемента этого столбца.

С  с неотрицательными элементами. В каждом столбце матрицы С  имеется, по крайней мере, один нуль.

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

В результате образуется матрица С 0 с неотрицательными элементами. В каждом столбце и каждой строке матрицы С 0 имеется, по крайней мере, по одному нулю.

Шаг 3 . Отме­тить произвольный нуль в первом столбце звездочкой. Начиная со второго столбца просматривать каждый столбец матрицы С 0 и отмечать в нем звездочкой нуль, расположенный в строке, где нет нуля со звездочкой. В каждом столбце можно отметить звездочкой только один нуль. Очевидно, что нули матрицы С 0 , отмеченные звездочкой, являются по построению независимыми. На этом предварительный этап заканчи­вается.

( k + 1)-я итерация . Допустим, что k -я итерация уже проведена и в результате получена матрица С k . Если в матрице С k имеется ровно п нулей со звездочкой, то процесс решения заканчивается. Если же число нулей со звездочкой меньше п , то переходим к (k + 1)-й ите­рации.

Каждая итерация начинается первым и заканчивается вторым эта­пом. Между ними может несколько раз проводиться пара этапов: третий – первый . Перед началом итерации знаком «+» выделяют столбцы матрицы С k , которые содержат нули со звездочкой .

Первый этап . Просмотреть невыделенные столбцы матри­цы С k . Если среди них не окажется нулевых элементов, то перейти к третьему этапу .

Если же невыделенный нуль матрицы С k обнаружен, то возможен один из двух случаев:

эта строка не содержит нуля со звездочкой.

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

 Если такой нуль найден и он единственный в столбце, то отметить его штрихом и выделить строку (строки), содержащую такой нуль (нули), знаком «+». Затем просмотреть эту строку (строки), отыскивая в них нуль со звез­дочкой.

 Если такой нуль в столбце найден, но он не единственный в столбце, то из этих нулей следует выбрать:

в первую очередь такой нуль, в одной строке с которым, нет 0*;

во вторую очередь такой нуль, в одной строке с которым имеется 0*, но в одном столбце с этим 0* имеется невыделенный нуль;

в последнюю очередь такой нуль, в одной строке с которым имеется 0*, но в одном столбце с этим 0* отсутствует невыделенный нуль;

Этот процесс законечное число шагов заканчивается одним изследующих исходов:

Исход 1 . Все нули матрицы С k выделены, т. е. находятся в выделенных строках или столбцах. В этом случае перейти к третьему этапу ;

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

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

Второй этап . Построить следующую цепочку из элементов матрицы С k : исходный нуль со штрихом, нуль со звездочкой, располо­женный в одном столбце с первым, нуль со штрихом, расположенный в одной строке с предшествующим нулем со звездочкой, и т. д. Итак, цепочка образуется передвижением от 0" к 0* по столбцу , от 0* к 0" по строке и т. д.

Можно доказать, что описанный алгоритм построения цепочки однозначен и конечен. При этом цепочка всегда начинается и закан­чивается нулем со штрихом . Далее над элементами цепочки, стоящими на нечетных местах (0"), поставить звездочки, уничтожая их над четными элементами (0*). Затем уничтожить все штрихи над элементами мат­рицы С k и знаки «+». При этом количество независимых нулей будет увеличено на единицу . (k + 1)-я итерация закончена .

Третий этап . К этому этапу следует переходить после первого этапа в случае, если все нули матрицы С k выделены , т. е. находятся в выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы С k выбрать минимальный элемент и обозначить его h > 0.

вычесть h из всех элементов матрицы С k , расположенных в невыделенных стро­ках , и

прибавить h ко всем элементам матрицы С k , расположенным в выделенных столбцах .

В результате получается новая матрица , эквивалентнаяС k .

Поскольку среди невыделенных элементов матрицы
появятся новые нули (согласно определению), следует перейти к первому этапу, а вместо матрицыС k рассматривать матрицу
.

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

В первом случае после проведения второго этапа итерация закан­чивается .

Во втором случае после проведения третьего этапа получается матрица
~
~С k . В матрице
появятся невыделенные нули, и всю последовательность операций, начиная с первого этапа, надо повторить.После конечного числа повторений очередной первый этап обязательно закончится переходом на второй этап , при выполнении которого количество независимых нулей увеличится на единицу, а после выполнения которого (k + 1)-я итерация за­канчивается .

Пример 9. Решим венгерским методом задачу:

На боевом надводном корабле имеется 5 зенитных огневых средств (ЗОС). На корабль совершается одновременный налет авиации противника в количестве 5 единиц. Поражающий потенциал каждого i –го ЗОС по j –му летательному аппарату противника равен (количество потенциально уничтожаемыхj –х летательных аппаратов за время атаки НК одним ЛА). Предполагается, что любое ЗОС может обстрелять любую цель.

Распределить ЗОС по ВЦ таким образом, чтобы суммарный поражающий потенциал был максимален, при условиях:

на одну ВЦ может быть назначено только одно ЗОС;

все цели должны быть обстреляны ЗОС.

Решение :

Предварительный этап .





Первая итерация .

Первый этап .

+ +



В

+ +

торой этап .



Вторая итерация .

П

+ +

ервый этап .



Поскольку все нули матрицы С 1 выделены следует перейти к третьему этапу.

Третий этап .

+ +

+ +

h =1 

Первый этап .



Второй этап .



В результате решения задачи о назначениях венгерским методом получили, что последовательность
=4,
=4,
=3,
=2,
=2 дает максимальное значение целевой функции=15. Из этого следует, что для отражения атаки СВН противника наиболее эффективным будет следующий вариант назначения ЗОС на ВЦ:

Упражнения .

Найти опорный план транспортной задачи методами «Северо-западного угла», «Наименьшей стоимости», «Фогеля»:

						a i
Заявки b j

Решить транспортную задачу из задания 1 распределительным методом.

Решить транспортную задачу из задания 1 методом потенциалов.

Венгерским методом решить задачу назначения при поиске максимума:

Венгерским методом решить задачу назначения при поиске минимума:

Контрольные вопросы :

Дайте формулировку транспортной задачи линейного программирования.

Чем отличается сбалансированная транспортная задача от не сбалансированной транспортной задачи?

Сколько в сбалансированной транспортной задаче должно быть базисных переменных?

Дайте определение понятиям: план, допустимый план, опорный допустимый план, оптимальный план, используемым при решении транспортной задачи.

Сформулируйте алгоритм нахождения опорного плана методом северо-западного угла.

Сформулируйте алгоритм нахождения опорного плана методом наименьшей стоимости.

Сформулируйте алгоритм нахождения опорного плана методом Фогеля.

Сформулируйте алгоритм нахождения оптимального плана распределительным методом.

Сформулируйте алгоритм нахождения оптимального плана методом потенциалов.

Дайте формулировку задачи о назначениях.

Каким образом в задаче о назначениях при разных количествах объектов и средств формируется квадратная матрица назначений?

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

Каким образом на предварительном этапе формируется исходная матрица назначений при максимизации целевой функции?

Каким образом на предварительном этапе формируется исходная матрица назначений при минимизации целевой функции?

В чем заключается суть первого этапа решения задачи о назначениях Венгерским методом?

В чем заключается суть второго этапа решения задачи о назначениях Венгерским методом?

В чем заключается суть третьего этапа решения задачи о назначениях Венгерским методом?

Сколько первых, вторых и третьих этапов может находиться в одной итерации решения задачи о назначениях Венгерским методом? Какова последовательность выполнения этапов в итерации?

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

Введение 3

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

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

1.2 Венгерский метод решения задачи о назначениях 7

2 Решение задачи о назначениях с помощью венгерского метода 15

Заключение 20

Список использованной литературы 21

Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.

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

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

Предположим, что имеется п различных работ, каждую из которых может выполнить любой из п привлеченных испол­нителей. Стоимость выполнения і-й работы j - м исполнителем известна и равна C і j (в условных денежных единицах). Необхо­димо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше, известна как задача о назначениях. Введем переменные X ij , где X ij принимает значение 1 в случае, когда і-ю работу выполняет j-й исполнитель, и значение 0 во всех остальных случаях, i,j = 1, п . Тогда ограничение

гарантирует выполнение каждой работы лишь одним исполни­телем, ограничение

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

Таким образом, задачу о назначениях можно записать следую­щим образом:

Задача о назначениях (1) является частным случаем классической транспортной задачи, в которой надо положить При этом условие означает выполнение требова­ния целочисленности переменных x і j . Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.

Как частный случай классической транспортной задачи, за­дачу о назначениях можно рассматривать как задачу линейного программирования. Поэтому в данном случае используют тер­минологию и теоретические результаты линейного программи­рования.

В задаче о назначениях переменное х і j может принимать значение 0 или 1. При этом, согласно (1), в любом допусти­мом решении лишь п переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.

На практике встречаются задачи о назначениях, в поста­новках которых параметр понимается как эффективность выполнения і-й работы j - м исполнителем. В этих случаях нужно так распределить работы между исполни­телями, чтобы суммарная эффективность их выполнения была бы максимальной, т.е.

(2)

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

Параметры задачи о назначениях (1) удобно представлять матрицей , которую называют матрицей стоимости. Предположим, что и С = (c і j) - две матрицы стоимости, элементы которых связаны следующим образом:

где - некоторые постоянные. Таким образом, для получения матрицы С* нужно к элементам каждой і-й строки матрицы С прибавить число d,-, а к элементам ее каждого j - г o столбца - число Ц. В этом случае, если X - допустимое решение, удовлетворяющее ограничениям из (1), и

то с учетом ограничений из (1) типа равенства имеем

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

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

(3)

формально нельзя отнести к задачам о назначениях, поскольку коэффициенты ее целевой функции не являются положитель­ными. Это несоответствие можно преодолеть, заменив (3) эквивалентной задачей

(4)

в которой

так как в этом случае для всех имеет место неравен­ство .

1.2 Венгерский метод решения задачи о назначениях

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

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

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

Оптимальный план назначения определится положением независимых нулей на последней итерации.

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

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

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

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

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

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