Вариационные неравенства для задачи равновесия транспортных потоков

Размещено на http://www.allbest.ru/

Омский государственный технический университет

ВАРИАЦИОННЫЕ НЕРАВЕНСТВА ДЛЯ ЗАДАЧИ РАВНОВЕСИЯ ТРАНСПОРТНЫХ ПОТОКОВ

А.В. Зыкина, Д.Н. Запорожец

Аннотация

В статье рассматриваются вариационные неравенства в качестве инструмента для построения математической модели задачи потокового равновесия в транспортной сети, задаваемой транспортные потоки из частного автотранспорта. Для исследования предлагаются итерационные методы, учитывающие специфику постановки задачи и допускающие использование технологии распараллеливания методов при численной реализации. Для численного решения предлагается пакет программ, в котором предусмотрен аппарат приведения моделируемой содержательной задачи к вариационному неравенству.

Ключевые слова - вариационные неравенства, потоковое равновесие, итерационные методы, параллельные технологии.

Введение

математический модель транспортный потоковый

Один из современных подходов построения математических моделей для различных видов равновесий - использование вариационных неравенств [1, 2]. При этом вариационные неравенства обобщают классические постановки задач оптимизации для построенных математических моделей и имеют многочисленные приложения в задачах равновесия. Это задачи равновесия транспортных потоков, задачи ценового равновесия, задачи выбора портфеля ценных бумаг и другие [3, 4]. Особенно эффективен для таких задач аппарат вариационных неравенств со связанными ограничениями, так как они позволяют описывать наиболее сложные ситуации, когда необходимо в построенной модели учитывать внешние воздействия на систему, или сбалансировать противоречивую моделируемую ситуацию [5, 6]. Таким образом, разработка математических моделей с использованием инструмента вариационных неравенств является актуальной в силу возможности моделировать наиболее сложные зависимости и разрешать противоречивые ситуации [7].

Классическая постановка вариационного неравенства состоит в следующем: решить вариационное неравенство - значит найти вектор x^* , удовлетворяющий следующему условию:

(1)

где заданное отображение - заданное выпуклое замкнутое множество.

Универсальный подход к решению вариационных неравенств - итерационные методы. Самыми известными и используемыми из них являются градиентные методы. Однако для успешного применения градиентных методов необходимы достаточно жесткие условия (к примеру, сильная монотонность оператора H или компактность исходного множества ). Чтобы решать задачи с более слабыми условиями, разработаны экстраградиентные методы [8, 9]. Кроме того, на практике градиентные методы, даже если сходятся, обладают довольно медленной скоростью сходимости, что при большом количестве переменных в исследуемых математических моделях делает решение задач градиентными методами неэффективным. Экстраградиентные методы и использование параллельных технологий в итерационных методах решения вариационных неравенств призваны повысить эффективность решения прикладных задач [10-13].

Постановка задачи равновесия транспортных потоков

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

- пользователи ТС выбирают свои маршруты движения с наименьшими расходами только для себя;

- пользователи ТС выбирают свои маршруты с наименьшими расходами для всех.

Первый вариант называют первым принципом Вардропа, второй - вторым принципом Вардропа [14]. В статье [15] построена математическая модель распределения транспортных потоков по первому принципу Вардропа. Содержательно модель по первому принципу Вардропа задает транспортные потоки из частного, как правило, легкового автотранспорта, водители которого преследуют личные цели, каждый водитель выбирает маршрут с наименьшими затратами только для себя. Такая модель поведения соответствует модели конкурентного бескоалиционного равновесия. Сформулированная задача распределения транспортных потоков может быть сведена к вариационному неравенству (1) следующим образом.

Оператор H(x) - это транспортные расходы:

H(x)=( H_г(x)), г. (2)

Здесь переменные моделирования х - это вектор с координатами x_г, г - величина потока по маршруту г, где - множество возможных маршрутов без петель и циклов из из пункта i в пункт j. Каждая переменная x_г должна быть неотрицательной и переменные x_г, г_ij, должны удовлетворять естественным балансовым ограничениям (суммарный поток по всем возможным маршрутам г_ij из пункта i в пункт j равен количеству пользователей ТС, планирующих прибывать из пункта i в пункт j ):

(3)

Допустимое множество вектора x определяется как декартово произведение множеств Х_ij:

(4)

Элементы p_ij матрицы корреспонденций P=(p_ij ), iI, jJ, определяют количество пользователей ТС, которые планируют прибывать из пункта i в пункт j.

Итерационные методы

Рассмотрим задачу транспортного равновесия (4)-(5) с фиксированным спросом P=(p_ij), iI, jJ, в виде вариационного неравенства (1), где H(x) - вектор-функция, заданная (2), множество Х определяется условиями (3)-(4).

Для решения вариационного неравенства (1) рассмотрим градиентные и экстраградиентные методы [8-10], а также основанные на них параллельные итерационные методы с памятью [11, 13].

Вычислительная схема градиентного метода для решения вариационного неравенства (1) имеет вид

, (5)

где б - длина шага метода, H - оператор вариационного неравенства, P - оператор проецирования на множество .

Экстраградиентные методы заключаются в том, что сначала делается вспомогательный шаг метода, затем берется направление во вспомогательной точке и делается шаг из первоначальной точки с полученным направлением. Преимущество таких методов заключается в возможности решать более широкий класс задач.

Одношаговый экстраградиентный метод для решения вариационного неравенства (1) задается следующими рекуррентными выражениями

, . (6)

Основное отличие одношагового экстраградиентного метода от градиентного заключается в вычислении одной прогнозной точки .

Двухшаговый экстраградиентный метод для решения вариационного неравенства (1) задается рекуррентными выражениями

, , (7)

В отличие от одношагового экстраградиентного метода двухшаговый метод для вычисления очередной точки использует две прогнозные точки и.

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

,

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

, (8)

где , .

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

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

Выводы и заключение

В статье решается фундаментальная научная проблема - построения адекватного инструментария для моделирования транспортного равновесия и разработки для исследования и решения этих моделей новых итерационных методов с использованием технологий параллельного программирования. Проведен анализ вычислительных схем алгоритмов с памятью для градиентного метода, для одношагового и двухшагового экстраградиентных методов решения задачи распределения транспортных потоков в транспортной сети с фиксированным спросом в условиях конкурентного бескоалиционного равновесия. Для каждого метода получены оценки трудоемкости итераций через количество операций произведения и сложения, оценки эффективности итерационных методов с памятью по времени и по числу итераций. Результаты вычислений показывают, что относительная эффективность применения итерационных методов с памятью для транспортного равновесия по числу итераций в градиентном методе и одношаговом экстраградиентном методе составляет до 50%, в двухшаговом экстраградиентном методе - до 80%.

Список литературы

1. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. М.: Наука, 1989. 400 с.

2. Коннов И.В. Модели равновесного типа в экономике: от уравнений к вариационным неравенствам // Исследования по информатике, 2002. №. 4. С. 67-76.

3. Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972. 517 с.

4. Зыкина А.В., Канева О.Н., Огородников С.Б. Двухэтапная задача стохастического программирования для формирования портфеля ценных бумаг // Экономика и математические методы, 2008. Т. 44, № 3. С. 111-116.

5. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.

6. Zykina A.V. Inverse complementarity in a resource deficit model // Computational Mathematics and Mathematical Physics, 2008. Vol. 48, No 11. P. 1971-1980.

7. Зыкина А.В., Канева О.Н. Параметризация в моделировании социальных и экономических процессов. Омск: Изд-во ОмГТУ, 2014. 160 с.

8. Антипин А.С. О методе выпуклого программирования, использующем симметрическую модификацию функции Лагранжа // Экономика и математические методы, 1976. Т. 12, № 6. С. 1164-1173.

9. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач // Экономика и математические методы. 1976. Т. 12, № 4. С. 747-756.

10. Zykina A.V., Melenchuk N.V. A two-step extragradient method for variational inequalities // Russian Mathematics, 2010. Vol. 54, No 9. P. 71-73.

11. Запорожец Д.Н. Распараллеливание экстраградиентных методов // Омский научный вестник. Серия: Приборы, машины и технологии, 2011. № 3(103). С. 22-25.

12. Запорожец Д.Н., Зыкина А.В., Меленьчук Н.В. Сравнительный анализ экстраградиентных методов решения вариационных неравенств для некоторых задач // Автоматика и телемеханика, 2012. № 4. С. 32-46.

13. Запорожец Д.Н. Двухшаговый экстраградиентный метод с памятью для решения вариационных неравенств со связанными ограничениями // Омский научный вестник. Серия: Приборы, машины и технологии, 2012. № 3(113). С. 274-277.

14. Пигу А.С. Экономическая теория благосостояния. Т. 1-2. М.: Прогресс, 1985.

15. Зыкина А.В. Многошаговые экстраградиентные методы для решения задачи равновесия транспортных потоков // Прикладная математика и фундаментальная информатика: сб. материалов III Рос. молодежной науч.-практ. конф.(Омск, 24-26 апреля 2013 г.). Омск: ОмГТУ, 2013. С. 57-61.

Размещено на Allbest.ru