- •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.
3.4. Система ограничений
Рассмотрим, какие ограничения могут существовать в задаче оптимизации транспортной сети.
Во-первых, это сетевые ограничения. Они состоят из условий непрерывности потоков в сети, условий неотрицательности потоков в сети, условий аддитивности.
Применимость этих ограничений зависит от постановки оптимизационной задачи.
Все виды ограничений мы будем обозначать векторным соотношением вида
.
Ниже приведем некоторые случаи ограничений, которые могут встречаться на практике:
-
не допускается, чтобы общие капитальные вложения превышали определенный уровень; этот уровень может быть фиксирован по региону R или по моменту времени t:
или
(Здесь множество определяет множество дуг сети в заданном регионе R; – величина затрачиваемых капитальных вложений в реконструкцию дуги ij с уровнем технической оснащенности ; , , – предельные значения капитальных вложений соответственно в исходном состоянии, в регион, за заданный промежуток времени.);
-
требуется определенный уровень эффективности транспортной системы; это означает, что не допускается, чтобы расходы пользователей превышали определенную величину . Сюда могут быть включены общие расходы пользователей или расходы пользователей по каждой транспортной связи, или просто уровень обслуживания по каждой дороге
;
-
из соображений безопасности или по другим причинам может быть задана минимальная величина расходов пользователей
-
уровни технической оснащенности различных дорог (или маршрутов) на сетях могут быть ограничены определенными величинами
для всех или для некоторых дуг .
-
может быть предъявлено требование относительно уровня занятости во всем изучаемом регионе или в отдельных районах (капитальные вложения должны быть не менее заданной величины):
;
или
;
-
только одна из двух возможных взаимоисключающих дорог может быть построена
-
может оказаться необходимым придерживаться определенной последовательности при строительстве дорог:
или
4. Методы решения задачи оптимизации транспортных сетей
4.1. Постановка задачи оптимизации транспортных сетей
Будем рассматривать статический случай в сети и один вид транспорта, игнорируя тот факт, что движение транспорта непостоянно от часа к часу в течение дня и по дням внутри года.
В качестве целевой функции будем использовать общественную прибыль S, равную разности между общественными доходами U и общественными издержками F, т.е. S=U-F.
Для простоты будем полагать, что общественные издержки состоят из расходов I, связанных с транспортной сетью, и издержек пользователей T (расходы I мы будем называть капитальными вложениями, т.е. F=I+T).
Общая матрица поездок, то есть компоненты вектора потоков транспортной сети, остается заданной.
В качестве ограничений используются обычные сетевые ограничения, т.е. условия непрерывности потоков на сети, условия неотрицательности и аддитивности потоков на сети.
Таким образом, в дальнейшем будем формулировать следующие постановки оптимизационных задач:
-
максимизация прибыли, дескриптивный случай
-
максимизация прибыли, нормативный случай
-
минимизация расходов, дескриптивный случай
-
минимизация расходов, нормативный случай
Здесь S – суммарная прибыль;
F – суммарные издержки;
– вектор транспортных потоков с компонентами или ;
– вектор уровней технической оснащенности дорог или трасс (пропускная способность, число полос, ширина проезжей части дорог) дуг сети ;
А – матрица, с помощью которой записываются сетевые ограничения;
– множество функций для описания поведения едущих (выбор маршрута в случае минимизации расходов);
– множество вектор-функций для описания остальных ограничений.
Суммарные общественные издержки в предыдущих формулировках записываются следующим образом:
.
Далее перейдем к рассмотрению методов решения задач, сформулированных ниже.