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

Рассмотрим Т_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₊₁ и проверка ее на оптимальность или на установление неразрешимости Т_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₊₁. Итак, пусть первый этап завершился таким образом, что для некоторого невыделенного неполного нуля, расположенного, например, на пересечении строки l₁ и столбца m₁, невязка . Этот элемент принимают за начало цепочки из отмеченных нулей матрицы С_k. Цепочку строят так.

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

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

. (3.3.22)

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

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

(3.3.23)

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

, (3.3.24)

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

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

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

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

то матрица Х_k₊₁ является решением Т_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 , которым отвечают ненулевые невязки, будем отмечать знаком '´'.

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