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

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

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

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

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

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

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

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

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

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

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

Наиболее существенные преимущества имитационных моделей [Вентцель Е.С, 1972]:

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

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

Имитационное моделирование наиболее целесообразно в тех случаях, когда:

§ не существует законченной математической постановки задачи, или еще не разработаны достаточно эффективные методы решения сформулированной задачи;

§ аналитические методы имеются, но математические процедуры при их использовании очень сложны и трудоемки;

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

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

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

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

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

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

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

ü соответствовать поставленной цели и иметь ясный физический смысл;

ü быть универсальным, т.е. способным учитывать все особенности реальных процессов;

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

Будем в дальнейшем обозначать показатель эффективности буквой R.

Рассмотрим ряд примеров, в каждом из которых показатель эффективности R выбран в интересах достижения определенной цели [Вентцель Е.С., 1972].

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

2. Ремонтная мастерская занимается обслуживанием машин; ее рентабельность определяется количеством машин, обслуживаемых в течение дня. Показатель эффективности – среднее число машин, обслуженных за день («среднее» потому, что фактическое число случайно).

3. Проводится борьба за экономию средств при производстве определенного вида товаров. Показатель эффективности – количество (или среднее количество) сэкономленных средств.

Наряду с определением показателей эффективности возникает необходимость определения критерия (правила) принятия решения. При этом большинство задач решаются как однокритериальные, т.е. используется максимум или минимум одного показателя эффективности (будем обозначать такой показатель R^*). Однако зачастую для решения задачи возникает необходимость использования не одного, а нескольких показателей эффективности. Такие задачи относятся к классу многокритериальных задач.

В настоящее время методы решения многокритериальных задач недостаточно разработаны. Поэтому на практике чаще всего данные задачи сводятся к однокритериальным. Основными методами решения данного типа задач являются:

ü метод выбора главного показателя;

ü метод выбора обобщенного показателя;

ü метод лексикографического выбора.

В процессе принятия решений необходимо также учитывать информационные ситуации, в которых принимается то или иное решение. При этом различают три основных типа информационных ситуаций [Вентцель Е.С., 1972]:

1. Принятие решения в условиях определенности.

и условия характеризуются наличием однозначной, детерминированной связи между принятым решением и полученным результатом. В этом случае показатель эффективности и ограничения зависят только от стратегий оперирующей стороны S = {s_i}, i = 1,n и фиксированных детерминированных факторов (вектор Д).

2. Принятие решения в условиях риска.

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

3. Принятие решений в условиях неопределенности.

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

В свою очередь, принятие решений в условиях неопределенности в зависимости от типа неопределенности подразделяют на [Вентцель Е.С., 1972]:

Ø конфликтные, в которых неопределенность создается за счет недостаточного знания поведения активного, «разумного» противника;

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

В этом случае, в зависимости от информационной ситуации, возможно применение нескольких критериев. Так, в условиях определенности целесообразно использовать критерий максимума результата; при известных априорных вероятностях развития событий P(v), v= 1,V целесообразно использовать критерий максимума математического ожидания выигрыша. Когда все возможные варианты развития событий равновероятны, целесообразно использовать критерий недостаточного основания Бернулли-Лапласа. При отсутствии какой-либо объективной информации о случайных факторах или когда известно лишь множество их возможных значений, целесообразно использовать критерии Вальда, Гурвица, Сэвиджа или же применять теорию антагонистических матричных игр двух лиц с нулевой суммой. В случае же, когда варианты развития событий характеризуются нечетким множеством, то, в зависимости от ситуации, можно применять все перечисленные выше критерии с учетом принадлежности вариантов действий нечеткому множеству.

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

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

Таблица 10

Критерии принятия решения при различных информационных ситуациях

№ п/п	Информационная ситуация	Критерии принятия решений
Наименование критерия	Математическое выражение
1.	Определенность	Максимум результата	R* = max R s S
2.	Известны априорные вероятности развития событий P(v), v= 1,V	Максимум математического ожидания выигрыша	V R* = max ∑ R P(v) s S v=1
3.	Все возможные варианты развития событий равновероятны	Критерий недостаточного основания Бернулли-Лапласса	V R* = max 1/V ∑ R s S v=1
4.	Нельзя что-либо сказать о возможных вариантах развития событий	Критерий крайнего пессимизма	R* = max min R s S v V
Критерий крайнего оптимизма	R* = max max R s S v V
Критерий пессимизма-оптимизма (Гурвица)	R*=α min R+(1-α) max R v V v V (0 ≤ α ≤ 1)
Критерий минимаксного риска (Сэвиджа)	R* = max min (max R–R) s S v V s S

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

Рассмотрим простое дерево решений (рис. 133).

Необходимо принять решение, описываемое лотереями А и В, которые зависят от различных случайных событий. В лотерее А имеется вероятность p получить выгоду u₁ и вероятность 1 - p потерпеть убытки u₂. Соответственно в лотерее В имеется вероятность q получить выгоду v₁ и вероятность 1 - q потерпеть убытки v₂. Используя правила теории ожидаемой полезности, выбирают эту лотерею тогда и только тогда, когда [Борисов А.Н. и др., 1990]:

pu₁ + (1 - p)u₂ > qv₁ + (1 - q)v₂.

Пусть μ_А(а), μ_B(b) – степени принадлежности a, b множествам ожидаемых полезностей лотерей A и B, тогда согласно принципу обобщения [Борисов А.Н. и др., 1990]:

μ_А(а) = max (min(μ_p(p), μ_А1(u₁), μ_А2(u₂))), (1)

pu₁ + (1 - p)u₂

μ_А(а) = max (min(μ_Q(q), μ_B1(v₁), μ_B2(v₂))), (2)

qv₁ + (1 -q)v₂

где μ_p(p) – степень принадлежности p множеству возможных значений для этой вероятности.

Чтобы оценить степень предпочтительности А относительно В, используют следующий метод [Борисов А.Н. и др., 1990]:

μ(X→Y) = μ(-X U Y) = max (1 - μ(X), μ(Y)), (3)

где X и Y есть степени истинности высказывания «или не X, или Y».

В более общей постановке, если X и Y есть нечеткие отношения между двумя переменными a и b, представленные функциями принадлежности μ_X(а,b), μ_Y(а,b), то

μ(X→Y) = min (1 – μ_X(a,b), μ_Y(a,b)), (4)

a,b

Пусть Y – утверждение о предпочтении:

Y₁: «А строго предпочтительнее В»,

1, если a > b;

μ_Y1(a,b) =

0, если а ≤ b;

Y₂: «А в некоторой степени предпочтительнее В»,

1, если a ≥ (b + 0,2);

μ_Y2(a,b) = 0,5 + 2,5 (a – b), если (b + 0,2) ≥ a ≥ (b – 0,2);

0, если а ≤ (b – 0,2),

где μ_X(a,b) – степень, с которой а принадлежит множеству ожидаемых полезностей для лотереи А и b – множеству для лотереи В. Из этого следует, что

μ_X(а,b) = min(μ_A(a), μ_B(b₁)).

При таких предпочтениях можно использовать (4) для вычисления степени предпочтения:

μ(X→Y) = min [max (1 – μ_X(a,b), μ_Y(a,b))] =

a,b

= min [max (1 – min (μ_A(a), μ_B(b)), μ_Y1(a,b))].

a,b

Для а > b μ_Y1(a,b) = 1. Если существует пара (а,b), для которой аргумент min

a,b

меньше единицы, то а ≤ b. Таким образом,

μ(X→Y) = min [max (1 – (μ_А(a), μ_В)) =

a≤b

= 1 - max (min (μ_A(a), μ_B(b))).

a,b

Можно показать, что максимум имеет место в граничной точке при а = b. Следовательно,

μ(X→Y) = 1 - max (min (μ_A(a), μ_B(a))).

Общая схема многокритериальной модели выработки решения представлена на рис. 134.

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

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

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

Сетевой график состоит из двух типов основных элементов: работ и событий [Абчук В.А. и др., 1972].

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

На сетевом графике работа изображается стрелкой, над которой проставляется ее продолжительность или затрачиваемые ресурсы или то и другое одновременно (рис. 135 – [Абчук В.А. и др., 1972]). Работа, отражающая только зависимость одного мероприятия от другого, называется фиктивной работой. Такая работа имеет нулевую продолжительность (или нулевой расход ресурсов) и обозначается пунктирной стрелкой.

Начальная и конечная точки работы, т.е. начало и окончание некоторого мероприятия (например, окончание погрузки), называются событиями.

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

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

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

Из определения отношения «предшествующий – последующий» вытекают свойства сетевого графика.

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

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

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

Для нумерации событий применяется следующий способ [Абчук В.А. и др., 1972]. Вычеркиваются все работы, выходящие из события № 0, и просматриваются все события, в которых оканчиваются эти вычеркнутые работы. Среди просмотренных находятся события, которые не имеют входящих в них работ (за исключением уже вычеркнутых). Они называются событиями первого ранга и обозначаются числами натурального ряда, начиная с единицы (на рис. 135 это событие № 1). Затем вычеркиваются все работы, выходящие из событий первого ранга, и среди них находятся события, не имеющие входящих работ (кроме вычеркнутых). Это – события второго ранга, которые нумеруются следующими числами натурального ряда (например, 2 и 3 на рис. 135). Проделав таким способом k-1 шаг, определяют события (k-1)-го ранга. Затем, вычеркивая все работы, выходящие из событий (k-1)-го ранга, и просматривая события, в которых эти работы заканчиваются, выбирают события, не имеющие ни одной входящей в них работы (кроме вычеркнутых). Это события k-го ранга, и нумеруются они последовательными числами натурального ряда, начиная с наименьшего, еще не использованного числа при предыдущей нумерации на (k-1)-м шаге.

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

Работа обычно кодируется номерами событий, между которыми они заключены, т.е. парой (i, j), где i – номер предшествующего события, j – номер последующего события.

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

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

Последовательные работы и события формируют цепочки (пути), которые ведут от исходного к завершающему событию сетевого графика. Например, путь 0-1-2-3-4-5-6-7 сетевого графика, показанного на рис. 135, включает в себя события 0, 1, 2, 3, 4, 5, 6, 7 и работы (0-1), (1-2), (2-5), (5-6), (6-7).

На основании изложенного можно сказать, что ранг события – это максимальное число отдельных работ, входящих в какой-либо из путей, ведущих из нулевого (исходного) события в данное. Так, события первого ранга не имеют путей, состоящих более чем из одной работы, ведущих в них из 0 (например, событие 1 на рис. 135). События второго ранга связаны с 0 путями, которые состоят не более чем из двух работ, причем для каждого события второго ранга хоть один такой путь обязательно существует. Например, на рис. 135 событие 4 – событие третьего ранга, так как пути, ведущие в это событие из 0, включают только три работы – (0-1), (1-3) и (3-4) или (0-1), (1-2) и (2-4).

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

Графом называется множество точек, соединенных линиями. Точки, называемые вершинами графа, обозначают объекты или события, а линии, называемые дугами или ребрами графа, - отношения между ними.

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

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

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

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

Продолжительность работы представляет собой (в терминах теории графа) длину дуги. Следовательно, длина пути Т – это сумма длин всех дуг, образующих данный путь, т.е. [Абчук В.А. и др., 1972]

Т = Σ t_i,j ,

t_i,j Т

где символом t_i,j обозначается дуга, которая соединяет вершины i и j и направлена от вершины i к вершине j.

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

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

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

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

Параметрами сетевой модели являются [Абчук В.А. и др., 1972]:

§ наиболее раннее возможное время наступления j-го события – T_p(j);

§ самое позднее допустимое время наступления i-го события – T_п(i);

§ резерв времени данного события - R_i;

§ полный резерв времени работы (i, j) - r_п(i, j);

§ свободный резерв времени работы (i, j) – r_с(i, j).

Наиболее раннее возможное время наступления j-го события определяется формулой [Абчук В.А. и др., 1972]:

T_p(j) = max {T_p(i) + t_ij}, (1)

i S^-1_j

где t_ij – продолжительность (i, j)-й работы;

S^-1_j множество событий, предшествующих j-му событию.

Вычисления по формуле (1) выполняются шаг за шагом, двигаясь в порядке нумерации событий. Например, для сетевого графика, приведенного на рис. 135, применяя формулу (1), получим [Абчук В.А. и др., 1972]:

T_p(0) = 0;

T_p(1) = T_p(0) + 4 = 4;

T_p(2) = T_p(1) + 8 = 12;

T_p(3) = T_p(1) + 4 = 8;

T_p(4) = max [(T_p(2) + 12), (T_p(3) + 24)] = 32;

T_p(5) = max [(T_p(2) + 4), (T_p(4) + 4)] = 36;

T_p(6) = max [(T_p(4) + 4), (T_p(5) + 8)] = 44;

T_p(7) = T_p(6) + 4 = 48.

Самое позднее допустимое время наступления события i определяют с помощью аналогичной формулы, но обращаясь не к предшествующим, а к последующим событиям, т.е. [Абчук В.А. и др., 1972]

T_п(i) = max {T_п(j) - t_ij}, (2)

j S_i

где S_i – множество событий, следующих за i-м событием.

Для определения T_п(i) по формуле (2) надо двигаться от конечного события n к исходному событию 0, при этом T_п(n) = T_p(n). Для примера обратимся к сетевому графику, показанному на рис. 135.

T_п(7) = 48;

T_п(6) = T_п(7) - 4 = 44;

T_п(5) = T_п(6) - 8 = 36;

T_п(4) = min [(T_п(6) - 4), (T_п(5) - 4)] = 32;

T_п(3) = T_п(4) - 24 = 8;

T_п(2) = min [(T_п(4) - 12), (T_п(5) - 4)] = 20;

T_п(1) = min [(T_п(3) - 4), (T_п(2) - 8)] = 4;

T_п(0) = T_п(1) - 4 = 0.

Резервом времени данного события называется разность между T_п(i) и T_р(i), которая вычисляется по формуле [Абчук В.А. и др., 1972]

R_i = T_п(i) - T_р(i) (3)

В нашем примере R₀ = 0; R₁ = 0; R₂ = 8; R₃ = 0; R₄ = 0; R₅ = 0; R₆ = 0; R₇ = 0.

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

Полный резерв времени работы (i, j) вычисляется по формуле [Абчук В.А. и др., 1972]

r_п(i, j) = T_п(j) - T_р(i) - t_ij . (4)

Свободный резерв времени работы (i, j) вычисляется по формуле [Абчук В.А. и др., 1972]

r_с(i, j) = T_p(j) - T_п(i) - t_ij . (5)

В примере полные резервы времени соответственно равны:

r_п(0,1) = 4 – 0 - 4 = 0; r_п(2,4) = 32 – 12 - 12 = 8;

r_п(1,2) = 20 – 4 - 8 = 8; r_п(4,5) = 36 – 32 - 4 = 0;

r_п(2,5) = 36 – 12 - 4 = 20; r_п(1,3) = 8 – 4 - 4 = 0;

r_п(5,6) = 44 – 36 - 8 = 0; r_п(3,4) = 32 – 8 - 24 = 0;

r_п(6,7) = 48 – 44 - 4 = 0; r_п(4,6) = 44 – 32 - 4 = 8.

Свободные резервы этих же работ равны:

r_с(0,1) = 4 – 0 - 4 = 0; r_c(2,4) = 32 – 20 - 12 = 0;

r_c(1,2) = 12 – 4 - 8 = 0; r_c(4,5) = 36 – 32 - 4 = 0;

r_c(2,5) = 36 – 20 - 4 = 12; r_c(1,3) = 8 – 4 - 4 = 0;

r_c(5,6) = 44 – 36 - 8 = 0; r_c(3,4) = 32 – 8 - 24 = 0;

r_c(6,7) = 48 – 44 - 4 = 0; r_c(4,6) = 44 – 32 - 4 = 8.

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

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

Задержка в выполнении работы (i, j) на величину ∆t_ij > r_п(i, j) приводит к задержке в наступлении завершающего события на величину ∆t_ij - r_п(i, j).

Задержка в выполнении работы на величину ∆t_ij ≤ r_п(i, j) вообще не повлияет ни на один срок, определенный данным сетевым графиком. Следовательно, у критических работ и полные, и свободные резервы времени равны нулю. Вообще говоря, равенство нулю полного резервного времени работы является необходимым и достаточным признаком того, что данная работа критическая. Напротив, свободный резерв времени может быть равным нулю и у некритических работ.

Таким образом, критический путь находится посредством определения работ, полные резервы времени которых равны нулю. В приведенном примере критическим путем является 0-1-3-4-5-6-7.

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

T_кр = t_0,1 + t_1,3 + t_3,4 + t_4,5 + t_5,6 + t_6,7 = 48.

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

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

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

Для определения временных и других характеристик, необходимых для оценки длительности работ или расхода ресурсов, могут использоваться статистические данные, полученные опытным путем. Если такие данные отсутствуют, то исполнителями сетевого графика даются три оценки времени: оптимистическая (t_min), пессимистическая (t_max) и наиболее вероятная (t_нв).

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

Пессимистическая оценка – продолжительность работы при самом неблагоприятном стечении обстоятельств.

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

На основании этих оценок вычисляются оценки t_ij и их дисперсии σ²_ij по следующим эмпирическим формулам [Зайденман И.А., Маргулис Д.Д., 1967]:

t_ij = (t_min + 4t_нв + t_max)/6 (6)

σ²_ij = [(t_max – t_min)/6]² (7)