Задача о назначениях. Смотреть страницы где упоминается термин метод венгерский

Задача о назначениях

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

Задача о назначении на узкие места

ЛЕКЦИЯ 13. Задачи о назначении. Венгерский алгоритм

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

Имеется n рабочих мест на некотором конвейере и n рабочих, которых нужно на эти рабочие места расставить; известна производительность c ij рабочего i на рабочем месте j . Тот факт, что при некотором распределении на рабочие места рабочий i k попадает на рабочее место j k можно описать следующей таблицей:

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

Задача состоит в том, чтобы максимизировать

Шаг 0. Фиксируем матрицу производительностей и любое назначение на рабочие места. Пусть s - минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C ; в клетку с номером (ij ) в этой таблице проставим символ «´», если ; в противном случае эту клетку оставим пустой.

Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шагу, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к Шагу 0. Если же число ребер окажется меньше n , то имеющееся назначение на рабочие места уже оптимально.

Постановки задачи:

Пример 13.1 . Требуется распределить m работ (или исполнителей) по n станкам. Работа i (i =1,...,m ), выполняемая на станке j (j=1,...,n ), связана с затратами. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат c ij .

Пример 13.2. C= (c ij ) – стоимость производства детали i на станке j нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.

Пример 13.3. Транспортная задача. Заданы пункты производства товара, пункты потребления товара. Требуется определить оптимальное взаимно-однозначное соответствие между пунктами производства и пунктами потребления, исходя из матрицы стоимостей перевозок C между соответствующими пунктами (т.е. минимизировать суммарную стоимость перевозки).

Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1. Аналогично спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) работы i к станку j равна c ij . Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу.

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

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

Замечание 1. Для заданного значения n существует n ! допустимых решений.

Математическая модель задачи:

Минимизировать функцию , при ограничениях:

, (12.1)

, (12.2)

Ограничения (12.1) необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения (12.2) гарантируют, что каждому станку будет приписана ровно одна работа.

Пример 13.4. Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками. Стоимость производства детали i на станке j :

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

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

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

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

Оптимальное назначение: , , , остальные , .

К сожалению, не всегда удается определить решение так просто. Для таких случаев рассмотрим следующий алгоритм.

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

Шаг 2. (Определение назначений). На этом шаге можно использовать алгоритм поиска «наибольшего паросочетания с матрицей двудольного графа (существуют и другие возможности), если все =0 матрицы заменить на «1», а >0 на «0».

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

Шаг 3 . (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей:

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

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

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

Перейти к шагу 2.

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

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

Итерация 1

Шаг 1 . Редукция строк и столбцов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Корнай (Kornai) Янош (р. 1928), венгерский экономист-математик, академик АН Венгерской республики. Окончил Будапештский университет (1955), работал в АН, Институте текстильной промышленности , вычислительном центре Академии наук с 1967 г. - профессор и руководитель отдела АН Венгрии, с 1986 г. - профессор экономики в Гарвардском университете. В конце 50-х гг. вместе с Т. Липтаком разработал метод решения задач блочного программирования - метод планирования на двух уровнях (см. Корнай-Липтака метод). Исследовал проблемы функционирования экономики в условиях неравновесия, взаимоотношения между дефицитом и инфляцией. Был одним из идеологов венгерской экономической реформы конца 60-х гг. Иностранный член Британской, Шведской, Финляндской академий наук , почетный член Американской академии искусств и наук, Американской экономической ассоциации почетный доктор университетов многих стран мира . Государственная премия ВНР - 1983 г.

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

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

Шаг 3 . (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей:

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

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

Перейти к шагу 2.

Итерация 1

Шаг 1 . Редукция строк и столбцов.

Шаг 2 . Поиск допустимого решения, для которого все назначения имеют нулевую стоимость. Используем алгоритм поиска наибольшего паросочетания. Преобразуем матрицу в матрицу двудольного графа, затем в рабочую таблицу:

Находим паросочетание:

Это паросочетание не совершенное, т.е. полного назначения нет. На Шаг 3.

Шаг 3. Модификация редуцированной матрицы.

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно. Для столбцов соответствующие величины равны 2, 1, 1 и 1.

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

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1 соответственно. Для столбцов соответствующие значения равны 2, 1, 0, и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль – элемент (2,2). Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу:

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

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

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

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