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

+ +

h =1 

Первый этап .



Второй этап .



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

Упражнения .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Графы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Понизим способности разработчиков на 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.Если в полученной матрице можно выбрать по одному нулевому элементу так, чтобы соответствующие этим элементам решение было допустимым(то есть каждому исполнителю назначена была одна работа и каждая работа выполнялась одним исполнителем), то данное (нулевое) назначение будет оптимальным. Иначе переходим к следующему пункту.

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