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

Заявки b j

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

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

ВЕНГЕРСКИЙ МЕТОД

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

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

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

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

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

Шаг 1 . При максимизации целевой функции С найти максимальный элемент и каждый элемент этого столбца вычесть из максимального. При минимизации целевой функции (суммы показателей эффективности назначений) в каждом столбце матрицы С найти минимальный элемент и вычесть его из каждого элемента этого столбца.

С  с неотрицательными элементами. В каждом столбце матрицы С  имеется, по крайней мере, один нуль.

Шаг 2 . В каждой строке матрицы С  найти минимальный элемент и вычесть его из каждого элемента этой строки.

В результате образуется матрица С 0 с неотрицательными элементами. В каждом столбце и каждой строке матрицы С 0 имеется, по крайней мере, по одному нулю.

Шаг 3 . Отметить произвольный нуль в первом столбце звездочкой. Начиная со второго столбца просматривать каждый столбец матрицы С 0 и отмечать в нем звездочкой нуль, расположенный в строке, где нет нуля со звездочкой. В каждом столбце можно отметить звездочкой только один нуль. Очевидно, что нули матрицы С 0 , отмеченные звездочкой, являются по построению независимыми. На этом предварительный этап заканчивается.

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

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

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

Если же невыделенный нуль матрицы С k обнаружен, то возможен один из двух случаев:

эта строка не содержит нуля со звездочкой.

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

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

 Если такой нуль в столбце найден, но он не единственный в столбце, то из этих нулей следует выбрать:

в первую очередь такой нуль, в одной строке с которым, нет 0*;

во вторую очередь такой нуль, в одной строке с которым имеется 0*, но в одном столбце с этим 0* имеется невыделенный нуль;

в последнюю очередь такой нуль, в одной строке с которым имеется 0*, но в одном столбце с этим 0* отсутствует невыделенный нуль;

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

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

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

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

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

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

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

вычесть h из всех элементов матрицы С k , расположенных в невыделенных строках , и

прибавить h ко всем элементам матрицы С k , расположенным в выделенных столбцах .

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

Поскольку среди невыделенных элементов матрицы
появятся новые нули (согласно определению), следует перейти к первому этапу, а вместо матрицыС k рассматривать матрицу
.

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

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

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

Пример 9. Решим венгерским методом задачу:

На боевом надводном корабле имеется 5 зенитных огневых средств (ЗОС). На корабль совершается одновременный налет авиации противника в количестве 5 единиц. Поражающий потенциал каждого i –го ЗОС по j –му летательному аппарату противника равен (количество потенциально уничтожаемыхj –х летательных аппаратов за время атаки НК одним ЛА). Предполагается, что любое ЗОС может обстрелять любую цель.

Распределить ЗОС по ВЦ таким образом, чтобы суммарный поражающий потенциал был максимален, при условиях:

на одну ВЦ может быть назначено только одно ЗОС;

все цели должны быть обстреляны ЗОС.

Решение :

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





Первая итерация .

Первый этап .

+ +



+ +

торой этап .



Вторая итерация .

+ +

ервый этап .



Поскольку все нули матрицы С 1 выделены следует перейти к третьему этапу.

Третий этап .

+ +

h =1 

Первый этап .



Второй этап .



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

Упражнения .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 (xij)m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk (xij)m,n. Близость этой матрицы к решению задачи характеризует число Dk - суммарная невязка матрицы Хk:

В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительного этапа).

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

Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.

Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.

И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.

Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.

Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.

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