- •1. Потоки в транспортных сетях
- •1.1. Графы и сети
- •1.2. Структуры данных для предоставления графов
- •1.3. Поток на дуге и техническая оснащенность дуги
- •1.4. Условия непрерывности потока в сети
- •1.5. Основная транспортная задача
- •1.6. Многопродуктовые потоки
- •2. Описание системы перевозок на транспортных сетях
- •2.1. Транспортная инфраструктура
- •2.2. Потребность в перевозках
- •2.3. Равновесие в транспортной сети
- •2.4. Принцип Вардропа
- •2.5. Задача распределения перевозок
- •2.6. Определение дескриптивных и нормативных систем перевозок
- •2.7. Дескриптивное и нормативное распределение потоков в сети
- •2.8. Парадокс Брайеса
- •2.9. Уменьшение различия между дескриптивным и нормативным распределением потоков в сети
- •3. Задача оптимизации транспортной сети
- •3.1. Оптимальное планирование транспортной инфраструктуры
- •3.2. Искомые переменные
- •3.4. Система ограничений
- •4. Методы решения задачи оптимизации транспортных сетей
- •4.1. Постановка задачи оптимизации транспортных сетей
- •4.2. Методы математического программирования
- •4.3. Метод ветвей и границ
- •4.4 Эвристические методы
- •4.5 Метод отбора наиболее перспективных проектов
- •4.6 Примеры сетевых задач, сводящихся к задачам линейного программирования
- •4.7 Общая постановка классической транспортной задачи
- •4.7 Пример графического решения задачи линейного программирования
- •Список использованных источников
- •443086, Самара, Московское шоссе, 34
- •443086, Самара, Московское шоссе, 34.
2.8. Парадокс Брайеса
В 1968 году американский специалист по транспортной логистике Брайес опубликовал парадокс, возникающий при планировании перевозок.
Парадокс заключается в том, что добавление дуги к сети может повлечь за собой увеличение общих расходов для каждого пользователя.
Приведем пример парадокса Брайеса (Рисунок 20).
Рисунок 20 – Парадокс Брайеса:
а) исходная сеть; б) сеть с добавленной дугой 34
Заданы следующие соотношения по расходам пользователей:
Задан поток величиной в 6 единиц из пункта 1 в пункт 2. В случае а) дуга 34 отсутствует.
Рассмотрим решение по дескриптивному распределению. Оно будет состоять в том, что поток по дугам 132 и 142 будут одинаковыми, т.е. по 3 единицы транспортных средств.
При этом расходы пользователей составят:
по дуге 132 –
Итого на каждую единицу транспортных средств;
по дуге 142 –
Итого на каждую единицу транспортных средств.
Общие расходы пользователей сети составят:
.
Теперь рассмотрим случай, когда в сеть добавляется дуга 34.
Точно так же рассмотрим решение по дескриптивному распределению потоков в сети (Рисунок 21).
Рисунок 21 – Парадокс Брайеса, случай б)
Определим расходы пользователей:
по дуге 132 –
Итого ;
по дуге 142 –
Итого ;
по дуге 1342 –
Итого .
Общие расходы пользователей составят:
.
Таким образом, добавление в сеть дуги 34 увеличивает общие расходы пользователей на 11% (552>498).
Запишем теперь для второго случая (при наличии дуги 34) задачу нормативного распределения и задачу дескриптивного распределения как оптимизационные задачи. Для удобства введем следующие обозначения (Рисунок 21): поток по дуге 142 – ; поток по дуге 1342 – ; поток по дуге 132 – .
В рассматриваемом случае единственное ограничение на непрерывность потоков дает:
.
Кроме того, есть ограничение на неотрицательность потоков, то есть:
Тогда задача нормативного распределения потоков в сети принимает вид:
Это последнее выражение после раскрытия скобок принимает вид:
Отсюда видно, что целевая функция становится нелинейной, а записанные выше ограничения задачи являются линейными. Таким образом, в данном случае имеет место задача нелинейного программирования.
В случае дескриптивного распределения потоков на сети в рассматриваемом случае, получим следующее выражение для целевой функции задачи:
.
Ограничения в данном случае остаются прежними.
Вычислим записанные выше интегралы и в результате получим:
Из анализа записанных выше целевых функций и видно, что это две различные задачи. И их решения не всегда могут совпадать.
Для решение будет следующим:
для решение будет следующим:
Отсюда видно, что при нормативном распределении потоков в сети (так называемая общественная оптимизация) поток на дуге 34 отсутствует. И наоборот, при дескриптивном распределении по дуге 34 имеет место поток в 2т.е.
2.9. Уменьшение различия между дескриптивным и нормативным распределением потоков в сети
Для общества и часто для отдельных пользователей дорог и маршрутов выгодно, когда нет различия между результатами нормативного и дескриптивного распределения.
Принимая в качестве общих издержек пользователей суммарные общественные издержки, мы видим, что результаты нормативного и дескриптивного распределения совпадают, если издержки пользователей не зависят от транспортных потоков.
В других случаях дескриптивное и нормативное распределение не приводят к одному и тому же результату.
Чтобы такое совпадение имело место, необходимо применять дополнительные меры: например, более гибкую систему управления движением или использование механизма цен (тарифов).
Использование механизма цен означает, что при перегрузках на элементах сети вводятся налоги, которые должны быть настолько высокими, чтобы критерий индивидуального выбора маршрута совпадал с условиями оптимального нормального распределения.
Из предыдущего ясно, что пользователь дороги должен рассматривать свои расходы в виде следующей комбинации
вместо просто t.
Здесь – это скорость возрастания издержек пользователя в зависимости от возрастания потока на дуге.
Таким образом, дополнительные расходы, связанные с перегрузками в сети, должны быть , что равно увеличению издержек всех пользователей дороги.
В частности, в теории управления описанный выше прием управления называется пропорционально-дифференциальным управлением [2].