14. 5.2. Алгоритм расчета пропускной способности сети (величины установившегося потока).

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

Дано: GáU,Vñ - ориентированный граф, который является сетью.

С(N,N) - матрица смежности, задающая пропускную способность дуг графа.

Найти: W = Sf svj =Sf viT - количество потока, протекающего по сети.

Алгоритм поиска максимального потока построен на поиске увеличивающих цепей для какого-либо начального потока.

Цепь является увеличивающей, если в она состоит из дуг, позволяющих увеличить достигнутый в ней результирующий поток.

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

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

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

Кроме того, допустимой является дуга, в которой поток не совпадает с направлением цепи. Такие допустимые дуги называются несогласованными. Величиной, на которую позволяет увеличить поток в цепи несогласованная дуга является достигнутое в ней значение потока.

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

0. Задаться любым потоком, можно нулевым, т.е. потоком в котором во всех трубах поток нулевой f ij = 0.

Рис 5.1. Заданный сетевой граф.

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

Если такая цепь есть

то: пересчитать потоки, передаваемые по ее дугам, учетом достигнутой величины увеличения .

Переход к п.1

иначе: переход к п.2

1. Подсчитать W - величину потока, вытекающего из истока

W = Sf sj

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

Лучшие результаты обеспечивают алгоритмы, в которых для поиска увеличивающей цепи используется методы направленного поиска цепи с наименьшей длинной (алгоритм Дейкстра), где в качестве критерия оптимальности принимается величина наибольшего увеличения результирующего потока. Критерий "Макси-мина".

15. Исследование переходных процессов систем на основе теории конечных автоматов.

Конечный автомат – это объект, у которого возможные состояния в дискретные промежутки времени определены и конечны.

Конечные автоматы характеризуются:

- конечным множеством возможных состояний, которые он может принимать.

- конечным множеством входных сигналов, т.е. некоторых внешних воздействий, которые вызывают изменение состояния автомата.

- конечным множеством выходных сигналов. Выходной сигнал – это сигнал, который вырабатывает конечный автомат при переходе в некоторое новое состояние.

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

Согласно общей теории динамики систем состояние системы в момент времени t - z(t) , определяется состоянием в предшествующий момент времени τ - (z_τ) и совокупностью входных сигналов поданных в интервале [τ, t] х_τt (или х(∙)).

z(t) = σ(t; τ, z_τ , х_τt)

Значение выходного сигнала в момент времени t, определяется состоянием автомата в рассматриваемый момент z(t).

y(t) = η (t,z(t)), t ϵ T

В теории конечных автоматов выходную функцию чаще рассматривают так же через предшествующее состояние автомата и поданные входные сигналы

y(t) = φ(t; τ , z_τ, х_τt)

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

Переходная функция при этом будет иметь вид

,

где Z_(t) – новое состояние конечного автомата.

Z_(t-1) – предшествующее состояние конечного автомата

X_(t) – сигнал под воздействием которого произошел переход

Выходная функция будет иметь вид.

Построение модели конечного автомата.

Построение модели конечного автомата включает в себя:

-установление множеств Z,X,Y

- установление функций переходов и выходной функции

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

Пример функции перехода в табличном виде.

X(t)	Z(t-1)
	a	b	c	d
1	c	b	-	-
2	a	-	d	-
3	a	a	a	a

Для В функции переходов возможны следующие случаи для различных комбинаций входных сигналов и предшествующих состояний:

- под воздействием входных сигналов конечный автомат меняет состояние на некоторое новое.

- конечный автомат не реагирует на поданный сигнал, т.е. новое состояние такое же как и предшествующее

- запрещенная комбинация входного сигнала и предшествующего состояния, т.е. для данного состояния такой входной сигнал невозможен.

Пример: Построить модель конечного автомата для объекта «телефон».

Возможные состояния объекта:

П	Покой
ГН	Поднята трубка, готовность к набору номера
Р	Разговор
ЗВ	Вызов

Множество входных сигналов:

ВТ	Взятие трубки
ВК	Вызов коммутатора
НН	Набор номера
ПТ	Положить трубку

Функция переходов в табличном виде:

X(t)	Z(t-1)
	П	ГН	Р	ЗВ
ВТ	ГН	ГН	Р	Р
ВК	ЗВ	ГН	Р	ЗВ
НН	П(-)	Р	-	-
ПТ	-	П	П	-

Функция выходных сигналов в табличном виде:

	Z(t-1)
	П	ГН	Р	ЗВ
ВТ	Г	Г	Ш	Ш
ВК	З	Г	Ш	З
НН	М(-)	Ш	-	-
ПТ	-	М	М	-

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

Рис 7.1. Граф последовательности смены состояний конечного состояния.

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