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

Рассмотрим Т_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.

• ⇐ Назад
1
2
34