Автоматизированные информационно-управляющие системы

Кафедра «Системы управления транспортной инфраструктурой»

Учебная дисциплина:

Автоматизированные информационно-
управляющие системы

Курсовой проект

Иконников С.Е.

Москва – 2019 г.

Структура курсового проекта

1. Составление введения

• А) Выполнить анализ литературы и ёмко изложить суть проектирования
  автоматизированных информационно-управляющих систем (АИУС). В тексте выполнить
  ссылки на литературные источники.

Б) Выполнить классификацию известных АИУС, а также методов проектирования АИУС.
Возможные формы представления классификации: текстовое перечисление, блок-
схема, таблица.

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

Структура курсового проекта

2. Сбор и обработка исходных данных

• А ) Выделить и включить в пояснительную записку к курсовому проекту только те
  данные которые заданы индивидуально, согласно варианту.

Б) Обязательно должны быть представлены:

• - графовая схема системы передачи информации;
• - данные по потокам сообщений;
• - матрица ёмкостей ветвей заданного графа;

Структура курсового проекта

• 3. Составление общей характеристики для систем
  передачи информации

• А) Выполнить классификацию известных систем передачи информации

Б) Обосновать выбор используемых в курсовом проекте методов и средств
проектирования.

• В) Обосновать выбор целевой функции.

Структура курсового проекта

• 4. Выполнение расчёта оптимального по
  быстродействию управления сетью передачи
  информации

• А) Расчёт оптимального по быстродействию маршрута осуществляется симплекс-
  методом.

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

• В) По неравенствам составляется симплекс-таблица.

Г) Необходимо составить алгоритм и написать программное обеспечение,
реализующее обсчёт таблицы симплекс-методом.

Д) Получить таблицу оптимальных по быстродействию путей.

Структура курсового проекта

• 5. Подготовить заключение к курсовому проекту

А) Заключение должно содержать вывод о проделанной работе.

Б) Заключение должно включать в себя список использованной в ходе выполнения
исследований литературы.

Применение симплекс-метода

• 1. Составить по исходному графу сети матрицы смежности;
• 2. Построить деревья возможных путей по маршрутам вторичной сети;
• 3. Определить накладываемые на СПИ ограничения;
• 4. Перейти к основной задаче линейного программирования с учётом определённых в
  пункте 3 ограничений;
• 5. Составить симплекс-таблицу;
• 6. Пересчитать симплекс-таблицу в соответствии с алгоритмом симплекс-метода до
  достижения признака оптимального решения;
• 7. Построить граф вторичной сети (оптимальное решение определяет оптимальные
  пути, по которым возможна максимальная загрузка сети).

Применение симплекс-метода

• А) Определение элементов матрицы смежности проводится по формуле:

с.. = <
ij

• 1, если вершине i смежна вершина j
• 0, иначе

Б) Матрица весовых коэффициентов составляется на основе матрицы смежности – все
единицы заменяются на значение весов рёбер графа;

• В) Матрица потоков сообщений составляется на основе информации, получаемой по
  фу, причём fj=fjj в матрице.

Применение симплекс-метода

• I) На схеме дерева отмечается начальный, i-й узел, а в матрице смежности
  рассматривается соответствующая i-я строка;
• II) Под меткой «1 ярус» отмечаются номера тех узлов, для которых в строке матрицы
  записано значение, равное «1»;
• III) Далее в качестве начального узла рассматривается каждая из вершин 1-го яруса в
  отдельности. Для каждой записываются смежные узлы в последующий ярус. Вершины,
  которые встречались на пути ранее, при составлении следующего яруса не
  учитываются.
• IV) Построение дерева заканчивается номером яруса p-1, где p - число вершин
  исходного графа. Иногда максимально длинный маршрут в дереве может быть короче,
  чем p-1.

Применение симплекс-метода

• 1. Перечислить необходимые пути, например:

M15 | ^1 , ^2 , И3 , №4 , ^5 , ^6, ^7

I 1,2,3,5 1,2,5 1,2,6,5 1,3,2,5 1,3,2,6,5 1,3,5 1,4,5

начальный и конечный узел

определяется по ф

начальный и конечный узел
определяется по ф

M 42

^№16 ,
4,1,3,5,2

^17 , ^18, ^19, /^20 , ⁴21

4,1,3,5,6,2 4,1,2 4,5,2 4,5,3,2 4,5,6,2

начальный узел определяется по
индексу узла с заданным

⁴ п оря д ко в Ы1 и _ н ом ер _ пут и
^п р ^{о х о} д ^{и м ы е} у ^{зл ы}

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

где M_ij – массив возможных путей, ведущих из узла i в узел j.

Пути составляются по направлению интенсивности передачи, а также по направлению
потоков сообщений. ₉

Применение симплекс-метода

• 2. Составить целевую функцию по всем возможным путям:

L = M, ₅+ M_{2 3}+ М^

• 3. Преобразовать её под условия нахождения минимума:

L = 0 - L

• 4. Задать ограничения по потокам сообщений:

М. <

У ^У

• 5. Задать ограничения по переходам между узлами:

P < b..
ij ij

где P_ij – массив путей, на которых встречается непосредственный переход из узла i в
узел j или наоборот.

Применение симплекс-метода

• 6. Переписать для расчёта по симплекс-методу:

' L=0-X M

’ У1 = v - M

= Ъ.. — Р

I y 2 ij ij

• 7. Составить симплекс-таблицу вида:

  	Св. чл.	μ	μ	μ	μ	μ	μ	μ	μ	μ	μ
  L	0
  y	φ
  y	φ
  y	φ
  y	b
  y	b
  y	b
  y	b

Таблица заполняется нолями и единицами в зависимости от наличия соответствующего
μ в рассматриваемом y. ₁₁

Применение симплекс-метода

• 8. Составить блок-схему алгоритма симплекс-метода для проведения расчётов на ЭВМ.
• 9. Найти оптимальное решение с использованием программного обеспечения
  «potok.vi», входящего в состав модуля SPI.llb. Для выполнения необходимо наличие
  пакета прикладных программ LabView.
• 10. Составить маршрутную таблицу оптимальных путей с точки зрения минимума
  затрат.