Двойственная пара транспортных задач

Построим двойственную задачу простейшей транспортной задачи (Т-задачи). Предварительно изменим знаки в выражении критерия и в условиях по пунктам назначения. Тогда модель прямой задачи примет вид:

Здесь слева от равенств записаны сопоставленные им двойственные переменные. Модель двойственной задачи запишем по правилам, приведенным в разд. 4.11.3:

;

Если C_ij перенести в левую часть, то согласно (5.19) условия двойственной задачи приобретают смысл признака оптимальности "Δ_ij£0.

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

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

(5.21)

Отсюда находим:

Учитывая линейность (5.21), полный дифференциал запишем в виде

Изменения a_i и b_j могут быть только равными, иначе нарушится сбалансированность задачи. Если положить D a_i= D b_j =1, то получим

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

25. Метод потенциалов для T_d-задачи

Транспортная задача с ограниченными пропускными способностями (5.7)-(5.10) отличается от T-задачи наличием ограничений сверху на перевозки:

0 £ x_ij £ d_ij.

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

0 < x_ij < d_ij. (5.24)

В вырожденном решении некоторые базисные переменные равны граничным значениям (0 или d_ij).

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

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

X_ij =min(остаток от a_i, остаток до b_j, d_ij).

Если минимум достигается на d_ij, то не закрывается ни строка, ни столбец, и следует продолжать движение по строке или столбцу (если двигались по столбцу). Однако может оказаться, что в строке (столбце) больше нет открытых клеток, а она не закрыта. Это значит, что начальный план получается недопустимым. Если часть строк (столбцов) не закрыта, то обязательно не закроются и некоторые столбцы (строки). Так как задача сбалансированная, то суммарная величина незакрытия строк будет равна суммарному незакрытию столбцов . Обозначим эту величину g. Чтобы в этом случае завершить построение начального плана, добавляют фиктивного потребителя (столбец) и фиктивного поставщика (строку) с одинаковой потребностью и возможностью g. Так как их клетки соответствуют искусственным переменным, которые в разрешимой задаче должны стать равными нулю, затраты в них полагают бесконечно большими (М), а в клетке на пересечении фиктивного столбца с фиктивной строкой – равными нулю. Пропускные способности в фиктивных клетках не лимитируются. В процессе работы алгоритма план станет допустимым, когда все искусственные переменные обнулятся, то есть в юго-восточной клетке перевозка станет равна g (фиктивный поставщик замкнется на фиктивного потребителя).

После построения начального плана определяются базисные клетки по условию (5.24). Если таких клеток окажется меньше m+n-1 (вырожденный план), то в число базисных включают переменные (клетки), равные нулю или d_ij. При этом на базисных клетках не должен строиться замкнутый цикл, иначе клетки добавлены неверно.

Пример 5.4. Исходные данные задачи приведены в табл. 5.6. В клетках слева даны пропускные способности (красным цветом), справа – затраты на перевозки (синим цветом). Задача сбалансированная. Начальный план строим по правилу минимального элемента, порядок построения показан стрелками (табл. 5.7). Строка 4 и столбцы 2 и 3 не закрылись: g =3.

 

Таблица 5.6 Таблица 5.7

bj ai					bj ai
12	8 3	5 1	10 5			8 3	5 1 ·5	10 5 7
	5 2	9 4	4 7			5 2	9 4 6	4 7
	12 6	11 2	10 3			12 6	11 2 11	10 3 9
	20 4	10 5	7 9			20 4 15	10 5 10	7 9 7

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

Так как общее число пунктов равно 9, то базисных переменных должно быть 8. Из сравнения значений x_ij и d_ij находим только 7 базисных переменных (базисные клетки закрашены), то есть план вырожденный. В качестве недостающей базисной клетки возьмем клетку 4,2 (закрашена более темным цветом), в которой значение переменной находится на верхней границе.

Нетрудно убедиться, что ни из каких базисных клеток нельзя построить замкнутый цикл. (Чтобы соблюдалось это требование в случае вырожденности плана, можно рекомендовать рассматривать в качестве кандидатов на включение в число базисных в первую очередь те клетки, в которых происходит поворот на 90 градусов при построении плана. Так, в данном примере такими являются клетки 4,2 и 4,3.) ▲

Таблица 5.8

bj ai				g =3
	8 3	5 1 5	10 5 7	М
	5 2	9 4 6	4 7	М
	12 6	11 2 11	10 3 9	М
	20 4 15	10 5 10	7 9 7	М 3
g =3	М	М 1	М 2

Теперь рассмотрим изменения на основном этапе алгоритма. Признак оптимальности в T_d-задаче расширяется. Согласно (5.15) при введении в решение небазисной переменной x_ij= 0, то есть ее увеличении, критерий уменьшается при D _ij >0 и увеличивается при D _ij <0. Если же вводить переменную x_ij=d_ij, а это означает ее уменьшение, то критерий уменьшится при D _ij <0 и возрастет при D _ij >0. Этот характер изменения критерия показан на рис. 5.5. Поэтому решение не может быть улучшено, если выполняются условия, составляющие признак оптимальности задачи с ограниченными пропускными способностями:

(5.25)

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

- множество индексов переменных на нижней границе

;

- множество индексов переменных на верхней границе

.

Очевидно, что объединенное множество G= È является множеством индексов перспективных переменных (клеток): введение любой из них приведет к улучшению критерия. В Т-задаче имеется только множество , и выбор производится из него. Здесь же выбор переменной, вводимой в базис, осуществляется на множестве G:

(5.26)

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

Из (5.26) следует, что возможны 2 варианта при выборе вводимой переменной и соответственно 2 варианта перехода к новому плану:

1. Если , то цикл строится на клетке, в которой перевозка равна нулю. Новый план получается прибавлением q₀ в четных вершинах цикла и вычитанием в нечетных. Поэтому

. (5.27)

2. Если , цикл строится на клетке, в которой перевозка равна d_ij. В этом случае вводимая переменная должна уменьшаться. Поэтому перемещение по циклу состоит в вычитании q₀ в четных вершинах и прибавлении в нечетных. Отсюда следует, что

. (5.28)

В обоих вариантах значение критерия улучшается на величину q₀ |D_kr|.

Таким образом, алгоритм решения сбалансированной Т_d-задачи включает следующие шаги:

1. Построение начального плана перевозок. План может получиться как допустимый, так и искусственный (недопустимый).

2. Выделение базисных клеток. Если их меньше m+n- 1, то добавляются клетки на границе.

3. Нахождение потенциалов из системы (5.18).

4. Вычисление оценок по формуле (5.19)

5. Начало цикла. Определение множества G по матрицам плана и оценок.

6. Проверка признака оптимальности: если G =Æ (эквивалент (5.25)), переход на шаг 10.

7. Определение вводимой переменной (клетки kr) по (5.26) и построение цикла пересчета.

8. Построение нового плана: вычисление q₀ в зависимости от принадлежности kr по (5.27) или (5.28) и соответствующее перемещение по циклу.

9. Получение матрицы оценок нового плана с помощью преобразования матрицы оценок старого плана (как в Т-задаче). Переход на шаг 5.

10. Конец. Полученный план является оптимальным, если не содержит запрещенных перевозок (с затратами М).

Когда решение начинается с искусственного плана, то после достижения допустимого решения можно сократить матрицы перевозок и оценок за счет отбрасывания фиктивных столбца и строки. Если в них было ровно две базисные клетки, то пересчитывать матрицу оценок не надо. Иначе она рассчитывается через потенциалы для сокращенного плана. Однако сокращение матриц не является обязательным.