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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

найти

при условиях

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

 — решение

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

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

Алгоритм[править | править код]

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

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

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

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

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

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

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

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

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

Незамкнутые задачи[править | править код]

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

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

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

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

Метод северо-западного угла[править | править код]

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

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

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

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

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

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

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

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

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

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

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

Ограничения на пропускную способность[править | править код]

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

найти

при условиях

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

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

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

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

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

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

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

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

Здесь

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

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

Алгоритм[править | править код]

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

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

Примечания[править | править код]

Ссылки[править | править код]

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