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

Существует два вида постановки — матричная и сетевая. В матричной постановке провоз разрешается только от производителя к потребителю. В сетевой постановке провоз может осуществляться в любом направлении (пункты могут быть транзитными). Пусть ${\displaystyle M}$  — пункты производства/потребления, ${\displaystyle N}$  — дуги перевозок, ${\displaystyle C[N]}$  — цены провоза по дугам ${\displaystyle N}$ , ${\displaystyle N_{B}}$  — набор базисных столбцов.

Задача формулируется как ^[1]

найти ${\displaystyle min(C[N]x[N])}$ 

при условиях ${\displaystyle A[M,N]x[N]=b[M]}$ 

где ${\displaystyle C[N]}$  — стоимости провоза по дугам, ${\displaystyle b[M]}$  — производство (+) / потребление (-)

${\displaystyle x[N]}$  — решение

Матрица ограничений транспортной задачи состоит из столбцов ${\displaystyle A[M,N]}$ , содержащих всего два ненулевых элемента — +1 для производителя и −1 для потребителя ^[2].

Замечание: Вообще говоря, любая квадратная подматрица ${\displaystyle A[M,M']}$  (т.е. ${\displaystyle |M'|=|M|,M'\subset N}$ ) матрицы ${\displaystyle A[M,N]}$  вырождена, так что для работы симплекс-метода необходимо вводить искусственные переменные, либо исключить одну строку из рассмотрения. При использовании свалки (см. ниже) именно соответствующая ей строка и исключается из рассмотрения.

Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица ${\displaystyle B[M,N_{B}]}$  представлена в виде дерева ^[3].

Двойственные переменные симплекс-метода для транспортной задачи называются потенциалами.

Потенциалы ${\displaystyle P[M]}$  вычисляются по формуле ${\displaystyle C[N_{B}]=B[M,N_{B}]P[M]}$  , что эквивалентно ${\displaystyle P[M]=C[N_{B}]B^{-1}[N_{B},M]}$ 

Для дуги ${\displaystyle n(i\rightarrow j)\in N_{B}}$  потенциалы дуг связаны формулой ${\displaystyle P[i]+C[n]=P[j]}$ .

Таким образом, потенциал потребителя равен потенциалу производителя + стоимость перевозки. С экономической точки зрения это можно трактовать как стоимость продукта в точке потребления.

Проверка оптимальности плана ${\displaystyle P[i]+C[n]\geq P[j]}$  легко трактуется с экономической точки зрения — если стоимость продукта в точке потребления больше стоимости в точке производства + цена перевоза, по этой дуге следует везти. Величина ${\displaystyle P[j]-P[i]-C[n]}$  называется невязкой дуги.

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

Остаётся только пересчитать потенциалы — добавить (или вычесть — зависит от направления дуги) ко всем вершинам «повисшей ветки» на величину невязки ${\displaystyle P[j]-P[i]-C[n]}$ 

Процесс завершается, когда условие оптимальности ${\displaystyle P[i]+C[n]\geq P[j]}$  выполняется для всех дуг.

Задача замкнута, если сумма производств равна сумме потребления.

Обычно в постановке сумма производства больше суммы потребления. Для решения незамкнутых задач, а также для простоты получения начального базисного плана используется метод искусственного базиса ^[4]. Для этого исходный граф расширяется, вводится «свалка» — дополнительный пункт, на который свозится все лишнее производство за нулевую цену.

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

Дуги на свалку от пунктов производства соответствуют дополнительным переменным в симплекс-методе, а дуги со свалки к пунктам потребления соответствуют искусственным переменным.

Для матричной транспортной задачи возможен другой алгоритм построения начального плана.

1. Выберем какую-либо вершину i.

2. Выберем дугу, инцидентную i. Поток по дуге положим равным минимуму из объёмов производства и потребления на концах дуги. Уменьшим эти объёмы на величину потока по дуге. Вершину с нулевым объёмом устраним из рассмотрения вместе с инцидентными ей дугами. Переходим к пункту 2.

Если вершины производств и потребления перенумерованы и каждый раз выбирается дуга с наименьшим номером, метод называется методом северо-западного угла ^[5].

Определение выводимой дуги и пересчет потенциалов достаточно эффективно реализуется. Основным «потребителем» времени становится проверка оптимальности^[6].

Для уменьшения времени на проверку оптимальности применяется несколько приемов.

1. Использование барьера — как только величина невязки больше некоторой величины, дугу вводим в базис, не перебирая остальные дуги. Если дуга не найдена, уменьшаем барьер до максимальной найденной невязки и соответствующую дугу вводим в базис.

2. Циклический просмотр — перебор начинается с того места, на котором остановились в предыдущем просмотре.

3. Выбор «претендентов» — при просмотре выбирается не одна дуга, а несколько. На следующем шаге проверяются только отобранные дуги.

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

Для некоторых дуг ${\displaystyle N_{L}}$  могут быть заданы ограничения на пропускную способность ${\displaystyle L[N_{L}]}$ . Небольшое усложнение алгоритма может позволить решить задачу с ограничениями на пропускную способность ^[7].

найти ${\displaystyle min(C[N]x[N])}$ 

при условиях

${\displaystyle A[M,N]x[N]=b[M]}$ 

${\displaystyle E[N_{L},N_{L}]x[N_{L}]+E[N_{L},N_{L}]p[N_{L}]=L[N_{L}]}$ 

Здесь ${\displaystyle p[N_{L}]}$  — дополнительные переменные (вводятся для преобразования неравенства в равенство).

Базис ${\displaystyle N_{B}}$  будет состоять из трех множеств — ${\displaystyle N_{BN}}$ , ${\displaystyle N_{BL}}$  и ${\displaystyle N_{BP}}$ .

где ${\displaystyle N_{BN}}$  — дуги, соответствующие, обычным ограничениям (${\displaystyle M}$ )

${\displaystyle N_{BL}}$  — дуги, вышедшие на ограничение на пропускную способность (насыщенные дуги) (${\displaystyle x[N_{L}]}$ )

${\displaystyle N_{BP}}$  — дуги, не вышедшие на ограничение на пропускную способность (соответствуют дополнительным переменным)(${\displaystyle p[N_{L}]}$ )

Базисная матрица имеет вид ${\displaystyle {\begin{bmatrix}A[M,N_{BN}]&A[M,N_{BL}]&0[M,N_{BP}]\\0[N_{BL},N_{BN}]&E[N_{BL},N_{BL}]&0[N_{BL},N_{BP}]\\0[N_{BP},N_{BN}]&0[N_{BP},N_{BL}]&E[N_{BP},N_{BP}]\\\end{bmatrix}}}$ 

Обратная к базисной тогда равна ${\displaystyle {\begin{bmatrix}A^{-1}[N_{BN},M]&-A^{-1}[N_{BN},M]A[M,N_{BL}]&0[M,N_{BP}]\\0[N_{BL},N_{BN}]&E[N_{BL},N_{BL}]&0[N_{BL},N_{BP}]\\0[N_{BP},N_{BN}]&0[N_{BP},N_{BL}]&E[N_{BP},N_{BP}]\\\end{bmatrix}}}$ 

Двойственные переменные вычисляются по формуле ${\displaystyle {\begin{bmatrix}C[N_{BN}]A^{-1}[N_{BN},M]&C[N_{BL}]-C[N_{BN}A^{-1}[N_{BN},M]A[M,N_{BL}]&C[N_{BP}]\end{bmatrix}}}$ 

Здесь

${\displaystyle C[N_{BN}]A^{-1}[N_{BN},M]}$  — потенциалы (как в стандартном методе потенциалов).

${\displaystyle C[N_{BL}]-C[N_{BN}]A^{-1}[N_{BN},M]A[M,N_{BL}]}$  — добавочная цена за провоз по насыщенной дуге.

Также ограничение пропускной способности дуги можно добавить небольшой модификацией графа ^[8].

В дугу А->В со стоимостью с и максимальной пропускной способностью p добавляются 2 вершины: C с потреблением -p и D с производством p. Вершины связываются по схеме A->C<-D->B вместо A->B. Дуга A->С имеет стоимость c, дуги C<-D и D->B - нулевую стоимость. Такая схема не позволяет пропустить между пунктами A->B поток больший, чем p.

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

Аналогично стандартному алгоритму пересчитываются и потенциалы.