Оптимизационные модели и методы равновесного распределения потоков в транспортных сетях тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Крылатов, Александр Юрьевич

• Крылатов, Александр Юрьевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Крылатов, Александр Юрьевич

Введение.......................................................

5

Актуальность темы исследования.................................. 5

Цели, задачи, новизна исследования.............................. 14

Положения, выносимые на защиту.................................. 15

Краткое содержание работы ...................................... 18

Глава 1. Принципы Вардропа распределения потоков в транспортных сетях 22

1.1 Конкурентное равновесие и системный оптимум Вардропа в

транспортной сети.........................................23

1.2 Двойственная задача распределения потоков в больших

транспортных сетях........................................29

1.3 Распределение потоков по маршрутам транспортной сети как

задача поиска неподвижной точки...........................37

1.4 Распределение потоков по дугам транспортной сети как задача

поиска неподвижной точки..................................44

Глава 2. Равновесие Нэша в транспортных сетях с множеством

групп пользователей 53

2.1 Конкурентная маршрутизация транспортных потоков с

множеством групп участников движения......................56

2.2 Связь принципов Вардропа и равновесия по Нэшу в модели с

множеством групп участников движения......................61

2.3 Равновесие по Нэшу в бескоалиционной игре групп участников

движения на маршрутах транспортной сети ..................69

2.4 Поведенческая модель конкурентной маршрутизации

транспортных потоков......................................73

Глава 3. Методы поиска распределения потоков в больших транспортных сетях 85

3

3.1 Метод наискорейшего спуска при поиске конкурентного

равновесия в транспортных сетях............................86

3.2 Проекционный метод поиска распределения потоков по

маршрутам транспортной сети................................91

3.3 Проекционный метод поиска распределения потоков по дугам

транспортной сети.........................................101

3.4 Сведение задачи поиска распределения потоков в линейной сети

к системе линейных уравнений..............................110

Глава 4. Параллельная декомпозиция транспортной сети 116

4.1 Декомпозиция транспортной сети на множество

параллелизованных подсетей................................118

4.2 Распределение потоков по маршрутам транспортной сети с

одной парой исток-сток....................................122

4.3 Распределение потоков по маршрутам транспортной сети

произвольной топологии....................................127

4.4 Распределение потоков по дугам транспортной сети

произвольной топологии....................................131

Глава 5. Оптимизация топологии больших транспортных сетей 137

5.1 Двухуровневое программирование при решении задач

оптимизации топологии транспортной сети...................139

5.2 Оптимизация пропускной способности транспортной сети

произвольной топологии....................................144

5.3 Оптимизация пропускной способности транспортной сети

коридорного типа..........................................148

5.4 Оптимизация пропускной способности транспортной сети в

условиях мультимодальности транспортных потоков...........154

Глава 6. Оптимальная топология транзитных транспортных подсетей 162

6.1 Критерии оптимальности различных транзитных транспортных

подсетей .................................................163

6.2 Распределение потоков на транспортных сетях с транзитными

подсетями.................................................173

4

6.3 Критерии оптимальности транзитных транспортных подсетей в

условиях конкурентной маршрутизации.......................180

6.4 Распределение потоков на транспортных сетях с транзитными

подсетями в условиях конкурентной маршрутизации...........188

Глава 7. Моделирование транспортных процессов в загруженных сетях большой размерности 202

7.1 Оптимизация режимов работы светофоров в загруженных

транспортных сетях........................................204

7.2 Восстановление и оценка матриц корреспонденций на базе двойственной задачи распределения транспортных потоков . . . .211

7.3 Минимизация уровня выбросов загрязняющих веществ путем

перераспределения транспортных потоков....................217

7.4 Динамическая маршрутизация в загруженных транспортных

сетях крупных городов.....................................225

Глава 8. Моделирование распределения нагрузки на линиях сетей электроснабжения 233

8.1 Моделирование электрических сетей с множеством поставщиков

и множеством потребителей электроэнергии..................237

8.2 Конкуренция потребителей электроэнергии на общих сетях

электроснабжения..........................................245

8.3 Интеграция поставщиков электроэнергии на общих сетях

электроснабжения..........................................251

8.4 Оптимальное ценообразование в системе с множеством поставщиков и потребителей на общих сетях электроснабжения . .255

Заключение.......................................................265

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

5

Введение

Введение диссертации (часть автореферата) на тему «Оптимизационные модели и методы равновесного распределения потоков в транспортных сетях»

Актуальность темы исследования

Транспортная сеть представляет собой масштабную систему связанных между собой элементов (улицы, перекрестки, светофоры, транспортные потоки и т.п.), со сложнейшими законами взаимозависимости этих элементов. Формализация этих законов помогает в принятии управленческих решений. На сегодняшний день формальное описание транспортных процессов происходит, прежде всего, средствами математического моделирования. При этом на международном рынке информационных технологий уже достаточно давно существует ряд крупных компаний, предоставляющих услуги в области планирования и поддержки принятия решений в транспортной сфере. В России актуальность применения методов математического моделирования при поддержке принятия решений также осознана на разных уровнях управленческой инфраструктуры в области транспорта. В частности, в апреле 2017 года Министерством транспорта Российской Федерации был объявлен конкурс на право заключения государственного контракта на выполнение научно-исследовательской работы по теме: «Проведение научных исследований в области применения программных продуктов математического моделирования транспортных потоков при разработке комплексных схем организации дорожного движения, проектов организации дорожного движения, а также проектов автоматизированных систем управления дорожным движением. Разработка предложений по нормативному и методическому обеспечению использования программных продуктов при проектировании в сфере организации дорожного движения» (код закупки: 171770236142777020100101210077220241). Более того, одним из ключевых направлений стратегии научно-технологического развития Российской Федерации является «Связанность территории Российской Федерации за счет создания интеллектуальных транспортных и телекоммуникационных систем, а также занятия и удержания лидерских позиций в создании международных транспортнологистических систем, освоении и использовании космического и воздушного пространства, Мирового океана, Арктики и Антарктики».

6

При этом, заметим, что в мире активное развитие теории транспортных потоков ведется уже на протяжении последних ста лет. Связано это, прежде всего, с тем, что личный автомобиль занимает все более и более значимую позицию в повседневной жизни каждого человека. Люди используют автотранспорт для того, чтобы ездить и на работу, и за город, и в театр, и, наконец, просто в магазин. Естественно, что такое широкое использование автомобиля большим количеством людей приводит к возникновению значительных нагрузок на элементах улично-дорожных сетей (далее УД С) городов. Особенно это заметно в крупных городах и мегаполисах. Там регулярно возникают ситуации, когда большое количество людей двигаются из одного района в другой в одно и то же время суток (например, утром из спального района в район деловой активности). Таким образом, можно говорить о существовании регулярных по времени потоков транспортных средств между районами отправления-прибытия или о существовании матрицы корреспонденции транспортных средств мегаполиса. Подобные потоки создают основную нагрузку на УДС крупных городов, в связи с чем, уместно ставить вопрос о методах управления транспортными потоками в условиях ограниченности транспортной инфраструктуры.

Теория транспортных потоков начала развиваться сто лет назад [43]. Основы же математического моделирования закономерностей дорожного движения были заложены в 1912 году русским ученым профессором Г.Д. Дубелиром [42]. Тогда ставилась задача анализа пропускной способности магистралей и пересечений, то есть речь шла исключительно об анализе мощностей самой транспортной инфраструктуры. Затем стали появляться многочисленные публикации, описывающие с помощью моделей и методов теории вероятностей и математической статистики возникновение и взаимодействие транспортных потоков на различных узлах (перекрестках, светофорах, сужениях и проч.) транспортной сети. Такие модели, как правило, описывали поведение транспортных потоков на локальных элементах УДС, но при переносе их на всю сеть становились чрезмерно громоздкими и оттого неприменимыми на практике. В 1934 году Б.Д. Гриншильд [146] предложил математическую модель движения транспортного потока, в которой движение каждого автомобиля было ограничено исключительно движением едущего впереди него транспортного средства. Подобные модели называют микроскопическими, так как они не дают ответа на вопрос о движении всего потока, а лишь дают некое представление о взаимодействии любых двух транспортных средств внутри потока. В 1955 году появилась первая макро-

7

скопиче ская модель транспортного потока, предложенная Лайтхилом и Уиземом [46, 192], в которой движение транспорта рассматривалось с позиции механики сплошной среды. Подобный подход также носил сугубо локальный характер применения и был способен лишь немного пролить свет на природу движения автомобилей в потоке. В конце 50-х выходит монография Ф. Хейта [49], в которой объединяются результаты всех проведенных к этому времени исследований о движении транспортных потоков. Считается, что именно с этого момента произошло выделение теории транспортных потоков в самостоятельный раздел прикладной математики.

В 1952 году Вардроп предположил, что любая транспортная система, по прошествии некоторого времени, приходит в равновесное состояние, сформулировав два принципа равновесного распределения транспортных потоков [275]. Согласно первому принципу: «Время передвижения по всем используемым маршрутам одинаково для всех участников движения, и меньше времени, которое потратит любой участник движения, изменив свой маршрут», а согласно второму принципу: «Среднее время передвижения является минимальным». Впервые математическую формулировку данных принципов в виде задачи оптимизации предложил Бекманн [71]. Впоследствии, предложенная математическая модель стала классической [252], и, на сегодняшний день, является одним из ключевых конструктов в теории транспортных потоков [И, 287]. При этом, важно отметить, что модель распределения транспортных потоков может быть записана в виде задачи оптимизации по существу только в том случае, когда время движения по дуге зависит от потока только этой дуги. В 60-70-е годы активная исследовательская работа в области транспортных потоков продолжалась.

Отметим, что идея Вардропа равновесного распределения потоков относится к области, так называемых, поведенческих моделей (behavioral models), современный исчерпывающий обзор которых можно найти в [121]. Однако, оценка распределения потоков по дугам транспортной сети может быть сделана не только на основе моделирования поведения участников движения при выборе ими маршрута следования. Впервые набор эвристических правил, позволяющих получать оценки нагрузки транспортных потоков на дуги улично-дорожной сети, были предложены Шелейховским Г.В. в 1936 году [55]. Математическое доказательство сходимости метода Шелейховского для задачи с транспортными ограничениями было дано в 1967 году [4]. В 1970 году Вильсон выделил энтропийный подход для моделирования распределения транспортных потоков [277].

8

Содержательно, математически формализованный метод Шелейховского можно отнести именно к энтропийному подходу. Воплощение развиваемых в данном направлении идей применительно к современной улично-дорожной сети Санкт-Петербурга можно найти в [47, 48].

В начале 80-х были получены принципиально новые формулировки общих задач сетевого равновесия в виде вариационного неравенства и задачи дополнительности [3, 110, 257]. Полученные результаты позволили расширить область применения моделей равновесного распределения транспортных потоков на случай наличия зависимости времени движения по любой дуге от потоков на других дугах. Таким образом, появилась возможность строить модели равновесного распределения транспортных потоков с произвольным видом зависимости времени движения по дуге (не только от потока по этой дуге, но и от потоков по другим дугам), что, с одной стороны, приводит к непотенциальным отображениям, но значительно расширяет область применения. Более того, для решения таких задач обычные методы оптимизации не работают, но существуют специальные методы решения вариационных неравенств и задач дополнительности, которые успешно применяются [24].

В конце 90-х Б. Кернером были выдвинуты новые положения в теории транспортных потоков [162, 164-166] и окончательно сформулированы в 2009 [163]. Он выделил три основных состояния или три фазы транспортного потока. Полученные им результаты, прежде всего, базируются на идеях макроскопических и микроскопических моделей, а сама теория трех фаз посвящена скорее описанию состояний, чем моделированию. Последнее, тем не менее, ни в коей степени не должно преуменьшать заслуг Кернера, так как его выводы способны существенно помочь тем, кто берется за моделирование транспортных потоков.

Среди современных отечественных исследований следует, в первую очередь, отметить работы И.В. Коннова [23, 171, 172], посвященные моделям и алгоритмам равновесного распределения транспортных потоков, а также сетевых ресурсов. Отметим, что в работе [171] была предложена принципиально новая интерпретация задачи равновесного распределения транспортных потоков в виде модели аукциона. И.В. Коннов обосновал положение, согласно которому модель равновесного распределения потоков является частным случаем аукционных рынков. Также работами, развивающими данное направление исследований в отечественной научной литературе, являются статьи В.И. Швецова [1, 52, 53], В.В. Мазалова [31, 206], В.И. Зоркальцева и М.А.Киселевой [19], а также других

9

авторов [5, 6, 8, 9, 22, 44, 45]. Примечательна работа [36], в которой на основании равновесной модели была проведена оценка распределения транспортных потоков по улицам сети города Владивостока. С разработками российских ученых, базирующихся на модели Лайтхилла-Уизема [192], можно ознакомиться в следующих публикациях [11, 33, 34, 50]. Обсуждение микро- и макро- моделей можно найти в [51].

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

Следует отметить, что в последние годы, в результате активного внедрения в практику систем навигации на транспорте усилилось влияние на распределение транспортных потоков, особенно, в крупных городах, различных компаний и служб, предоставляющих услуги по прокладке маршрутов для транспортных средств. Вследствие этого появилась необходимость в разработке и исследовании математических моделей для оценки влияния изменившейся ситуации на формирование в транспортных системах равновесных распределений. Примечательно, однако, что в научной литературе пока имеется незначительное число публикаций, посвященных проблемам распределения потоков в сетях при наличии групп участников движения и вопросам применения теоретико-игрового подхода для решения возникающих здесь задач [13, 16, 62-65, 295]. Вместе с тем, имеется значительное число исследователей, таких как, А.Ю. Гарнаев, Д.А. Новиков, Л.А. Петросян, А.А. Васин, В.В. Захаров и др., предлагающих в своих публикациях методы и теоретико-игровые модели, использование и развитие которых для рассматриваемого в исследовании класса задач представляется воз

10

можным. Полученные в настоящем исследовании результаты, касающиеся существования равновесия по Нэшу в случае нескольких провайдеров услуг навигации, а также его сравнение с системным оптимумом для моделей без навигации не имеют аналогов в мировой научной литературе и вносят важный вклад в разработку методов исследования процессов распределения потоков на транспортных сетях [13, 16, 181, 294].

Искомыми переменными в задачах равновесного распределения транспортных потоков являются объемы транспортных потоков по имеющимся дугам транспортной сети. Заданными (или определенными) в таких моделях считаются матрицы корреспонденций (OD-matrix) или общий спрос на переезды между районами отправления и прибытия. В связи с этим, применение интеллектуальной базы математического моделирования на практике для управления транспортными потоками большой плотности возможно при наличии определенных значений элементов матрицы корреспонденций. При этом вопрос нахождения матрицы корреспонденций является отдельной задачей, сложной с точки зрения постановки и трудоемкой с точки зрения вычислений. Более того, в зависимости от топологии исследуемой транспортной сети большого города и существующих на ней проблем, матрицы корреспонденций можно искать либо между выделенными макрорайонами, либо между микрорайонами внутри выделенных макрорайонов и т.п. Если ставится задача поиска решений транспортных проблем внутри отдельного сегмента транспортной сети, в целом, можно идти двумя путями: 1) оценить матрицу корреспонденций внутри этого сегмента; 2) оценить матрицу корреспонденций всей сети. В первом случае задача анализа транспортного сегмента рассматривается в отрыве от всей сети, во втором - в связке со всей сетью. Преимущества и недостатки обоих подходов обсуждаются исследователями в данной области.

Авторы статьи [20] утверждают, что для повышения эффективности транспортного процесса на улично-дорожной сети городов необходимо прибегать к комплексной схеме организации дорожного движения, а не растрачивать силы на решение локальных вопросов. В зарубежной научной литературе так же придерживаются четкого разделения между системными решениями и решениями локальными [284], осознавая важность каждого из них и, самое главное, осознавая разность областей их применения. Методология решения задач, связанных с управлением транспортными потоками, и построения оптимальной транспортной инфраструктуры разработана довольно хорошо. В самом деле, на сегодняш

и

ний день существует целый класс задач, связанный с разработкой комплексных схем организации дорожного движения, который носит название Urban Transportation Network Design Problem (UTNDP) - задача построения городской транспортной сети [128]. UTNDP [200] - это задача, которая имеет дело со всей иерархией принятия решений в области транспортного планирования, и включает стратегические, тактические и операционные решения. Стратегические решения - долгосрочные решения, связанные с инфраструктурой транспортных сетей, включая и транзитные и внутренние сети; тактические решения связаны с эффективным использованием ресурсов существующих городских транспортных сетей; операционные решения - краткосрочные решения, связанные с управлением транспортными потоками, нахождением матриц корреспонденций (информация об основных пунктах отправления и пунктах прибытия) или составлением расписаний. Более того, равновесное распределение транспортных потоков также зависит от топологии транспортной сети, так как является реакцией на ее параметры (возможные маршруты, пропускные способности улиц и т.п.). В связи с этим, важной задачей в области улучшения транспортной ситуации в крупных городах является задача поиска оптимальной топологии самой транспортной сети [284]. Задачи поиска оптимальной топологии транспортной сети крупного города чаще всего формулируются в виде двухуровневой задачи оптимизации [155]. Идея данной двухуровневой модели заключается в том, что пользователи транспортной сети стремятся минимизировать свое время движения от пункта отправления в пункт прибытия, а администрация города, зная оптимальную реакцию пользователей на инфраструктурные изменения, стремится создать наилучшую топологию улично-дорожной сети города. В российской научной литературе двухуровневая модель в игровой постановке впервые была представлена в [16].

Ограничить динамику процесса автомобилизации трудно, поэтому основным направлением усилий по устранению заторов становится проектирование и строительство новых дорог и изменение структуры УДС, позволяющее удовлетворить растущий спрос на движение транспорта по улицам города [136]. Инвестиции в это направление будут тем более эффективны, чем точнее будет прогноз этого спроса на достаточно длительную перспективу. Как отмечается в статье [40], для прогноза динамики потоков применяется несколько методик, наиболее известная из которых основана на расчете межрайонных корреспонденций и распределении потоков по транспортной сети с использованием мето

12

дов поиска равновесного состояния. Основная концепция в области поиска равновесного состояния транспортных потоков базируется на принципах, которые были впервые сформулированы Вардропом [275]. Данная концепция активно используется в практике при прогнозировании распределения потоков на заданной транспортной сети с использованием многих программных продуктов, наиболее популярными из которых являются PTV Vision и TransCad. Концепция равновесия по Вардропу уже достаточно глубоко исследована в теоретическом плане, тем не менее, появляются все новые ее расширения и уточнения [85]. В то же время в связи с массовым развитием средств телекоммуникации и внедрением в практику навигационных систем, поведение водителей на дороге меняется. Они часто предпочитают при выборе маршрута ориентироваться на советы имеющихся у них навигационных устройств. Таким образом, на УДС формируются группы пользователей (водителей), использующих одинаковые стратегии выбора маршрута. Поскольку каждый провайдер услуг навигации заинтересован в выборе наилучших маршрутов для членов своей группы, то его интересы вступают в противоречие с интересами других провайдеров. Равновесие, которое может быть образовано в такой сети, можно интерпретировать как равновесие по Нэшу, известное из теории игр и отличающееся в общем случае от равновесия Вардропа. Поэтому, рассматривая вопрос равновесного распределения потоков, стали появляться исследования, использующие игровую концепцию равновесия транспортных потоков [155].

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

13

жущихся из выявленных районов отправления в районы прибытия). При этом, следует отметить, что расчет матриц корреспонденций сам по себе является задачей, требующей отдельного, подчас очень трудоемкого, алгоритма. Данная проблемная область не оставалась без внимания исследователей на протяжении последних 40 лет [89, 253, 256, 266]. Существует огромное множество методов расчета матриц корреспонденций, среди которых одним из наиболее важных, на наш взгляд, является метод сбора информации о регистрационных номерах проезжающих автомобилей системами видеорегистрации дорожного движения [89] или системами сканирования, основанными на применении RFID-технологий. Информация о потоках, получаемая с помощью подобных датчиков, установленных в выбранных для целей исследования узлах дорожной сети, является наиболее информативной и позволяет определить траектории движения автомобилей через эти узлы [90, 194]. Более того, эффективные модели покрытия для устойчивой работы сенсорных сетей, разрабатываемые такими исследователями как А.И. Ерзин, С.Н. Астраков, В.В. Залюбовский и др., могут быть адаптированы, например, к моделированию покрытия транспортной сети датчиками сканирования [12, 127].

Напоследок заметим, что многопродуктовую задачу сетевого равновесия и задачу пространственного ценового равновесия можно рассматривать как прямое обобщение так называемой транспортной задачи Монжа-Канторовича [21]. Кроме того, в задаче сетевого равновесия специально указаны пары источник-сток каждого потока, в обычной задаче пространственного ценового равновесия поток однопродуктовый и связывает все вершины.

Таким образом, исследования транспортных сетей и транспортных потоков учеными всего мира ведутся с начала XX века. Интерес к подобным исследованиям вызван сочетанием двух аспектов в рамках данной задачи: 1) практическая значимость исследований; 2) научно-исследовательский потенциал моделей, возникающих при моделировании транспортных потоков. Если первый аспект представляется интуитивно ясным, то второй следует пояснить. Дело в том, что осознание способов моделирования транспортных потоков в транспортных сетях привело к появлению новых методов и подходов, например, к решению задач условной оптимизации [229]. В свою очередь, основными направлениями исследований в мировой науке, развивающих как инструменты решения практических задач, так и теорию, на сегодняшний момент, являются:

- Задача распределения потоков.

14

- Задача оценки матриц корреспонденций.

- Задача оптимизации топологии транспортной сети.

- Задача оптимального построения транзитных подсетей (маршрутов общественного транспорта, выделенных линий и т.п.).

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

Цели, задачи, новизна исследования

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

Указанная глобальная цель диссертационной работы конкретизируется в рамках следующих задач исследования:

- развитие моделей и методов равновесного распределения транспортных потоков по маршрутам транспортной сети;

- развитие проекционных алгоритмов распределения потоков по маршрутам и дугам транспортной сети;

- разработка алгоритмов декомпозиции транспортной сети для поиска потоков по маршрутам и дугам;

15

- развитие методов и подходов оптимизации транзитных транспортных подсетей;

- создание двухуровневых моделей оптимизации для разных типов прикладных задач в области транспортного планирования;

- создание моделей функционирования интеллектуальных сетей электроснабжения с множеством поставщиков и потребителей энергии.

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

Список литературы диссертационного исследования кандидат наук Крылатов, Александр Юрьевич, 2018 год

(Я - -

J) 1 —

в таком случае, соотношение (3.2.6) примет вид:

у*^+1 __ у* ___ ('(У*^) ___ ^3=1 S )

(3.2.7)

Заметим, что если воспользоваться формулой конечных приращений (теоремой Лагранжа о среднем значении), то для всех 2 = 1,А: имеет место равенство:

w;')-*.(/.')=*:(ө;')(/;'-д).

где принадлежит интервалу между точками ./'/ и /* и, следовательно, спра-

ведливо представление

2 = 1,А;.

(3.2.8)

Обозначим = 1 —

ставим (3.2.8) в (3.2.7):

2 = 1,А;, а Щ/з) = (Е/1(/^),...,^(/^)) и под-

/У - /* = ЩД) (Д -./,') -

Е21 г.(.Д) (Д - /Г) s(T')

94

в таком случае получаем оценку

/с

-Е 1^)1-LT?-/*'

S=1

(3.2.9)

Просуммируем левые части неравенства (3.2.9) по 2 = 1,А;, заметив, что

получим:

/с

S=1

и, следовательно,

/с

(3.2.10)

!=1

!=1

Имеет место сходимость ]]П(/^)]] 0 при /*, т.е.

Vs : 0 < s < 1 Зр : ]]2П(/^)]] s < 1 при G S*p(/*),

где S*p(/*) = {/ : ]]/ — /*]] р}. Таким образом из принадлежности G

S*p(/*) и неравенства (3.2.10) следует

! = 1 !=1

а значит S*p(/*). Получаем, что если G S*p(/*), то {/^} G S*p(/*) и

имеет место оценка

/с /с

!=1 !=1

откуда и следует сходимость последовательности {/*?}, причем со скоростью геометрической прогрессии. П

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

95

Теорема 3.2.2. 77усть о некотором окростмостм точкм f* ^умк^мм 7^(-) G

2 = 1,% м уЭоблотоо/?ятот услоомял/

]7((ж)] ос^ > 0 м ]^(ж)] )3^ < ос. (3.2.11)

ТодЭм сущостоуот 5-оқростмость точкм f* тмкмя, что м/?м лтобол/ оыбо/?о мм-чмльмодо м/?м6чмэл?оммя f^ мз этом оқростмостм мослоЗоомтатьмость {f^} мто-у?м^моммодо м/?о^оссм (3.2.7) мо еыхоЭмт мз моо м мл/оот л/осто комЭ/?мтмчммя с^оЭмл/ость этом мослоЭоомтйчьмостм к точко f*.

Докмэмтачьстоо. Если для всех 2 = 1,% функции 7^(-) G C^(R^^), то согласно формуле Тейлора имеет место разложение:

дд) = + ^(Д) (./,* - Д) + у^(ө^) (/* - д)", : = 1,2-,

где — некоторая точка между ./) и /*. Учитывая равенство /,(./'*) = перепишем выражение (3.2.12) в виде:

= 2(Д) + ^(Д) (д - Д) + yW) (д - д)-,

Запишем (3.2.6) следующим образом

2 = 1Д.

(3.2.12)

2 = 1Д,

(3.2.13)

и сложим полученное выражение с (3.2.13):

;' + ДД) (/У-д) = удө;о(д-

(3.2.14)

где

- Е21

Q =

^(/7)_

ҳ-^А; 1

^(/7)

При этом, в силу того, что Ғ = X^2=i /2* имеет место равенство:

[3 Г* _ I ^2/7)

_ ^=1^3 +

ҳ-^А; 1

^(/7)

Выразим 7^(/^), 2 = 1,7; из (3.2.13) и подставим в (3.2.15):

EL [аг-л) +

Q =-------L-----------

(3.2.15)

2*

1

^3=1 ^(/7)

- EL

Л

7

*

96

откуда окончательно получаем

Q =

(3.2.16)

Подставив (3.2.16) в (3.2.14), приходим к выражению:

и, следовательно,

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

<*^+1 г* 1 < -

у Z у 7 2

2^s=i

которая после суммирования по /'

1

М)]

= 1,7; примет вид

что с учетом выполнения (3.2.11) в некоторой окрестности f приводит к

(3.2.18)

! = 1

- 1

/=1

Таким образом, по определению, согласно (3.2.18) имеет место квадратичная сходимость последовательности {f?} итерационного процесса (3.2.1) при любом выборе fO из некоторой 5-окрестности f*. П

Замечание 3.2.1. Леноб (3.2.7) мл/ggm емЭ

97

м, сябЭоаатйчьно, л/аж'//а ?ал/«тчть ся^Эутощ^а На каж'Эал/ //ааал/ шааб а/и«-у?а^монно2о л/?о^бсса олтмл/мча^монная чаЭача (^7.3.7)-^7.3.3) «/?бшабтся» Эля случая яма^мных ^гата/м ?аЭс/?ж'лм, соотабтстаующмх ласа/исль//ьм/, л/?оасЭсн-ньш /с мсхоЭньш ^унк^мял/ лаЭс/?зл?/см а точках аначсамм олтмл/аяьноао у?асл/?с-Эсчснмя потока, лолучсаных на лрсЭшсстаутом^сду шасс.

Теоремы 3.2.1 и 3.2.2 позволяют утверждать, что итерационный процесс (3.2.1) при fO, принадлежащем некоторой 5-окрестности точки f*, сходится к значению конкурентного равновесия при распределении потока F в сети из параллельных каналов, причем при достаточно естественных требованиях к функциям задержки на дугах имеет место квадратичная сходимость. Как следует из доказательств обеих теорем, одним из ключевых требований к данной окрестности является выполнение равенства 7; = 7;*. Другими словами, как только итерационный процесс (3.2.1) «нащупает» оптимальное количество маршрутов, то реализуется квадратичная сходимость. С другой стороны, алгоритму можно "подсказать" какие маршруты являются оптимальными, например, реализовав предварительно процедуру поиска оптимальных маршрутов, описанную в [206]. Более того, следует отметить, что в загруженных сетях используются все возможные маршруты, а значит, в качестве можно брать = (Ғ/п,..., Ғ/*п)^.

Благодаря проектирующему оператору Ф (1.3.4), определенному в явном виде через (1.3.5)-(1.3.7), можно реализовать соответствующий проекционный алгоритм [178]. На каждой итерации алгоритм выполняет следующие три шага. ((? + 1) итерация:

1. Перенумеровать 7:<? компонент векторов /*? и 7(/*?) таким образом, что

«1(Я) «зС/Д «д/д.

2. Найти г (количество ненулевых компонент /з' 7 из условий

и^+.(Д,Д -а=(Д) W)

F+1

!=1

^F+1 + l (У/c^i + 1) wy

3. Вычислить

1

y^^q+1 1

2 1,7:^-]-i,

/^^=0, 2 = ^+i,?2.

98

4. Проверить выполнение критерия сходимости

! = 1

В 1970 году впервые было отмечено зацикливание (zig-zagging) алгоритма в окрестности решения [156, 209, 302]. Представленные обсуждения этого вопроса были интуитивными. Мы исследовали детально такое поведение данного алгоритма на примере простой сети из параллельных маршрутов. Предполагается, что функция задержки имеют следующий вид:

= 2 = 1,72.

Меняя параметры <р; и 2 = 1,72, мы получаем различные сети из параллельных маршрутов. Определим пять различных вариантов подобной сети (таблица 1) с фиксированным спросом F = 20.

Задача распределения потока может быть сформулирована для каждого варианта сети, после чего она может быть решена. Мы сравнили работу разработанного проекционного алгоритма и алгоритма Франк-Вульфа для сети из параллельных каналов.

(// + 1) итерация алгоритма Франк-Вульфа:

1. Решить задачу линейного программирования

!=1

при ограничениях (1.3.2), (1.3.3). Пусть т/? является ее решением, ар*? = (т/? — /*?) — итоговое направление поиска.

2. Найдем длину шага которая решает задачу min {Т(/^ + /р^) ] 0 1},

где Т является целевой функцией (1.3.1).

3. Пусть = уд + ^р? и ^у?+1 = > 0.1, 2 = 1,7т} является

множеством используемых маршрутов.

4. Если

то алгоритм сошелся, а решение задачи. Иначе, пусть := + 1,

переходим к Шагу 1.

99

Таблица 1 — Пять различных вариантов топологии сети

Вариант 1 Вариант 2 Вариант 3 Вариант 4

% = 2 (3 = 2 % = 2 (3 = 3 72 = 4 [3 = 3 72 = 4 [3 = 3

2 (2^ 6; 2 (2^ 2 (2^ 6; 2 (2^ 6;

1 2 1 1 2 1 1 2 1 1 2 1

2 1 2 2 1 2 2 1 2 2 1 2

3 1.25 2.5 3 200 200

4 1 3 4 1 3

Вариант 5

72 = 6 [3 = 2

2 (2^ 6;

1 2 1

2 1 2

3 200 200

4 1 3

5 300 300

6 1.25 2.5

Таблица 2 — Сравнение проекционного алгоритма и алгоритма Франк-Вульфа: количество итераций

Алгоритм Франк-Вульфа Проекционный алгоритм

Вариант 1 2 2

Вариант 2 2 2

Вариант 3 3 3

Вариант 4 сю 7

Вариант 5 ос 3

100

Количество итераций, затрачиваемых данными двумя алгоритмами, представлено в таблице 2. Бесконечное число итераций (ос) подразумевает зацикливание алгоритма.

Отметим особо, что простая топология сети исследуемой сети позволяет сделать важные выводы. В самом деле, решения задачи распределения потока для вариантов 1, 2 и 3 не имеют нулевых компонент, то есть нет неиспользуемых маршрутов. Однако, решения задачи распределения потоков для вариантов 4 и 5 содержат нулевые компоненты, то есть некоторые маршруты являются неиспользуемыми. Действительно, маршрут 3 в варианте 4, и маршруты 3 и 5 в варианте 5 являются, очевидно, слишком "дорогими" для использования. Таким образом, уже заранее достаточно ясно, что /* = 0 для / = 3 в варианте 4 и = 0 для 2 G {3,5} в варианте 5.

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

(3.2.19)

В свою очередь, алгоритм Франк-Вульфа ищет решение в пространстве всех компонент (3.2.19)-/ (рисунок 3.1).

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

101

Рисунок 3.1 — Сеть из параллельных маршрутов

а) Алгоритм Франк-Вульфа Ь) Проекционный алгоритм

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

3.3 Проекционный метод поиска распределения потоков по дугам транспортной сети

Теорема 1.4.1 говорит об эквивалентности задачи поиска конкурентного равновесия, сформулированной в виде оптимизационной задачи (1.4.1)-(1.4.3), и задачи поиска неподвижной точки (1.4.4) для сети из параллельных каналов. В свою очередь, благодаря появившейся возможности представления задачи поиска конкурентного равновесия в виде (1.4.4), нахождение равновесного распределения потоков в сети с одной парой исток-сток возможно может быть реализовано в виде следующего процесса простой итерации:

(д^(х^) (b + A -

(3-3.1)

102

где на каждом шаге компоненты \ t(x*?) и столбцы матрицы А перенумерованы таким образом, что выполняются покомпонентные неравенства

d^(x^) (А^Дх^)А^ (b + АА(х^(х^,

d^_^x^_ J > А^ (A^G^(x^)А^) (b + A^G^x^d^x^)).

Справедлива следующая

Теорема 3.3.1. 77рм лтобол/ сыборс нмчмльносо лрмбчмэюснмл х^ мл л/нозюсстсм, змЭммносо (^7.4.2) м (^7.4.3Д лослсЭосмтсчьность {х^} мтсрм^монносо лро^сссм (3.3.7) нс сыхоЭмт мл этосо л/нозюсстсм м мл/сст л/ссто схоЭмл/ость этом ло-слсЭосмтсчьностм со скоростью ссол/стрмчсском лро^эсссмм.

Докмзмтсчьстсо. Пусть х* — оптимальное решение задачи (1.4.1)-( 1.4.3). Рассмотрим разность (х^+^—х*). Будем считать, что х*? принадлежит такой 5-окрестности х*, что А; = А;*. Для удобства обозначим:

Y^M) = G^(xDA^AA(xDA^-)b + AA(xDd„(x^)),

в таком случае разность

примет вид:

(3.3.2)

Заметим, что

G^x^d^x^ = G^x^)C(x^) - х^,

а следовательно, выражение (3.3.2) эквивалентно

- х^ = (х^ - Х^) - G^)C(x^) + Y^(x^).

Рассмотрим произведение G/,(x^)C(x^):

G^(xDC(xD = G^(x^)(c(x^) - с(х^) + G^x^g^xD,

(3.3.3)

(3.3.4)

где

(3.3.5)

103

Покомпонентно применим формулу конечных приращений (теорема Лагранжа о среднем значении) к (3.3.5):

= G^)(G^))"'(x^-x(),

где 0^ принадлежит интервалу между точками и т*, /' = 1.А-, а = Подставляя (3.3.4) в (3.3.3), с учетом (3.3.6), получаем:

-х^ = (х^ -Х^ - G^(x^)^(xD + Y^(x^),

(3.3.7)

где Е/, — единичная матрица размерности А;.

Теперь, заметим, что

b + A^G^(x^)d^(x^) = + A^G^x^(x^) - А^ =

= -А^ (х^ - х^ + АА(х^) ^(х^) - ^(х^) + АА(х^(х^ =

= -А^ ^-G^x'D(G^e'D)^') (x'^-x^) +A^G^(x'D^(x^).

В таком случае, получаем

Рассмотрим второе слагаемое из правой части (3.3.8) отдельно, подставив вместо 1/;(х^) выражение из (1.4.27):

G^x^Af(A^G^x^Af)" А^Ях^ЛЯхО =

= G^(xDAf(A^G^(xDAf)" A^G^(xDA^A^G^(xDAf)"'(b+

104

= G^(x^(xD,

а значит Y^(x^) примет следующий вид:

= -G„(x^)Af(A^G^(x^)Af)-- С„(х'^)(с„(Ө^))-^ (х'^ -х^.) +

+ G^x^(x^)-

Окончательно получаем из (3.3.7):

- х^ = - G^(x^) (G^(@D) (х^ - х^) -

- G^)A^ (A,G,(xDА^) "А, - G,(xD (с.(Ө^)) (х^ - х^) +

+ G^(x^(xD - G^(x^)^(xD

или

- G„(x'DAf (A„G„(x'DAf)- A„ - G„(x'D (с^(Ө^))(x'^ - x^.).

(3.3.9)

Обозначим

ГДх^) = С^х^А^АА(х^)А^" А^, тогда (3.3.9) примет вид:

105

В таком случае получаем оценку (покомпонентно)

и, следовательно,

^(Е*+1П(х^)1)1и^)Цх^-х^

(3.3.10)

В силу того, что

АА(х^) =

(3.3.11)

для любого из области определения, то существует некоторая матрица М/,

такая, что

М

Таким образом, неравенство (3.3.10) примет вид:

^(Е„ + М^]и^х^)]]х^-х^,

где (^Е/, + М/, J — матрица с конечными положительными фиксированными элементами, откуда следует

^]]E, + M,]].]]U,(x^)]].]]x^-x^

(3.3.12)

Имеет место ] ]U/,(x^) ] ] —0 при х^ х^, т.е.

Vs: 0<s<13p: ]]E^ + M^]]-]]U^(x^)]]^s<l при x^GVp(x^),

где Vp(x^) = {х/; : ]]х/, — х^]] р}. Таким образом, из принадлежности х^ G

S*p(x^) и неравенства (3.3.12) следует

чМ sp < р,

а значит, х^ G S*p (х^). Получаем, что если х^ G S*p(x^), то {х^} G Vp(x^) и

имеет место оценка

II О ^11 oil 0 ^11

Цх^-х^]] s^]]x^-x^]] ,

откуда и следует сходимость последовательности {х^}, причем со скоростью геометрической прогрессии. П

Заметим, что теорема 3.3.1 справедлива для гладких функций задержки на дугах сети. Однако, если функции задержки являются дважды непрерывно дифференцируемыми, то справедлива

106

Теорема 3.3.2. 77ус/иь на л/нозл?бс/иа^ ааЭаннол/ (7.4.2) м Д.4.3Д ^унк^пп 7Д-) G C^(93^_), 2 = 1,п, уЭоблб/иао/?яю/и усложнял/

]7((ж)] ос^ > 0 м ]7^(ж)] )3^ < ос. (3.3.13)

ТогЭа н/?п любол/ аыбо/?б начального н/?пбчпзл?бнпя х^ по ^нозл?ос/иаа, заданного Д.4.2) п Д.4.3Д нослоЭоаа/ийчьнос/иь {x^} п/иора^понного н/?о^осса (3.3.7) но аы^оЭп/и по э/иого ^нозл?ос/иаа и пл^оо/и л^ос/ио кааЭра/ипчная с^оЭп^ос/иь Эанноп нослоЭоаа/иочьнос/ип.

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

I. Если для всех 2 = 1,п функции 7Д-) G С^(93^_), то согласно формуле

Тейлора имеет место разложение:

= 7,М) + 7'М) (Д - + ^'№) (Д - , 2 = 1Д,

где Ө( — некоторая точка между и ж* или в матричном виде

где ради удобства последующих построений под (х^ — х^ будем понимать покомпонентное возведение в квадрат вектора (х^ — х^).

Выразим Е;(х^) из (3.3.3) следующим образом

t*M.) + (х^' - х^) = (Gt(x^)) Ү^(х^)

и сложим полученное выражение с (3.3.14):

= (с^))"Д(х^) + ^с;,(ө^))"'(х^-хД

II. Выразим 1/с(х^) из (3.3.14)

(3.3.15)

и, учитывая равенство (1.4.27), получим:

107

- (<^М)) (х^ - (х^ - .

Подставим полученное выражение t/,(x^J в выражение для Y^(x^):

= G^)A^(A^G^(x^)A^ (А^ + A^G^(x^)^(x^) - А^х^,

Y^(xD = G„(xDAf (A,A(xDAf)-' [A,^+

+ A^G^(x^){ Af (A^G^(x;jAf) (b + A,AM.)d,,M.)) -

- (Gt(x^)) (х^. - x^) - (G^G^)) (x^ - x^) ) - A^

или после раскрытия скобок

Ү/М) = G^(x^)A^ (A A(x^) А^) А^ (х^ - х^ +

+ A A(xD Af (A,G,(xD Af) (b + A A(xDcMxD) -

- (х^ - х^) - ^А А(х^) (G^(GD) (х^ - х^) ],

что в свою очередь приводит к

Y^(x^) = G^(x^Af(A^G^(x^Af)"'

A^G^(x^)Af (A^G^(x^)Af) (b + AAMJd^.)) --1А^(х^(с^(Ө^)^(х^-х^\

ИЛИ

Y^) = G^x^JAf (A^G^(xDAf) (b + A^G^x^d^x^)) -

АА(х^)(сКӨ^))"'(х^.

что с учетом (1.4.27) окончательно приводит к

(3.3.16)

АА(х^(сКӨ^))"'(х^.

108

111. Подставив (3.3.16) в (3.3.15), приходим к выражению: MxD + (х^ - х^ = = ^(хП + ^(сЦ(Ө^)) (х^-х^) - - (AA(xDAf)" A,G,(xD (GK@D)(х^ - x^)",

или (хГ^ -х^) = ^G^xD(G^eD) (х^ -Х^ - (3.3.17) - ^G,(xDА^(A,G,(xDA^)" AA(xD (GK@D)(x^ - x^)". Таким образом, благодаря (3.3.17), получаем оценку

-1

2

х^-х^ +

-1

2

* G

+

и окончательно

2

-1

х^-х^

(3.3.18)

— это матрица, на главной диагона-

Заметим, что матрица G/,(x^) ^G^(G^)^

, а недиагональные элементы — нули. Таким

ли которой стоят отношения

образом, (3.3.18) с учетом выполнения (3.3.13) в некоторой окрестности х* при-

водит к

хГ' - х( + м)о^А^]х^. - х)( (3.3.19)

где А/, и Г2/, — квадратные матрицы размерности /с, на главных диагоналях которых стоят ос, и [3, соответственно, а не диагональные элементы — нули.

Таким образом, согласно (3.3.19), по определению, имеет место квадратичная сходимость последовательности {х*?} итерационного процесса (3.3.1) при любом выборе х" из множества допустимых решений. П

Замечание 3.3.1. Еслм учесть, что b = А/,х^ о G/,(x^)d/,(x^) =

= G/,(x^)t/;(x^) — х^, то мтеро^монным л/?о^осс (3.3.7) зюзято лоролмсоть о омЭо:

(3.3.20)

109

?с/л/стмл/, что чы/жжс/тс, стоям/сс о кеаЭ/?атных скобках, яслястся обобм/с//-ном л/?осктмру7ощсм л/ат/?м^см. Такмл/ обколол/, лолучсн ясным смЭ л/?осктм/?у7о-щссо оператора Эля чаЭачм (^7.V.7)-(^7.V.3).

Замечание 3.3.2. ТТтсра^монным л/?о^ссс (3.3.7) л/ожст быть лерслмсан о смЭс:

хУ = Х^. - Gt(x^.)t;,(x^ + Y^(x^)

млм локол/лонснтно

Таких/ обралол/, но каэ/сЭол/ посол/ шасс мтсра^монносо процесса олтмл/маа/^м-о////ая оаЭача (^7.V.7)-(^7.V.3) к/?сшастсяя Эля случая лмнсмных ///уу/кпип с пслссол/ ^унк^моналс. 7/////сп//ыс ^унк/^мм соотсстстсуют /^/с(/тсль//ь/л/, и/?оссбс////ь/л/ /с мсхоЭныл/ ^унк^мял/ 7Д-), 2 = 1,7;, с точках значении онтмл/альноео у?еи/енмя, полученных на л/?еЭи/естсу7ощез/ и/аее.

Теоремы 3.3.1 и 3.3.2 позволяют утверждать, что итерационный процесс (3.3.1) при х", принадлежащем некоторой 5-окрестности точки х*, сходится к значению конкурентного равновесия при распределении потока F в сети с одной парой исток-сток, причем при достаточно естественных требованиях к функциям задержки на дугах имеет место квадратичная сходимость. Как следует из доказательств обеих теорем, одним из ключевых требований к данной окрестности является знание множества используемых дур иначе придется решать ряд комбинаторных задач по перенумеровыванию маршрутов. Однако, полученный в явном виде проектирующий оператор (3.3.20) может быть эффективно использован в проекционных методах решения соответствующих вариационных неравенств. Доказано, что задача поиска конкурентного равновесия может быть также сформулирована в виде вариационных неравенств [229]. Таким образом, полученные результаты также вносят вклад в развитие проекционных методов решения вариационных неравенств.

110

3.4 Сведение задачи поиска распределения потоков в линейной сети к системе линейных уравнений

Рассмотрим транспортную сеть из параллельных маршрутов. Будем считать, что каждый из альтернативных (параллельных) маршрутов состоит из дуг с разными характеристиками [14]. В таком случае данную сеть будем называть сетью из параллельных неоднородных маршрутов. Введем следующие обозначения: N = {1,... ,72} — множество параллельных (непересекающихся) маршрутов между ОП-парой; Ғ^ = {1,..., — множество последовательно соединен-

ных дуг маршрута /' = 1,72; F — транспортный спрос между ОП-парой; — распределяемый транспортный поток по маршруту /' = 1./2, /' = (/']..... ,

I /', = Ғ; //,/ — свободный транспортный поток на дуге / маршрута

= 1,^; С/(/з,^з/) — время движения по загруженной дуге / маршрута / = 1. /' = l.n. Сформулируем задачу поиска конкурентного рав-

новесия Вардропа на сети из параллельных каналов в виде оптимизационных программ [252]:

И. 7,

min^(J) = min

3=1 / =

при ограничениях

X 2 = Г (3.4.2)

3 = 1

У) 0 V7 = 1,72.

(3.4.3)

Заметим, что в записи функционала (3.4.1) в качестве аргумента функции Х/( ) фигурирует для всех / = 1,^,7 = 1,72, несмотря на то, что управ-

ляемыми параметрами в сформулированных задачах являются распределяемые потоки / = (Ji,..., /^), а свободные потоки для всех / = 1, 7 = 1,72 входят

в функционал как заданные параметры. Такая формализация произведена намерено ввиду важности той смысловой нагрузки, которую /1 = //,,) будет

нести в дальнейших построениях.

Введем дополнительные обозначения:

^3 = ^3? ,

7=1

2 = 1,72.

(3.4.4)

Ill

Лемма 3.4.1. Foo улшлонмя обм^ностм буЭат/ счмтоть, что л/о/?ш/?уты лорону-л/ороооны токмл/ оброоол/, что

(3.4.5)

ТоаЭо кон/с^чонтноо у?об//ооосмо о сотм мо нооЭно/?оЭны^ л/о/?ш/?у-

тоо Эостмаоотся слоЭутом^мл/ у?осл/?оЭйчонмад2 т/?онсло/?т//ы^ лотокоо:

(3.4.6)

(3.4.7)

аЭо г ол/?оЭачяотся мо услоомм

(3.4.8)

Докооотачьстоо. Построим лагранжиан для задачи (3.4.1) с ограничениями

(3.4.2), (3.4.3)

L = ^2 / (о, + ^м + ^)бм + Е ^Ғ-^Д j + У2п^(-^)

!=1 *^0 \ р=1 / ^=1

и продифференцируем его

9L

(<Т + — t* — ту

V2 = 1,72.

(3.4.9)

Согласно условию дополнительной нежесткости гуД* = 0 для всех 2 = 1,72.

Таким образом, в силу (3.4.9), получаем:

= Г

> г

при Д* > О, при Д* = О,

V2 = 1,72.

откуда получаем

( t*—а^—

при + ^ < Г,

при Г,

V2 = 1,72.

Если выбрать г таким образом, что

оу Т 1 ^т+1 Т ^г+1,

(3.4.10)

112

то Г Г ; Х^ г Х^ t — — /Е = V ь, Z—1 Z—1

откуда выражаем Г 1 * + 2^s=l V"* V ' 2^s=i Е

В свою очередь для определение г воспользуемся условием (3.4.10) и придем к требуемому. П

Теорема 3.4.1. задача (7.7.2)-(7.7..5) с лмнбмньшм

экемеалбн/ина смстаз/б лмнбм//ы^^?аб//бнмм м нераебнсте относмтачь-но лотокое ло /.

//о /<*(/ ? (/ /и с. / ь с /и чо. Рассмотрим произвольный маршрут г Е /?"' между парой я? Е

IV. Маршрут г состоит из дуг г; (с точностью до обозначений), = 1. По маршруту г Е Я"" между парой /г Е II' распределяется поток V 0, который проходит по каждой дуге данного маршрута г;, = 1. При этом, по каждой

дуге г;, = 1. могут быть распределены потоки по другим маршрутам :

для каждой дуги г;, = 1. сумма таких потоков будет являться стационарным