Файл: Учебное пособие Издательство Нижневартовского государственного гуманитарного университета 2008.pdf

112 рования, которая при небольших изменениях плана, когда ограничения линейны, может быть решена методом линейного программирования.
5.4.4.2. Изменение сроков за счёт переброски сил
и средств с некритических работ
Допусти, что для оптимизации критического пути имеющиеся средства перебрасыва- ются с некритических работ на критические.
Пусть известен критический путь Т и, кроме того, имеется определённый запас под- вижных средств B, который распределён между работами a
1,
а
2
,..., а
п
в количествах b
1,
b
2
,..., b
п
.
Обозначим: x
i
– количество подвижных средств перебрасываемых с работы a
i
(x
t
бе- рётся отрицательным, если с работы а
t перебрасываются средства).
Естественно, что сумма средств, снимаемых с каких-то работ, должна быть равна сумме средств, добавляемых другим работам, то есть удовлетворять условию:
1 2
0
n
x
x
x



(5.5)
Величины x
i
должны удовлетворять ограничениям:
i
i
x
b


или
,
i
i
x
b
 
(5.6) где i=1,n
Известно:
1. Если количество средств х
i
снимается с работы a
i
, то время её выполнения возрастает:
'
(
)
;
i
i
i
i
t
f x
t


(5.7)
2. Если количество средств x
i
вкладывается в работы a
i
, то время её выполнения уменьшается:
"
(
)
i
i
i
i
t
x
t



(5.8)
Общий срок выполнения всех работ (новый критический путь) будет определяться как:
'
(
)
( )
min,
i
i
i
i
кр
кр
T
f x
f x





(5.9) где первая
кр

включает в себя все работы, с которых переносятся средства, а вторая
кр

– все работы, в которые вкладываются средства, если они входят в критический путь.
Казалось бы, что перенос средств имеет смысл делать только с некритических работ на критические. Однако в процессе таких переносов может получиться, что некритиче- ские работы будут переходить в критические и наоборот. Поэтому в уравнении (5.9) в общем случае, присутствует первое слагаемое
(
)
i
i
кр
f x

. Следовательно, задача стоит так: найти такие значения переменных x
1
, x
2
, ….x
n
, при которых бы удовлетворялись ог- раничения (5.5) и (5.6), а общий срок выполнения работ T
’
из (5.9) обращался бы в мини- мум. Это также задача нелинейного программирования, т.к. уравнение (5.9) всегда нели- нейно.

113
Задача 2.Известен критический путь T
0
i
кр
T
t
T



(5.10)
Предполагается увеличить время выполнения некоторых критических работ, так, что- бы T= T
0
и получить максимальную экономию средств. Если увеличим время выполне- ния критической работы a
i
на величину τ
i
, то на этой работе высвобождается некоторое количество средств x
i
( ).
i
i
x
f


(5.11)
Требуется выбрать такие значения неотрицательных переменных τ
i
, чтобы общая сум- ма критических времён была меньше директивного срока '
0
(
)
,
i
i
кр
T
t
T





(5.12) а сумма высвободившихся средств была максимальна
(
)
max .
i
i
i
i
кр
x
t






(5.13)
Эта задача так же относится к задачам нелинейного программирования. В случаях, ко- гда увеличение срока работ τ
i
мало, удаётся свести эту задачу к методу линейного про- граммирования.
Общая схема проведения оптимизации:
1. Проводится расчет сети исходя из нормальных длительностей работ.
2. Определяется сумма затрат на выполнение всего проекта при нормальной продол- жительности работ.
3. Рассматривается возможность сокращения продолжительности проекта. Поскольку этого можно достичь за счет уменьшения продолжительности какой-либо критической работы, то только такие операции подвергаются анализу.
3.1. Для сокращения выбирается критическая работа с минимальным коэффициентом нарастания затрат k(i,
j j), у которой есть запас сокращения времени.
3.2. Определяется время Δt(i,
j), на которое необходимо сжать длительность работы
(i,
j). При этом руководствуются следующими соображениями: максимально возможный запас времени для сокращения работы на текущий момент Z(i,
j) ограничивается значе- нием T
у
(i,
j), то есть Z (i,
j) = t т
(i,
j) – T
у
(i,
j) , где t т
(i,
j) – текущее время выполнения работы
(t т
(i,
j) = T
н
(i, j) только для работ еще не подвергшихся сокращению).
3.3. Кроме критического пути длительностью Т
кр в сети есть подкритический путь длительностью Т
п
. Критический путь нельзя сократить больше, чем на ΔT = T
кр
– T
п
, т.к. в этом случае подкритический путь станет критическим (критический путь перестанет быть критическим).
3.4. Исходя из вышесказанного, время сокращения длительности выбранной работы
(i,
j) равно Δt = t
Т
(i,
j) – min [Z(i,
j),ΔT]. Другими словами, если разность между длитель- ностью критического и подкритического пути ΔT меньше текущего запаса времени со- кращения работы Z(i, j), то имеет смысл сокращать работу только на ΔT дней. В против- ном случае можно сокращать работу полностью на величину Z(i, j).
4. В результате сжатия критической операции получают новый календарный план, возможно с новыми критическими и подкритическими путями, и обязательно с новыми более высокими затратами на выполнение проекта. Это происходит вследствие удорожа- ния ускоренной работы. Общая стоимость проекта увеличивается на ΔC = k (i,
j) Δt.
5. Переход на шаг 3, который повторяется до тех пор, пока стоимость проекта умень- шается. По результатам оптимизации строится график «Время – затраты».

114
Пример проведения оптимизации. Требуется определить максимально возможное уменьшение сроков выполнения проекта при минимально возможных дополнительных затратах (табл. 5.7).
Таблица 5.7
Исходные данные
Нормальный режим
Ускоренный режим
Работы
(i, j)
T
Н
(i, j) дни
C
Н
(i, j) руб.
T
У
(i, j) дни
C
У
(i, j) руб.
Коэффициент ускорения k(i, j)
(1,2)
8 100 6
200 50
(1,3)
4 150 2
350 100
(2,4)
2 50 1
90 40
(2,5)
10 100 5
400 60
(3,4)
5 100 1
200 25
(4,5)
3 80 1
100 10
Исходя из нормальных длительностей работ получаем следующие характеристики се- тевой модели:
— общие затраты на проект (рис. 5.16)
0
( , )
( , )
580
пр
Н
i j
C
C
i j




руб.;
— длительность проекта (рис. 5.17)
0
кр
Т =18 дней.
;
— критический путь
0 1, 2, 5
кр
L 
или
0
(1, 2);(2, 5).
кр
L 
;
— подкритический путь
0 1, 2, 4,5
П
L 
или
0
(1, 2); (2, 4);(4,5),
П
L 
Т
П
= 13 дней.
Рис. 5.16. Общие затраты на проект

115
Рис. 5.17. Сетевой график
Для ускорения выбираем работу (1,
2) с k(1,
2) = 50 руб./день. Текущий запас сокраще- ния или предел сокращения работы (1,
2) на данный момент равен Z
0
(1,
2) = 8 – 6 = 2.
Разность между продолжительностью критического и подкритического путей ΔT = 18 –
– 13 = 5 дней. Поэтому согласно п. 3.2. сокращаем работу (1,
2) на Δt = min [2,
5] = 2 дня.
Новое текущее значение t
1
(1,
2) = 8 – 2 = 6 дней, а запас ее дальнейшего сокращения пол- ностью исчерпан, т.е. Z
1
(1,
2) = 0. Новый сетевой график имеет вид (рис. 5.18).
Рис. 5.18. Ускоренный сетевой график (за счет работы 1,2)
Исходя из новой длительности работы (1,
2) получаем:
―
затраты на работу (1,
2) возросли на 100 руб. = 2 дня × 50 руб/день;
—
общие затраты на проект составляют
1 580 100 680
пр
С
руб



руб.;
—
длительность проекта
1 16
кр
Т
дней

дней;
—
критический путь
1
(1, 2);(2, 5).
кр
L 
;

116
—
подкритический путь
1 1
(1, 3); (3, 4); (4, 5),
12
П
П
L
Т
дней


дней.
Работу (1,
2) не имеет смысла рассматривать, т.к. Z
1
(1,
2) = 0. Для рассмотрения оста- ется единственная критическая работа (2,
5) с k(2,
5) = 60 руб./день и пределом сокраще- ния Z
1
(2,
5) = 10 – 5 = 5 дней.ΔT = 16 – 12 = 4 дня, поэтому сокращаем работу (2,
5) на
Δt = min[5,
4] = 4 дня. Новое текущее значение t
2
(2,
5) = 10 – 4 = 6 дней, а запас ее даль- нейшего сокращения Z
2
(2,
5) = 1 день. Новый сетевой график имеет вид (рис. 5.19).
Рис. 5.19. Ускоренный сетевой график (за счет работы 2,5)
Исходя из новой длительности работы (2,
5) получаем:
— затраты на работу (2,
5) возросли на 240 руб.=4 дня × 60 руб/день;
— общие затраты на проект
920 240 680 2



пр
C
руб.;
— длительность проекта
12 2

кр
T
дней;
— два критических пути
(2,5)
(1,2);
2

кр
L
и
(1,3);
2

кр
L
(1,
3); (3,
4);(4,
5);
— подкритический путь
2

П
L
(1,
2); (2,
4); (4,
5),
11 2

П
T
дней.
Появление нескольких критических путей говорит о том, что для дальнейшего сокра- щения длительности проекта необходимо уменьшать длину всех критических путей од- новременно. Из первого критического пути
2
(1, 2); (2, 5)
кр
L 
можно сократить только ра- боту (2,
5) с пределом сокращения Z
2
(2,
5) = 1, а из второго пути – работу (4,
5) с коэффи- циентом ускорения k(4,
5) = 10 руб/день и пределом сокращения Z
2
= (4,5) = 3 – 1 =
= 2 дня. ΔT = 13 – 12 = 1 день, поэтому сокращаем работу (2,5) и работу (4,5) на Δt = min
[1,
2,
1] = 1 день, где первые два элемента при выборе минимума это Z
2
(2,
5) = 1 и Z
2
(4,
5) =
= 2. Новое текущее значение t
3
(2,
5) = 6 – 1 = 5 дней, и запас ее дальнейшего сокращения исчерпан Z
3
(2,
5) = 0, для работы (4,
5) новое текущее значение t
3
(4,5) =3 – 1 = 2 дня и
Z
3
(4,
5) = 1 день. Новый сетевой график имеет вид (рис. 5.20).

117
Рис. 5.20. Ускоренный сетевой график
(за счет длительности критических путей)
Исходя из новой длительности работы (2,
5) и (4,
5) получаем:
— затраты на работу (2,
5) возросли на 60 руб. = 1 день × 60 руб/день;
— затраты на работу (4,
5) возросли на 10 руб. = 1 день × 10 руб/день;
— общие затраты на проект
3 920 60 10 990
пр
С
руб




руб.;
— длительность проекта
3 11
кр
Т
дней

дней;
— два критических пути
3
(1, 2); (2, 5)
кр
L 
и
3
(1, 3);(3, 4); (4, 5).
кр
L 
;
— Подкритический путь
3 3
(1, 2);(2, 4);(4,5),
10
П
П
L
Т
дней


дней.
Поскольку все критические операции пути
3
(1, 2); (2, 5)
кр
L 
сжаты до установленного предела T
у
(i,
j), то дальнейшее сокращение продолжительности проекта невозможно. Ре- зультаты оптимизации представлены на (рис. 5.21).
6
4
2
2
5
5
2
0
6
6
0
0
0
1
4
4
4
5 11
11
0
0
0
3
9
9

118
Рис. 5.21. Результаты оптимизации
Под параметрами работ C
Н
(i,
j) и C
У
(i,
j) понимаются так называемые прямые затраты.
Косвенные затраты типа административно-управленческих во внимание не принимают- ся. Однако их влияние учитывается при выборе окончательного календарного плана про- екта. В отличие от прямых затрат косвенные затраты при уменьшении продолжительно- сти проекта убывают, что показано на графике. Оптимальный календарный план соот- ветствует минимуму общих затрат (точка А).
С
990
920
680
580
min
общих затрат
А
Общие затраты
Косвенные затраты
прямые затраты
11
12
16
18

119
ТЕСТЫ
Выберите один или несколько правильных ответов.
1. Дайте определение сетевого графика:
a) сетевым графикомназывается полное графическое отображение структуры сетевой модели на плоскости; b) сетевым графикомназывается постановка стратегических целей и задач на уровне графического изображения; c) сетевой графикявляется составной частью управления проектом, охватывает про- цессы, необходимые для обеспечения своевременного завершения проекта и включает определение состава работ, последовательности выполнения, оценку длительностей ра- бот, разработку графика проекта и контроль его исполнения; d) сетевым графикомназывается особым образом организованный комплекс работ, направленный на решение определенной задачи или достижение определенной цели, вы- полнение которого ограничено во времени.
2. Критическим путем называется:
a) разность между ранним временем наступления события (j), поздним временем на- ступления события (i) и продолжительностью работы t(i, j); b) самый продолжительный из всех полных путей сетевой модели. Продолжитель- ность критического пути равна сумме продолжительностей всех работ, составляющих этот путь;
c) разность между поздним временем наступления события (j), ранним временем на- ступления события (i) и продолжительности работы t(i, j);
d) путь, совпадающий с самым поздним (максимальным) ранним временем окончания из всех тех работ, для которых данное событие является конечным.
3. Значения параметров модели заносятся в кружки событий в случае применения:
a) табличного метода; b) метода диагональной таблицы; c) метода потенциалов; d) трехсекторного метода.
4. При использовании секторных методов в кружки событий обычно заносятся:
a) номер события; b) раннее свершение события; c) позднее свершение события; d) частный резерв времени; e) не заносится никаких данных.
5. Выберите правильный вариант расчета приведенного сетевого графика.
В нижнем секторе должен быть указан полный резерв события. Расчет произвести 4-х секторным методом:
Исходный сетевой график:
7 1
2 3
4 5
6 7
2 1
3 4
5 6
5 4
9 2
6

120 7
1 2
3 4
5 6
7 2
1 3
4 5
6 5
4 9
2 6
0 0
0 24 24 0
22 4
4 0
0 9
9 6
2 8
18 18 0
14 8
7 1
2 3
4 5
6 7
2 1
3 4
5 6
5 4
9 2
6 0
0 0
25 25 0
23 4
4 0
0 10 7
2 9
19 19 0
14 9
а)
в)
7 1
2 3
4 5
6 7
2 1
3 4
5 6
5 4
9 2
6 0
0 0
24 24 0
22 4
4 0
0 9
9 6
2 8
18 18 9
22 8
б)
10
6. Выберите правильный вариант расчета представленного сетевого графика.
В верхнем секторе должен быть указан номер предшествующего события, через кото- рое ведет максимальный путь к данному событию, в нижнем секторе — номер данного события.
Исходный сетевой график:

121

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

123
8. Оптимизация сетевой модели может проводиться:
a) по стоимости работ; b) по качеству материалов; c) по трудовым ресурсам; d) по информационным ресурсам; e) по параметрам «время—стоимость»; f) по параметрам «цена—качество».
9. Оптимизация сетевой модели может предполагать:
a) приведение параметров сетевого графика к существующим ограничениям; b) повышение качества производимой продукции; c) повышение заработной платы исполнителей; d) перепланирование работ по проекту; e) изменение топологии сетевого графика.
10. Главный вид оптимизации — это оптимизация:
a) по стоимости; b) по ресурсам; c) по времени.
11. Оптимизация сетевого графика по времени производится в случаях:
a) когда проект не укладывается в директивные сроки; b) когда проект заканчивается раньше запланированного времени; c) когда имеются бюджетные ограничения.
12. Методами оптимизации сетевого графика по времени являются:
a) сокращение продолжительности критических работ; b) перенос директивных сроков на более позднее время; c) изменение топологии сетевого графика за счет изменения технологии работ.

124