Пример решения транспортной задачи венгерским методом

Пример 1. Имеются 5 лесопунктов и 5 комплектов лесозаготовительного оборудования (5 технологических линий). Каждая технологическая линия может дать производительность С(ij).

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

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

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

Первое преобразование проделывается со всеми столбцами матрицы С. Из максимального элемента j-го столбца (i = 1, 2,..., n) вычитаются элементы этого столбца:

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

Второе преобразование производится со строками матрицы С΄. Из элементов i-й строки матрицы С΄ вычитается минимальный элемент этой строки:

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

Предварительный этап (преобразование 1)

0*
		0*
	0*

			0*

Предварительный этап (преобразование 2)

Если в каждой строке матрицы С' = (c΄_ij), полученной после первого преобразования матрицы С, уже имеется хотя бы один нуль, то второе преобразование не производится.

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

Отмечаем произвольный нуль в первом столбце звездочкой (*). Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет 0*, то отмечаем его звездочкой. Аналогично просматриваются один за другим все остальные столбцы матрицы C˝. Очевидно, что нули матрицы C˝, отмеченные звездочкой, по построению являются независимыми.

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

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

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

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

0*
		0*	0΄		+
	0*

				0*

Итерация 1

Поскольку во второй строке имеется 0*, то строка подлежит выделению (ставим знак «+» справа от второй строки). Одновременно уничтожается (обводится рамкой) знак выделения над третьим столбцом, содержащим 0* во второй строке.

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

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

IB — все нули матрицы С_k выделены, т. е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу.

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

У нас имеет место случай IB, следовательно, мы переходим к третьему этапу.

Третий этап. К этому этапу переходят после первого, если все нули матрицы С_k выделены, т. е. находятся в выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы С_k выбирают минимальный и обозначают его h > 0. Далее величину h вычитают из всех элементов матрицы С_k, расположенных в невыделенных строках, и прибавляют ко всем элементам, расположенным в выделенных столбцах. Получают новую матрицу С_k⁽¹⁾, эквивалентную С_k.

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

0*		0΄
		0*	0΄
	0*

				0*

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

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

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

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

Просматриваем невыделенные нули матрицы, четвертого столбца. Отмечаем штрихом нуль этого столбца, расположенный во второй строке. Поскольку в этой строке имеется 0*, то строка подлежит выделению (ставим знак «+» справа от второй строки). Одновременно уничтожается (обводится рамкой) знак выделения над третьим столбцом, содержащим 0* во второй строке. Рассматриваем третий столбец матрицы (так как мы сняли выделение). В этом столбце, в 1 строке имеется нуль, но в этой строке уже выделен нуль со звездочкой в 1-ом столбце. Выделяем штрихом нуль в третьем столбце, выделяем строку (ставим знак «+» справа от первой строки). Уничтожаем (обводим рамкой) знак выделения над первым столбцом, содержащим 0*.В итоге имеем три невыделенных столбца (первый, третий, четвертый).

0*		0΄			+
		0*	0΄		+
	0*
0΄
				0*

Итерация 2

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

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

0*		0΄			+
		0*	0΄		+
	0*
0΄
				0*

Итерация 2

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

Строим цепочку. От последнего 0' (четвертая строка, первый столбец) движемся по столбцу до 0*, расположенного на пересечении первой строки и первого столбца, далее от 0* — к 0', находящемуся в этой же строке в третьем столбце. Так как в третьем столбце есть 0*, то движемся до второй строки, далее в четвертый столбец. В четвертом столбце нет 0*, процесс образования цепочки закончен.

Искомая цепочка состоит из элементов: 0'₄₁, 0*₁₁, 0'_13, 0*₂₃, 0'₂₄. Снимаем звездочки у нулей из цепочки и заменяем звездочками штрихи у нулей из цепочки. В результате второй итерации число независимых нулей увеличилось на единицу и стало равно 5, поэтому процесс решения задачи закончен.

Оптимальный вариант назначений Х₁₃ = Х₂₄ = Х₃₂ = Х₄₁ = Х₅₅ = 1. Соответствующая ему суммарная производительность 5+8+7+8+5=33