Главная | Обратная связь
МегаЛекции

Лекция. Задача синтеза транспортной сети





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

Каждой дуге сети поставлены в соответствие три характеристики:

- – функция стоимости;

- – пропускная способность;

- – величина перемещаемого потока.

Задача состоит в построении такой сети, которая обеспечит перемещение всего потока из в с минимальной стоимостью.

Функция стоимости представляет собой затраты на создание и перемещение потока, т.е.

,

где – себестоимость транспортирования;

– стоимость создания ребра .

Для выполнения этих условий вводится специальная функция

и функция стоимости принимает вид

. (7.1)

На величины потоков накладываются ограничения:

- поток по ребру не может превышать величину пропускной способности

; (7.2)

- сумма исходящих из потоков должна равняться , а входящих в – равняться

(7.3)

- сумма входящих в вершину i потоков равна сумме выходящих

 

(7.4)

 

Задача построения сети для перемещения всего потока в с минимальными затратами может быть представлена моделью математического программирования.

Определить , удовлетворяющие условиям

(7.5)

, (7.6)

, (7.7)

, (7.8)

, (7.9)

(7.10)

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

Воспользуемся приближенным итерационным алгоритмом [7], состоящим из последовательности следующих шагов.

Шаг 0. Произвести первоначальное распределение потока, удовлетворяющее ограничениям (7.6 – 7.9).

Шаг 1. Построить дерево графа, включая в него в первую очередь основные дуги (т.е. дуги , на которых ). Если таковых меньше, чем дуг дерева ( где – число вершин графа), то включаются дуги с нулевым ( ) или насыщенным ( ) потоком.



Шаг 2. Для каждой хорды строится цикл из дуг дерева. Направление обхода цикла определяется из следующих условий:

1) если , то поток на дуге можно только увеличить, и направление обхода цикла совпадает с направлением дуги ;

2) если , то поток на ней можно только уменьшить, и направление обхода будет противоположно дуге .

Обозначим совокупность дуг цикла, направление которых совпадают с направлением обхода, положительной полуцепью , в противном случае – . Например, если , то

,

.

На дугах положительной полуцепи возможно увеличение потока до пропускной способности, т.е.

,

а на дугах отрицательной – уменьшение потока до нуля, т.е.

.

Общее изменение потока в цикле

.

Шаг 3. Величина нового потока в цикле определяется соотношением

.

Шаг 4. Проверяется целесообразность изменения потока. Изменение потока в цикле целесообразно, если стоимостная функция в цикле уменьшается, т.е. подсчитывается

,

.

Если , поток не меняется, проверяется следующий цикл (шаг 2).

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

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

После построения дерева подсчитываются потенциалы вершин.

.

Распределение оптимально, если в каждом цикле , построенном на дугах дерева добавлением одной дуги , выполняются условия:

 

,

 

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

 





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2019 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.