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

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

Формулировка транспортной задачи 
Существует два вида постановки — матричная и сетевая.
В матричной постановке провоз разрешается только от производителя к потребителю.
В сетевой постановке провоз может осуществляться в любом направлении (пункты могут быть транзитными).
Пусть  — пункты производства/потребления,  — дуги перевозок,  — цены провоза по дугам ,  — набор базисных столбцов.

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

найти 

при условиях 

где  — стоимости провоза по дугам,  — производство (+) / потребление (-)

 — решение

Матрица ограничений транспортной задачи состоит из столбцов , содержащих всего два ненулевых элемента — +1 для производителя и −1 для потребителя .

Замечание: Вообще говоря, любая квадратная подматрица  (т.е. ) матрицы  вырождена, так что для работы симплекс-метода необходимо вводить искусственные переменные, либо исключить одну строку из рассмотрения. При использовании свалки (см. ниже) именно соответствующая ей строка и исключается из рассмотрения.

Алгоритм 
Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица  представлена в виде дерева .

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

Потенциалы  вычисляются по формуле
 , что эквивалентно

Для дуги  потенциалы дуг связаны формулой .

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

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

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

Остаётся только пересчитать потенциалы — добавить (или вычесть — зависит от направления дуги) ко всем вершинам «повисшей ветки» на величину невязки 

Процесс завершается, когда условие оптимальности  выполняется для всех дуг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

найти 

при условиях

Здесь  — дополнительные переменные (вводятся для преобразования неравенства в равенство).

Базис  будет состоять из трех множеств — ,  и .

где
 — дуги, соответствующие, обычным ограничениям ()

 — дуги, вышедшие на ограничение на пропускную способность (насыщенные дуги) ()

 — дуги, не вышедшие на ограничение на пропускную способность (соответствуют дополнительным переменным)()

Базисная матрица имеет вид

Обратная к базисной тогда равна

Двойственные переменные вычисляются по формуле

Здесь

 — потенциалы (как в стандартном методе потенциалов).

 — добавочная цена за провоз по насыщенной дуге.

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

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

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

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

Примечания

Ссылки 

 
 Дж. Данциг. Линейное программирование, его применения и обобщения. Издательство «Прогресс» Москва 1966
 С.Гасс. Линейное программирование (методы и приложения). Перевод с английского Гольштейна Е. Г. и Сушкевича М. И. Под редакцией Юдина Д.Б. М:Государственное издательство физико-математической литературы 1961 
А.В. Кузнецов, Н.И. Холод, Л.С Костевич. Руководство к решению задач по математическому программированию. Минск, «Вышэйшая школа» 1978
 Лунгу К.Н., Линейное программирование. Руководство к решению задач. — М.: Физматлит, 2005. — 128 с. — ISBN 5-9221-0631-7.
 http://www.ami.nstu.ru/~headrd/seminar/publik_html/MO_conspect.pdf Лемешко Б.Ю., Методы оптимизации: Конспект лекций / Б.Ю. Лемешко. – Новосибирск: Изд-во НГТУ, 2009
 Панюков А.В., ТелегинВ.А., ТЕХНИКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ ПОТОКОВЫХ АЛГОРИТМОВ
 https://web.archive.org/web/20130618194857/http://www.iasa.org.ua/lections/
 ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ, ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по дисциплине Теория принятия решения,Иркутск 2009г.

Алгоритмы оптимизации