Реферат: Сетевые модели планирования и управления

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Экономический факультет

Курсовая работа

По теме: «СЕТЕВЫЕ МОДЕЛИ ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ»

Барнаул 2001

Введение

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

Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет,

во-первых, более четковыявить взаимосвязи этапов реализации проекта и

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

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

Первая глава: Сетевые модели планирования и управления.

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

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

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

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

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

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

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

В экономическихисследованиях сетевые модели возникают при моделировании экономическихпроцессов методами сетевого планирования и управления (СПУ).

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

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

Основные понятиясетевой модели:

· событие,

· работа

· путь.

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

Работахарактеризует материальное действие, требующее использования ресурсов, илилогическое, требующее лишь взаимосвязи событий. При графическом представленииработа изображается стрелкой, которая соединяет два события. Она обозначаетсяпарой заключенных в скобки чисел (i,j), где i — номер события, изкоторого работа выходит, а j — номер события, в которое она входит.Работа не может начаться раньше, чем свершится событие, из которого онавыходит. Каждая работа имеет определенную продолжительность t (i,j)-Например,запись t (2,5) = 4 означает, что работа (2,5) имеет продолжительность 5 единиц.К работам относятся также такие процессы, которые не требуют ни ресурсов, нивременивыполнения.Они заключаются в установлении логической взаимосвязи работ и показывают, чтоодна из них непосредственно зависит от другой; такие работы называютсяфиктивными и на графике изображаются пунктирными стрелками (см. работу (6,9)).

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

В сетевой моделиимеется начальное событие (с номером 1), из которого работы только выходят, иконечное событие (с номером N), в которое работы только входят.

Путь — это цепочкаследующих друг за другом работ, соединяющих начальную и конечную вершины,например, в приведенной выше модели путями являются L1 = (1, 2, 3,7, 10, 11), L2 = (1, 2, 4, 6, 11) и др.

Продолжительностьпутиопределяется суммой продолжительностей составляющих его работ. Путь, имеющиймаксимальную длину, называют критическим и обозначают LKp, а егопродолжительность — tкр. Работы, принадлежащие критическому пути,называются критическими. Их несвоевременное выполнение ведет к срыву сроков всегокомплекса работ.

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

Перед расчетомСМ следует убедиться, что она удовлетворяет следующим основным требованиям:

1. Событияправильно пронумерованы, т. е. для каждой работы (i, j) i <j (см. на рис. 2работы (4,3) и (3,2)). При невыполнении этого требования необходимоиспользовать алгоритм пере нумерации событий, который заключается в следующем:

нумерация событий начинается с исходногособытия, которому присваивается № 1;

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

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

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

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

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

4. Отсутствуютциклы, т. е. замкнутые пути, соединяющие событие с ним же самим (см. путь(2,4,3)).

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

Ранний срок свершениясобытия определяется величиной наиболее длительного отрезка пути от исходногодо рассматриваемого события, причем tр(1) = 0, a tр (N) = tKp(L):

tр(j)=max{ tр(j)+(i,j)}; j=2,N

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

tn(i) = min { tn (i) — t(i,j)};j=2,N-1

Этот показательопределяется «обратным ходом», начиная с завершающего события, с учетом соотношенияtn(N) = tp (N).

Все события, заисключением событий, принадлежащих критическому пути, имеют резерв R(i):

R(i)=tn(i) — tp (i)

Резервпоказывает, на какой предельно допустимый срок можно задержать наступлениеэтого события, не вызывая при этом увеличения срока выполнения всего комплексаработ. Для всех работ (i,j) на основе ранних и поздних сроковсвершения всех событий можно определить показатели:

Ранний срокначала — tpn(i,j)=p(i),

Ранний срококончания — tpo(i,j)=tp(i)+t(i,j)

Поздний срококончания — tno(U)=tn(j)

Поздний срокначала —tпн(i,j)=tn(j) — t(i,j)

Полный резерв времени —Rn(i,j)=tn(j)-tp(i)- t(i,j),Независимый резерв —Rн(i,j)=max{0;tp(j)–tn(i) — t(i,j)}=

= max {0; Rn(i,j)-R(i)-R(j)}.

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

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

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

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

Перечисленныевыше характеристики СМ могут быть получены на основе приведенных аналитическихформул, а процесс вычислений отображен непосредственно на графике, либо вматрице (размерности N*N), либо втаблице.

Рассмотримпоследний указанный способ для расчета СМ, которая представлена на рис. 1; результатырасчета приведены в табл. 1

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

Таблица 1 Расчет основныхпоказателей сетевой модели

Кпр

(i,j) t(i,j)

tpн(i,j)= tp

tpo(i,j)

tnн(i,j)

tno(i,j)= tn

Rн

Кн

1 2 3 4 5=4+3 6=7-3 7 8 9 10 (1,2) 6 6 6 1 1 (2,3) 5 6 11 12 17 6 0,67 1 (2,4) 3 6 9 6 9 1 1 (2,5) 4 6 10 11 15 5 5 0,44 1 (3,7) 1 11 12 17 18 6 0,67 1 (4,5) 6 9 15 9 15 1 1 (4,6) 4 9 13 17 21 8 0,47 1 (4,9) 7 9 16 14 21 5 0,67 2 (5,8) 3 15 18 17 20 2 0,78 2 (5,10) 9 15 24 15 24 1 1 (6,9) 13 13 21 21 8 0,38 1 (6,11) 5 13 18 28 33 15 7 0,38 1 (7,10) 6 12 18 18 24 6 0,67 1 (8,10) 4 18 22 20 24 2 0,78 2 (9,10) 3 16 19 21 24 5 0,67 4 (10,11) 9 24 33 24 33 1

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

Для работ,начинающихся с номера «1», предшествующих работ нет. Для работы, начинающейсяна номер «k», просматриваются все верхние строчки второй графы таблицы иотыскиваются строки, оканчивающиеся на этот номер. Количество найденных работзаписывается во все строчки, начинающиеся с номера «k». Например, дляработы (5,8) в гр. 1 поставим цифру 2, так как в гр. 2 на номер 5 оканчиваютсядве работы: (2,5) и (4,5).

Заполнениетаблицы начинается с расчета раннего срока начала работ. Для работ, имеющихцифру «ноль» в первой графе, в гр. 4 также заносятся нули, а их значение в гр.5 получается в результате суммирования гр. 3 и 4. В нашем случае таких работтолько одна — (1, 2), поэтому в гр. 4 в соответствующей ей строке проставим 0,а в гр. 5 — 0+6 = 6.

Для заполненияследующих строк гр.4, т. е. строк, начинающихся с номера 2, просматриваются заполненныестроки гр. 5, содержащие работы, которые оканчиваются на этот номер, имаксимальное значение переносится в гр. 4 обрабатываемых строк. В данном случае такая работа лишь одна (1, 2), о чем можно судить по гр. 1. Цифру 6 изгр. 5 переносим в гр.4 для всех работ, начинающихся с номера 2, т. е. в трипоследующие строки с номерами (2, 3), (2, 4), (2, 5). Далее для каждой изэтих работ путем суммирования их значений гр. 3 и 4 сформируем значениегр.5.:

tpo(2.3)= 5 + 6 =11

tpo(2.4)= 3 + 6 = 9

Этот процесс повторяетсядо тех пор, пока не будет заполнена последняя строка таблицы.

Графы 7 и 6заполняются «обратным ходом», т. е. снизу вверх. Для этого просматриваютсястроки, оканчивающиеся на номер последнего события, и из гр. 5 выбираетсямаксимальная величина, которая записывается в гр. 7 по всем строчкам,оканчивающимся на номер последнего события (см. формулу tn(N) = tp(N)). В нашемслучае t(N) = 33. Затем для этих строчек находится содержимое гр. 6 какразность между гр. 7 и 3 Имеем:

tpo(10.11)= 33 — 9 = 24.

Далеепросматриваются строки, оканчивающиеся на номер события, которое непосредственнопредшествует завершающему событию (10). Для определения гр. 7 этих строк(работы (5,10), (7,10), (8,10), (9,10)) просматриваются все строчки гр. 6,лежащие ниже и начинающиеся с номера 10.

В гр. 6 срединих выбирается минимальная величина, которая переносится в гр. 7 по обрабатываемымстрочкам. В нашем случае она одна — (10,11), поэтому заносим во все строкиуказанных работ цифру «24». Процесс повторяется до тех пор, пока не будутзаполнены все строки по гр. 6 и 7.

Содержимое гр. 8равно разности гр. 6 и 4 или гр. 7 и 5. Гр. 9 проще получить, воспользовавшисьформулой.

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

LKp =(1,2,4,5,10,11), а tкр= 33 дня.

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

KH=(i,j)=t(Lmax)-tkp /tkp — tkp`= 1- Rn — Rn (i,j)/ tkp — tkp`

где t(L max) —продолжительность максимального пути, проходящего через работу (i,j);

tkp`—продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.

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

• напряженные(KH(i,j) > 0,8);

• подкритические (0,6 < KH(i,j) < 0,8);

• резервные (KH (i,j) < 0,6).

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

При расчете этихпоказателей целесообразно пользоваться графиком СМ. Итак, для работ критическогопути (1,2), (2,4), (4,5),(5,10),(10,11) Kн=1. Для другихработ:

Kн(2,3) = 1 — (6:(33 — (6 + 9)) = 1- 0,33 = 0,67

Kн (4,9) — 1 — (5: (33 — (6 + 3 + 9)) = 1 — 0,33 = 0,67

Kн (5,8) = 1 — (2: (33 — (6 + 3 + 6 + 9)) = 1 — 0,22 = 0,78 и т.д.

В соответствии срезультатами вычислений Кн для остальных работ, которые представлены в последнейграфе табл.1, можно утверждать, что оптимизация СМ возможна в основном за счетдвух резервных работ: (6,11) и (2,5).

Сетевое планирование в условияхнеопределенности.

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

Минимальная(оптимистическая) оценка tmin(i,j) характеризует продолжительностьвыполнения работы при наиболее благоприятных обстоятельствах, а максимальная(пессимистическая)tmin(i,j)— при наиболее неблагоприятных. Продолжительность работы в этом случаерассматривается, как случайная величина, которая в результате реализации можетпринять любое значение в заданном интервале. Такие оценки называютсявероятностными (случайными), и их ожидаемое значение tox оценивается по формуле(при бета-распределении плотности вероятности):

tож(i,j)=(3tmin(i,j) + 2t max(i,j)): 5.

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

S2 (i,j)= (t max (i,j) – t min (i,j) 2 :5 2 =

=0.04 ( t max (i,j) – t min (i,j)2

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

Кроме обычныххарактеристик СМ, при вероятностном задании продолжительности работ можнорешить две дополнительные задачи:

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

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

Первая задачарешается на основе интеграла вероятностей Лапласа Ф(г) использованием формулы:

P (t kp< T) =0,5 + 0,5 Ф(z),

Где нормированноеотклонение случайной величины: z = (Т — tKp)/S Kp;

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

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

При достаточнобольшой полученной величине вероятности (более 0,8) можно с высокой степеньюуверенности предполагать своевременность выполнения всего комплекса работ.

Для решениявторой задачи используется формула:

Т =t ож<sub/>(Lkp)+ z *S kp

Таблица 2. Фрагменттаблицы стандартного нормального распределения

z Фz z Фz 0,1 0,0797 1,5 0,8664 0,2 0,1585 1,6 0,8904 0,3 0,2358 1,7 0,9104 0,4 0,3108 1,8 0,9281 0,5 0,3829 1,9 0,9545 0,6 0,4515 2,0 0,9643 0,7 0,5161 2,1 0,9722 0,8 0,5763 2,2 0,9786 0,9 0,6319 2,3 0,9836 1,0 0,6827 2,4 0,9876 1,1 0,7287 2,5 0,9907 1,2 0,7699 2,6 0,9931 1,3 0,8064 2,7 0,9949 1,4 0,8385 2,8 0,9963

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

Вторая глава: Построение сетевой модели

Структурасетевой модели и оценки продолжительности работ (в сутках) заданы в табл. 3.Требуется:

а) получить всехарактеристики СМ;

б) оценитьвероятность выполнения всего комплекса работ за 35 дней, за 30 дней;

в) оценитьмаксимально возможный срок выполнения всего комплекса работ с надежностью 95%(т. е. р = 0,95).

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

tож(i,j)=(3tmin(i,j) + 2t max(i,j)): 5

tож(1,2)=(3*5+2*7,5):5 =6

tож(2,3)=(3*4+2*6,5):5 =5

S2 (i,j)= (t max (i,j) – t min (i,j) 2 :5 2 =

=0.04 ( t max (i,j) – t min (i,j)2

S2 (1,2)= (7,5 — 5) 2 :25 =0,25

S2 (2,3) =(6,5 — 4) 2 :25 =0,25

Работа Продолжительность Ожидаемая Дисперсия

(i,j)

tmin(i,j)

t max(i,j)

Продолжительностьtож(i,j)

S2 (i,j)

(1.2) 5 7.5 5 0.25 (2.3) 4 6.5 5 0.25 (2.4) 3 6 3 1.00 (2.5) 1 5.5 4 0.25 (3.7) 0.5 3.5 1 0.36 (4.5) 5 7.5 6 0.25 (4.6) 3 5.5 4 0.25 (4.9) 5 10 7 1.00 (5.8) 2 4.5 3 0.25 (5.10) 7 12 9 1.00 (6.9) 0.00 (6.11) 3 8 5 1.00 (7.10) 4 9 6 1.00 (8.10) 2 7 4 1.00 (9.10) 1 6 3 1.00 (10.11) 8 10.5 9 0.25

Получим сетевуюмодель аналогичную рассматриваемой во второй главе:

Таким образомход расчета характеристик модели остается аналогичен рассмотренному во второйглаве. Напомним, что критическим является путь: Lкр=(1,2,4,5,10,11),а его продолжительность равна tкр= tож= 33 дня.

Дисперсиякритического пути составляет:

S2Kp= S2(l,2) + S2(2,4) + S2(4,5) + S2(5,10)+ S2(10,M) =

= 0,25 + 1,00 +0,25 + 1,00 + 0,25 = 2,75.

Дляиспользования формулыпоказателядисперсии необходимо иметь среднее квадратическое отклонение, вычисляемое путемизвлечения из значения дисперсии квадратного корня, т. е. SKp =1,66.Тогда имеем:

Р(tкр<35) = 0,5 +0,5 Ф{(35 — 33)1,66} =

=0.5+ 0.5 Ф(1,2)=0,5+0,5*0,77=0,885

Р(tкр<30) = 0,5 +0,5 Ф{(30 — 33)/1,66} = 0,5 — 0,5Ф(1,8) =

= 0,5 — 0,5 •0,95 = 0,035.

Таким образом,вероятность того, что весь комплекс работ будет выполнен не более чем за 35дней, составляет 88,5%, в то время как вероятность его выполнения за 30 дней —всего 3,5% .

Для решениявторой (по существу обратной) задачи прежде всего в табл.2 найдем значениеаргумента z, которое соответствует заданной вероятности 95%. В графе Ф(z) наиболееблизкое значение (0,9545 • 100%) к ней соответствует г = 1,9. В этой связи вформуле (3.61) будем использовать именно это (не совсем точное) значение. Тогдаполучим:

Т = tож(Lкр) + z-SKp= 33 + 1,9*1,66= 36,2 дн.

Следовательно,максимальный срок выполнения всего комплекса работ при заданном уровне вероятностир = 95% составляет 36,2 дня.

Составим словесно-формульное описаниеалгоритма

1. Началопроцесса

2. Вводданных ((i,j),tmin(i,j), t max(i,j), tож(i,j), S2 (i,j);

3. Организацияцикла

4. Вычислениедля каждого значения работы:

tож(i,j)=(3tmin(i,j) + 2t max(i,j)): 5

S2 (i,j)= (t max (i,j) – t min (i,j) 2 :5 2 =

=0.04 ( t max (i,j) – t min (i,j)2

5. Завершениецикла

6. Вычислениедисперсии критического пути