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

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

5.2.2. Переход от одного плана перевозок к другому

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

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

Такая цепь называется циклом пересчета. Он является геометрическим представлением разложения небазисного вектора условий при переменной в свободной клетке по векторам текущего базиса. Если базисная клетка не попала в цикл пересчета, то соответствующий базисный вектор имеет в этом разложении нулевой коэффициент. Так как любой небазисный вектор выражается через базис единственным образом, то для любой небазисной (свободной) клетки можно построить один и только один цикл пересчета. Примеры конфигурации циклов показаны на рис. 5.2.

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

Теперь становится очевидным, что в каждой строке и каждом столбце, по которым проходит цикл пересчета, будет две и только две вершины: одна четная и одна нечетная. Если бы оказалось вершин больше двух, то из базисных клеток образовался бы цикл, что невозможно. В этом легко убедиться на примере: допустим, в правом цикле на рис. 5.2 отрезки 1-8 и 5-4 лежат в одной строке, тогда вершины 1, 4, 3 и 2 образуют цикл.

В результате цикл пересчета, построенный в допустимой матрице перевозок, обладает замечательным свойством: если перемещать по нему некоторое количество груза q >0, прибавляя его к Xij в четных вершинах и вычитая из Xij в нечетных, то условия задачи (5.3) и (5.4) не нарушатся. Чтобы новое решение было допустимым, то есть выполнялось и условие неотрицательности переменных, необходимо ограничить значение q:

q £ q0=min Xij, ijÎ нечет. (5.14)

Здесь нечет – множество индексов переменных в нечетных вершинах цикла.

Для получения базисного решения (нового опорного плана) достаточно взять q =q0. При этом переменная свободной клетки, на которой строился цикл, становится базисной со значением q0, а переменная, доставляющая минимум в (5.14), обнуляется и переходит в небазисные.

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

5.2.3. Признак оптимальности

При перемещении q по циклу пересчета увеличиваются на эту величину значения переменных Xij в четных вершинах, а следовательно, увеличиваются и затраты на перевозку на q Cij. Одновременно уменьшаются на q переменные в нечетных вершинах и на q Cij соответствующие им затраты. Отсюда следует, что значение критерия в новом, (k+1)-м решении можно определить по критерию в исходном решении и изменениям в клетках цикла:

или

, (5.15)

где

(5.16)

Здесь, как и в симплекс-методе, Δij – относительная оценка переменной Xij, на которой построен цикл. Для базисных переменных оценка всегда равна нулю. Согласно (5.15) Δij показывает, как изменится критерий (в какую сторону и насколько) при перемещении по циклу единицы груза (q =1).

Если Δij>0, то введение Xij в число базисных приведет к уменьшению суммарных затрат. Если же Δij<0, критерий возрастет, что противоречит цели. Следовательно, решение нельзя улучшить, когда среди оценок нет положительных, и поэтому признак оптимальности имеет вид

"Δij£0. (5.17)

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

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

Поставим в соответствие каждому пункту отправления сбалансированной задачи некоторую величину Ui, i=1, 2,…, m, а каждому пункту назначения – Vj, j=1, 2,…, n так, чтобы для базисных клеток выполнялись равенства

Vj -Ui=Cij, i jÎбаз. (5.18)

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

Зная Ui и Vj, можно вычислить относительную оценку для любого цикла в текущем плане перевозок. Покажем это на произвольно взятом цикле (рис. 5.3).

В скобках указаны индексы клеток (переменных), в которых расположены вершины цикла. Вычисляем относительную оценку свободной клетки i0j0 ( небазисной переменной Xiojo) по формуле (5.16):

Δiоjо=Ciоj1 - Ci1j1+ Ci1j2 - Ci2j2+ Ci2jо - Ciоjо.

Заменим в этом выражении затраты в базисных клетках согласно (5.18). Тогда получим

Δiоjо =Vj1 -U iо -Vj1+Ui1+Vj2 -Ui1 -Vj2+Ui2+Vjо -Ui2 -Ciоjо =Vjo-Uio-Ciojo.

Выполненные сокращения не зависят от конфигурации цикла, так как все индексы кроме начальных входят в выражение два раза. Поэтому в итоге остаются только Vjo, Uio и Ciojo. Таким образом, для любой свододной клетки ij относительная оценка может быть вычислена без построения цикла пересчета по формуле

Δij=Vj-Ui-Cij. (5.19)

Из сравнения (5.18) и (5.19) видно, что для базисных клеток Δij=0.

Новые переменные Ui и Vj называются потенциалами пунктов отправления и назначения соответственно, отсюда происходит название метода. Из формулы (5.19) следует, что значение постоянной величины при нахождении потенциалов из системы (5.18) не влияет на оценки.

Потенциалы можно интерпретировать как локальные цены. Если цена в пункте отправления i равна Ui и груз из него доставляется в пункт назначения j по коммуникации ij, то локальная цена в ПН возрастет по отношению к ПО на величину транспортных затрат:

Vj=Ui+ Cij. (5.20)

Из этого соотношения также следует, что в оптимальном решении не может иметь место неравенство

Vj >Ui+ Cij,

так как оно означает, что локальная цена в пункте j выше, чем в случае прямой доставки из i в j.▲

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

Рассмотрим конкретно преобразование матрицы D(k) в матрицу D(k+1) на основе нового решения X(k+1). Как отмечалось выше, новое решение получено вводом небазисной переменной с максимальной оценкой в D(k). Пусть max Dij=Dkr. В матрице D(k) отмечаем элементы, соответствующие базисным в новом решении X(k+1) (на рис. 5.4 помечены символом *), максимальную оценку отмечаем особо. Далее строим цепочку выделения. Она строится с особо отмеченного элемента, который соединяют с отмеченными в этой строке. Затем отмеченные элементы, попавшие в цепочку, соединяют с отмеченными в их столбцах. Далее снова проводим соединение по строкам, и так до тех пор, пока не оборвутся все ветви.

Рис.5.4

Элементы, попавшие в цепочку выделения, выделяют строку и столбец за исключением особо отмеченного элемента, который выделяет только строку. К выделенным столбцам прибавляем, а из выделенной строки вычитаем . Нетрудно увидеть, что при этом переменной Xkr будет соответствовать нулевая оценка, как и тем перменным из решения X(k), которые сохранили статус базисных. Таким образом, преобразованная матрица соответствует новому опорному плану.

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

5.2.4. Алгоритм метода потенциалов

Алгоритм включает предварительный и основной этапы.

Предварительный этап:

1.  В матрице перевозок построить начальный план X(0).

2.  Решением системы (5.18) определить потенциалы всех пунктов в начальном плане.

3.  Вычислить оценки небазисных переменных (свободных клеток) по формуле (5.19) и записать матрицу D(0).

Основной этап (получены X(k) и D(k)):

1.  Проверить оценки в D(k). Если нет положительных, то перейти на п. 9.

2.  Определить максимальную оценку Dkr = max Dij.

3.  В матрице X(k) построить цикл пересчета на клетке kr.

4.  В построенном цикле вычислить q0=min Xij, ijÎ нечет.

5.  Прибавить q0 в четных вершинах цикла и вычесть в нечетных, результат – матрица перевозок X(k+1).

6.  В матрице D(k)) провести выделение строк и столбцов по решению X(k+1).

7.  К выделенным столбцам прибавить, а из выделенных строк вычесть Dkr, результат – матрица D(k+1).

8.  Перейти на п.1 основного этапа.

9.  Конец.

Примечание. Если имелись запрещенные перевозки (некоторые Cij=M), то соответствующие переменные в последнем решении должны равняться нулю. В противном случае задача неразрешима.

Пример 5.3. Решить методом потенциалов транспортную задачу, представленную в табл. 5.4.

Таблица 5.4

Поставщик (ПО)	Потребитель (ПН)	Количество груза
B1	B2	B3	B4
A1	3	8	2	1	10
A2	1	4	3	5	30
A3	7	2	1	6	40
Потребность в грузе	20	5	30	25	S=80

Решение. Задача сбалансированная. Начальный опорный план перевозок строим по правилу северо-западного угла. Полученный план невырожденный (табл. 5.5). Число базисных переменных (занятых клеток) r=m+n-1=3+4-1=6, они выделены цветом.

Таблица 5.5

Поставщик (ПО)	Потребитель (ПН)	Количество груза
B1	B2	B3	B4
A1	3 10 -	8	2	1 +	10
A2	1 10 +	4 5	3 15 -	5	30
A3	7	2	1 15 +	6 25 -	40
Потребность в грузе	20	5	30	25	S=80

Значение критерия в начальном плане

Вводим потенциалы для ПО и для ПН так, чтобы для базисных клеток выполнялись равенства:

Полагая последовательно находим остальные потенциалы:

Вычисляем для свободных клеток:

Записываем матрицу оценок для начального плана перевозок:

В начальном плане строим цикл на клетке с максимальной оценкой. Это клетка (1,4). Находим значение вводимой переменной:

=min(10,15,25)=10.

Переместив q0 по циклу, получаем новый план перевозок

для которого первая итерация улучшила критерий на 90 единиц.

Для выяснения статуса нового решения находим матрицу оценок. С этой целью в D(0) отмечаем элементы, соответствующие базисным в X(1), и строим цепочку выделения. Так как в строке с максимальной оценкой других отмеченных элементов нет, выделенной оказывается только первая строка. Вычитая из нее Dkr, получаем матрицу

.

Как следует из анализа матрицы D(1), решение X(1) не является оптимальным. Следующее решение получаем с помощью построенного в X(1) цикла, перемещая по нему :

Мы получили новый план перевозок с критерием

.

Матрицу оценок этого плана находим преобразованием матрицы D(1) аналогично описанному выше. В результате имеем

В матрице есть положительный элемент, поэтому на клетке (3,2) строим цикл пересчета. Определяем и, перемещая 5 по циклу, находим очередной план перевозок

которому соответствует значение критерия. Преобразуя матрицу D(II), получаем

.

Эта матрица не содержит положительных оценок, следовательно, план  является оптимальным. Согласно этому плану от 1-го поставщика надо поставить 10 ед. продукции 4-му потребителю, от 2-го поставщика - 20 ед. первому и 10 ед. четвертому потребителям, от 3-го поставщика - 5, 30 и 5 ед. соответственно 2, 3 и 4 потребителям. Такая схема перевозок обеспечивает минимум суммарных затрат, которые равны 150.▲

Примечания. 1).Метод потенциалов применим и для решения трипланарных задач. Отличие лишь в том, что циклы пересчета и цепочки выделения строятся не на плоскости, а в трехмерном пространстве. 2).Если на каждой итерации оценки вычислять непосредственно по построенным циклам (на всех свободных клетках), то получим распределительный метод. Поэтому метод потенциалов называют также модифицированным распределительным методом. Однако метод потенциалов значительно эффективнее распределительного на задачах средней и большой размерности.

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

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

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

;

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

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

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

(5.21)

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

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

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

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

5.3. Приведение открытой транспортной задачи к закрытой

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

.

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

Рассмотрим формальные приемы. Пусть в исходной задаче предложение превышает спрос:

Тогда условия задачи имеют вид

(5.22)

(5.23)

В каждое неравенство (5.22) введем дополнительную переменную xi,n+1. В сумме эти переменные должны равняться величине дебаланса:

Добавляя это равенство к условиям (5.23), получаем закрытую задачу:

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