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

Курсовая работа - Математические основы теории систем (МОТС)
скачать (1003 kb.)
Доступные файлы (4):
n1.docx504kb.14.12.2010 23:14скачать
n2.docx87kb.14.12.2010 23:27скачать
n3.docx189kb.14.12.2010 23:35скачать
n4.docx253kb.14.12.2010 23:50скачать

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 задан верхней треугольной «половиной» матрицы весов. При этом отсутствие элемента cij в матрице указывает на отсутствие в графе ребра, связывающего вершины xi и xj. Необходимо найти кратчайший путь из истока в каждую из остальных вершин.




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(x1?x2)=7: x1?x2

l(x1?x3)=4: x1?x3

l(x1?x4)=8: x1?x3?x4

l(x1?x5)=5: x1?x5

l(x1?x6)=13: x1?x3?x4?x6

l(x1?x7)=15: x1?x3?x4?x6?x7

l(x1?x8)=21: x1?x3?x4?x6?x8

l(x1?x9)=12: x1?x2?x9

l(x1?x10)=19: x1?x2?x9?x10

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. Структура графа определяется следующим условием: он имеет дугу, связывающую вершину xi с вершиной xj, если в исходных условиях задан вес. Необходимо найти путь от заданной начальной вершины (истока) к заданной конечной вершине (стоку), имеющий наибольшую длину, равную сумме весов дуг, входящих в этот путь.

с(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. Вершины, через которые проходит критический путь: х1?x2?x3?x9?x8?x10?x12?x13.

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

Дана транспортная сеть, представляющая собой связный ориентированный граф, состоящий из вершин х1х6 и дуг, характеризуемых матрицей пропускных способностей с(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


Стадия А

Стадия Б




Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации