О.Н. Ванеев Моделирование систем

1

ОБЩИЕ СВЕДЕНИЯ

Курс "Моделирование систем" изучается в течение восьмого семестра. По учебному плану для студентов заочной формы обучения по данному курсу предусмотрено 12 часов лекций, 8 часов практических занятий и выполнение одной контрольной работы. Всего на изучение курса с учетом самостоятельной работы отводится 120 часов. Завершается изучение курса экзаменом.

1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ

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

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

Задачи изучения дисциплины:

•изучение основ системного анализа и методов формализованного описания систем;

•изучение основных типов моделей и видов моделирования;

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

Связь изучаемой дисциплины с другими дисциплинами.

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

2

2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ЕЕ ИЗУЧЕНИЮ

Раздел 1. Введение

Определение системы и системного подхода. Система. Внешняя среда. Элемент системы. Цель функционирования системы. Общая характеристика проблемы моделирования системы. Основные положения теории подобия. Классификация моделей и виды моделирования. Полные, неполные и приближенные модели. Детерминированное, стохастическое, динамическое и дискретное моделирование. Этапы построения математической модели. Определение математического моделирования (ММ). Моделирование как метод решения задач. Этапы решения задач методом ММ. Состав дисциплин, используемых в ММ. Аналитические и имитационные модели.

Литература: [1, с. 12-28; 2, с. 3-59; 8, с. 1-2].

Методические указания

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

Контрольные вопросы

1.Дать определение модели и моделируемого объекта. Этапы решения задачи методом математического моделирования.

2.Определение процесса моделирования. Типы математических моделей по способу отображения свойств моделируемого объекта и в зависимости от используемого математического аппарата.

Раздел 2. Построение и анализ аналитических моделей

Основные положения дисциплин, используемых при построении

ММ.

3

Математические модели на основе дискретной математики. Теоре- тико-множественные, логические модели, модели на основе теории графов. Анализ аналитических моделей. Постановка задач, решаемых на основе теории графов.

Литература: [3, с. 4-32; 8, с. 3-22].

Методические указания

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

Литература: [3, с. 42-76; 8, с. 22-26].

Контрольные вопросы

1.Дать определение множества. Отношения на множествах. Диаграммы Эйлера. Операции над множествами.

2.Понятие соответствия. Элементы соответствия. Методы задания соответствий. Отношения как частный вид соответствий. Понятие графа.

3.Указать основные элементы графа. Пояснить понятие инцидентности, смежности. Методы задания графов. Характеристики вершин (степень, полустепень).

4.Задача поиска цепи, связывающей две заданные вершины невзвешенного графа. Ее практическое применение и методы решения.

5.Понятие остового дерева. Построение остового дерева для графа, используемые алгоритмы.

4

Раздел 3. Оптимизационные задачи, решаемые на графовых моделях

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

Литература: [5, с. 241-262; 5, с. 124-127; 8, с. 26-30].

Методические указания

Основная задача данного раздела - изучение методов решения основных оптимизационных задач. Прежде всего, необходимо рассмотреть общую постановку оптимизационной задачи, основные ее элементы. Множество элементов, множество возможных решений, ограничения. Критерий оптимальности. Пример постановки оптимизационной задачи в прикладной области, ее приведение к общей постановке. Необходимо рассмотреть взвешенные графы как инструмент построения моделей для решения оптимизационных задач. Рассмотреть основные оптимизационные задачи на графах, методы их решений и подробно разобрать один из методов. В качестве оптимизационных задач целесообразно рассмотреть задачу поиска минимального остового дерева, задачу поиска кратчайшего пути и задачу коммивояжера. Алгоритмы их решения целесообразно разобрать в общем виде и рассмотреть пример их решения с помощью данных алгоритмов.

Как особый пример графовых моделей необходимо разобрать гра- фы-сети. Рассмотреть понятие потока, единицы потока, и алгоритм нахождения максимального потока.

Контрольные вопросы

1.Взвешенные графы. Методы их задания.

2.Оптимизационная задача. Ее постановка. Понятие критерия оптимальности.

3.Задача поиска кратчайшего пути на взвешенном графе. Методы решения.

5

4.Поиск кратчайшего пути на взвешенном графе с помощью алгоритма направленного поиска (алгоритм Дейсктры). Прямой ход.

5.Понятие наименьшего остового дерева. Алгоритм построения наименьшего остового дерева графа.

6.Задача коммивояжёра. Ее общая постановка и методы решения.

7.Метод поиска оптимального гамильтоного цикла с помощью метода ветвей и границ.

8.Понятие сети. Характеристики сети. Классификация вершин сети. Методы задания сетей. Требования, выполняемые для установившегося потока. Понятие максимального потока.

9.Понятие максимального потока. Задача поиска максимального потока в сети. Практические задачи, сводимые к задаче поиска максимального потока. Алгоритм поиска максимального потока.

Раздел 4. Имитационное моделирование систем

Принципы построения моделей систем. Типы имитационных моделей. Анализ имитационных моделей. Организация статистического моделирования. Его этапы, методы проведения. Теория систем массового обслуживания (СМО). Основные элементы. Имитационный эксперимент.

Методические указания

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

Литература: [2, с. 56-93; 5, с. 92-104; 8].

Контрольные вопросы

1. Имитационная модель. Этапы исследования объектов с помощью имитационного моделирования.

6

2.Системы массового обслуживания. Общее определение. Типы потоков событий.

3.Описание системы массового обслуживания. Классификация систем СМО в зависимости от допустимого времени пребывания заявок

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

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

Раздел 5. Специальные теории и средства моделирования

Модели на основе конечных автоматов. Сети Петри. Определение. Построение моделей на основе теории сетей Петри. Исследование сетей Петри. Средства универсальных языков программирования. Специальные языки моделирования. Язык GPSS.

Литература: [5, с. 107-116].

Контрольные вопросы

1.Определение конечного автомата. Его характеристики.

2.Сети Петри. Типы вершин. Маркер. Понятие текущей маркировки. Методы задания сетей. Временное упорядочивание событий в сетях Петри.

3.Сети Петри. Функции входных инцинденций и выходных инцинденций. Построение графа возможных маркировок.

4.Реализация сетей Петри средствами универсальных языков программирования.

5.Основные объекты языка GPSS. Понятие транзакта. Построение модели системы средствами GPSS.

7

3. ЛАБОРАТОРНЫЕ РАБОТЫ, ИХ СОДЕРЖАНИЕ И ОБЪЕМ В ЧАСАХ

4. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

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

Содержание контрольной работы

Контрольная работа включает два задания. В первом задании студент должен построить теоретико-множественные модели, выполнить над ними различные операции. Объектами моделирования являются слова, составляющие фамилию, имя, отчество студента. Кроме того, в первом задании необходимо построить графовую модель, отображающую последовательность букв в ФИО, и выполнить поиск цепей, связывающих начальную букву со всеми другими буквами, то есть построить вариант остового дерева. Для решения задачи поиска необходимо использовать алгоритмы поиска цепей на графе “в глубину” или “в ширину”.

8

4.1.Первое задание

4.1.1.Порядок выполнения первого задания

•Найти множество букв: И – в вашем имени, О – в отчестве, Ф –

вфамилии.

•Найти множество А1 = И ∩ О ∩ Ф, А2 = И О Ф, А2 = = О \ И \Ф,

•Отобразить графически отношения букв в ваших ФамилииИмениОтчестве, записанных без пробела. Количество вершин можно сократить, удалив буквы с наименьшей повторяемостью.

•Преобразовать полученные отношения в ориентированный граф, удалив кратные дуги и петли.

•Задать полученный граф перечислением дуг с помощью матрицы смежности.

•По алгоритму поиска "в глубину" или "в ширину" найти путь на построенном графе от начальной буквы до всех остальных букв. То есть построить вариант остового дерева.

4.1.2.Методические указания для выполнения первого задания

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

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

В алгоритме используются следующие данные.

Множество исследуемых вершин (множество И) – по данному множеству массива контролируются уже просмотренные вершины.

Основная цепь (ОЦ) − одномерный массив. Заполняется в процессе работы алгоритма. В исходном состоянии пуст (содержит нули).

Матрица векторов смежности (МВС) − двумерный массив, стро-

ки соответствуют элементам ОЦ. Каждая строка является вектором смежности для вершины, занесенной в соответствующую строку ОЦ.

Результирующая цепь (РЦ) − одномерный массив, в него заносится последовательность вершин, образующих искомую цепь, но в обратном порядке, от N1 до N2.

9

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

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

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

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

Алгоритм поиска "в глубину".

Исходные данные: множество дуг, N1 − начальная вершина цепи, N2 − конечная вершина цепи.

Прямой ход.

Этап 0. Все вершины заносятся в множество И (исследуемые вершины).

1.Начальная вершина N1 заносится в основную цепь (ОЦ), в качестве очередной просматриваемой (ОП) принимается первая вершина из ОЦ.

2.Вершина ОП вычеркивается из И.

3.Выявляется очередная вершина из множества И, смежная с ОП (ВСОП).

4.Если ВСОП нет, то ОП вычеркивается из ОЦ. В качестве ОП принимается предшествующая вершина из ОЦ. Переход к П.2.

5.Если ВСОП не является искомой вершиной N2, то ВСОП помещается очередным элементом в вектор смежности вершины ОП и в

основную цепь (ОЦ). Иначе − переход к П.7.

6.В качестве ОП принимается следующая вершина из ОЦ. Переход к П.2.

7.Конец прямого хода.

Обратный ход.

Обратный ход начинается от найденной вершины N2.