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

+ +

h =1 

Первый этап .



Второй этап .



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

Упражнения .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы принятия управленческих решений

РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ

Задачу о назначениях можно сформулировать следующим образом: имеется n исполнителей и n работ, задана - эффективность выполнения каждой работы каждым исполнителем (таблица, в которой содержатсяn 2 чисел, характеризующих эффективность, называется n xn - или n 2 -матрицей). Задача заключается в том, чтобы назначить каждому исполнителю одну и только одну работу таким образом, чтобы оптимизировать заданную функцию эффективности. Математическая модель выглядит следующим образом:

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

(венгерский метод)

, (
, что
.

Шаг 1 . Получение нулей в каждой строке

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

Шаг 2. Получение нулей в каждом столбце.

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

Шаг 3 . Поиск оптимального решения

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

Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

Все строки, в которых не имеется ни одного отмеченного нуля;

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

Все строки, содержащие отмеченные нули хотя бы в одном из отмеченных столбцов.

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

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

Шаг 5 . Перестановка некоторых нулей.

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

ПРИМЕР

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

Решение считается оптимальным , если все измененные таким образом затраты
, (
) и можно отыскать такой набор, что
.

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

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

Вычтем минимальные элементы из соответствующих столбцов.

Сделаем назначения

Число отмеченных (желтым цветом) нулей равно 3, т.е. назначение не является полным (3<4).

Найдем минимальный набор строк и столбцов, содержащий все нули.

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

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

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

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

Это назначение является полным, так как число отмеченных (желтым цветом) нулей равно 4.

Время выполнения всех (четырех) проектов:

Т =3х1+4х1+2х1+8х1=17.

Данное назначение не единственное. Если во второй строке сначала отметить не второй, а четвертый нуль, получим следующее назначение.

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

Т =3х1+5х1+2х1+7х1=17.

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

Задача: Решить задачу о назначениях на максимум.

Не будем приводить какое-либо словесное условие, они могут быть разные, например «На работу устраиваются 6 кандидатов на 6 вакансий и они получили соответствующие оценки при собеседовании на каждую вакансию, провести набор кандидатов на шесть вакансий так, чтобы суммарная оценка кандидатов была максимальной» или «шесть станков выполняют шесть работ за время, заданное в таблице, составить производственный план…». Будем считать, что перед нами матрица (платежная, временная и т.д.) и нужно решить задачу о назначениях венгерским методом на максимум, т.е. выбрать по одной клетке в строке и столбцу так, чтобы из сумма была максимальна.

Решение:
Шаг 1:
Замечание: первый шаг требуется только для решения задачи на максимум, если вам требуется решить её на минимум, то пропустите его.

Преобразуем матрицу, заменив каждый элемент матрицы разностью максимального элемента этой строки и самого элемента.

Вычтем

Шаг 2.

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

Вычтем

Шаг 3.

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

Отметим как «недовольную строку», 5-ю, в которой мы такой ноль отметить не смогли, и второй столбец, он содержит ноль в пятой строке. Но второй столбец также содержит ноль в первой строке, отметим и ее как «недовольную». Первая строка нулей больше не содержит, т.е. процесс отмечания недовольных строк закончен, и мы получили ситуацию под названием «узкое место».

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

Выберем минимальный элемент в помеченных строках вне отмеченных строк. Это 3, стоящая в пятом столбце и пятом столбце.
Вычтем этот элемент из отмеченных строк и прибавим в полученных столбцах.

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

Шаг 4.

Не хватает еще нуля в 6-ой строке. Отметим её как недовольную, она имеет ноль в первом столбце, отметим его как недовольный, он, в свою очередь, содержит ноль во второй строке, отметим её, но она более нулей не содержит, процесс отмечания законен.

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

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

при следующих ограничениях.

Ясно, что если отбросить последнее условие и заменить его условием

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

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

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

Теорема 1.

Если минимизирует

по всем, таким что и

то минимизирует также функционал

где при всех

Теорема 2.

Если все и можно отыскать набор такой, что

то это решение оптимально.

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

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

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

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

Таблица А)

Таблица Б)

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

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

Заметим предварительно, что любое дальнейшее вычитание из строки или столбца, хотя и может приводить к появлению новых нулей, неизбежно приводит в появлению отрицательных элементов, так что нулевое решение теперь не обязательно будет оптимальным. Однако отрицательные элементы можно исключить, прибавляя соответствующие числа к строкам или столбцам. Так например, если вычесть 2 из столбца 1 в таблице (Б), то в строке 1 появится элемент - 2. Если теперь прибавить 2 к строке 1, то вновь получим матрицу с неотрицательными элементами. Задача заключается в том, чтобы получать новые нули указанным способом, но вместе с тем в конечном счете получить матрицу, содержащую решение среди одних нулей. Можно доказать, что описываемый ниже алгоритм обеспечивает решение этой задачи.

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

Таблица 1

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

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

Таблица 2

Этот шаг должен приводить к появлению нуля в клетке, где его ранее не было. В рассматриваемом примере это клетка (5,2).

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

Таблица 3

В этой таблице уже содержится решение, помеченное скобками и имеющее значение 13, что на 1 лучше исходного допустимого решения. , .

Пример 2.

Представлено четыре студента и четыре вида работ. Следующая таблица соответствует матрице стоимостей для этой задачи.

Выполним первый шаг алгоритма.

Теперь вычтем минимальные стоимости из элементов соответствующих строк.

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

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

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

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

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

Оптимальное решение, показанное в таблице, предлагает Даше убрать гараж, Кате стричь газоны, Алле мыть машины, а Саше выгуливать собак. Соответствующее значение целевой функции равно 1+10+5+5=21. Такое же значение можно получить путем суммирования значений и и значения элемента, наименьшего среди всех невычеркнутых.

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 (xij)m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk (xij)m,n. Близость этой матрицы к решению задачи характеризует число Dk - суммарная невязка матрицы Хk:

В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительного этапа).

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

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

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

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

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

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

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