Основы сетевого моделирования и теория графов. Основные методы расчета сетевых моделей. Обобщенные детерминированные сетевые модели

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

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

Графом называется совокупность двух конечных множеств:

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

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

В экономике чаще всего используются два вида графов: дерево и сеть.

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

Сеть — это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».

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

За рубежом система СП известна как система РЕRТ (Рrоgram Еvaluation and Review Тechnique – метод анализа и оценки программ) или СРМ (Critical Рath Мethod – метод критического пути).

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

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

Сетевая модель должна удовлетворяет следующим требованиям:

Не должно быть событий с одинаковыми номерами.

Для каждой работы (i,j) должно выполняться i <j

Должны быть только одно начальное и одно конечное события.

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

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

Метод определения такого пути рассмотрим на примере.

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

Расчет критического пути включает два этапа.

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

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

Рассмотрим теперь прямой проход.

Пусть - ранний срок начала всех операций, выходящих из события i. Таким образом, является ранним сроком наступления события i. Если принять i=0, т.е. считать, что номер исходного события сети равен нулю, то при расчете сети. вычисления при прямом проходе выполняются по формуле:

Следовательно, чтобы вычислить ES j для события j, нужно сначала определить ES i начальных событий всех операций (i, j), входящих в событие j.

Обратный проход начинается с завершающего события сети. При этом целью является определение - поздних сроков окончания всех операций, входящих в событие i. Если принять i=n, где n - завершающее событие сети, то является отправной точкой обратного прохода. В общем виде для любого события i

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

Операция (i, j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям:

ES i = LC i,

ES j = LC j,

ES j - ES i = LC j - LC i = D ij.

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

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