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

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

Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях 2может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.

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

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

Постановка задачи. Предположим, что имеется различных работ и механизмов, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы обозначим, и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы

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

Введем следующие понятия.

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

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

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

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

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

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы

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

Введем следующие понятия.

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

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D ), если для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

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

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

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

Далее рассматривают i - ю строку полученной матрицы, разыскивают ее минимальный элемент a i и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С 0 (С 0 ~ C ), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С 0 называется приведением матрицы.

Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы С 0 и отмечаем, если возможно, следующие нули знаком "*". Очевидно, что нули матрицы С 0 , отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.

(k +1)-ая итерация. Допустим, что k -я итерация уже проведена и в результате получена матрица С k . Если в ней имеется ровно n нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k +1) - й итерации.

Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий - первый. Перед началом итерации знаком "+" выделяют столбцы матрицы С k , которые содержат нули со звездочками.

Первый этап. Просматривают невыделенные столбцы С k . Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы С k обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.

Во втором случае переходим сразу ко второму этапу, отметив этот нуль штрихом.

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

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

Этот процесс за конечное число шагов заканчивается одним из следующих исходов:

1) все нули матрицы С k выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;

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

Второй этап. На этом этапе строят следующую цепочку из нулей матрицы С k : исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0 " к 0 * по столбцу, от 0 * к 0 " по строке и т.д.

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

Далее над элементами цепочки, стоящими на нечетных местах (0 ") -, ставим звездочки, уничтожая их над четными элементами (0 *). Затем уничтожаем все штрихи над элементами С k и знаки выделения "+". Количество независимых нулей будет увеличено на единицу. На этом (k+ 1) -я итерация закончена.

Третий этап. К этому этапу переходят после первого, если все нули матрицы С k выделены. В таком случае среди невыделенных элементов С k выбирают минимальный и обозначают его h (h >0). Далее вычитают h из всех элементов матрицы С k , расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С " k , эквивалентную С k . Заметим, что при таком

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

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

Пример 3.4. Решить задачу о назначениях с матрицей

При решении задачи используем следующие обозначения:

Знак выделения "+", подлежащий уничтожению, обводим кружком; цепочку, как и ранее, указываем стрелками.

Предварительный этап. Отыскиваем максимальный элемент первого столбца - 4. Вычитаем из него все элементы этого столбца. Аналогично для получения второго, третьего, четвертого и пятого столбцов новой матрицы вычитаем все элементы этих столбцов от п"яти, трех, двух и трех соответственно. Получим матрицу С " (C " ~C ). Так как в каждой строке С " есть нуль, то С " = С 0 и процесс приведения матрицы заканчивается. Далее ищем и отмечаем знаком "*" независимые нули в С 0 , начиная с первой строки.

Первая итерация . Первый этап. Выделяем знаком "+" первый, второй, и четвертый столбцы матрицы С 0 , которые содержат 0 * .

Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С 23 = 0, отмечаем его штрихом и выделяем знаком "+" вторую строку. Просматриваем эту строку, находим в ней элемент С 22 = 0 * и уничтожаем знак выделения второго столбца, содержащего 0 * . Затем просматриваем второй столбец - в нем нет невыделенных элементов. Переходим к последнему невыделенному столбцу (пятому), ищем в нем невыделенные нули. Поскольку невыделенных нулей нет, то переходим к третьему этапу.

Третий этап. Находим минимальный элемент в невыделенной части матрицы С 0 (т.е. элементы, которые лежат в столбцах и строках, не отмеченных знаком "+"). Он равен h = 1.

Вычтем h = 1 из всех элементов невыделенных строк (т.е. всех, кроме второго) и прибавим ко всем элементам выделенных столбцов (первого и четвертого). Получим матрицу С " 1 и перейдем к первому этапу.

Первый этап. Перед его началом вновь выделяем знаком "+" первый, второй и четвертый столбцы. Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С 23 = 0, отмечаем его знаком штрих. Поскольку во второй строке есть 0 * (элемент С 22), то выделяем знаком "+" вторую строку, далее уничтожаем знак выделения второго столбца, где лежит 0 * . Потом просмотрим второй столбец, находим в нем невыделенный нуль С 12 = 0, отмечаем его знаком штрих. Поскольку в первой строке есть нуль со звездочкой С 14 = 0 * , то выделяем его знаком "+", и уничтожаем знак выделения четвертого столбца, где находился этот знак 0 * . Затем пересматриваем четвертый столбец и находим в нем невыделенный нуль С 54 = 0. Так как в строке, где он находится, нет нуля со звездочкой, то отметив этот 0 штрихом, переходим ко второму этапу.

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

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

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

ЛЕКЦИЯ 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 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.