Транспортная задача с ограниченными пропускными способностями

Рассмотрим Т _d - задачу:

Минимизировать

при условиях

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

1. Элемент с_ij = 0 матрицы С называется Х - неполным нулем, если в плане Х Т_d - задачи элемент х_ij < d_ij. Если же х_ij = d_ij, то элемент с_ij называется Х - полным нулем.

2. Х - существенным нулем матрицы С называется такой ее элемент с_ij = 0, для которого х_ij > 0, в противном случае этот элемент называется несущественным нулем.

Описание алгоритма венгерского метода. Алгоритм решения Т _d -задачи, основанный на венгерском методе, состоит из предварительного этапа и ряда однотипных итераций [18; 59].

Предварительный этап. Его цель - приведение матрицы С и построение начального приближения к решению Х ₀.

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

После этого формируют матрицу Х ₀=|| x_ij ⁰ ||, процесс построения которой ведут по столбцам. Пусть уже заполнены первые (j -1) столбцы матрицы Х ₀. Перенумеруем нули j-го столбца матрицы С₀ сверху вниз и через i_kj (k =1,2,., r) обозначим номер строки, содержащей k-й нуль j -го столбца. Тогда элементы j -го столбца определяются в соответствии с формулой

если k=1,2.. (3.3.21)

Если для матрицы Х ₀ суммарная невязка

то Х ₀ - оптимальной план Т _d -задачи.

Если же D₀>0, то переходят к первой итерации.

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

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

Пусть и еще не установлена неразрешимость Т_a-задачи.

Целью (k +1)-й итерации является построение матрицы Х _{k +1} и проверка ее на оптимальность или на установление неразрешимости Т _d -задачи. Перед началом итерации знаком '+' выделяют те столбцы матрицы С _k, для которых невязка

.

Первый этап. Выбирают произвольный невыделенный Х _k - неполный нуль матрицы С _k, если это элемент С _ij^k, то вычисляют невязку строки i, его содержащей:

.

Тогда возможен один из двух случаев:

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

В первом случае знаком '+' выделяют i -ю строку матрицы С _k, а элемент с_ij^k отмечают штрихом. Если на пересечении μ -го выделенного столбца i-й строки матрицы С _k расположен Х _k -существенный нуль матрицы С _k, то знак выделения этого столбца уничтожают, а сам элемент c_iμ^k =0 отмечают звездочкой. Далее просматривают столбец m, отыскивают в нем невыделенный неполный нуль (нули). Если такой нуль имеется, то отмечают его штрихом и анализируют строку, содержащую его. За конечное число шагов процесс выделения Х _k -неполных нулей матрицы С _k заканчивается одним из трех исходов:

1) найден Х _k -неполный нуль в строке і, где > 0, тогда переходим ко второму этапу, отметив этот нуль штрихом;

2) все Х _k -неполные нули выделены, для каждого из них , а среди невыделенных элементов матрицы С _k имеются либо положительные, либо среди дважды выделенных элементов С _k (т.е. элементов, расположенных на пересечении выделенных строк и столбцов), отрицательные элементы. В этом случае переходим к третьему этапу;

3) все Х _k -неполные нули выделены (для кажого из них d_и ^(k) = 0), все невыделенные элементы С _k - отрицательны, а дважды выделенные -положительны. Это означает неразрешимость Т _d - задачи.

Второй этап. Он состоит в построении цепочки из нулей матрицы С _k, отмеченных штрихами и звездочками. С помощью этой цепочки осуществляют переход от Х _k к Х _{k +1}. Итак, пусть первый этап завершился таким образом, что для некоторого невыделенного неполного нуля, расположенного, например, на пересечении строки l ₁ и столбца m ₁, невязка . Этот элемент принимают за начало цепочки из отмеченных нулей матрицы С _k. Цепочку строят так.

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

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

. (3.3.22)

Элементы х_ij (k+1) матрицы Х _{k +1} вычисляют по рекуррентной формуле

если - не входят в цепочку; если - нечетный элемент цепочки; если - четный элемент цепочки.

(3.3.23)

Параметр определяют из соотношения

, (3.3.24)

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

- невязкая строки, откуда начинается цепочка,

- невязкая столбца, где цепочка заканчивается.

Если суммарная невязка

то матрица Х _{k +1} является решением Т _d -задачі, в противном случае переходят к следующей итерации.

Третий этап. На этом этапе производят преобразование матрицы С _k в эквивалентную матрицу С _k '.

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

,

где h ' - минимальный среди невыделенных положительных элементов матрицы С _k; h '' - минимальный среди дважды выделенных отрицательных элементов матрицы С _k, взятых с обратным знаком. Вычитаем h из элементов матрицы С _k, расположенных в невыделенных строках, и прибавляем h к элементам С _k, расположенным в выделенных столбцах. Получим матрицу С _k '. Если дважды выделенный отрицательный элемент С _k становится нулем в С _k ', то знак выделения над столбцом уничтожают, а сам элемент отмечают звездочкой. Остальные знаки выделения, а также все отметки нулей переносят из матрицы С _k в матрицу С _k '.

Далее, снова переходят к первому этапу, заменив С _k на С _k '. Если первый этап снова завершится вторым исходом, то опять возвращаются к третьему этапу. Циклы, состоящие из первого и третьего этапов, проводят до тех пор, пока последний из них не закончится первым или третьим исходом. При первом исходе переходят ко второму этапу, а при третьем - делают вывод о неразрешимости Т _d -задачи из-за несовместимости ее условий.

Пример 3.6. Решить венгерским методом Т _d -задачу со следующими условиями

- матрица пропускных способностей коммуникаций.

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

.

Затем строим матрицу Х ₀ с учетом матрицы D:

.

Будем отмечать одной точкой сверху неполные нули матрицы С _k, а двумя точками Х _k -полные нули этих матриц. Строки матрицы С _k, которым отвечают ненулевые невязки, будем отмечать знаком '´'.

Первая итерация Третий этап

Первый этап Второй этап

Первая итерация. Первый этап. Знаком '+' выделяем четвертый столбец. Так как матрица С ₀ не содержит ни одного Х ₀ - неполного нуля, то сразу переходим к третьему состоянию, отыскиваем неполный невыделенный нуль, c ₂₃ и, отметив его штрихом, переходим ко второму этапу. Цепочка, построенная на втором этапе, состоит из одного элемента x ₃₂⁰ . Поэтому

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

+

Третья итерация

Первый этап Третий этап

Второй этап

D₃ = 2

Третья итерация состоит из первого и третьего этапов при h = 1, а также из первого и второго этапов, причем цепочка второго этапов, причем цепочка второго этапа содержит лишь один элемент x ₃₁².

Четвертая итерация

Первый и третий этапы

Третий этап Первый этап

Второй этап

Поскольку суммарная невязка D₄=0, то Х _4-оптимальный план. Соответствующее значение целевой функции L _min=3.I + 1.4 + 2.2 + 1.4 + 2.1 + 1.3 + 1.2 + 1.1 = 23.