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

Предположим, что у нас имеются $4$ склада $A_1,\ A_2,\ A_3,\ A_4$ и $4$ магазина $B_1,\ B_2,\ B_3,\ B_4$. Расстояния от каждого склада до каждого магазина заданы с помощью следующей матрицы:

Например, расстояние от $A_1$ до $B_1$ равно элементу $a_{11}=10$, расстояние от $A_2$ до $B_2$ равно элементу $a_{12}=20$, и т.д.

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

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

1. В каждой строке матрицы назначения находим минимальный элемент и вычитаем его из всех элементов строки.
2. В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца.
3. Находим строку с одним нулем. Этот ноль заключаем в квадрат и называем отмеченным. В столбце, где стоит отмеченный ноль, все остальные нули зачеркиваем и в дальнейшем не рассматриваем. Этот шаг продолжаем, пока возможно.
4. Находим столбец с одним нулем и этот ноль отмечаем. В строке, где стоит отмеченный ноль, все остальные нули зачеркиваются. Этот шаг продолжаем, пока возможно.
5. Если после выполнения шагов $3$ и $4$ еще остаются неотмеченные нули, то отмечаем любой их них, а в строке и столбце, где стоит отмеченный ноль, все остальные нули зачеркиваются.
6. Если каждая строка и каждый столбец матрицы содержит ровно один отмеченный ноль, то получено оптимальное решение. Каждый из отмеченных нулей прикрепляет поставщика к потребителю. В противном случаем проводим минимальное количество пересекающихся вертикальных и горизонтальных прямых через все нули. Среди не зачеркнутых этими прямыми чисел ищем минимум. Этот минимум вычитаем их всех не зачеркнутых чисел и прибавляем ко всем числам на пересечении прямых. К полученной матрице применяем вышеприведенный алгоритм, начиная с шага $3$.

Пример решения

Находим минимальный элемент в каждой строке матрицы и вычитаем его из всех элементов строки.

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

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

Следующая строка, в который находится ровно один ноль, это $4$-я. С ней поступаем точно так же. Больше нет строк, содержащих ровно один ноль, но имеются столбцы с одним нулем. Второй столбец содержит ровно один ноль, который мы и отметим. Поскольку этот ноль находится в $3$-й строке, то вычеркиваем все нули, находящиеся в $3$-й строке. Получим матрицу:

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

Находим минимальный элемент среди не зачеркнутых этими прямыми чисел: ${\min \left(5,\ 13,\ 7,\ 2,\ 11,\ 8\right)\ }=2$. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:

Полученное распределение не является оптимальным, поскольку в $4$-й строке нет отмеченных нулей. Проводим прямые:

${\min \left(11,\ 5,\ 9,\ 6,\ 6,\ 1\right)\ }=1$. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:

К полученной матрицы применяем вышеописанный алгоритм:

Видим, что в каждой строке и в каждом столбце матрицы находится ровно один отмеченный ноль. Получено оптимальное распределение. $A_1$ прикрепляем к $B_4$, $A_2$ - к $B_1$, $A_3$ - к $B_2$, $A_4$ - к $B_3$. Для того, чтобы найти суммарное распределение, нужно сложить числа, расположенные в исходной матрице на месте отмеченных нулей. Получим: $5+3+8+8=24$.

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

Содержательная постановка задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Q i тонн груза (i = 1,2,…, n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве R j тонн в месяц (j = 1,2,…, n).
Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составляется матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут.

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

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

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

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

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

3. Графы

Двудольный граф – граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. В нашей задаче тоже есть четкое разделение: одни вершины – это разработчики, другие – задачи, и связи (эффективность владения) есть только между разработчиками и задачами.
Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение» , чтобы каждый задействованный разработчик взял на себя отдельную задачу. И не получилось такого, что два разработчика прорабатывают одну проблему, или один «бедняга» отвечал за две задачи.

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

4. Максимальное паросочетание

Как же увеличить паросочетания (назначения)?

• если нашли свободную – поиск завершен
• если задача уже кому-то назначена, то пройдя по этому ребру паросочетания, попытаемся «переназначить» технологию разработчику, участвующему в данном назначении

Добавим еще немного терминологии из теории графов, простыми словами:

Экспонированная вершина – это вершина, которая не участвует в текущем паросочетании. Т.е. либо «незадействованный разработчик», либо «свободная задача».
Альтернирующая цепь – это цепь, ребра которой попеременно лежат или не лежат в паросочетании. (…- владение технологией – назначенная задача – владение технологией – назначенная задача - …)
Альтернирующее дерево – дерево, состоящее из альтернирующих цепей
Аугментальная цепь – это такая альтернирующая цепь, начальная и конечная вершины которой экспонированы. Вот как называется то, что мы и ищем! =)
Аугментальное дерево – соответственно дерево, в котором хотя бы одна из веток – это аугментальная цепь.

Вот и нашли способ наращивать паросочетание, стремясь получить максимальное. Нужно строить альтенирующее дерево. Когда оно станет аугментальным, искать аугментальные цепи из «незадействованного разработчика» в «свободную задачу» и потом «переназначать» задачи вдоль них. Это выгодно, т.к. увеличивает количество «задач в обработке» на 1:

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

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

Мы бы для начала всем разработчикам до упора назначили задачи в соответствии с их максимальными способностями. Если всем разработчикам удалось сразу же распределить задачи - отлично. Но такое происходит не часто. Вдруг два человека, оптимально владеют одной и той же технологией, кому она достанется и что делать в этой ситуации? Одному из разработчиков нужно будет подыскать иную свободную задачу, так же наиболее соответствующую его способностям. Если при текущих (максимальных требованиях) условиях не найдется свободной задачи, то нужно будет попробовать подыскать среди задач, предварительно немного занизив наши требования. Как бы искусственно занизить способности разработчиков в графе. Если в таких условиях обнаружим свободную задачу – получим аугментальное дерево. «Поменяем» по цепочке паросочетания, после чего будет +1. И продолжим назначать таким вот оптимальным образом, пока всем не подыщем работу.

Стратегия ясна.

Вся «фишка» этого алгоритма заключается в следующем. Нам дан всего один параметр в графе – эффективность решения определенной задачи разработчиком, что указано на ребрах. Эта величина присвоена парам разработчик-задача. Мы же «разделим» (отделим от пар) эти величины на две. Искусственно добавим два дополнительных параметра. Одни величины будут приписаны вершинам задач, другие - вершинам разработчиков.

Попробую привести такую интерпретацию:

• у разработчиков мы укажем их «способности» , допустим в единицах «сил», просто указывающие на то, насколько эффективно мы можем их задействовать или задействовали.
• у задач мы укажем их «изученность» , или, если можно так выразиться, «переизбыток внимания». Этот параметр будем так же измерять в «силе». Переизбыток внимания к задаче возникает в следующей ситуации. Если мы какого-то разработчика «недогрузили», т.е. он способен решать задачу на 5, а ему досталась всего на 3. То у него остается еще 2 «силы» которые он, в принципе, может уделить какой-то из знакомых ему задач. Бегать между кабинетов, консультировать по телефону, давать советы тем, кто занимается любимой ему технологией.

Таким образом, величины указанные на ребрах мы «разделим» на 2 значения, приписанных уже вершинам: эффективность решения задачи = способность разработчика + изученность задачи. В принципе, логично. Чем способней разработчик или чем более известна технология, тем лучше будет реализована эта часть в проекте. Эффективней.

В конце, после того как мы найдем решение, мы конечно будем учитывать только величины на ребрах, но сейчас эта «фишка» поможет нам найти решение. =)

6. Описание алгоритма

При поиске «свободной задачи» для «незадействованного разработчика» мы ограничимся теперь только (назовем их) оптимальными ребрами графа, т.е. теми, для которых выполняется равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина) .

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

• Удалось обнаружить свободную задачу. Дерево стало аугментальным. «Переназначаем» задачи, наращиваем паросочетание. Начинаем строить альтернирующее дерево заново, т.к. мало ли как там граф изменился
• Мы не нашли (не достигли) свободную задачу по оптимальным ребрам. А она есть, т.к. начинали ведь мы со свободного разработчика, а в графе у нас одинаковое количество задач и разработчиков. Полученное альтернирующее дерево становится, так называемым, Венгерским (весь метод так же называется). В данном случае нам нужно будет немного понизить наши требования к разработчикам и начать поиски заново. Failure is simply the opportunity to begin again, this time more intelligently (с) .

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

• Незадействованные разработчики, т.к. именно с них мы начинаем стоить дерево
• Разработчики и задачи, до которых можно дотянуться по оптимальным ребрам из незадействованных разработчиков. Т.к. именно через их «переназначение» мы пытаемся трудоустроить последних.

• Разработчики и задачи, находящиеся в паросочетании, но недоступные из свободных вершин (разработчиков). Нашли им работу – нечего их пока трогать.
• Задачи, недостижимые по оптимальным ребрам – до них нам и нужно будет добраться. Поэтому при построении дерева мы будем отмечать вершины, в которые удалось попасть. А эти задачи, соответственно, останутся неотмеченными.

После чего внутри венгерского дерева мы:

• Понизим способности разработчиков на delta, чтобы «присоединить» наименее безболезненным способом, по крайней мере, одно ребро к альтернирующему дереву, по которому в следующий раз будем продолжать поиски свободной задачи
• Повысим «изученность» задач на delta, чтобы внутри уже сейчас построенного аугментального графа ребра - остались оптимальными. Т.е. чтобы сохранилось равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина)

Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts .

7. Алгоритм словами, очень кратко

• Инициализация. Разработчикам – max способности. Задачи – не изучены.
• Пока не всем разработчикам нашли задачи.
  • Пока удается построить аугментальное дерево (находить свободные задачи) по оптимальным ребрам
    • «Переназначаем» задачи, увеличивая паросочетания
  • Не достигли свободной задачи. Венгерское дерево.
    • Понижаем способности разработчиков на min величину

8. Листинг

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

int n;
vector < vector > a; // Матрица эффективности a[разраб][задача]
vector xy, yx; // Паросочетания: xy[разраб], yx[задача]
vector vx, vy; // Альтернирующее дерево vx[разраб], vy[задача]
vector maxrow, mincol; // Способности, изученность

bool dotry (int i) {
if (vx[i]) return false ;
vx[i] = true ;
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = true ;
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) {
xy[i] = j;
yx[j] = i;
return true ;
}
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) {
xy[i] = j;
yx[j] = i;
return true ;
}
return false ;
}

int main() {

// ... чтение a ...

Mincol.assign (n, 0);
minrow.assign (n, 0);
for (int i=0; ifor (int j=0; j maxrow[i] = max (maxrow[i], a[i][j]);

Xy.assign (n, -1);
yx.assign (n, -1);
for (int c=0; c vx.assign (n, 0);
vy.assign (n, 0);
int k = 0;
for (int i=0; iif (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) {
int z = INF;
for (int i=0; iif (vx[i])
for (int j=0; jif (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
for (int i=0; iif (vx[i]) maxrow[i] -= z;
if (vy[i]) mincol[i] += z;
}
}
}

int ans = 0;
for (int i=0; i ans += a[i]];
printf ("%d\n" , ans);
for (int i=0; i printf ("%d " , xy[i]+1);
}

* This source code was highlighted with Source Code Highlighter .

9. Итого

Теги:

• задача о назначениях
• венгерский алгоритм
• алгоритм Куна

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

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

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

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

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

, (
, что
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕР

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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