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

исполнители

потребности

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

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

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

Задачу о назначениях можно сформулировать следующим образом: имеется 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 месяцам.

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

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

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

А. Решение задач на минимум затрат

1. Проводим редукцию матрицы по строкам и столбцам, как и в методе ветвей и границ


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

Минимальный элемент сокращенной матрицы (2) вычитаем из всех ее элементов и складываем его с элементами, расположенными на пересечениях вычеркнутых строк и столбцов: 12 + 2 = 14; 3 + 2 = 5 редуцированной матрицы. В результате получаем эквивалентную матрицу

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

В. Решение задач на максимум прибыли

1. Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (17) так, чтобы матрица не содержала бы отрицательных элементов:


2. Редуцируя матрицу по строкам и столбцам, получим эквивалентную матрицу

3. Методом проб и ошибок строим матрицу назначения X и но ней вычисляем максимальную (в исходной матрице значения в прямоугольниках) прибыль:

Пример 4.6. Распределить производство трех видов товара Т|, Т 2 , Т3 среди пяти предприятий П|, П 2 , П:(, П 4 , П-, с целью получения максимальной прибыли от продажи товаров по следующим данным:

Издержки производства с,у единицы товара (долл.)

Годовой спрос (шт.) и цепа товара (долл.)

Формируем матрицу годовой прибыли с учетом спроса (тыс. долл.)

2. Модифицируем матрицу умножением всех элементов на (-1) и сложением с максимальным числом матрицы (8000) и для устранения дисбаланса вводим два вида Т 4 , Т Г) фиктивной продукции с нулевой прибылью, поскольку матрица должна быть квадратной:

3. Редуцируем матрицу по строкам и столбцам:


4. Модифицируем матрицу путем исключения строк 4, 5 и столбцов 3, 4, получим сокращенную матрицу

Затем определяем в ней минимальный элемент 180, вычитаем его из всех элементов этой матрицы и суммируем его с элементами, находящимися на пересечениях исключаемых строк и столбцов редуцированной матрицы (выделена в прямоугольниках), объединяем результаты и получаем эквивалентную матрицу


по которой строим матрицу назначения

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

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

Таблица 4.18

Должность

Качества

Директор

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

Менеджер

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

Экономист

Образование, аналитичность, опыт, коммуникабельность, уравновешенность, работа с людьми, интуиция, пунктуальность, бесконфликтность, умение предвидеть, уверенность, умение составлять бизнес-план, практичность

Бухгалтер

Образование, стаж, внимательность, усидчивость, любовь к счету, четкость, пунктуальность, исполнительность, ответственность, целеустремленность, умение вести контроль, неподкупность, логичность, практичность, самообладание, аналитичность, формализм, бюрократизм

Коммер

сант

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

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

Таблица 4.19

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

Жадность, бесчувственность, ехидство, жесткость, лукавство, мстительность, скряжничество, эгоистичность, скупость, некоммуникабельность, конфликтность

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

Корыстолюбие, небрежность, беспринципность, жуликоватость, дерзость, меркантильность, плутовство, фантазерство, нахальство, азартность

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

Подхалимство, чинопочитание, жадность, меркантильность, воро- ватость, непорядочность, взяточничество, увертливость, скользкость, неуравновешенность

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

Неуклюжесть, грубость, невежество, плутовство, подозрительность, бескультурье, нетерпимость к людям, конфликтность, безволие

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

Решение начинаем с определения веса - значимости должностных качеств (см. табл. 4.18) методом парных сравнений (см. п. 1.3), начиная с директора (табл. 4.20).

Определяем правильность заполнения матрицы:

Вес качеств определяем по формуле М; = 5,-/и 2 , результаты заносим в табл. 4.20.

Затем, сравнивая необходимые качества должности директора (см. табл. 4.20) с качествами претендентов (табл. 4.21), строим матрицу наличия качеств директора у претендентов (см. табл. 4.21) и вычисляем значения коэффициентов эффективности Су.

Наиболее подходящим кандидатом на эту должность является Гобсек, Су = 0,6224.

По результатам сравнения определяем коэффициенты эффективности су и заносим в табл. 4.22.

Аналогичным образом проводим операции сравнения по другим должностям, а полученные значения Су представим в виде матрицы эффективности (см. табл. 4.22).

Решая полученную матрицу венгерским методом на максимум, получим матрицу оптимального распределения претендентов по должностям (табл. 4.23).

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

Таблица 4.20

Качества

директора

Качества директора

1. Ответственность

2. Образование

3. Энтузиазм

4. Здоровье

5. Организатор

7. Интуиция

8. Опыт работы

9. Коммуникабельность

10. Самокритичность

11. Уравновешенность

12. Объективность

14. Знание этикета

Качества директора

Претендент

1. Ответственность

2. Образование

3. Энтузиазм

4. Здоровье

5. Организатор

7. Интуиция

8. Опыт работы

9. Коммуникабельность

10. Самокритичность

11. Уравновешенность

12. Объективность

13. Умение разбираться в людях

14. Знание этикета

Таблица 4.22

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

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

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

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


Вычтем

Шаг 2.

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


Вычтем

Шаг 3.

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

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

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

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

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


Шаг 4.

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

Теорема 1.

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

для из базиса

Метод потенциалов

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

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

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

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



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

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

Рассмотри задачу о назначениях с матрицей эффективностей

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

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

Теорема 2 (Эгервари).

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

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

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

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

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

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

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

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

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

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

Основной этап

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

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

Если нулей со звездочкой меньше , то

2. Помечаем знаком «+» сверху столбцы матрицы, в которых есть , и считаем эти столбцы занятыми.

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

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

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

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

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

Снимаем все пометки, кроме звездочек, и возвращаемся ко второму абзацу пункта 1.

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