Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Владимирский государственный гуманитарный университет

Технико-экономический факультет

Кафедра менеджмента

Управление проектами

Дипломная работа

"Развитие сетевого моделирования путем создания факторовых сетевых моделей (пространственные, многоцелевые, динамические по целям и ресурсам, адаптивные к внешним и внутренним условиям, учитывающие риски)"

Выполнила: студентка гр. М-43

Алексеева М.

Принял: научный руководитель

зав. кафедрой менеджмента профессор,

д. т.н. Денисенко В.И.

Владимир 2009

Содержание

Введение

Глава 1.Проектное управление: модели и методы принятия решений

1.1 Объект проектного управления

1.2 Теоретические основы проектного управления

1.3 Методы расчета временных параметров и критического пути сетевой модели проекта

Глава 2. Основные понятия и элементы сетевых моделей

2.1 Понятие модели и ее особенности

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

2.3 Вероятностные сетевые модели

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

3.1 Аналитическое моделирование

3.2 Симуляционное моделирование

3.3 Моделирование сети с помощью процессов (тредов)

3.4 Сетевые технологии на основе сетевого формализма в глобальной сети Internet

3.5 Нейрокомпьютинг в Internet: от World Wide Web к "World Wide Brain"

3.6 Обзорная классификация и тенденции развития сетевого моделирования

Заключение

Список используемой литературы

Введение

В конце 50-х годов в США для осуществления программы исследовательских и конструкторских работ по созданию ракеты "Поларис" впервые был использован метод планирования и управления, основанный на идее определения, оценки вероятных сроков и контроля так называемого "критического пути" всего комплекса работ. Результаты превзошли все ожидания: во-первых, заметно уменьшилось число сбоев в работе из-за несогласованности используемых ресурсов, резко сократилась общая продолжительность выполнения всего комплекса работ, получен огромный эффект из-за снижения суммарной потребности в ресурсах и, соответственно, уменьшения общей стоимости программы. Вскоре после того, как результаты выполнения программы "Поларис" стали достоянием общественности, весь мир заговорил о методе PERT (Project Evaluation and Review Technique) как о новом подходе к организации управления.

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

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

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

Задачи данной научной работы состоят в следующем:

1) изучить теоретические основы проектного управления;

2) изучить понятие модели и ее классификация;

3) изучить сетевое моделирование;

4) изучить сетевую технологию проектирования на платформе локальных сетей типа Ethernet и глобальной сети Internet;

5) изучить Нейрокомпьютинг в Internet.

Глава 1.Проектное управление: модели и методы принятия решений

1.1 Объект проектного управления

Термин проект, как известно, происходит от латинского слова projectus, что в буквальном переводе означает "брошенный вперед". Таким образом, сразу становится ясно, объект управления, который можно представить в виде проекта, отличает возможность его перспективного развертывания, т.е. возможность предусмотреть его состояния в будущем. Хотя различные официальные источники трактуют понятие проекта по-разному 2, во всех определениях четко просматриваются особенности проекта как объекта управления, обусловленные комплексностью задач и работ, четкой ориентацией этого комплекса на достижение определенных целей и ограничениями по времени, бюджету, материальным и трудовым ресурсам.

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

Деятельность как объект управления рассматривается в виде проекта тогда, когда

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

· переходы от одной работы к другой определяют основное содержание всей деятельности;

· достижение целей деятельности связано с последовательно-параллельным выполнением всех элементов этой деятельности;

· ограничения по времени, финансовым, материальным и трудовым ресурсам имеют особое значение в процессе выполнения комплекса работ;

· продолжительность и стоимость деятельности явно зависит от организации всего комплекса работ.

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

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

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

1.2 Теоретические основы проектного управления

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

В сетевой модели роль вершин графа могут играть события, определяющие начало и окончание отдельных работ, а дуги в этом случае будут соответствовать работам. Такую сетевую модель принято называть сетевой моделью с работами на дугах (Activities on Arrows, AoA). В то же время, возможно, что в сетевой модели роль вершин графа играют работы, а дуги отображают соответствие между окончанием одной работы и началом другой. Такую сетевую модель принято называть сетевой моделью с работами в узлах (Activities on Nodes, AoN).

Пусть множество A={a1, a2, a3, ... an} - комплекс работ, выполнение которых требуется для решения определенной задачи, например, строительства дома. Тогда, если множество V={v1, v2, v3, ..., vm} будет представлять комплекс событий, возникающих в процессе выполнения комплекса работ, то сетевая модель будет задаваться ориентированным графом G=(V, A), в котором элементы множества V играют роль вершин, а элементы множества A - роль дуг, соединяющих вершины, причем каждой дуге ai можно поставить в однозначное соответствие пару вершин (vsi, vfi), первая из которых будет определять момент начала работы аi, а вторая - момент окончания этой работы. Такая сетевая модель будет сетевой моделью с работами на дугах.

Теперь пусть множество A={a1, a2, a3, ... an} - по-прежнему будет рассматриваться как комплекс работ, выполнение которых требуется для решения определенной задачи, например, строительства дома. Тогда, если множество V={v1, v2, v3, ..., vm} будет представлять комплекс отношений предшествования-следования работ в процессе их выполнения, то сетевая модель будет задаваться ориентированным графом G=(A, V), в котором элементы множества A играют роль вершин, а элементы множества V - роль дуг, соединяющих вершины, причем каждой дуге vi можно поставить в однозначное соответствие пару вершин (asi, afi), первая из которых будет непосредственно предшествующей работой в данной паре, а вторая - непосредственно следующей. Такая сетевая модель будет сетевой моделью с работами в узлах.

Сетевая модель может быть представлена: 1) сетевым графиком, 2) в табличной форме, 3) в матричной форме, 4) в форме диаграммы на шкале времени. Как будет показано ниже, переход от одной формы представления к другой не составляет большого труда.

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

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

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

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

· событий - моментов времени, когда происходит начало или окончание выполнения какой-либо работы (работ);

· работ - неделимых частей комплекса действий, необходимых для решения некоторой задачи;

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

Графически события изображаются кружками, разделенными на три равных сегмента (радиусами под углом в 120°); работы изображаются сплошными линиями со стрелками на конце, ориентированными слева направо; фиктивные работы изображаются пунктирными линиями со стрелками на конце, ориентированными слева направо. Пример сетевого графика модели АоА представлен ниже на рис. 1.

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

Если сетевым графиком отображается модель типа AoN, то избыточности структуры удается избежать. Здесь нет необходимости вводить в качестве дополнительного структурного элемента фиктивные работы, поскольку отсутствуют те структурные элементы, которые они призваны обслуживать, а именно - события. В сетевом графике модели типа AoN есть только узлы (или вершины), которые обозначают работы и дуги (сплошные линии со стрелками, ориентированными слева направо), которые обозначают отношения предшествования-следования работ. Никаких событий и никаких фиктивных работ! Заметим, что в наиболее известной программе по проектному управлению Microsoft Project реализуется именно этот тип модели.

Здесь узлы сети, соответствующие работам, принято изображать прямоугольниками, поделенными на 5 секторов. В центральном секторе проставляется индекс (или записывается наименование работы). Заполнение остальных секторов рассматривается ниже. Пример сетевого графика для модели типа AoN представлен ниже на рис. 2.



Рисунок 2. Пример сетевого графика модели типа АоN

В табличной форме сетевая модель задается множеством {A, A(IP)}, где А - это множество индексов работ, а A(IP) множество комбинаций работ, непосредственно предшествующих работе А. Для рассматриваемого выше примера табличная форма сетевой модели будет такой, которая представлена в табл. 1.

Таблица 1. Табличная форма сетевой модели

Матричная форма описания сетевой модели задается в виде отношения между событиями (ei, ej), которое равно 1, если между этими событиями есть работа (либо реальная, либо фиктивная) и 0 - в противном случае. Матричная форма для описания сетевой модели из рассматриваемого выше примера приведена ниже в табл. 2:

Таблица 2.

События	1	2	3	4	5	6	7
1		1	1
2	1					1
3	1			1	1
4			1		1	1
5			1	1			1
6		1		1			1
7					1	1

Описание сетевой модели в форме временной диаграммы (или графика Ганта) предполагает размещение работ в координатной системе, где по оси абсцисс (X) откладывается время (t), а по оси ординат (Y) - работы. Точкой начала отсчета любой из работ будет момент окончания всех ее предшествующих работ. Если работе не предшествует ничто, то она откладывается от начала временной шкалы, т.е. с самого левого края диаграммы. На рис. 3 представлен график Ганта для сетевой модели по данным табл. 1 с добавлением информации о продолжительности выполнения работ.

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

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

Рисунок 3.

Различаются следующие разновидности событий сетевого графика модели АоА:

· исходное событие - результат, в отношении которого условно предполагается, что он не имеет предшествующих работ;

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

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

· начальное событие - событие, непосредственно предшествующее данной конкретной работе;

· конечное событие - событие, непосредственно следующее за данной работой.

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

Различают следующие временные параметры:

· продолжительность работ;

· раннее время начала работы;

· раннее время окончания работы;

· позднее время начала работы;

· позднее время окончания работы;

· раннее время наступления события;

· позднее время наступления события;

· продолжительность критического пути;

· резерв времени наступления события;

· полный резерв времени выполнения работы;

· свободный резерв времени выполнения работы;

· независимый резерв времени выполнения работы.

Продолжительность работы (ti) - календарное время, которое занимает выполнение работы.

Раннее время начала работы (ESTi) - наиболее ранний из возможных сроков начала выполнения работы.

Раннее время окончания работы (EFTi) - равно раннему времени начала работы плюс ее продолжительность.

Позднее время окончания работы (LFTi) - наиболее поздний из допустимых сроков окончания работы.

Позднее время начала работы (LSTi) - равно позднему времени окончания работы минус ее продолжительность.

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

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

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

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

Работы, лежащие на критическом пути, называются критическими работами, а события - критическими событиями.

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

Резерв времени наступления события - это разница между поздним и ранним сроками наступления этого события.

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

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

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

Параметры раннего и позднего времени наступления события используются в маркировке вершин сетевого графика модели типа АоА. В левый сегмент записывается раннее время наступления соответствующего события (ЕETj), а в правый - позднее (LETj), что показано на рис. 4.

Рисунок 4. Пример маркировки времени наступления событий

В маркировке вершин сетевого графика модели типа AoN помимо индекса работ используются параметры (см. Рис. 5):

· раннего времени начала выполнения работы (ESTj), которое записывается в левый верхний сектор прямоугольника, маркирующего вершину работы;

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

· продолжительность выполнения работы (tj), которая записывается в левый нижний сектор прямоугольника, маркирующего вершину работы;

· полный резерв времени выполнения работы (TFi) - который записывается в правый нижний сектор прямоугольника, маркирующего вершину работы.

Рисунок 5. Пример маркировки вершин сетевого графика модели типа АоN

1.3 Методы расчета временных параметров и критического пути сетевой модели проекта

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

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

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

Рисунок 6. Пример сетевого графика для иллюстрации методов расчета временных параметров

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

Раннее время начала работы [ij] совпадает с ранним временем наступления события [i], т.е.

ESTij = EET [i].

Позднее время окончания работы [ij] совпадает с поздним временем наступления события [j], т.е.

LFTij = LET [j].

Раннее время окончания работы [ij]:

EFTij = ESTij + tij.

Позднее время начала работы [ij]:

LSTij = LFTij - tij.

Раннее время наступления события [j] совпадает с самым поздним (максимальным) ранним временем окончания из всех тех работ, для которых данное событие является конечным, т.е.

EET[j] = max { EFTrj, EFTnj, ..., EFTmj},

где [rj], [nj], ..., [mj] - индексы работ, для которых событие [j] является конечным.

Позднее время наступления события [j] совпадает с самым ранним (минимальным) поздним временем начала из всех тех работ, для которых данное событие является начальным, т.е.

LET[j] = min { LSTjr, LSTjn, ..., LSTjm},

где [jr], [jn], ..., [jm] - индексы работ, для которых событие [j] является начальным.

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

EET[s] = LET[s]

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

Итак, для заключительного события справедливо:

EET[f] = LET[f] = TK,

где TK - продолжительность критического пути.

Полный резерв времени выполнения работы [ij]:

TFij = LЕT[j] - EET[i] - tij.

Свободный резерв времени выполнения работы [ij]:

FFij = EЕT[j] - EET[i] - tij.

Независимый резерв времени выполнения работы [i]:

IFi = EЕT[j] - LET[i] - tij.

Рассмотрим сначала матричный метод определения временных параметров.

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

Рисунок 7. Разметка матрицы при определении временных параметров сетевой модели матричным методом

Первый шаг заполнения матрицы заключается в следующем. Если события [i] и [j] соединяются какой-то работой, то продолжительность этой работы tij заносится в числители двух клеток: клетки, лежащей на пересечении i-й строки и j-го столбца, и клетки лежащей на пересечении j-й строки и i-го столбца. Эти действия выполняются для всех работ сетевой модели, а числители всех остальных клеток, кроме клеток, лежащих на главной (слева сверху вправо вниз) диагонали матрицы, заполняются нулями или вообще не заполняются.

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

Рисунок 8.

Нетрудно проверить по формулам, что раннее время окончания работы 1-2 равно 4, а работы 1-4 равно 7.

Следующий шаг заполнения матрицы начинается с того, что мы должны решить, какое значение должно стоять в числителе диагональной клетки второй строки. По определению это должно быть значение, соответствующее раннему началу события 2. Раннее начало некоторого события, являющегося конечным для нескольких работ, равно моменту раннего окончания самой поздней из работ, которые заканчиваются данным событием. Значит, просто необходимо просмотреть знаменатели клеток столбца 2 сверху вниз до главной диагонали и выбрать максимальное значение, после чего записать его в числитель диагональной клетки 2. В нашем примере это будет знаменатель клетки 1-2, который равен 4.

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

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

Дойдя до последней диагональной клетки (см. Рис. 9), мы получили значение раннего времени наступления завершающего события сетевой модели (36), которое и определяет продолжительность критического пути. Вместе с тем, для завершающего события, как известно, раннее время равно позднему времени его наступления, следовательно, знаменатель этой клетки будет равен ее числителю. Запишем это.

Получив значение знаменателя последней диагональной клетки, можно вычислить значения знаменателей клеток (чьи числители больше 0), находящихся в той же строке слева (ниже) от главной диагонали. Они будут равны разнице значения знаменателя соответствующей диагональной клетки и значения числителя клетки, для которой производится расчет. Так, например, значение знаменателя клетки 8-7 будет равно 36-5=31, а клетки 8-4 будет равно 36-6=30.

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

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

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



Рисунок 9.

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

Так, для работы 3-5 полный резерв будет равен 29-9=20, свободный - 17-2-7=8, а независимый - 17-22-7=-12 (принимается равным 0). Для работы 2-6 полный резерв будет равен 26-12=14, свободный - 26-4-8=14 и независимый - 26-4-8=14.

На рис. 10 приведены результаты расчетов всех резервов времени на основании данных из таблицы на рис. 9.

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

1. индекс работы;

2. индексы непосредственно предшествующих работ;

3. индексы непосредственно следующих работ;

4. продолжительность выполнения работы;

5. раннее время начала выполнения работы;

6. позднее время начала выполнения работы;

7. раннее время окончания выполнения работы;

8. позднее время окончания выполнения работы;

9. полный резерв времени работы;

10. свободный резерв времени работы;

11. независимый резерв времени работы.

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

Алгоритм табличного метода предусматривает выполнение следующих последовательных шагов.

Рисунок 10.

ШАГ 1. Определение индексов непосредственно следующих работ.

Рассматриваем работу с индексом [i]. Непосредственно следующие за ней работы - это те работы, для которых работа [i] является непосредственно предшествующей. Следовательно, индексы непосредственно следующих работ - это индексы тех работ, у которых в столбце (2) содержится индекс работы [i].

ШАГ 2. Определение раннего времени начала и раннего времени окончания работ.

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

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

· Раннее время окончания рассматриваемой работы равно раннему времени ее начала (из столбца (5)) плюс продолжительность работы (из столбца (4)).

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

Продолжительность критического пути равна максимальному значению в столбце (7).

ШАГ 3. Определение позднего времени окончания и позднего времени начала работ.

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

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

· Позднее время начала рассматриваемой работы равно позднему времени ее окончания (из столбца (8)) минус продолжительность работы (из столбца (4)).

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

Шаг 4. Определение полного резерва времени выполнения работы.

Полный резерв времени работы [i] находится как разность значений ее позднего и раннего времени окончания (соответственно, столбцы (8) и (7)), либо как разность значений ее позднего и раннего начала выполнения (соответственно, столбцы (6) и (5)).

Шаг 5. Определение свободного резерва времени выполнения работы.

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

Шаг 6. Определение независимого резерва времени выполнения работы.

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

По приведенным выше правилам заполнена следующая табл. 3.

Таблица 3.

Работа	Непосредс. Предшеств.	Непосредств Следующая.	t	EST	LST	EFT	LFT	TF	FF	IF
A	-	D, E	4	0	0	4	4	0	0	0
B	-	H, I, J	7	0	7	7	14	7	7	0
C	-	F, G	2	0	20	2	22	20	0	0
D	A	M	8	4	18	12	26	14	14	14
E	A	H, I, J	10	4	4	14	14	0	0	0
F	C	K, L	7	2	22	9	29	20	8	0
G	C	N	6	2	25	8	31	23	11	0
H	B, E	M	12	14	14	26	26	0	0	0
i	b, e	-	6	14	30	20	36	16	16	16
J	B, E	K, L	3	14	26	17	29	12	0	0
K	F, J	-	4	17	32	21	36	15	15	3
L	F, J	N	2	17	29	19	31	12	0	0
M	D, H	-	10	26	26	36	36	0	0	0
N	G, L	-	5	19	31	24	36	12	12	0

Глава 2. Основные понятия и элементы сетевых моделей

2.1 Понятие модели и ее особенности

Линейные модели. Управление большими и сложными комплексными программами, активно развивавшееся с начала ХХ века до середины 50-х годов, не имело эффективных моделей. Наиболее часто используемыми инструментами управления являлись график (диаграмма) Ганта и циклограмма. Принципы построения этих моделей схожи, и их можно отнести к линейным моделям.

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

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

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

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

Циклограммы активно использовались до 80-х годов ХХ века в основном в строительной отрасли, особенно при организации поточного строительства.

Рис 1. Циклограмма равноритмичного потока

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

Рис 2.Циклограмма неритмичного потока с однородным изменением ритма

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

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

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

Теория графов. В связи с недостатками линейных моделей возникла необходимость создания новых моделей. И в середине 50-х годов ХХ века были созданы модели, основанные на теории графов, которая является разделом дискретной математики. Теория графов активно используется при решении многих задач управления в рамках так называемого исследования операций. Объектом изучения теории графов является граф.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. номер последующему событию следует присваивать после присвоения номеров предшествующим событиям.

4. стрелка (работа) должна быть всегда направлена из события с меньшим номером в событие с большим номером.

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

2.3 Вероятностные сетевые модели

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

Наиболее традиционным способом учета данных неопределенностей является переход к стохастическим (вероятностным) моделям.

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



Рис. 6.21 Вероятностные СМ: а - распределение срока наступления событияили; б - варианты -распределения

Задачи расчета вероятностных СМ

Это усложняет расчет СМ, поскольку здесь ставятся несколько другие задачи:

- определить функцию распределения вероятности времени наступления события;

- определить вероятность того, что событие наступит ранее момента времени;

- определить функцию распределения критического пути--

- определить среднее значение длительности критического пути --;

- определить максимальное и минимальное значения длительности критического пути --;

- определить возможность (вероятность) выполнения общего комплекса работ за плановое время и т. д.

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

Статистическими исследованиями было установлено, что длительностьдля большинства известных типов работ хорошо описываетсяраспределением (рис. 6.21, б):

Здесь С,-- константы, причем С определяется из условия нормирования:

Константыизависят от характера работ (см. рис 6.21, б - здесь ,).

Методы расчета вероятностных СМ

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

Аналитические методы. В этом случае на основании заданной структуры СМ и распределений вероятностейвычисляются распределения времени наступления каждого из событийили. Рассмотрим рис. 6.22. Здесь изображены два простейших фрагмента СМ - параллельное (а) и последовательное (б) соединения двух работ с распределениями длительностей и соответственно. Необходимо определить распределение итоговой длительности

Рис. 6.22 Аналитические методы расчета СМ: а - параллельное сочленение работ; б - последовательное соединение

В первом случае, во втором --.

Рассмотрим второй случай. Вероятность того, что , а (а в итоге ) есть . Интегрируя по всем допустимым значениям, получаем:

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

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

Метод Монте-Карло. Этот метод (метод статистических испытаний) представляет собой классический образец имитационного моделирования сложных систем на ЭВМ.

Процесс выглядит примерно так:

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

- затем генерируется совокупность, на основе которой определяетсяи т. д.

Поскольку точность метода Монте-Карло пропорциональна (N - число испытаний), обычно процесс повторяется раз. В итоге получается ряд значений = . Этот результат может быть представлен в виде гистограммы (рис. 6.23, а, здесь N= 61).



Рис. 6.23. Исследование СМ методом Монте-Карло (а); метод PERT (б)

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