Этап сетевого планирования проекта.
СПУ представляет собой систему методов и моделей планирования и управления разработкой сложных взаимосвязанных комплексов работ: крупных народно-хозяйственных комплексов, комплексных целевых программ (например, программа подготовки к олимпиаде «Сочи-2014»), технической подготовки производства на крупных промышленных предприятиях, планов строительства и реконструкции жилых и промышленных комплексов и т.п.
СПУ основано на моделировании процесса с помощью построения сетевого графика, отображающего планируемый комплекс работ.
Система СПУ позволяет:
Формировать календарный план реализации некоторого комплекса работ;
Выявлять и мобилизовать резервы времени, трудовые, материальные ресурсы и денежные ресурсы;
Осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ.
Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданную в специфической форме сети, графическое изображение которой называется сетевым графиком . Сетевой график – это ориентированный граф без контуров, отражающий логическую взаимосвязь всех операций (работ).
Главными элементами сетевой модели являются события и работы.
Работа (операция) – это активный процесс, требующий затрат ресурсов (например, сборка изделия, рытье котлована и т.п.), либо пассивный процесс(ожидание) – протяженный во времени процесс, не требующий затрат ресурсов (например, процесс сушки после покраски, процесс твердения бетона и т.п.). Кроме активных и пассивных работ выделяются фиктивные работы – логические зависимости (связи) между работами и (или) событиями, не требующие затрат времени и ресурсов.
Событие – это результат (промежуточный или конечный) выполнения одной или нескольких работ. Событие может свершиться только тогда, когда закончатся все работы, предшествующие этому событию. Последующие работы могут начаться только тогда, когда событие свершится. Предполагается, что событие не имеет продолжительности и совершается как бы мгновенно.
Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие не имеет предшествующих работ и событий, относящихся к рассматриваемому комплексу работ (это событие – начало всего комплекса работ). Завершающее событие не имеет последующих работ и событий (это событие – окончание всего комплекса работ).
События на сетевом графике изображаются кружками (вершинами графа), и работы – стрелками (ориентированными дугами графа).
Путь – любая непрерывная последовательность (цепь) работ и событий.
Полный путь – любой путь, начало которого совпадает с исходным событием, а конец – с завершающим.
Критический путь – наиболее продолжительный полный путь в сетевом графике. Этот путь не имеет резервов и включает самые напряженные работы комплекса. Все остальные работы (не лежащие на критическом пути) являются некритическими и имеют резервы времени, которые позволяют передвигать сроки их выполнения, не влияя на общую продолжительность работ.
Все события и работы в сетевом графике нумеруются. При этом работы удобно нумеровать двумя числами: первое число – номер события из которого исходит работа, второе число – номер события, к которому приводит работа.
При построении сетевых моделей необходимо соблюдать следующие правила:
1. Сеть вычерчивается слева направо, и каждое событие с большим номером изображается правее (или на одном уровне) предыдущего. Ориентация стрелок, изображающих работы, также в основном должна быть слева направо. При этом каждая работа должна выходить из события с меньшим номером и входить в событие с большим номером.
2. Два события могут быть объединены только одной работой. Для изображения параллельных работ вводятся промежуточные события и фиктивные работы.
3. В сети не должно быть тупиков, то есть событий (кроме завершающего), из которых не выходит ни одна работа.
4. В сети не должно быть событий (кроме исходного), которым не предшествует хотя бы одна работа.
5. В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, образующих замкнутую цепь.
Отметим, что над стрелками, обозначающими работы, в сетевом графике обычно указывается их (работ) продолжительность.
Приведем пример построения сетевого графика. П
Пусть речь идет об издании книги некоторого автора некоторым издательством. Упрощенная последовательность процессов (работ), приводящая к реализации проекта издания книги представлена в таблице 7.1.
Таблица 7.1. Исходные данные процесса издания книги.
| Процесс (работа) | Предшествующие процессы, которые должны быть выполнены до начала данного | Длительность (недели) |
| - | ||
| - | ||
| C: Разработка обложки книги | - | |
| D: Подготовка иллюстраций | - | |
| A,B | ||
| E | ||
| F | ||
| D | ||
| I: Подготовка печатных форм | G,H | |
| C,I |
Сетевой график, отображающий комплекс работ по изданию книги представлен на рисунке 7.1 (Красным выделен критический путь, расчет произведен ниже)
Рис.7.1. Сетевой график комплекса работ по изданию книги.
Расчет сетевого графика заключается в определении:
Ранних сроков свершения событий, ранних сроков начала и окончания работ;
Поздних сроков наступления событий, поздних сроков начала и окончания работ;
Резервов времени работ и событий, критического пути.
Введем следующие обозначения:
Тi р – ранний срок наступления события i ;
Тi п – поздний срок наступления события i ;
Тij рн – ранний срок начала работы ij ;
Тij ро – ранний срок окончания работы ij ;
Тij пн – поздний срок начала работы ij ;
Тij по – поздний срок окончания работы ij ;
R i – резерв времени события i ;
R ij – резерв времени работы ij ;
tij – продолжительность выполнения работы ij .
Алгоритм расчета параметров сетевого графика состоит из следующих основных этапов:
Этап 1. Двигаясь от исходного события к завершающему, определяются ранние сроки наступления событий, ранние сроки начала и окончания работ:
1.1 Ранний срок наступления исходного события полагается равным нулю: То р = 0.
Ранний срок начала всех работ, исходящих из исходного события также полагается равным нулю: Тоj рн = 0.
Ранний срок окончания работ, исходящих из исходного события определяется по формуле: Тоj ро = Тоj рн + tоj
1.2. Ранний срок наступления события j определяется по формуле:
Тj р = max { Тi р + tij }
Ранний срок наступления события j – это самый ранний срок, к которому завершаются все работы, предшествующие этому событию.
Ранний срок начала всех работ, исходящих из события j полагается равным раннему
сроку наступления события:: Тjk рн = Тj р
Ранний срок окончания работ, исходящих из события j определяется по формуле:
Тоj ро = Тоj рн + tоj
Этап 2. Двигаясь от завершающего события к исходному, определяются поздние сроки наступления событий, поздние сроки начала и окончания работ.
2.1. Для завершающего (конечного) события поздний срок его наступления полагается равным раннему, определенному на первом этапе:
Тk п = Тk р (здесь номером k обозначен номер завершающего события сети)
Для всех работ, входящих в завершающее событие (то есть для работ, результатом которых является завершающее событие сети) определяются поздние сроки начала и окончания по формулам:
2.2. Поздний срок наступления события i определяется по формуле:
Тi п = min { Тj п - tij }
Выбор минимального значения происходит по всем событиям {j}, которые непосредственно связаны с событием i через работы, то есть в сети есть работа ij.
Поздний срок наступления события i – это предельный срок, когда событие может наступить, не повлияв при этом на общий срок завершения всего комплекса работ.
Для всех работ, результатом которых является событие i, определяются поздние сроки начала и окончания по формулам:
Тik по = Тk п; Тik пн = Тik по – tik .
2.3. Для всех событий и работ определяются резервы времени:
Ri = Тi п – Тi р; Rij = Тij пн – Тij рн = Тij по – Тij ро
События и работы, резерв времени которых равен нулю , образуют критический путь . Именно работы, составляющие критический путь, определяют общую продолжительность всего комплекса, и любая задержка в их выполнении приводит к увеличению сроков выполнения всего комплекса работ.
События и работы, не лежащие на критическом пути, имеют резервы времени, отличные от нуля. Резерв показывает, на какой допустимый срок можно задержать наступление события, или на какой срок увеличить продолжительность выполнения работы, не вызывая при этом увеличения времени выполнения всего комплекса работ.
Рассчитаем сетевой график, представленный на рисунке 7.1, исходные данные которого представлены в таблице 7.1. Предварительно, с учетом построенного графика, обозначим работы с помощью двух чисел (первое число –номер события, из которого исходит работа, второе – номер события, к которому приводит работа), и заполним графы 1-3 таблицы 7.2. В последующих графах произведен расчет ранних и поздних сроков начала т окончания работ, а также резерва работ. Работы, составляющие критический путь выделены красным шрифтом.
Таблица 7.2. Расчет сетевого графика процесса издания книги.
| Процесс (работа) | Номер работы | Длит. (недели) | Тij рн | Тij ро | Тij по | Тij пн | Rij |
| A: Прочтение рукописи редактором | 0,1 | ||||||
| B: Пробная верстка отдельных страниц | 0,2 | ||||||
| C: Разработка обложки книги | 0,7 | ||||||
| D: Подготовка иллюстраций | 0,3 | ||||||
| Фиктивная работа | 1,2 | ||||||
| E: Просмотр автором редакторских правок | 2,4 | ||||||
| F: Верстка (создание макета книги) | 4,5 | ||||||
| G: Проверка автором макета книги | 5,6 | ||||||
| H: Проверка автором иллюстраций | 3,6 | ||||||
| I: Подготовка печатных форм | 6,7 | ||||||
| J: Печать и брошюровка книги | 7.8 |
После изучения данного раздела следует выполнить задачи 6,7 контрольной работы № 6
ЛИТЕРАТУРА
1. Экономико-математические модели и методы: учебно-практическое пособие/Под ред. С.И. Макарова, С.А. Севастьяновой. – М.: КНОРУС,2009
2. Орлова И.В. Экономико-математические методы и модели: компьютерное моделирование.- М.: Вуз. учеб., 2010
3. Мадера А.Г. Математические модели в управлении. -М.: РГТУ, 2007
4. Бразовская Н.В. Математические методы принятия управленческих решений. -Барнаул: Изд-во АлтГТУ, 2009
5. Вагнер Г. Основы исследования операций: В Зт. – М.: Мир, т. 1 1972, т. 2,3 – 1973
6. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. – М.: Наука, 1988
Могут строиться не только в виде формул (аналитическое представление модели), но и в виде числовых примеров (численное представление), в виде таблиц (матричное) и в виде графов (сетевое представление).
Соответственно по этому принципу различают модели:- Аналитические
- Матричные
- Сетевые
В используется метод сетевого планирования. Он базируется на применении сетевых графиков . Последние выражаются в виде определенной цепи работ и событий, связанных технологической последовательностью. Под работой здесь понимается процесс, который предшествует возникновению определенного события. Работа включает как технологические процессы, так и время ожидания, сопряженное с перерывами в этих процессах. Под событием понимают результат работы, без которого не могут быть начаты другие работы. В сетевых графиках события обозначаются кружками, где внутри пишется номер. Стрелки, помещающиеся между кружками, выражают намеченную последовательность выполнения работ. Числа, указанные возле стрелок, характеризуют намеченную длительность выполнения работ. С помощью сетевых графиков достигается либо оптимизация времени выполнения, либо оптимизация величины себестоимости осуществляемых работ.
Сетевой графикМодель сетевая (модель управления и планирования производством) — план выполнения некоторой совокупности взаимосвязанных операций (работ) заданный в специфической форме сети. Примером данной модели может служить сетевой график.
В кружках указаны номера событий, соединительными линиями (стрелками) работа, а цифры над ними указана ориентировачная стоимость, продолжительность или трудоемкость работ. В соответствии элементам графов (дугам и вершинам) ставятся числовые оценки (параметры операции: продолжительность, стоимость или трудоемкость). Что позволяет осуществлять глубокий анализ, а в ряде случаев оптимизацию.
Сетевая модель определяет с любой требуемой степенью детализации состав работ комплекса и порядок выполнения их во времени.
Отличительной особенностью сетевой модели в сравнении с другими формами представления планов является четкое определение всех временных взаимосвязей операций.
Сетевые модели используются не только как средство решения разнообразных задач планирования и прогнозирования. Сетевые модели также служат для построения специального класса системы организационного управления, получивших название систем сетевого планирования и управления.
Среди различных методом систем сетевого планирования и управления наиболее распространены: метод критического пути — анализ состояния процесса в каждый заданный момент времени и определение последовательности работ с целью избежания задержки времени выполнения плана к намеченному сроку и метод оценки пересмотра программ.
Поиск более эффективных способов планирования сложных процессов привели к необходимости использования моделей сетевого планирования и управления (СПУ). СПУ основано на моделировании процесса с помощью сетевого графика (сетевой модели). Сетевая модель и её основные элементы.
Сетевая модель
представляет план выполнения некоторого комплекса работ.
Главными элементами сетевого графика является события и работа.
События
– это завершение, какого либо процесса, отражающий отдельный этап выполнения проекта. На сетевом графике событие изображается кружком. Временные параметры сетевых графиков, коэффициенты напряжённости работы, анализ и оптимизация сетевого графика
ЗАДАЧА
Пусть для некоторого комплекса работ установлены оценки для каждой работы на уровне нормативных продолжительностей и срочного режима, а также даны стоимости. Информация представлена в таблице.
Таблица 1.
Нормативный режим |
Срочный режим |
|||
| Продолжительность, дни | Стоимость, м/р | Продолжительность, дни | Стоимость, м/р | |
| (1,2) | 3 | 6 | 2 | 11 |
| (1,3) | 5 | 8 | 3 | 12 |
| (1,4) | 4 | 7 | 8 | 9 |
| (2,5) | 10 | 25 | 8 | 30 |
| (3,5) | 8 | 20 | 6 | 24 |
| (3,6) | 15 | 26 | 12 | 30 |
| (4,6) | 13 | 24 | 10 | 30 |
| (5,7) | 3 | 15 | 6 | 25 |
| (6,7) | 4 | 10 | 3 | 15 |
Построить график данного комплекса работ.
- временные характеристики сетевого графика при нормальном режиме работ;
- найти критический путь;
- полные резервы времени;
- временные характеристики сетевого графика при срочном режиме работ;
- найти критический путь;
- полные резервы времени;
- определить стоимость работ.
Решение:
Рассчитаем временные характеристики для нормативного режима.
К временным характеристикам относятся ранние и поздние сроки наступления события. Ранний срок наступления события рассчитывается по формуле:
tp(j) =mac ((t p (i) +t (ij)), где
t p (j) –ранний срок наступления предшествующего I события.
t (ij)- работа.
t p(1)= ma х (tp(1)=0)
t p(2)= ma х (tp(1)+ tp(1,2)) =0+3=3
t p(3)= ma х ((tp(1)+ tp(1,3))=0+5=5
t p(4)= ma х (tp(1)+ tp(1,4))=0+4=4
t p(5)= ma х ((tp(4)+ tp(4,5)) =(2+10);(5+9)=14
t p(6)= ma х (tp(4)+ tp(4,6); tp(3)+ tp(3,6))=(4+13):(5+15)=20
t p(7)= ma х (tp(5)+ tp(5,7); tp(6)+ tp(6,7)=(14+8)(20+4)=24.
Очевидно, завершающее 7-е событие может наступить через 24 дня от начала выполнения всего комплекса работ. Поздний срок наступления события определяется по формуле:
tп(i)=min (tп(j)-t(ij))
Для расчёта t п(i) для комплекса будем считать, что самый поздний срок наступления 7-го события равен 24 дня, т.е. раннему сроку наступления 7-го события, тогда будем иметь:
tп(7)=min(24) =24
tп(6)=min(tп(7) - t(5,7)=(24-4)=20
tп(5)=min(24-4)=20
tп(4)=min(20-13)=7
tп(3)=min((16-9);(20-15) =5
tп(2)= min (16-10)=6
tп(1)= min (6-3; 5-5;7-4)=0
Р(i)=tp(j) - t п (i)
Р(1) =0-0=0
Р(2)=6-3=3
Р(3)=5-5=0
Р(4)=7-4=3
Р(5)=16-12=2
Р(6)=20-20=0
Р(7)=24-24=0
Полученные резервы времени показывают на какое время можно задержать наступление того или иного события, не вызывая опасности срыва выполнения комплекса работ. Те события, которые не имеют резервов времени, находятся на критическом пути.
Критический путь это наиболее продолжительный путь сетевого графика, который ведёт к завершению комплекса работ.
Находим пути и их длительности для данного комплекса работ:
1) 1-2-5-7 его стоимость: 3+10+8=21.
2) 1-3-5-7 его стоимость 5+9+8=22
3) 1-3-6-7. его стоимость: 5+15+4=24
4) 1-4-6-7. его стоимость: 4+13+4=21.
Критический путь: (1,3)-(3,6)-(6,7)
Резервы времени для работ, находящихся на критическом пути равны нулю.
(1,3)=0; (3,6)=0; (6,7)=0,
Рассчитаем временные характеристики сетевого графика при срочном режиме работ. Ранний срок наступления события рассчитывается по формуле:
tp(j) =maх((tp(i) +t(ij)), где
tp(j) –ранний срок наступления предшествующего I события.
t(ij)- работа.
Для расчёта t p (j) для данного комплекса будем считать, что ранний срок наступления 1-го события равно tp(1)=0, тогда для последующих событий будем иметь:
tp(1)= maх (t p(1)=0
tp(2)= maх (tp(1)+ tp(1,2)) =0+2=2
tp(3)= maх ((tp(1)+ tp(1,3))=0+3=3
tp(4)= maх (tp(1)+ tp(1,4))=0+8=8
tp(5)= maх ((tp(4)+ tp(4,5)) =(2+8);(3+6)=10
tp(6)= maх (tp(2)+ tp(2,5); tp(3)+ t p(4,6))=(3+12):(8+10)=18
tp(7)= maх (tp(5)+ tp(5,7); tp(6)+ t p(6,7)=(15+3);(18+3)=21.
Очевидно, завершающее 7-е событие может наступить через 21 день от начала выполнения всего комплекса работ.
Поздний срок наступления события определяется по формуле:
tп(7)=min(22) =24
tп(6)=min(t п (7)- t(5,7)=(21-3)=18
tп(5)=min(21-6)=15
tп(4)=min(18-10)=8
tп(3)=min((16-6);(19-15) =4
tп(2)= min (15-8)=7
tп(1)= min (15-2; 20-8;8-8)=0
Полученный результат говорит о том, что расчёты произведены правильно.
Резервы времени определяем как разность между поздними и ранними сроками по формуле:
Р(i) =t p(j) - t п (i)
Р(1) =0-0 =0
Р(2)=7-2=5
Р(3)=8-8=14
Р(4)=8-8 =0
Р(5)=12-8=4
Р(6)=18-18=0
Р(7)=22-22= 0
Найдём все пути: и их длительности.
1) 1-2-5-7 его стоимость: 3+8+6=16.
2) 1-3-5-7 его стоимость 3+6+6=15
3) 1-3-6-7. его стоимость:3+12+3=18
4) 1-4-6-7. его стоимость: 8+10+3=21.
Очевидно, что на критическом пути резервов времени нет.
Критический путь (1-3-6-7). Его длительность равна 21.
Материал подготовлен с использование работы: webforum . land . ru .
Методики сетевого планирования были разработаны в конце 50-х годов в США.
Однако первые ЭВМ были дороги и доступны только крупным организациям. Таким образом, исторически первые проекты представляли из себя грандиозные по масштабам работ, количеству исполнителей и капиталовложениям государственные программы.
В настоящее время сложились глубокие традиции использования систем управления проектами во многих областях жизнедеятельности
Сущность и назначение сетевого планирования и управления
Недостатки линейного календарного графика в значительной мере устраняются при использовании системы сетевых моделей, которые позволяют анализировать график, выявлять резервы и использовать электронно-вычислительную технику.
Весь процесс находит отражение в графической модели, называемой сетевым графиком. В сетевом графике учитываются все работы от проектирования до ввода в действие, определяются наиболее важные, критические работы, от выполнения которых зависит срок окончания проекта. В процессе деятельности появляется возможность корректировать план, вносить изменения, обеспечивать непрерывность в оперативном планировании. Существующие методы анализа сетевого графика позволяют оценить степень влияния вносимых изменений на ход осуществления программы, прогнозировать состояние работ на будущее. Сетевой график точно указывает на работы, от которых зависит срок выполнения программы.
Основные элементы сетевого планирования и управления
Сетевое планирование и управление - это совокупность расчётных методов и контрольных мероприятий по планированию и управлению комплексом работ с помощью сетевого графика.
Сетевая модель - это план выполнения некоторого комплекса взаимосвязанных работ, заданного в форме сети, графическое изображение которой называетсясетевым графиком .
Главными элементами сетевой модели являются работы и события .
Под событие понимается момент начала и момент окончания работы. Событие не имеет временной длительности.
Событие может свершиться только тогда, когда закончатся всё работы, ему предшествующие по сетевому графику. Для всех непосредственно предшествующих событию работ оно является конечным, а для всех непосредственно следующих за ним - начальным.
Каждое событие, включаемое в сетевую модель, должно быть полно, точно и всесторонне определено, его формулировка должна включать в себя результат всех непосредственно предшествующих ему работ.
Под работой понимается процесс, имеющий временную длительность.
Во-первых, это действительная работа - протяжённый во времени процесс, требующий затрат. Каждая действительная работа должна быть конкретной, чётко описанной и иметь ответственного исполнителя. Во-вторых.
Во вторых, это ожидание - протяжённый во времени процесс, не требующий затрат труда.
В-третьих, это зависимость , илификтивная работа - логическая связь между двумя или несколькими работами. Она указывает, что возможность одной работы непосредственно зависит от результатов другой. Фиктивная работа отражает только тот факт, что одна работа не может быть начата раньше, чет закончится другая работа. Продолжительность фиктивной работы принимается равной нулю.
Сетевая модель сетевого графика может задаваться в двух интерпретациях:
в виде событийного графа (графа, основанного на событиях; CRM-диаграмма) ;
в виде вершинного графа (графа, основанного на работах; PERT-диаграмма) .
Сетевые графики составляются на начальном этапе планирования. Вначале планируемый процесс разбивается на отдельные работы, составляется перечень работ и событий, продумываются их логические связи и последовательность выполнения, работы закрепляются за ответственными исполнителями. С их помощью и с помощью нормативов, если таковые существуют, оценивается продолжительность каждой работы. Затем составляется (сшивается ) сетевой график. После упорядочения сетевого графика рассчитываются параметры событий и работ, определяются резервы времени икритический путь . Наконец, проводятся анализ и оптимизация сетевого графика, который при необходимости вычерчивается заново с пересчётом параметров событий и работ.
Формирование событийного графа.
При формировании событийного графа используются следующие обозначения.
События в событийном графе изображаются кружками (вершины графа) с указанием номера события. Все вершины в пределах графа должны иметь разные номера. Нумеровать вершины можно в произвольном порядке без пропуска номеров, начиная с 1. Пример вершины-события приведен на рис. 5.11.
Рис. 5.11. Пример вершины событийного графа
Работы в событийном графе изображаются однонаправленными стрелками. Фиктивная работа изображается пунктирной линией. Эти линии в теории графов называются ребрами, а такой граф – направленным графом. Рядом с ребром необходимо указать длительность работы.
При формировании событийного графа нужно выполнить определенные требования:
граф должен иметь только одну начальную вершину;
граф должен иметь только одну конечную вершину;
в графе не должно быть петель, т. е. ребер с началом и концом в одной вершине;
в графе не должно быть циклов, т. е. путь из начальной вершины графа по стрелкам и любому пути всегда приводит к конечной вершине графа;
любые две вершины, т. е. два события, желательно должны иметь только одно ребро, т. е. одну работу. Это условие не обязательное.
Наиболее часто в сложной структуре графа делается ошибка с циклами. Эту ошибку невозможно обнаружить на компьютере и, поэтому надо очень внимательно готовить граф. Если в графе окажутся циклы, то программы сетевого планирования просто или зациклятся или выдадут неверный результат.
Пример событийного графа приведен на рис. 5.12.
Рис. 5.12. Пример событийного графа
Пример неверного графа с циклом приведен на рис. 5.13.
Рис. 5.13. Ошибочный граф с циклом
Сетевые графики на основе событийного графа получили наибольшее распространение. Это, прежде всего, связано с очень хорошей математической проработкой сетевого планирования на основе этих графов. Такие графы наиболее понятны профессионалам-математикам.
На практике используется изображение графа без указания номеров узлов и длительностей работ. Если в сетевой модели нет числовых оценок, то такая сеть называется структурной . Однако для расчетов необходимо использовать сети, в которых заданы оценки продолжительности работ, а также оценки других параметров, например трудоёмкости, стоимости и т. п.
Если сеть имеет одну конечную цель, то сеть называется одноцелевой . Сетевой график, имеющий несколько завершающих событий, называетсямногоцелевым . Многоцелевые сети и не могут быть рассчитаны по одному алгоритму. Расчет здесь ведется относительно каждой конечной цели. Примером может быть строительство жилого микрорайона, где ввод каждого дома является конечным результатом, и в графике по возведению каждого дома определяется свой критический путь. Однако, при раздельном расчете по каждой конечной цели могут оказаться не совпадающие в общей части графа критические пути. В связи с этим, если проект единый, то конечные узлы такого графа нужно соединить фиктивными работами. Направление ребра фиктивной работы указывается произвольным и от этого направления результат сетевого планирования не зависит.
В событийном графе нет необходимости указывать работу-ожидание. Если в ее указании есть острая необходимость, то такая работа указывается как обычная работа. Указание работы-ожидания может быть возможным в графе с несколькими началами и известными временными интервалами между этими началами.
Формирование вершинного графа.
Событийный граф не пользуется вниманием среди профессиональных экономистов, т. к. он им менее понятен, чем вершинный граф.
Вершинный граф строится на основе взаимодействия работ друг с другом. Вершиной в этом графе является работа, а ребром – связь одной работы с другой. Для экономистов такая структура понята, т.к. необходимо задавать связи одной работы с другой.
Работа в вершинном графе задается вершиной графа, т.е. в виде окружности, как и в стрелочном графе. Все вершины нумеруются, начиная с 1 и без пропуска номеров. Граф не должен иметь вершин с одинаковыми номарами. Рядом с вершиной указывается длительность работы. Фиктивные работы в вершинном графе не задаются, т. к. здесь это не имеет смысла.
Связь одной работы с другой задается направленным ребром графа. Ребро такого графа отражает только факт связи двух работ и, поэтому на ребре не указывается никакой длительности и ребра не нумеруются.
Пример вершинного графа, соответствующего событийному графу рис. 5.12, приведен на рис. 5.14.
Рис. 5.14. Пример вершинного графа
Примечательно то, что вершинный граф легко получить на основании событийного графа. Для этого надо в событийном графе ребро мысленно представить точкой и нарисовать взаимодействие полученных точек на основании событийного графа. Получить же, наоборот, событийный граф на основании вершинного - очень не просто. В связи с этим лучше всего первым изображать событийный граф.
В вершинном графе может быть несколько начальных и конечных вершин-работ. Единственным условием корректности графа является нулевое время начала всех начальных работ и одно время завершения всех конечных работ. Многоцелевой вершинный граф задать, в отличие от событийного, невозможно без дополнительных словесных пояснений. Этот факт продемонстрирован на рис. 5.15.
Рис. 5.15. Пример многоцелевого событийного графа и соответствующего вершинного
Как следует из рис. 5.15, в вершинном графе нет однозначности в неодновременном окончании всех работ и, поэтому будет считаться, что работы заканчиваются одновременно.
Сетевое планирование на основе вершинного графа имеет более сложную математическую реализацию в общем случае. Расчет критического пути сетевого графика, с одной стороны, здесь имеет более простой алгоритм реализации. С другой стороны, вычисление ранних о поздних начальных и конечных времен в вершинном графе реализуется со значительно более непонятным и сложным алгоритмом.
Сети на основании работ оказываются значительно более громоздкими, так как событий обычно значительно меньше, чем работ (показатель сложности сети , равный отношению числа работ к числу событий, как правило, существенно больше единицы). Поэтому эти сети менее эффективны с точки зрения управления комплексом.
Во многих областях экономики, технологии, проектирования, строительства, научных исследований важное значение имеют задачи оптимизации распределения ресурсов (трудовых, финансовых и др.). Особую значимость приобретают эти задачи в условиях реализации новых проектов, когда выполняется огромное количество взаимозаменяемых операций, в работу вовлекается множество работников, предприятий, организаций, так как в этих случаях управление работами усложняется новизной разработки, трудностью точного определения сроков и затрат ресурсов на том или ином этапе. Высокоэффективными инструментами для решения таких задач являются сетевые методы и модели.
Основные понятия сетевого моделирования
Сетевой моделью (другие названия: сетевой график, сеть) называется экономико-математическая модель, отражающая комплекс работ (операций) и событий, связанных с реализацией некоторого проекта (научно-исследовательского, производственного и др.), в их логической и технологической последовательности и связи. Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет, во-первых, более четко выявить взаимосвязи этапов реализации проекта и, во-вторых, определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ. Таким образом, методы сетевого моделирования можно отнести к методам принятия оптимальных решений.
Математический аппарат сетевых моделей базируется на теории графов. Графом называется совокупность двух конечных множеств: множества точек, которые называются вершинами , и множества пар вершин, которые называются ребрами. Представление о графе можно получить, если рассмотреть некоторый геометрический многогранник, например куб; в кубе можно выделить два конечных множества, состоящих соответственно из восьми вершин и двенадцати ребер.
Если рассматриваемые пары вершин являются упорядоченными, т.е. на каждом ребре задается направление, то граф называется ориентированным; в противном случае - неориентированным. Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь. Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным. В экономике чаще всего используется два вида графов: дерево и сеть. Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. Сеть - это ориентированный конечный связный граф, имеющий начальную вершину (источник ) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида "сеть".
В экономических исследованиях сетевые модели возникают при моделировании экономических систем и процессов методами сетевого планирования и управления (СНУ).
Объектом управления в системах сетевого планирования и управления являются коллективы исполнителей, располагающие определенными ресурсами и выполняющие заданный комплекс операций, который призван обеспечить достижение намеченной цели, например разработку нового изделия, строительство объекта и т.п.
Основой СНУ служит сетевая модель (СМ), в которой моделируется совокупность взаимосвязанных работ и событий, отображающих процесс достижения определенной цели. Она может быть представлена в виде графика или таблицы.
Основными понятиями СМ являются следующие: работа, событие, путь. На рис. 3.7 графически представлена СМ, состоящая из 5 событий (кружочки) и 6 работ (стрелки); продолжительность выполнения работ в некоторых единицах времени указана над стрелками.
Рис. 3.7.
Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом распределении работа изображается стрелкой, которая соединяет два события. Ома обозначается парой заключенных в скобки чисел (i,j), где i - номер события, из которого работа выходит, a j - номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t(i,j). Например, запись t (2, 5) = 9 означает, что работа (2, 5) имеет продолжительность 9 единиц времени (см. рис. 3.7). К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой и не может выполняться, прежде чем эта другая будет завершена; такие работы называются фиктивными и на графике изображаются пунктирными стрелками.
Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени. Событие свершается в тот момент, когда оканчивается последняя из работ, входящая в него. События обозначаются одним числом и при графическом представлении СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2,... N). В СМ имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.
Путь в СМ - это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в приведенной на рис. 3.7 модели путями являются L 1 = (1, 2, 5), L 2 = (1, 4, 5) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают L кр, а его продолжительность - t кр Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.