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

Существует два вида постановки — матричная и сетевая. В матричной постановке провоз разрешается только от производителя к потребителю. В сетевой постановке провоз может осуществляться в любом направлении (пункты могут быть транзитными). Пусть ${\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.