Курсовая работа - Математические основы теории систем (МОТС) - файл n1.docx

Содержание

1. Задачи на графах

1.1. Задача о кратчайших путях в графе

1.2. Задача о графе минимальной длины

1.3. Задача о критическом пути в графе

1.4. Задача о максимальном потоке в графе

1.5. Транспортная задача на графе

2. Анализ линейных непрерывных систем

2.1. Построение сигнального графа

2.2. Преобразование модели к одному дифференциальному уравнению

2.3. Нахождение переходного процесса при заданных условиях

2.3.1. Аналитический способ

2.3.2. Численный метод с использованием ЭВМ

2.4. Нахождение амплитуды выходного сигнала при заданных условиях

2.5. Нахождение среднеквадратического значения сигнала на выходе системы при заданных условиях


1. Задачи на графах

1.1. Задача о кратчайших путях в графе

Неориентированный граф с десятью вершинами x1…x10 задан верхней треугольной «половиной» матрицы весов. При этом отсутствие элемента c_ij в матрице указывает на отсутствие в графе ребра, связывающего вершины x_i и x_j. Необходимо найти кратчайший путь из истока в каждую из остальных вершин.

	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1		7	4	12	5
x2			2						5
x3				4					9
x4					7	5		18
x5							14
x6							2	8	1	13
x7										12
x8									9	3
x9										7
x10

Исток: х1

Соответствующий таблице граф выглядит следующим образом:



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

x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
0	?	?	?	?	?	?	?	?	?
0	7	4	12	5	?	?	?	?	?
0	7	4	8	5	?	?	?	13	?
0	7	4	8	5	?	19	?	13	?
0	7	4	8	5	?	19	?	12	?
0	7	4	8	5	13	19	26	12	?
0	7	4	8	5	13	19	26	12	19
0	7	4	8	5	13	15	21	12	19
0	7	4	8	5	13	15	21	12	19
0	7	4	8	5	13	15	21	12	19

Определяем полный путь для каждой вершины:

l(x₁?x₂)=7: x₁?x₂

l(x₁?x₃)=4: x₁?x₃

l(x₁?x₄)=8: x₁?x₃?x₄

l(x₁?x₅)=5: x₁?x₅

l(x₁?x₆)=13: x₁?x₃?x₄?x₆

l(x₁?x₇)=15: x₁?x₃?x₄?x₆?x₇

l(x₁?x₈)=21: x₁?x₃?x₄?x₆?x₈

l(x₁?x₉)=12: x₁?x₂?x₉

l(x₁?x₁₀)=19: x₁?x₂?x₉?x₁₀

1.2. Задача о графе минимальной длины

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

	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1		7	4	12	5
x2			2						5
x3				4					9
x4					7	5		18
x5							14
x6							2	8	1	13
x7										12
x8									9	3
x9										7
x10

Соответствующий таблице граф выглядит следующим образом:



По известному ранее алгоритму строим новый граф, который будет содержать все вершины, соединённые рёбрами минимальной суммарной длины:



Граф минимальной длины построен, сумма всех его рёбер составляет 34.

1.3. Задача о критическом пути в графе

Дан ориентированный граф, в котором отсутствуют контуры, и каждой дуге которого приписан вес c(i,j)>0. Структура графа определяется следующим условием: он имеет дугу, связывающую вершину x_i с вершиной x_j, если в исходных условиях задан вес. Необходимо найти путь от заданной начальной вершины (истока) к заданной конечной вершине (стоку), имеющий наибольшую длину, равную сумме весов дуг, входящих в этот путь.

с(1,2)=7; с(1,6)=2; с(1,7)=17; с(2,3)=4; с(2,7)=2; с(2,8)=12; с(2,9)=7; с(3,4)=11; с(3,9)=10; с(4,12)=4; с(5,7)=6; с(5,11)=14; с(5,13)=6; с(6,5)=12; с(6,7)=14; с(7,8)=10; с(7,10)=7; с(7,11)=12; с(7,13)=14; с(8,4)=3; с(8,10)=15; с(8,12)=12; с(9,4)=12; с(9,8)=10; с(10,12)=6; с(10,13)=11; с(11,13)=4; с(12,13)=12;
Граф будет выглядеть следующим образом:



Действуя по алгоритму решения задачи, перенумеровываем вершины и присваиваем им метки. Находим длину критического пути.



Длина критического пути составляет 64. Вершины, через которые проходит критический путь: х₁?x₂?x₃?x₉?x₈?x₁₀?x₁₂?x₁₃.

1.4. Задача о максимальном потоке в графе (сети)

Дана транспортная сеть, представляющая собой связный ориентированный граф, состоящий из вершин х₁…х₆ и дуг, характеризуемых матрицей пропускных способностей с(i,j). Необходимо найти такое распределение потоков по дугам графа, при котором величина потока сети была бы наибольшей для заданной структуры графа и заданных пропускных способностей.

	x1	x2	x3	x4	x5	x6
x1		12	11	19
x2				10	7
x3						14
x4			9		13
x5						22
x6

Для решения пользуемся алгоритмом Форда и Фалкерсона. Строим граф и присваиваем дугам соответствующие метки:



Далее присваиваем метки вершинам, поочередно выполняем итерации.

Итерация 1

Итерация 2

Итерация 3