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

 

 

Содержание

 

Введение ….……………………………………..…….……………………………………..3

Исходные данные……………………………………………………………………………6

Расчетная часть………………………………………………………………………………7

Заключение ……..……………………………...…………………………….………..……26

Список использованной литературы……………………………………….………..…….

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Система ОрВД относится к системам жизнеобеспечения и является полиэргатичекой (сложной), и исследовать ее очень трудно, поэтому прибегают к такому методу исследования процессов и систем, как моделирование.

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

Эффективность ОВД можно  декомпозировать на его составляющие: 

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

λ(t) = ∆N(t)/ ∆t

 

 

Интенсивность - это количество ВС, фактически поступивших (входящих) в зону УВД. Интенсивность потока в любой дуге сети удовлетворяет  соотношению: 0 ≤ λ_ij ≤ µ_ij

Пропускная способность - это количество ВС, которые могут  быть обслужены в данной зоне органом  ОВД за единице времени.

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

В системе ОрВД на разных этапах функционирования в качестве критериев могут выступать такие показатели, как

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

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

В общем виде задачу оптимизации  можно сформулировать так : среди  допустимых значений параметров процесса из набора X = ( найти такие , при которых критерий I достигает своего наибольшего (наименьшего) значения. Обобщенная математическая модель запишется следующим образом :

 

 

где  I – критерий оптимизации;

f(X) – целевая функция, т.е. функция, указывающая зависимость критерия оптимизации от значения параметров X;

X = ( -  набор из n-параметров процесса, которыми можно управлять при поиске (создании) оптимального решения;

- функции ограничения,  число которых m;

 – некоторые постоянные  величины выражающие количественные значения ограничений, знаки () подразумевают, что в записи ограничения вместо «» может быть или «», или «».

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

1 Объект исследования  – организация ВД в транспортной  сети.

2. Выделяем проблему: условия  оптимальные для функционирования.

3. Цель – поиск условий  эффективного использования ВП  данной сети.

4. Предмет исследования  – условия при которых функционирования сети будет наиболее эффективным (по безопасности и экономичности).

5. Гипотеза – найденные  в результате исследования условия,  на наш взгляд, создадут предпосылки  эффективного функционирования  данной транспортной сети.

Моделирование – распространенный метод количественной или качественной оценки процессов в любых системах

Модель – это идеальный или материальный объект, который в некоторых условиях заменяет объект-оригинал.

Для моделирования транспортной сети будем использовать положения  теории графов и сетей.

Граф – это модель системы объектов, объединенных между собой определенными отношениями. Объектам соответствуют вершины графа, связям – ребра, дуги. Ориентированный граф (орграф) – граф, у которого есть вход, выход, а стрелками указаны направления. Под моделью транспортной сети будем понимать ориентированный граф, в котором выделяется две вершины: s –исток и t –сток, а дугам присвоен вес, означающий пропускную способность.

Поток сети -  совокупность объектов, транспортируемых по сети из s в t,причем эти объекты могут быть распределены по дугам сети различным образом.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Исходные данные.

Вариант №68. Имеем матрицу:

Начальный поток λ₀(St)=3, S=8, t=7.

 

	1	2	3	4	5	6	7	8
1
2			8			9		4
3					6			11
4		7			4
5		5						2
6	2		10				6
7					3
8				16

Согласно предложенной матрице можно построить модель транспортной сети:

 

 

 

Цикл 1

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₁[St(8,5,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-5   λ(u)> µ(u) → ∞

5-7   λ(u)= µ(u) → ∞

Нулевой путь не найден, конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 2

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₂[St(8,4,5,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-4   λ(u)< µ(u) → 0

4-5   λ(u)< µ(u) → 0

5-7   λ(u)= µ(u) → ∞

Нулевой путь не найден, конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 3

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₃[St(8,2,6,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-2   λ(u)< µ(u) → 0

2-6   λ(u)< µ(u) → 0

6-7   λ(u)< µ(u) → 0

Нулевой путь найден.

Шаг 3. Находим приращение dР₃

dP₃[St(8,2,6,7)] = (4,9,6)

µ_min=4

dP₃=4–3=1

Шаг 4. Находим новый поток.

λ ₃= λ₀ + dP₃=3+1=4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 4

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₄[St(8,3,6,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-3   λ(u)< µ(u) → 0

3-6   λ(u)< µ(u) → 0

6-7   λ(u)< µ(u) → 0

Нулевой путь найден.

Шаг 3. Находим приращение dР₄

dP₄[St(8,3,6,7)] = (11,10,6)

µ_min=6

dP₄=6–3=3

Шаг 4. Находим новый поток.

λ ₄= λ₀ + dP₄=3+3=6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 5

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₅[St(8,3,5,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-3   λ(u)< µ(u) → 0

3-5   λ(u)< µ(u) → 0

5-7   λ(u)= µ(u) → ∞

Нулевой путь не найден, конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 6

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₆[St(8,2,5,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-2   λ(u)< µ(u) → 0

2-5   λ(u)< µ(u) → 0

5-7   λ(u)= µ(u) → ∞

Нулевой путь не найден, конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 7

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₇[St(8,2,3,6,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-2   λ(u)< µ(u) → 0

2-3   λ(u)< µ(u) → 0

3-6   λ(u)< µ(u) → 0

6-7   λ(u)< µ(u) → 0

Нулевой путь найден.

Шаг 3. Находим приращение dР₇

dP₇[St(8,2,3,6,7)] = (4,8,10,6)

µ_min=4

dP₇=4–3=1

Шаг 4. Находим новый поток.

λ ₇= λ₀ + dP₇=3+1=4

Конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 8

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₈[St(8,3,2,6,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-3   λ(u)< µ(u) → 0

3-2   λ(u)< µ(u) → 0

2-6   λ(u)< µ(u) → 0

6-7   λ(u)< µ(u) → 0

Нулевой путь найден.

Шаг 3. Находим приращение dР₈

dP₈[St(8,3,2,6,7)] = (11,8,9,6)

µ_min=6

dP₈=6–3=3

Шаг 4. Находим новый поток.

λ ₈= λ₀ + dP₈=3+3=6

Конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цикл 9

Шаг 1. Рассмотрим сеть воздушных  трасс.

Выберем путь. Это путь P₉[St(8,4,5,2,6,7)].

Шаг 2. Строим орграф приращений.

 

 

Находим путь «нулевой длинны»:

8-4   λ(u)< µ(u) → 0

4-5   λ(u)< µ(u) → 0

5-2   λ(u)< µ(u) → 0

2-6   λ(u)< µ(u) → 0

6-7   λ(u)< µ(u) → 0

Нулевой путь найден.

Шаг 3. Находим приращение dР₉

dP₉[St(8,4,5,2,6,7)] = (16,4,5,9,6)

µ_min=4

dP₉=4–3=1

Шаг 4. Находим новый поток.

λ ₉= λ₀ + dP₉=3+1=4

Конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

Основываясь на исходных данных и полученных знаниях по моделированию, была разработана модель транспортной сети, представляющая собой орграф. Данная модель состоит из 8 вершин. Заданная интенсивность – , также заданы пропускные способности каждого ребра (μ), которые представляют собой маршруты движения ВС из одного пункта в другой. Полученная транспортная сеть имеет вход – аэропорт г. Ульяновск, выход - аэропорт г. Казань, статические объекты – ПОД - пунктам обязательного донесения, с расположенными на них РЛС, а также – воздушные трассы. Важно учесть, что транспортная сеть не является масштабным изображением реальной системы, то есть здесь не отображаются реальные расстояния между объектами. Наше воздушное пространство поделено на две зоны, в каждой зоне воздушный поток обслуживает один диспетчер.