Транспортные задачи (стр. 3 )

Второй случай несбалансированности задачи имеет место, когда спрос превышает предложение:

.

При этом исходные условия записываются в виде:

Поступаем аналогично первому случаю. Введем в каждое неравенство дополнительную переменную xm+1,j. Очевидно, что сумма этих переменных равна величине дебаланса:

С учетом этого равенства сбалансированная модель принимает вид:

Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью am+1 и нулевыми затратами Cm+1,j. Дополнительная переменная xm+1,j имеет смысл количества груза, недопоставленного j-му ПН.

Рассмотренный формальный способ будет неприемлем, если потребители по-разному реагируют на недопоставки. Тогда возможны два варианта решения задачи:

1.  ЛПР корректирует потребности, обеспечивая баланс.

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

Если ожидается, что спрос будет длительное время превышать существующие возможности на величину am+1, то встает вопрос о расширении производства. Он может решаться в рамках транспортной модели следующим образом. Проектируются варианты увеличения производства, каждый на величину am+1. В исходную таблицу добавляется столько строк, сколько предлагается вариантов. При k вариантах это приведет к противоположному дебалансу, равному (k–1)·am+1. Поэтому для сбалансированности модели добавляется фиктивный потребитель с такой потребностью. А в качестве затрат во всех клетках таблицы принимаются суммарные затраты на перевозку и производство С’ij=Cij+Ci, где Ci – себестоимость в i-м ПО. Исключение составляет фиктивный столбец: в первых m клетках затраты равны M, а в остальных – нулю. Те варианты, которые в оптимальном решении закрепятся за фиктивным потребителем, должны быть отброшены.

При прогнозировании длительного превышения возможностей над спросом может возникнуть вопрос о сокращении производства. Он также может быть представлен в виде транспортной задачи. Достаточно в затраты включить себестоимость, как в предыдущем случае, и добавить фиктивного потребителя с потребностью bn+1 и нулевыми затратами. Оптимальные значения дополнительных переменных в фиктивном столбце дадут величину сокращения производства в соответствующих ПО с учетом полных затрат.

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

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

0 £ xij £dij.

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

0 < xij <dij. (5.24)

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

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

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

Xij=min(остаток от ai, остаток до bj, dij).

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

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

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

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

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

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

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

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

Таблица 5.8

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

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

(5.25)

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

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

;

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

.

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

(5.26)

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

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

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

. (5.27)

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

. (5.28)

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

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

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

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

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

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

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

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

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

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

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

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

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

5.5. Решение задачи по критерию времени

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

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

Любым из способов строится начальный план перевозок. Затем определяется текущее значение критерия Т(0) как максимальное время в занятых клетках (xij>0). Далее рассмотрим действия в цикле.

Пусть на k-й итерации получен план со значением критерия Т(k). Оно может быть уменьшено, если освободить клетку с tij= Т(k). С этой целью на клетке строится разгрузочный цикл так, чтобы в нечетных вершинах выполнялось неравенство tij<Т(k), а в четных – xij>0 (исходная вершина – четная). Очевидно, что такие правила позволяют в общем случае строить более одного цикла на выбранной клетки. В цикле вычисляется q0 как минимальная перевозка в четных вершинах. Вычитая q0 в четных вершинах и прибавляя в нечетных, получаем новый план. Если клетка с максимальным временем была единственной и перевозка в ней стала равна нулю, новый план улучшил значение критерия. Если клетка не обнулилась, то на ней строится другой разгрузочный цикл. В случае нескольких клеток со временем Т(k) для улучшения критерия необходимо разгрузить все. Решение завершается, когда нельзя разгрузить клетку (клетки), определяющую значение критерия.

Естественно, что рассмотренный метод не гарантирует получение оптимального решения.

5.6. Транспортные задачи в сетевой постановке
(транспортные сети)

Транспортную задачу можно представить в виде ориентированного графа с одним истоком (в него не входит ни одна дуга) и с одним стоком (из него не выходят дуги), который называют в этом случае сетью. Вершинам графа ставятся в соответствие пункты отправления, назначения и промежуточные пункты. Основной параметр вершины – количество груза. Дуги отображают коммуникации. Им могут быть приписаны такие параметры как количество груза, затраты на перевозку, пропускная способность.

Исходный граф транспортной задачи легко сводится к сети с одним стоком и одним истоком путем введения фиктивных пунктов t (исток) и s (сток). Фиктивным дугам приписываются значения параметров: dti=ai, djs=bj, Cti=Cjs=0. Пример сети транспортной задачи без промежуточных пунктов приведен на рис. 5.6.

Модель Тd-задачи в сетевой постановке имеет вид:

ååCijxij®min; (5.29)

k¹t, k¹s; (5.30)

(5.31)

В сбалансированной транспортной задаче

Z=åai=åbj; (5.32)

0£xij£dij. (5.33)

Равенства (5.30) отражают условия баланса для всех пунктов кроме источника и стока. Баланс для последних представлен уравнением (5.31). В модели использованы обозначения: – множество дуг, входящих в вершину k и выходящих из нее, Z – новая величина, называемая потоком сети.

Наибольший интерес представляет постановка задачи, в которой критерием является поток сети:

Z® max; (5.34)

k¹t, k¹s; (5.35)

(5.36)

0£xij£dij. (5.37)

Задача (5.34) – (5.37) называется задачей о максимальном потоке. Она имеет большое практическое значение. Для нее разработаны алгоритмы, которые эффективнее методов решения транспортных задач. Они работают непосредственно с сетью как разновидностью графов.

В связи с этим напомним понятие разреза графа (сети), которое используется в основополагающей теореме Форда-Фалкерсона.

Пусть дан ориентированный граф G=(V,U), где V и U - множества вершин и дуг соответственно. Разрезом сети на подмножестве вершин AÌV, A¹Æ, A¹V, tÎA, sÎV\A называется множество дуг ijÎU таких, что iÎA & jÎV\A. Обозначим его P(A). Сумма пропускных способностей дуг разреза называется величиной (пропускной способностью) разреза:

Пример 5.5. Построим один из разрезов сети, приведенной на рис.5.7.

Если A={t,1,2,3}, то разрезом будет множество дуг P(A)={1,4; 1,6; 2,5; 3,6}, а его величина определяется как d(A)=d14+d16+d25+d36. Дуги, составляющие этот разрез, выделены жирными линиями.▲

Разрез сети, имеющий минимальную пропускную способность, называется минимальным разрезом.

Можно показать, что задачи максимизации потока и минимизации величины разреза являются двойственной парой. Из этого факта следует
Теорема Форда и Фалкерсона:

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

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