В предыдущих разделах не учитывались вероятностные соображения, а предполагалось, что продолжительность работы точно известна. На практике сроки выполнения операций обычно являются довольно неопределенными. Часто можно лишь выдвинуть некоторые предположения о том, сколько времени потребуется для выполнения каждой работы. Нельзя предусмотреть возможные трудности или задержки выполнения. Неопределенность сроков выполнения операций означает, что общая продолжительность проекта также подвержена неопределенности. Выбор метода, позволяющего учесть эту неопределенность, зависит от типа проекта и природы неопределенности. Алгоритм, получивший наиболее широкое применение, называется методом оценки и пересмотра проектов (Project Evaluation and Review Technique – PERT).
Для каждой работы проекта принимаются три оценки продолжительности выполнения:
1) наиболее вероятное время выполнения m,
2) оптимистическая оценка времени а,
3) пессимистическая оценка времени в.
Наиболее вероятная (нормальная) оценка, характеризует усредненные условия выполнения операции и определяется как время выполнения работы при нормальных условиях.
Оптимистическая (минимальная) оценка, соответствует наиболее благоприятным условиям выполнения операции, когда все идет по плану.
Пессимистическая (максимальная) оценка, соответствует самым неблагоприятным условиям выполнения операции (нехватка рабочей силы, перебои в снабжении, механические поломки).
Оптимистическая и пессимистическая оценки задают размах колебаний продолжительности работы под влиянием неопределенности. Поскольку обе эти оценки являются лишь приемлемыми предположениями, фактическая продолжительность работы может лежать за пределами этого интервала, но вероятность такого события очень мала. В методе PERT принимается бета-распределение продолжительности работ с модой в точке m и концами в точках a и b.
Ожидаемая продолжительность (м.о.) работы приближенно определяется как
. (1)
Поскольку фактическая продолжительность может отличаться от среднего значения (м.о.), необходимо знать дисперсию продолжительности работы. У большинства распределений крайние значения отстоят на три среднеквадратических отклонения от среднего значения. Таким образом, размах распределения равен шести среднеквадратическим отклонениям, т.е. s = .
Дисперсия продолжительности работы равна . (2)
В методе PERT с помощью оценок продолжительности a, b, m по формулам (1) и (2) вычисляется средняя продолжительность (м.о.) и ее дисперсия для каждой работы. Однако продолжительности работ являются случайными величинами. Следовательно, продолжительность проекта Т также является случайной величиной, и можно говорить о средней продолжительности проекта и ее дисперсии. В предположении, что сроки выполнения операций не зависят друг от друга, распределение времени выполнения проекта в целом является нормальным, среднее значение нормального распределения определяется как сумма математических ожиданий продолжительности критических операций, а дисперсия – как сумма их дисперсий.
Полученное нормальное распределение можно использовать для оценки вероятности завершения проекта к заранее установленной дате.
Пример. Рассмотрим проект, состоящий из девяти работ с отношениями предшествования и оценками продолжительности, показанными в таблице 1.
Таблица 1
|
Работа |
Предшествующие работы |
Оценка продолжительности оптимистическая наиболее вероятная пессимистическая а m в |
||
|
A |
- |
2 |
5 |
8 |
|
B |
A |
6 |
9 |
12 |
|
C |
A |
6 |
7 |
8 |
|
D |
B,C |
1 |
4 |
7 |
|
E |
A |
8 |
8 |
8 |
|
F |
D,E |
5 |
14 |
17 |
|
G |
C |
3 |
12 |
21 |
|
H |
F,G |
3 |
6 |
9 |
|
I |
H |
5 |
8 |
11 |
Вначале вычислим среднюю продолжительность и дисперсию для каждой работы. Полученные данные приведены в таблице 2.
Таблица 2
|
Работа |
Ожидаемая Продолжительность m |
Среднеквадратическое отклонение s |
Дисперсия
|
|
A* |
5 |
1 |
1 |
|
B* |
9 |
1 |
1 |
|
C |
7 |
1/3 |
1/9 |
|
D* |
4 |
1 |
1 |
|
E |
8 |
0 |
0 |
|
F* |
13 |
2 |
4 |
|
G |
12 |
3 |
9 |
|
H* |
6 |
1 |
1 |
|
I* |
8 |
1 |
1 |
Рис. 1.
На рис. 1 показана сетевая модель проекта с обозначениями работ в виде дуг, где числа под дугами показывают среднюю продолжительность работ.
С помощью средних продолжительностей работ вычисляются наиболее ранний возможный и наиболее поздний допустимый сроки наступления каждого события и делается расчет сети.
|
Activity Name |
On Critical Path |
Activity Mean Time |
Earliest Start |
Earliest Finish |
Latest Start |
Latest Finish |
TF |
s |
s^2 |
|
A |
Yes |
5 |
0 |
5 |
0 |
5 |
0 |
1 |
1 |
|
B |
Yes |
9 |
5 |
14 |
5 |
14 |
0 |
1 |
1 |
|
C |
no |
7 |
5 |
12 |
7 |
14 |
2 |
1/3 |
1/9 |
|
D |
Yes |
4 |
14 |
18 |
14 |
18 |
0 |
1 |
1 |
|
E |
no |
8 |
5 |
13 |
10 |
18 |
5 |
0 |
0 |
|
F |
Yes |
13 |
18 |
31 |
18 |
31 |
0 |
2 |
4 |
|
G |
no |
12 |
12 |
24 |
19 |
31 |
7 |
3 |
9 |
|
H |
Yes |
6 |
31 |
37 |
31 |
37 |
0 |
1 |
1 |
|
I |
Yes |
8 |
37 |
45 |
37 |
45 |
0 |
1 |
1 |
Completion Time = 45 days
Критический путь определяется как (A, B, D, F, H, I). Обозначим через Т продолжительность проекта. Тогда ожидаемая продолжительность проекта равна сумме ожидаемых продолжительностей работ A, B, D, F, H, I:
E(T) = 5 + 9 + 4 + 13 + 6 + 8 = 45 (дней)
Дисперсия продолжительности проекта равна сумме дисперсий продолжительности работ A, B, D, F, H, I:
D(T) = 1 + 1 + 1 + 4 + 1 + 1 = 9.
Среднеквадратическое отклонение продолжительности проекта равно s(T) = 3.
Вероятность завершения проекта
Продолжительность проекта Т равна сумме продолжительностей всех работ, находящихся на критическом пути. В системе ПЕРТ предполагается, что продолжительности всех работ независимы и распределены по одному закону. Следовательно, в силу центральной предельной теоремы, случайная величина Т имеет нормальное распределение с математическим ожиданием Е(Т) и дисперсией D(T).
В нашем примере продолжительность Т имеет нормальное распределение с м.о. Е(Т) = 45 и s(T) = 3. В случае нормального распределения вероятность того, что значение случайной величины отличается от м.о. не более чем на одно среднеквадратическое отклонение, равна 0,68. Следовательно, с вероятностью 0,68 продолжительность проекта составит от 42 до 48 дней. Аналогично с вероятностью 0,997 продолжительность проекта Т будет отличаться от среднего значения не более чем на три s (от 36 до 54 дней).
Можно также вычислить вероятность завершения проекта к определенному сроку. Например, руководителю нужно знать вероятность осуществления проекта за 50 дней, т.е. требуется вычислить Р (Т £ 50). Эту вероятность можно найти с помощью таблицы для нормированного нормального распределения с нулевым м.о. и s = 1. Согласно теории вероятностей случайная величина имеет нормальное распределение с нулевым м.о. и s = 1. Следовательно,
.
Таким образом, вероятность того, что проект будет закончен за 50 дней, составляет 0,9522. Допустим, что необходимо знать вероятность завершения проекта на 4 дня раньше, чем ожидается. Это означает, что требуется вычислить
.
Следовательно, вероятность того, что проект будет закончен через 41 день, составляет всего 0,0912.
Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 5 млн. руб. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами суммарных затрат (C) и доходов (R), связанных с реализацией каждого из проектов. Соответствующие данные приведены в таблице, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказаться от расширения какого-либо предприятия.
Таблица 1
|
Проект |
Предприятие 1 |
Предприятие 2 |
Предприятие 3 |
|||
|
|
|
|
|
|
|
|
|
1 2 3 4 |
0 1 2 - |
0 5 6 - |
0 2 3 4 |
0 8 9 12 |
0 1 - - |
0 3 - - |
Цель фирмы состоит в получении максимального дохода от инвестиций при условии, что на каждом из предприятий реализуется не более одного проекта.
СЕТЕВАЯ МОДЕЛЬ
Вычисления на сетях характерны для динамического программирования. Для построения сети следует определить этапы решения задачи. В рассмотренном примере каждому из предприятий ставится в соответствие некоторый этап, поскольку требуется выбрать оптимальный проект для каждого предприятия. Известно, что этапы связаны между собой посредством ограничения на суммарный объем капиталовложений. При построении модели необходимо учесть эту связь таким образом, чтобы получить возможность по отдельности решать подзадачи, соответствующие каждому этапу, не нарушая при этом условия допустимости.
Введем следующие обозначения:
X1 – объем капиталовложений, распределенных на этапе 1.
X2 – объем капиталовложений, распределенных на этапах 1 и 2.
X3 – объем капиталовложений, распределенных на этапах 1,2,3.
Заметим, что конкретные значения X1 и X2 заранее не известны, однако эти значения лежат в интервале между 0 и 5. Так как затраты на реализацию каждого из проектов выражаются целыми числами, значения X1 и X2 могут быть равны 0,1,2,3,4,5. С другой стороны, значение переменной X3 равно 5.
Рис. 1 служит иллюстрацией сетевой модели для рассматриваемой задачи. Каждому возможному значению X1, X2 и X3 поставлен в соответствие узел, ассоциированный с одним из этапов j = 1, j=2, j=3.
Начальный этап j=0 введен в рассмотрение для удобства вычислений. Длины дуг, соединяющих узлы на некотором этапе с узлами на последующем этапе, равны доходам от реализации наилучшего допустимого проекта. Рассмотрим дуги, соединяющие узел 0 на этапе j=0 с узлами X1 = (0,1,2,3,4,5) на этапе j=1. Дуга (0,0) соответствует случаю, когда средства на этапе 1 не выделяются. Допустимым здесь является проект 1 с и дуге (0,0) приписывается длина .
Рис. 1.
С другой стороны, для дуги (0,1) допустимыми оказываются проекты 1 и 2, что предопределяет выбор проекта 2 с более высоким уровнем дохода , а дуге (0,1) приписывается длина 5. По тем же самым причинам дуге (0,2) приписывается длина 6, поскольку здесь все три проекта являются допустимыми, а проекту 3 соответствует самый высокий уровень дохода . Значения X1= 3, 4 и 5 соответствуют «избыточным» вариантам, для которых в лучшем случае .
Дуги, соединяющие узлы на этапе 1 с узлами на этапе 2 задаются узлами X1 и X2. Величина X2 – X1 равна объему капиталовложений, распределенных только на этапе 2. Таким образом, дуга (X1, X2) является допустимой лишь для проектов, затраты на реализацию которых не превышают X2 – X1. Длина этой дуги равна наибольшему значению для таких проектов. Пусть, например, X1 =1 и X2 = 5. Объем распределенных на этапе 2 капиталовложений равен X2 – X1= 4 и все 4 проекта оказываются допустимыми. Так как проекту 4 соответствует самый высокий уровень дохода ( = 12), дуге (1,5) приписывается длина 12. С другой стороны, для дуги (1,3)
X2 – X1 = 2, откуда вытекает допустимость только проектов 1 и 2. Следовательно, длина дуги (1,3) равна 8. Заметим, наконец, что в случае X1 X2 соответствующая дуга не существует.
Исследуем свойства сетевой модели. Каждая дуга единственным образом связана с некоторым проектом. Наша цель состоит в отыскании связной последовательности дуг, соединяющей узел 0 на этапе j=0 с узлом 5 на этапе j=3 и обладающей максимальной длиной (соответствующей максимальному доходу). Из определения величин X1, X2 и X3 следует, что любой связный путь из узла 0 на этапе j=0 в узел 5 на этапе j=3 соответствует допустимой комбинации проектов.
После того, как сеть построена, найдем самый длинный путь от узла 0 на этапе j=0 в узел 5 на этапе j=3 . Опишем метод поиска. Обозначим через величину самого длинного пути, ведущего в узел на этапе j. Поскольку j=0 – исходный этап, . Далее вычисления проводятся поэтапно.
ЭТАП 1. Так как узел 0 на этапе j=0 с каждым из шести узлов X1 = {0,1,2,3,4,5} на этапе j=1 соединяет единственная дуга, самый длинный путь до узла X1, определяется формулой = + (0, X1), где (0, X1)- длина (доход) дуги (0, X1). В результате имеем
= 0 + 0 = 0
= 0 + 5 = 5
= 0 + 6 = 6
= 0 + 6 = 6
= 0 + 6 = 6
= 0 + 6 = 6.
Полученные результаты представлены на рис. 2(а).
На каждой дуге число представляет собой номер проекта, ассоциированного с этой дугой. Числа, набранные жирным шрифтом, указывают значение расстояния на самом длинном пути до соответствующего узла.
ЭТАП 2. На данном этапе вычисляются величины самых длинных путей до всех узлов X2 = {0,1,2,3,4,5}. В результате имеем
Рис. 2 (а).
= 0 + 0 = 0; = max{0+0; 5+0}= 5;
= max{0+8; 5+0; 6+0}= 8;
= max{0+9; 5+8; 6+0; 6+0}= 13;
= max{0+12; 5+9; 6+8; 6+0; 6+0}= 14;
= max{0+12; 5+12; 6+9; 6+8; 6+0; 6+0}= 17;
Полученные результаты представлены на рис. 2(б), на котором показаны дуги, соответствующие вычисленным значениям .
Рис. 2(б).
ЭТАП 3.
|
= |
max по допустимым дугам ( , ) |
|
= max{0+3; 5+3; 8+3; 13+3; 14+3; 17+0}= 17
На рис.2(в) изображены оптимальные дуги, соответствующие вычисленному значению .
Рис. 2(в).
Из рис. 3 можно заметить, что любой связный путь от узла 0 этапе j=0 до узла 5 на этапе j=3 определяет оптимальное решение исходной задачи. Всего имеется три различных решения. Всем трем решениям соответствует доход 17 млн. руб.
|
Оптимальный путь |
Оптимальный набор проектов |
|
(0,1)(1,4)(4,5) (0,1)(1,5)(5,5) (0,2)(2,4)(4,5) |
(2,3,2) (2,4,1) (3,2,2) |
Рис. 3
Задача распределения капиталовложений – как задача линейного программирования с булевыми переменными
Пусть
Xij = 1, если на i-м предприятии ден. средства вкладываются в j-й проект
Xij = 0, если на i-м предприятии ден. средства не вкладываются в j-й проект
|
|
|
Переменные |
|
|
|
|
||
|
X11 |
X12 |
X13 |
X21 |
X22 |
X23 |
X24 |
X31 |
X32 |
F(X) = 0*X11 + 5*X12 + 6*X13 + 0*X21 + 8*X22 + 9*X23 + 12*X24 + 0*X31 + 3*X32 ® max
X11 + X12 + X13 <= 1 на каждом предприятии
X21 + X22 + X23 + X24 <= 1 реализуется не более одного
X31 + X32 <= 1 проекта 0*X11 + 1*X12 + 2*X13 + 0*X21 + 2*X22 + 3*X23 + 4*X24 + 0*X31 + 1*X32 <= 5
Xij Î {0,1}