Метод потенциалов | это... Что такое Метод потенциалов? (original) (raw)

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

Содержание

1 Формулировка транспортной задачи
2 Алгоритм
3 Незамкнутые задачи
4 Несколько замечаний об эффективности алгоритма
5 Ограничения на пропускную способность
- 5.1 Алгоритм

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

Пусть - пункты производства/потребления, - дуги перевозок, C[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}$ - дуги, соответствующие, обычным ограничениям ()

$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}] - CN_{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 (как в стандартном алгоритме) или на верхнюю границу пропускной способности - переводим ее в насыщенные.

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

Методы оптимизации
Одномерные	Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск
Прямые методы	Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка
Первого порядка	Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта
Второго порядка	Метод Ньютона • Метод Ньютона — Рафсона
Стохастические	Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц
Методы линейного программирования	Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов
Методы нелинейногопрограммирования	Последовательное квадратичное программирование