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

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

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

при следующих ограничениях.

Ясно, что если отбросить последнее условие и заменить его условием

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

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

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

Теорема 1.

Если минимизирует

по всем, таким что и

то минимизирует также функционал

где при всех

Теорема 2.

Если все и можно отыскать набор такой, что

то это решение оптимально.

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

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

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

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

Таблица А)

Таблица Б)

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

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

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

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

Таблица 1

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

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

Таблица 2

Этот шаг должен приводить к появлению нуля в клетке, где его ранее не было. В рассматриваемом примере это клетка (5,2).

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

Таблица 3

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

Пример 2.

Представлено четыре студента и четыре вида работ. Следующая таблица соответствует матрице стоимостей для этой задачи.

Выполним первый шаг алгоритма.

Теперь вычтем минимальные стоимости из элементов соответствующих строк.

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

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

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

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

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

Оптимальное решение, показанное в таблице, предлагает Даше убрать гараж, Кате стричь газоны, Алле мыть машины, а Саше выгуливать собак. Соответствующее значение целевой функции равно 1+10+5+5=21. Такое же значение можно получить путем суммирования значений и и значения элемента, наименьшего среди всех невычеркнутых.

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

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

Введение 3

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

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

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

2 Решение задачи о назначениях с помощью венгерского метода 15

Заключение 20

Список использованной литературы 21

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

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

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

Предположим, что имеется п различных работ, каждую из которых может выполнить любой из п привлеченных испол­нителей. Стоимость выполнения і-й работы j - м исполнителем известна и равна C і j (в условных денежных единицах). Необхо­димо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше, известна как задача о назначениях. Введем переменные X ij , где X ij принимает значение 1 в случае, когда і-ю работу выполняет j-й исполнитель, и значение 0 во всех остальных случаях, i,j = 1, п . Тогда ограничение

гарантирует выполнение каждой работы лишь одним исполни­телем, ограничение

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

Таким образом, задачу о назначениях можно записать следую­щим образом:

Задача о назначениях (1) является частным случаем классической транспортной задачи, в которой надо положить При этом условие означает выполнение требова­ния целочисленности переменных x і j . Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.

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

В задаче о назначениях переменное х і j может принимать значение 0 или 1. При этом, согласно (1), в любом допусти­мом решении лишь п переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.

На практике встречаются задачи о назначениях, в поста­новках которых параметр понимается как эффективность выполнения і-й работы j - м исполнителем. В этих случаях нужно так распределить работы между исполни­телями, чтобы суммарная эффективность их выполнения была бы максимальной, т.е.

(2)

где максимум ищется при ограничениях, указанных в (1).

Параметры задачи о назначениях (1) удобно представлять матрицей , которую называют матрицей стоимости. Предположим, что и С = (c і j) - две матрицы стоимости, элементы которых связаны следующим образом:

где - некоторые постоянные. Таким образом, для получения матрицы С* нужно к элементам каждой і-й строки матрицы С прибавить число d,-, а к элементам ее каждого j - г o столбца - число Ц. В этом случае, если X - допустимое решение, удовлетворяющее ограничениям из (1), и

то с учетом ограничений из (1) типа равенства имеем

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

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

(3)

формально нельзя отнести к задачам о назначениях, поскольку коэффициенты ее целевой функции не являются положитель­ными. Это несоответствие можно преодолеть, заменив (3) эквивалентной задачей

(4)

в которой

так как в этом случае для всех имеет место неравен­ство .

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

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

Суть венгерского метода состоит в следующем: Путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные x ij равными 1, а все остальные – равными 0, согласно утверждению 2, получим оптимальный план назначения.

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

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

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

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

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

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

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

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

Теорема 1.

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

для из базиса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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