Дайте полное определение сетевой математической модели системы

1. Сетевая модель и ее основные элементы.

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

Главными элементами сетевой модели являются событиями и работы

Термин работа используется в СПУ в широком смысле.Во-первых, это действительная работа — протяженный во временипроцесс, требующий затрат ресурсов (например, сборка изделия, испытание прибора и т.п.). Каждая действительная работа, должна быть конкретной, четко описанной и иметь ответст­венного исполнителя.

Во-вторых, это ожидание — протяженный во времени процесс,не требующий затрат труда (например, процесс сушки после окраски, старения металла, твердения бетона и т.п.).

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

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

Среди событий сетевой модели выделяют исходное и завершающее события. Исходное собы­тие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ. Завершающее событие не имеет последующих работ и событий.

События на сетевом графике (или, как еще говорят, на графе)изображаются кружками (вершинами графа), а работы — стрелками(ориентированными дугами), показывающими связь между работами. Пример фрагмента сетевого графика представлен на рис 1:

На рис. 2, а приведен сетевой график задачи моделирования и построения оптималь­ного плана некоторого экономического объекта. Чтобы решить эту задачу, необходимо провести следующие работы: А – сформулировать проблему исследования; В5 — матема­тическую модель изучаемого объекта; В — собрать информацию; Г — выбрать метод решения задачи; Д — построить и отладить программу для ЭВМ; Е — рассчитать опти­мальный план; Ж — передать результаты расчета заказчику. Цифрами на графике обозначены номера событий, к которым приводит выполнение соответствующих работ.

Из графика, например, следует, что работы В и Г можно начать выполнять независимо одна от другой только после свершения события 3, т.е. когда выполнены работы А и Б; работу Д — после свершения события 4, когда выполнены работы А, Б и Г; а работу Е можно выполнить только после наступления события 5, т.е. при выполнении всех предшествующих ему работ А, Б, В, Г и Д.

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

Но прежде сделаем следующее замечание. В рассмотренных примерах сетевые графики со­стояли из работ и событий. Однако может быть и иной принцип построения сетей — без событий. В такой сети вершины графа (например, изображенные прямоугольниками) означают определен­ные работы, а стрелки — зависимости между этими работами, определяющие порядок их выполнения. В качестве примера сетевой график «события — работы» задачи моделирования и построе­ния оптимального плана некоторого экономического объекта, приведенный на рис. 2 а, пред­ставлен в виде сети «работы — связи» на рис. 2 б. А сетевой график «события — работы» той же задачи, но с неудачно составленным перечнем работ, представлен на рис. 2 в (см. правило 3 в разд. 3).

Следует отметить, что сетевой график «работы — связи» в отличие от графика «события — ра­боты» обладает известными преимуществами: не содержит фиктивных работ, имеет более про­стую технику построения и перестройки, включает только хорошо знакомое исполнителям понятие работы без менее привычного понятия события. Вместе с тем сети без событий оказываются значительно более громоздкими, так как событий обычно значительно меньше, чем работ (пока­затель сложности сети, равный отношению числа работ к числу событий, как правило, существенно больше единицы). Поэтому эти сети менее эффективны с точки зрения управления ком­плексом. Этим и объясняется тот факт, что (при отсутствии в целом принципиальных различий между двумя формами пред­ставления сети) в настоящее время наибольшее распространение получили сетевые графики «со­бытия — работы».

Источник

3.2.14. Сетевые модели

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

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

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

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

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

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

Математические методы сетевого планирования достаточно хорошо разработаны. Имеются многочисленные программы анализа сетевых моделей и решения задач календарного планирования на их основе.

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

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

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

Источник

10. Сетевые модели вычислительных систем

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

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

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

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

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

Моделирование параллельных процессов проще всего проводить в рамках специализированных языков моделирования (например, GPSS) и на алгоритмических языках реального времени (например язык АДА). Однако перед написанием программы моделирования необходимо описать алгоритм реализации параллельных процессов, что сделать традиционными методами очень даже не просто.

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

10.1. Определение: Сеть Петри

П озиция p_i является входной позицией для перехода t_j в том случае, если ; позиция p_i является выходной позицией для перехода t_j в том случае, если .

Пример Примером аналитического описания структуры сети Петри является следующий текст:

Источник