Метод потенциалов

Общим методом решения транспортных задач является метод потенциалов.

Рассмотрим закрытую модель транспортной задачи на минимум (n поставщиков и m потребителей). Поставим в соответствие каждому поставщику некоторое число u_i, , а каждому потребителю - v_j, . Назовем эти числа потенциалами (по своему смыслу это переменные задачи, двойственной транспортной; u_i соответствуют первой группе ограничений, а v_j – второй [4, 5]).

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

Метод потенциалов решения транспортной задачи основан на двух теоремах [1, 12, 14], которые здесь приводятся без доказательства:

Теорема об изменении плана транспортной задачи.

Условие теоремы: пусть Х^о, Х¹ - опорные планы. Для всех базисных компонент первого из них сумма потенциалов равна коэффициенту целевой функции (т.е. если переменная x_ij^о – базисная, то c_ij = u_i + v_j). Во втором плане Х¹ все номера базисных компонент те же, кроме одной (т.е. при переходе от первого плана ко второму одна переменная из базиса вышла, а другая вошла). При этом для новой базисной переменной x_i₁_j1, сумма потенциалов больше коэффициента целевой функции (c_i₁_j1 < u_i₁ + v_j₁).

Утверждение теоремы: тогда новый план дешевле или по крайней мере не дороже (т.е. - при переходе к плану Х¹ целевая функция не возрастает).

Замечание: можно доказать, что при этом значение целевой функции уменьшится на x_i₁_j1¹(u_i₁ + v_j₁- с_i1_j1). В этом произведении второй сомножитель – обязательно положительный по условию теоремы, а вот первый может быть нулевым, если опорный план – вырожденный. Поэтому в случае вырожденности опорных планов (если x_i₁_j1¹ = 0) значение целевой функции может не измениться.

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

					u₁
					…
					u_i1
					…
					u_n
v₁	…	v_j1	…	v_m



			x_i₁_j1¹

Рисунок 1 – Иллюстрация к теореме об изменении плана
транспортной задачи

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

Теорема о критерии оптимальности транспортной задачи.

Пусть существует опорный план, для всех компонент которого сумма потенциалов не больше коэффициента целевой функции (т.е. u_i + v_j c_ij i,j). Причем для базисных компонент этого плана имеет место строгое равенство: u_i + v_j = c_ij. Тогда это оптимальный план.

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

1. Строится опорный план транспортной задачи. Это можно сделать любым из рассмотренных выше способов.

2. Для базисных элементов плана (т.е. заполненных клеток таблицы) формируется система уравнений {u_i + v_j = c_ij с неизвестными u_i и v_j.

Осуществляют решение этой системы. В этой системе (m+n–1) уравнение на (m+n) переменных, и она имеет бесконечное множество решений. Находят хотя бы одно решение.

3. Находят суммы потенциалов (u_i + v_j) для всех клеток таблицы. Они сравниваются с коэффициентами целевой функции c_ij также для всех клеток таблицы: {u_i + v_j c_ij.

Если это верно, то имеющийся план оптимален (по соответствующей теореме).

Если это не так, то находят ту клетку, для которой сумма потенциалов больше коэффициента целевой функции, т.е. (i₁,j₁): u_i₁ + v_j₁> c_i₁_j1

4. На основе (i₁,j₁) строится цикл пересчета плана.

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

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

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

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

5. Осуществляют разметку цикла следующим образом: в пустой клетке ставят знак «+», а затем помечают вершины цикла, чередуя знаки «-» и «+» (поскольку число клеток четное, направление безразлично).

6. Определяют величину пересчета плана, как наименьшее число из всех базисных компонент, помеченных знаком «-».

7. Строится новый опорный план следующим образом: в пустой клетке ставят число, равное величине пересчета плана - эта компонента входит в базис. К остальным вершинам цикла прибавляют или вычитают эту величину в зависимости от того, каким знаком они помечены. Компонента, соответствующая той клетке, в которой стояло это число, выходит из базиса, становится равной нулю. Если минимум (величина пересчета плана) достигается в нескольких клетках, то одну из этих клеток оставляют пустой, а в остальных ставят нули (имеет место вырожденный базис).

Затем возвращаются к пункту 2.

Рисунок 2 – Самопересечение цикла

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

Отметим, что для того, чтобы применить метод потенциалов к задаче на максимум, не обязательно ставить ее на минимум, - можно просто использовать другой критерий оптимальности (u_i + v_j c_ij) и соответственно выбирать клетку (i_o,j_o): u_io + v_jo < c_iojo.

Теорема о целочисленности решения транспортной задачи.

Если объемы запасов и потребностей заданы целыми числами, то и решение транспортной задачи, полученное методом потенциалов, будет целочисленным: a_i, b_j Î Z, i,j x_ij Z, i,j.