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

Введение 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с.

Алгоритм решения:

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

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

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

3. Минимальным числом прямых вычёркиваем все нули в матрице и среди не вычеркнутых элементов выбираем минимальный, его прибавляем к элементам, стоящим на пересечении прямых и отнимаем от всех не вычеркнутых элементов. Далее переходим к шагу 2.

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

Пример

Задача о назначениях является частным случаем транспортной задачи, в которой ai = bj = 1. Поэтому ее можно решать алгоритмами транспортной задачи. Рассмотрим другой метод, который является более эффективным, учитывающим специфику математической модели. Этот метод называется венгерским алгоритмом.

Он состоит из следующих шагов:

1) преобразования строк и столбцов матрицы ;

2) определение назначения;

3) модификация преобразованной матрицы.

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

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

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

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

Пример .

Распределить ресурсы по объектам.

Решение. 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим

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

3-й шаг. Вычеркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2:

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

Ответ. Первый ресурс направляем на 3-й объект, второй — на 2-й объект, четвертый — на 1-й объект, третий ресурс — на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28.

Примечания. 1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

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

исполнители
потребности

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

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

3. Графы

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

Двудольный граф – граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. В нашей задаче тоже есть четкое разделение: одни вершины – это разработчики, другие – задачи, и связи (эффективность владения) есть только между разработчиками и задачами.
Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение» , чтобы каждый задействованный разработчик взял на себя отдельную задачу. И не получилось такого, что два разработчика прорабатывают одну проблему, или один «бедняга» отвечал за две задачи.

В теории графов наша проблема, как это ни странно, называется Задачей о Назначениях (ЗН) . =) Она является частным случаем задачи нахождения максимального паросочетания. В самом деле, мы ведь стремимся максимально задействовать ресурсы, чтобы одновременно прорабатывалось максимальное число технологий, поэтому в терминах графов - пытаемся найти «максимальное паросочетание», составить максимальное количество пар разработчик-задача.

4. Максимальное паросочетание

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

Как же увеличить паросочетания (назначения)?

Выберем незадействованного разработчика, которому еще не назначена задача. Посмотрим, с чем бы он мог справиться, т.е. знакомые ему технологии. Если нашли среди них свободную – отлично, это то, что мы и искали. Назначаем. А если задача уже «занята» другим разработчиком? Попробуем занятому разработчику подыскать другую свободную технологию, ведь в таком случае эту - мы бы назначили нашему незадействованному подопечному. В общем, из вершины незадействованного разработчика или разработчика, которому мы пытаемся переназначить задачу, мы просматриваем все знакомые ему технологии на наличие свободной:

• если нашли свободную – поиск завершен
• если задача уже кому-то назначена, то пройдя по этому ребру паросочетания, попытаемся «переназначить» технологию разработчику, участвующему в данном назначении

В ходе такого обхода графа мы пытаемся из «незадействованного разработчика» попасть в «свободную задачу». Таким образом поиск «разворачивается» в следующее дерево:

Добавим еще немного терминологии из теории графов, простыми словами:

Экспонированная вершина – это вершина, которая не участвует в текущем паросочетании. Т.е. либо «незадействованный разработчик», либо «свободная задача».
Альтернирующая цепь – это цепь, ребра которой попеременно лежат или не лежат в паросочетании. (…- владение технологией – назначенная задача – владение технологией – назначенная задача - …)
Альтернирующее дерево – дерево, состоящее из альтернирующих цепей
Аугментальная цепь – это такая альтернирующая цепь, начальная и конечная вершины которой экспонированы. Вот как называется то, что мы и ищем! =)
Аугментальное дерево – соответственно дерево, в котором хотя бы одна из веток – это аугментальная цепь.

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

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

5. Венгерский метод.

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

Мы бы для начала всем разработчикам до упора назначили задачи в соответствии с их максимальными способностями. Если всем разработчикам удалось сразу же распределить задачи - отлично. Но такое происходит не часто. Вдруг два человека, оптимально владеют одной и той же технологией, кому она достанется и что делать в этой ситуации? Одному из разработчиков нужно будет подыскать иную свободную задачу, так же наиболее соответствующую его способностям. Если при текущих (максимальных требованиях) условиях не найдется свободной задачи, то нужно будет попробовать подыскать среди задач, предварительно немного занизив наши требования. Как бы искусственно занизить способности разработчиков в графе. Если в таких условиях обнаружим свободную задачу – получим аугментальное дерево. «Поменяем» по цепочке паросочетания, после чего будет +1. И продолжим назначать таким вот оптимальным образом, пока всем не подыщем работу.

Стратегия ясна.

Мы почти разгадали принцип Венгерского алгоритма. Но как все же построить решение по принципу «жадных алгоритмов»: до упора назначить по max способностям, потом чуть занизить способности и добавив к рассмотрению новые задач, до упора назначить их, занизить… и.т.д.? Как оценить способности и оптимальность текущего назначения?

Вся «фишка» этого алгоритма заключается в следующем. Нам дан всего один параметр в графе – эффективность решения определенной задачи разработчиком, что указано на ребрах. Эта величина присвоена парам разработчик-задача. Мы же «разделим» (отделим от пар) эти величины на две. Искусственно добавим два дополнительных параметра. Одни величины будут приписаны вершинам задач, другие - вершинам разработчиков.

Попробую привести такую интерпретацию:

• у разработчиков мы укажем их «способности» , допустим в единицах «сил», просто указывающие на то, насколько эффективно мы можем их задействовать или задействовали.
• у задач мы укажем их «изученность» , или, если можно так выразиться, «переизбыток внимания». Этот параметр будем так же измерять в «силе». Переизбыток внимания к задаче возникает в следующей ситуации. Если мы какого-то разработчика «недогрузили», т.е. он способен решать задачу на 5, а ему досталась всего на 3. То у него остается еще 2 «силы» которые он, в принципе, может уделить какой-то из знакомых ему задач. Бегать между кабинетов, консультировать по телефону, давать советы тем, кто занимается любимой ему технологией.

Таким образом, величины указанные на ребрах мы «разделим» на 2 значения, приписанных уже вершинам: эффективность решения задачи = способность разработчика + изученность задачи. В принципе, логично. Чем способней разработчик или чем более известна технология, тем лучше будет реализована эта часть в проекте. Эффективней.

В конце, после того как мы найдем решение, мы конечно будем учитывать только величины на ребрах, но сейчас эта «фишка» поможет нам найти решение. =)

6. Описание алгоритма

Инициализируем граф. Будучи «упертыми оптимистами », мы для каждого разработчика рассчитаем его максимальную «способность» по знакомым ему технологиям, и присвоим ему это число. Everyone enjoys doing the kind of work for which he is best suited . О задачах пока ничего неизвестно, поэтому их «изученность» инициализируем нулями.

При поиске «свободной задачи» для «незадействованного разработчика» мы ограничимся теперь только (назовем их) оптимальными ребрами графа, т.е. теми, для которых выполняется равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина) .

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

• Удалось обнаружить свободную задачу. Дерево стало аугментальным. «Переназначаем» задачи, наращиваем паросочетание. Начинаем строить альтернирующее дерево заново, т.к. мало ли как там граф изменился
• Мы не нашли (не достигли) свободную задачу по оптимальным ребрам. А она есть, т.к. начинали ведь мы со свободного разработчика, а в графе у нас одинаковое количество задач и разработчиков. Полученное альтернирующее дерево становится, так называемым, Венгерским (весь метод так же называется). В данном случае нам нужно будет немного понизить наши требования к разработчикам и начать поиски заново. Failure is simply the opportunity to begin again, this time more intelligently (с) .

Вот и подошли к последнему моменту Венгерского метода для чего все эти дополнительные параметры и «способности» задумывались. Допустим, что, наращивая альтернирующее дерево, мы в конечном итоге получили - Венгерское дерево. Рассмотрим, какие вершины попадут в это дерево:

• Незадействованные разработчики, т.к. именно с них мы начинаем стоить дерево
• Разработчики и задачи, до которых можно дотянуться по оптимальным ребрам из незадействованных разработчиков. Т.к. именно через их «переназначение» мы пытаемся трудоустроить последних.

Снаружи этого дерева, в оставшемся графе будут присутствовать:

• Разработчики и задачи, находящиеся в паросочетании, но недоступные из свободных вершин (разработчиков). Нашли им работу – нечего их пока трогать.
• Задачи, недостижимые по оптимальным ребрам – до них нам и нужно будет добраться. Поэтому при построении дерева мы будем отмечать вершины, в которые удалось попасть. А эти задачи, соответственно, останутся неотмеченными.

Далее в цикле мы пробежим по «границе» дерева: по тем ребрам, которые соединяют незадействованных разработчиков или разработчиков, достижимых из них (может их удастся «переназначить»), со смежными задачами (по неоптимальным ребрам). По этим ребрам мы вычислим минимальное на текущий момент «несоответствие» способностей разработчика, чтобы он смог приступить к этой задаче: delta = min(способность разработчика (вершина) + изученность задачи (вершина) - эффективность решения задачи (ребро)) .

После чего внутри венгерского дерева мы:

• Понизим способности разработчиков на delta, чтобы «присоединить» наименее безболезненным способом, по крайней мере, одно ребро к альтернирующему дереву, по которому в следующий раз будем продолжать поиски свободной задачи
• Повысим «изученность» задач на delta, чтобы внутри уже сейчас построенного аугментального графа ребра - остались оптимальными. Т.е. чтобы сохранилось равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина)

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

Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts .

7. Алгоритм словами, очень кратко

Соберем теперь все до кучи:

• Инициализация. Разработчикам – max способности. Задачи – не изучены.
• Пока не всем разработчикам нашли задачи.
  • Пока удается построить аугментальное дерево (находить свободные задачи) по оптимальным ребрам
    • «Переназначаем» задачи, увеличивая паросочетания
  • Не достигли свободной задачи. Венгерское дерево.
    • Понижаем способности разработчиков на min величину

8. Листинг

Код, конечно, будет покороче, чем все мое описание. =)

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

int n;
vector < vector > a; // Матрица эффективности a[разраб][задача]
vector xy, yx; // Паросочетания: xy[разраб], yx[задача]
vector vx, vy; // Альтернирующее дерево vx[разраб], vy[задача]
vector maxrow, mincol; // Способности, изученность

bool dotry (int i) {
if (vx[i]) return false ;
vx[i] = true ;
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = true ;
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) {
xy[i] = j;
yx[j] = i;
return true ;
}
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) {
xy[i] = j;
yx[j] = i;
return true ;
}
return false ;
}

int main() {

// ... чтение a ...

Mincol.assign (n, 0);
minrow.assign (n, 0);
for (int i=0; ifor (int j=0; j maxrow[i] = max (maxrow[i], a[i][j]);

Xy.assign (n, -1);
yx.assign (n, -1);
for (int c=0; c vx.assign (n, 0);
vy.assign (n, 0);
int k = 0;
for (int i=0; iif (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) {
int z = INF;
for (int i=0; iif (vx[i])
for (int j=0; jif (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
for (int i=0; iif (vx[i]) maxrow[i] -= z;
if (vy[i]) mincol[i] += z;
}
}
}

int ans = 0;
for (int i=0; i ans += a[i]];
printf ("%d\n" , ans);
for (int i=0; i printf ("%d " , xy[i]+1);
}

* This source code was highlighted with Source Code Highlighter .

9. Итого

Если кто-то видит Венгерку впервые. И после прочтения описания, а за ним листинга – возникнет уверенное впечатление «да тут по листингу и без этих описаний все понятно, что было распинаться». Буду все же надеяться, что хоть отчасти описание добавило понимания в работу алгоритма. Буду искренне рад за Вас! а мне, в свою очередь, это немного даст почувствовать, что писал, наверное, не зря. =)

Теги:

• задача о назначениях
• венгерский алгоритм
• алгоритм Куна

Добавить метки

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

Шаг 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 методом потенциалов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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