Обоснование метода потенциалов

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

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

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

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

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

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

q £ q₀ =min X_ij, ijÎ нечет. (5.14)

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

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

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

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

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

или

, (5.15)

где

(5.16)

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

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

"Δ_ij£0. (5.17)

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

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

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

V_j -U_i=C_ij, i j Îб аз. (5.18)

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

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

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

Δ _iоjо=C_iоj1 - C_i1j1+ C_i1j2 - C_i2j2+ C_i2jо - C_iоjо.

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

Δ _iоjо = V_j1 -U _iо -V_j1+U_i1+V_j2 -U_i1 -V_j2+U_i2+V_jо -U_i2 -C_iоjо = V_jo-U_io-C_iojo.

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

Δ _ij=V_j-U_i-C_ij. (5.19)

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

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

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

V_j=U_i+ C_ij. (5.20)

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

V_j >U_i+ C_ij,

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

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

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

Рис.5.4

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

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