План лекции. 1. Сетевое моделирование

1. Сетевое моделирование

2. Классификация сетевых моделей

3. Правила построение сетевых моделей

1. Сетевое моделирование

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

Сетевая модель (сеть) - это ориентированный граф без контуров и кратных дуг, элементам которого сопоставлены числа.

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

Требование отсутствия в графе контуров и кратных дуг является несущественным. Однако выполнение этого требования облегчает исследование модели сети и позволяет использовать разработанные в настоящее время программы вычисления параметров сетевой модели. Диаграмма сетевой модели называется сетевым графиком. Основными элементами сетевой модели являются операции (работы) и события.

Операцией (работой) называется любое действие, приводящее к достижению определенных результатов.

Операции по отношению к затратам средств и времени на их осу­ществление подразделяются на действительные и фиктивные.

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

Фиктивная операция - операция, на осуществление которой не требуется никаких затрат.

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

Событием называется факт достижения требуемого результата.

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

При сетевом моделировании сложных процессов важное значение имеет отношение предшествования или следования, определяемое для операций и событий.

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

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

2. Классификация сетевых моделей

По количеству сетей, описывающих исследуемый комплекс операций, различают односетевые и многосетевые модели. По количеству конечных целей, для достижения которых осуществляется комплекс операций, сетевые модели подразделяются на одноцелевые (с одним завершающим событием) и многоцелевые (с несколькими завершающими событиями). По количеству исходных событий или операций различают сеть с одним исходным событием (одной исходной операцией) и несколькими исходными событиями (несколькими исходными операциями). По степени неопределенности сетевой модели разли­чают детерминированные и стохастические сетевые модели. По количеству операций, составляющих комплекс, сетевые модели подразделяются на сети большого объема (свыше 10 000 операций), среднего объема (от 1500 до 10 000 операций) и малого объема (до 1500 операций). На рис. 2. приведена рассмотренная классификация сетевых моделей.

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

Рис. 2.

3. Правила построение сетевых моделей

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

К основным правилам, которыми следует руководствоваться при по­строении сетевых моделей, относятся следующие.

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

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

3. В сети не должно быть петель, контуров и кратных дуг.

4. В сети должны быть только одна исходная и одна завершающая вершины.

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

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

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

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

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

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

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

составление перечня операций;

составление матрицы смежности;

заполнение таблицы слоев;

нумерация вершин и построение сетевого графика.

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

1. Что такое сетевая модель?

2. Назовите основные правила построения сетевых моделей?

3. Назовите основные этапы построения сетевых моделей?

Тема № 2 «Сетевое моделирование процессов»

Лекция № 4 «Анализ сетевых моделей»

Цель лекции.

а) учебная цель:

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

Дата добавления: 2014-01-05