- •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.
1.6. Многопродуктовые потоки
В предыдущем разделе мы познакомились с постановками сетевых задач, в которых было много пунктов производства и много пунктов потребления. Причем поток мог быть послан из любого произвольного пункта отправления в любой произвольный пункт назначения.
Если требуется, чтобы поток из определенных пунктов отправления должен быть послан в определенные пункты назначения, то мы получаем новый класс задач – задачи о многопродуктовых потоках.
Особый случай многопродуктовых потоков – когда каждый поток идет только из одного определенного пункта отправления только в один определенный пункт назначения.
Для общего потока из узла А в узел В используем обозначение и введем следующее определение.
Определение.
Упорядоченная пара узлов А, В, состоящая из пункта отправления А и пункта назначения В называется транспортной связью.
Множество всех транспортных связей на сети будем обозначать через S.
Отметим, что транспортная связь АВ только тогда имеет смысл, когда в сети существует путь, связывающий А и В.
С учетом введенного определения условия непрерывности потоков в сети приобретают вид:
Здесь – поток на дуге ij, который порождается транспортной связью АВ. Эта величина называется транспортной корреспонденцией (пассажирской или грузовой).
В случае многопродуктовых потоков справедливо также требование, чтобы потоки были неотрицательными:
.
В ряде случаев условие непрерывности потока в сети удобнее выразить через понятие пути. Обозначим – поток на дугеij, порожденный транспортной связью АВ и использующий путь р из А в В.
Тогда условия непрерывности потоков в сети можно представить в виде
.
Кроме того, сюда следует добавить условия неотрицательности потоков
.
Полученные выше соотношения образуют технические соотношения транспортной сети и называются характеристиками транспортной обеспеченности.
2. Описание системы перевозок на транспортных сетях
2.1. Транспортная инфраструктура
Определим перевозки как перемещение грузов и (или) пассажиров на транспортных средствах между различными географическими пунктами.
При движении транспортных средств используется транспортная инфраструктура, в которой можно выделить три составляющие:
постоянные устройства, такие как автомагистрали, второстепенные дороги, городская сеть дорог, железные дороги, трубопроводы, аэропорты и т.д. [речные и морские порты и вокзалы];
транспортные средства, использующие постоянные устройства;
организационная структура для обеспечения эффективного использования транспортных средств и постоянных устройств.
В математических моделях, которые далее будут рассматриваться, система транспортной инфраструктуры представляется в виде транспортной сети, состоящей из узлов и дуг с определенными характеристиками.
Для такой сети сохраняются, введенные нами ранее, сетевые ограничения, которые означают, что сетевые потоки:
всегда неотрицательны;
аддитивны (т.е. могут суммироваться по дуге);
непрерывны в каждом узле, кроме пунктов отправления и назначения.
Более того, узлы и дуги могут обладать дополнительными характеристиками. Например, дуга может быть использована только для одного вида транспорта (воздушная линия, соответствующая заданному эшелону движения воздушных судов).
Для дальнейшего введем два следующих понятия:
транспортную обеспеченность перевозок;
потребность в перевозках.
Транспортная инфраструктура создает транспортную обеспеченность, а потребность в перевозках формируется из предъявляемых к перевозке грузов и пассажиров с учетом основных причин, вызывающих эти перевозки.