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

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

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

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

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

Алгоритм

Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица $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\rightarrow j)\in N_{B}$ потенциалы дуг связаны формулой $P[i]+C[n]=P[j]$.

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

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

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

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

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

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

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

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

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

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

Метод северо-западного угла

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

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

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

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

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

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

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

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}]$ — добавочная цена за провоз по насыщенной дуге.

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

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

Алгоритм

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

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