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

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

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

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

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

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

, (
, что
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕР

руководитель,	Время выполнения i -м научным руководителем j

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

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

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

руководитель,	Время выполнения i -м научным руководителем j -го исследовательского проекта				Минимальное

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

руководитель,	а ij
Минимальное время по графе

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

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

руководитель,	а ij

руководитель,	а ij

руководитель,	а ij

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

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

руководитель,	а ij

руководитель,	а ij

руководитель,	а ij

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

руководитель,	а ij

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

руководитель,	а ij

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

руководитель,	а ij

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

руководитель,	а ij

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

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

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

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

руководитель,	а ij

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

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

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

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

Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 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

• Tutorial

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

Пару слов о методе

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

• Задача о назначении работников на должности. Необходимо распределить работников на должности так, чтобы достигалась максимальная эффективность, или были минимальные затраты на работу.
• Назначение машин на производственные секции. Распределение машин так, чтобы при их работе производство было максимально прибыльным, или затраты на их содержание минимальны.
• Выбор кандидатов на разные вакансии по оценкам. Этот пример разберем ниже.

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

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

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

Step-by-step алгоритм на примере

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

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

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

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

Т.к. все минимальные элементы – нулевые, то матрица не изменилась. Проводим редукцию по столбцам:

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

Продолжаем решение дальше. Вычеркиваем строки и столбцы, которые содержат нулевые элементы (ВАЖНО! Количество вычеркиваний должно быть минимальным ). Среди оставшихся элементов ищем минимальный, вычитаем его из оставшихся элементов (которые не зачеркнуты) и прибавляем к элементам, которые расположены на пересечении вычеркнутых строк и столбцов (то, что отмечено зеленым – там вычитаем; то, что отмечено золотистым – там суммируем; то, что не закрашено – не трогаем):

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

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

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

Реализация на языке программирования R

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

Данные для решения задачи берутся из файла example.csv который имеет вид:

#Подключаем библиотеку для удобства расчетов library(dplyr) #Считываем csv фаил (первый столбик - названия строк; первая строка - названия столбцов) table <- read.csv("example.csv",header=TRUE,row.names=1,sep=";") #Проводим расчеты unique_index <- hungarian_algorithm(table,T) #Выводим cat(paste(row.names(table)," - ",names(table)),sep = "\n") #Считаем оптимальный план cat("Оптимальное значение -",sum(mapply(function(i, j) table, unique_index$row, unique_index$col, SIMPLIFY = TRUE))) #____________________Алгоритм венгерского метода__________________________________ hungarian_algorithm <- function(data,optim=F){ #Если optim = T, то будет искаться максимальное оптимальное значение if(optim==T) { data <- data %>% apply(1,function(x) (x-max(x))*(-1)) %>% t() %>% as.data.frame() optim <- F } #Редукция матрицы по строкам data <- data %>% apply(1,function(x) x-min(x)) %>% t() %>% as.data.frame() #Нахождение индексов всех нулей zero_index <- which(data==0, arr.ind = T) #Нахождение всех "неповторяющихся" нулей слева-направо unique_index <- from_the_beginning(zero_index) #Если количество "неповторяющихся" нулей не равняется количеству строк в исходной таблице, то.. if(nrow(unique_index)!=nrow(data)) #..Ищем "неповторяющиеся" нули справа-налево unique_index <- from_the_end(zero_index) #Если все еще не равняется, то продолжаем алгоритм дальше if(nrow(unique_index)!=nrow(data)) { #Редукция матрицы по столбцам data <- data %>% apply(2,function(x) x-min(x)) %>% as.data.frame() zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) if(nrow(unique_index)!=nrow(data)) { #"Вычеркиваем" строки и столбцы которые содержат нулевые элементы (ВАЖНО! количество вычеркиваний должно быть минимальным) index <- which(apply(data,1,function(x) length(x)>1)) index2 <- which(apply(data[-index,],2,function(x) length(x)>0)) #Среди оставшихся элементов ищем минимальный min_from_table <- min(data[-index,-index2]) #Вычитаем минимальный из оставшихся элементов data[-index,-index2] <- data[-index,-index2]-min_from_table #Прибавляем к элементам, расположенным на пересечении вычеркнутых строк и столбцов data <- data+min_from_table zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) #Если все еще количество "неповторяющихся" нулей не равняется количеству строк в исходной таблице, то.. if(nrow(unique_index)!=nrow(data)) #..Повторяем весь алгоритм заново hungarian_algorithm(data,optim) else #Выводим индексы "неповторяющихся" нулей unique_index } else #Выводим индексы "неповторяющихся" нулей unique_index } else #Выводим индексы "неповторяющихся" нулей unique_index } #_________________________________________________________________________________ #__________Функция для нахождения "неповторяющихся" нулей слева-направо___________ from_the_beginning <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ #Выбор индексов нулей, которые не лежат на строках i, и столбцах j find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ #Записываем индекс строки в вектор i <- c(i,as.vector(find_zero)) #Записываем индекс столбца в вектор j <- c(j,as.vector(find_zero)) #Записываем индексы в data frame (это и есть индексы уникальных нулей) index <- rbind(index,setNames(as.list(find_zero), names(index))) #Повторяем пока не пройдем по всем строкам и столбцам from_the_beginning(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________ #__________Функция для нахождения "неповторяющихся" нулей справа-налево___________ from_the_end <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ i <- c(i,as.vector(find_zero)) j <- c(j,as.vector(find_zero)) index <- rbind(index,setNames(as.list(find_zero), names(index))) from_the_end(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________

Результат выполнения программы:

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

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

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

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

Вычтем

Шаг 2.

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

Вычтем

Шаг 3.

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

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

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

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

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

Шаг 4.

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