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

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

Формулировка транспортной задачи

Пусть $M$ - пункты производства/потребления, $N$ - дуги перевозок, $C[N]$ - цены провоза по дугам $N$, $N_B$ - набор базисных столбцов.

Задача формулируется как найти $min(C[N]x[N])$

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

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

$x[N]$ - решение

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

Алгоритм

Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица $B[M,N_B]$ представлена в виде дерева.

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

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

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

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

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

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

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

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

Незамкнутые задачи

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

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

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

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

Несколько замечаний об эффективности алгоритма

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

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

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

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

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

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

Ограничения на пропускную способность

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

найти $min(C[N]x[N])$

при условиях

$A[M,N]x[N]=b[M]$

$E[N_L,N_L]x[N_L]+E[N_L,N_L]p[N_L]=L[N_L]$

Здесь $p[N_L]$ - дополнительные переменные (вводятся для преобразования неравенства в равенство).

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

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

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

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

Базисная матрица имеет вид $\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}$

Обратная к базисной тогда равна $\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}$

Двойственные переменные вычисляются по формуле $\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}$

Здесь

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

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

Алгоритм

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

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

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