Оптимизация сетевого графика по времени
Лабораторная работа
Оптимизация сетевого графика по времени
Цель Научиться решать задачу сетевого планирования с одновременной
оптимизацией средствами EXCEL.
Постановка задачи 1.
Проект представлен сетевым графиком.
Для каждой работы известна ее продолжительность tij и минимально
возможное время выполнения dij. Пусть задан срок выполнения проекта t0, а расчетное tкр > t0. Продолжительность
выполнения работы (i, j) линейно зависит от суммы дополнительно вложенных
средств хij и выражается соотношением: t’ij =
tij - kijxij. Технологические коэффициенты kij известны.
Требуется найти такие t н ij, toij, xij, чтобы:
·
срок выполнения всего комплекса работ не превышал заданной
величины t0;
·
суммарное количество дополнительно вложенных средств было
минимальным;
·
продолжительность выполнения каждой работы t’ij
была не меньше заданной величины dij.
Номер задачи
|
Параметры
|
Работы
|
Срок выполнения проекта t0
|
|
|
1,2
|
1,3
|
1,4
|
2,4
|
2,5
|
3,4
|
3,6
|
4,5
|
4,6
|
5,6
|
|
|
tij
|
7
|
11
|
16
|
6
|
10
|
8
|
13
|
12
|
14
|
9
|
|
*
|
dij
|
4
|
8
|
13
|
5
|
7
|
6
|
10
|
10
|
11
|
7
|
34
|
|
kij
|
0,1
|
0,3
|
0,2
|
0,05
|
0,25
|
0,2
|
0,12
|
0,5
|
0,08
|
0,02
|
|
|
tij
|
9
|
12
|
18
|
8
|
12
|
5
|
12
|
10
|
13
|
12
|
|
1
|
dij71015610387121035
|
|
|
|
|
|
|
|
|
|
|
|
|
kij
|
0,05
|
0,2
|
0,25
|
0,08
|
0,15
|
0,1
|
0,06
|
0,05
|
0,1
|
0,5
|
|
|
tij
|
10
|
13
|
24
|
9
|
11
|
17
|
10
|
15
|
15
|
20
|
|
2
|
dij
|
5
|
9
|
11
|
6
|
9
|
12
|
7
|
13
|
13
|
15
|
56
|
|
kij
|
0,08
|
0,25
|
0,1
|
0,15
|
0,3
|
0,2
|
0,08
|
0,4
|
0,2
|
0,1
|
|
|
tij
|
6
|
13
|
20
|
9
|
14
|
16
|
15
|
10
|
17
|
13
|
|
3
|
dij
|
5
|
10
|
16
|
7
|
11
|
13
|
12
|
7
|
15
|
9
|
40
|
|
kij
|
0,05
|
0,25
|
0,3
|
0,07
|
0,15
|
0,1
|
0,05
|
0,03
|
0,14
|
0,5
|
|
|
tij
|
19
|
10
|
35
|
18
|
20
|
9
|
22
|
17
|
20
|
18
|
|
4
|
dij
|
16
|
5
|
25
|
13
|
15
|
6
|
17
|
13
|
16
|
14
|
60
|
|
kij
|
0,25
|
0,07
|
0,1
|
0,2
|
0,13
|
0,15
|
0,06
|
0,4
|
0,2
|
0,1
|
|
|
tij
|
6
|
15
|
26
|
7
|
11
|
10
|
11
|
12
|
13
|
17
|
|
5
|
dij
|
5
|
13
|
20
|
5
|
9
|
7
|
8
|
9
|
12
|
15
|
50
|
|
kij
|
0,07
|
0,2
|
0,3
|
0,1
|
0,05
|
0,1
|
0,04
|
0,05
|
0,15
|
0,5
|
|
|
tij
|
10
|
18
|
16
|
12
|
7
|
13
|
11
|
10
|
13
|
12
|
|
6
|
dij71412105987121042
|
|
|
|
|
|
|
|
|
|
|
|
|
kij
|
0,5
|
0,1
|
0,25
|
0,4
|
0,2
|
0,15
|
0,3
|
0,5
|
0,1
|
0,5
|
|
|
tij
|
9
|
18
|
21
|
7
|
12
|
19
|
20
|
9
|
15
|
20
|
|
7
|
dij
|
6
|
14
|
18
|
4
|
9
|
15
|
16
|
6
|
13
|
15
|
33
|
|
kij
|
0,2
|
0,25
|
0,15
|
0,4
|
0,3
|
0,12
|
0,2
|
0,2
|
0,2
|
0,1
|
|
|
tij
|
15
|
8
|
7
|
5
|
13
|
11
|
7
|
15
|
17
|
13
|
|
8
|
dij
|
12
|
5
|
4
|
3
|
10
|
8
|
4
|
12
|
15
|
9
|
47
|
|
kij
|
0,25
|
0,2
|
0,15
|
0,1
|
0,3
|
0,4
|
0,25
|
0,14
|
0,5
|
|
|
tij
|
13
|
22
|
19
|
17
|
10
|
25
|
12
|
13
|
20
|
18
|
|
9
|
dij
|
10
|
18
|
15
|
14
|
7
|
21
|
9
|
10
|
16
|
14
|
49
|
|
kij
|
0,3
|
0,1
|
0,05
|
0,2
|
0,4
|
0,2
|
0,25
|
0,3
|
0,2
|
0,1
|
|
|
tij
|
16
|
12
|
10
|
8
|
3
|
9
|
11
|
16
|
13
|
17
|
|
10
|
dij
|
10
|
7
|
6
|
5
|
2
|
7
|
9
|
10
|
12
|
15
|
29
|
|
kij
|
0,2
|
0,1
|
0,16
|
0,3
|
0,25
|
0,1
|
0,4
|
0,2
|
0,15
|
0,5
|
|
1 Запишем все данные на
сетевой график и рассчитаем сроки свершения событий.
Расчеты показали, что срок
выполнения проекта tкр = 40, т.е. превышает директивный срок t0
= 34.
2. Составление
математической модели задачи.
Целевая функция имеет вид
f= х12 + х13 + х14 + х34
+ х35 + х45 + х14 + х34 + х35 +
х45 (min).
Запишем ограничения задачи:
а) срок выполнения проекта не должен
превышать t0 = 34:
tо36 £ 34; tо46 £ 34; tо56 £ 34;
б) продолжительность выполнения
каждой работы должна быть не меньше минимально возможного времени:
tо12 - t н 12 ³ 4; tо34 - t н 34 ³ 6;
tо13 - t н 13 ³ 8; tо36 - t н 36 ³ 10;
tо14 - t н 14 ³ 13; tо45 - t н 45 ³ 10;
tо24 - t н 24 ³ 5; tо46 - t н 46 ³ 11;
tо25 - t н 25 ³ 7; tо56 - t н 56 ³ 7;
в) зависимость продолжительности
работ от вложенных средств:
tо12 - t н 12 = 7 - 0,1x12; tо13 - t н 13 = 11 - 0,3x13;
tо14 - t н 14 = 16 - 0,2x14; tо24 - t н 24 = 6 - 0,05x24;
tо25 - t н 25 = 10 - 0,25x25; tо34 - t н 34 = 8 - 0,2x34;
tо36 - t н 36 = 13 - 0,12x36; tо45 - t н 45 = 12 - 0,5x45;
tо46 - t н 46 = 14 - 0,08x46; tо56 - t н 56 = 9 - 0,02x56;
г) время начала выполнения каждой
работы должно быть не меньше времени окончания непосредственно предшествующей
ей работы:
t н 12 = 0; t н 13 = 0; t н14 = 0;
t н 24 ³ tо12; t н 25 ³ tо12;
t н 34 ³ tо13; t н 36 ³ tо13;
t н 45 ³ tо14; t н 45 ³ tо24;
t н 45 ³ tо34;
t н 46 ³ tо14; t н 46 ³ tо24;
t н 46 ³ tо34;
t н 56 ³ tо25; t н 56 ³ tо45;
д) условие неотрицательности
неизвестных:
t
н ij ³ 0, tоij ³ 0, xij ³ 0, (i, j) Î
.
3. Численное
решение задачи:
Табличную запись
математической модели см. табл. 2.2.
Решив данную задачу средствами EXCEL, получаем следующие
результаты:
t н12 = 0; tо12 = 7; t н13 = 0; tо13 = 8; t н14 = 0; tо14 = 15;
t н 24 = 7; tо24 = 13; t н 25 = 7; tо25 = 17;
t н 34 = 8; tо34 = 15; t н 36 = 8; tо36 = 21;
t н45 = 15; tо45 = 25; t н 56 = 25; tо56 = 34;
x12 = 0; x13 = 10; x14 = 5; x24 = 0; x25 = 0;
x34 = 5; x36 = 0; x45 =4; x46 =0; x56 = 0;
fmin = 24.
4. Анализ
полученных результатов. Чтобы выполнить
работы проекта за директивное время t0=34, необходимо
дополнительно вложить 24 ден. ед. При этом средства распределятся следующим
образом: 10 ден. ед. - в работу (1,3), 5 ден. ед. - в работу (1,4), 5 ден. ед.
- в работу (3,4) и 4 ден. ед. - в работу (4,5), что приведет к сокращению
продолжительности работы (1,3) на 3 дня, работы (1,4) - на 1 день, работы (3,4)
- на 1 день и работы (4,5) - на 2 дня. Сокращение срока реализации проекта за
счет вложения дополнительных средств составит 6 ед. времени.
Постановка задачи 2.
Проект представлен сетевым графиком.
Для каждой работы известна ее продолжительность tij и минимально
возможное время выполнения dij. Для сокращения срока реализации
проекта выделено В ден. ед. Вложение дополнительных средств хij в
работу (i, j) сокращает время ее выполнения до t’ij = tij
- kijxij. Технологические коэффициенты kij известны.
Требуется найти такие t н ij, toij, xij, чтобы:
·
время выполнения всего комплекса работ было минимальным;
·
количество используемых дополнительных средств не превышало B ден. ед.;
·
продолжительность выполнения каждой работы была не меньше заданной
величины dij.
Номер задачи
|
Пара- метры
|
Работы
|
Срок выполнения проекта t0
|
|
|
1,2
|
1,3
|
1,4
|
2,4
|
2,5
|
3,4
|
3,6
|
4,5
|
|
|
tij
|
7
|
11
|
16
|
6
|
10
|
8
|
13
|
12
|
|
*
|
dij
|
4
|
8
|
13
|
5
|
7
|
6
|
10
|
10
|
34
|
|
kij
|
0,1
|
0,3
|
0,2
|
0,05
|
0,25
|
0,2
|
0,12
|
0,5
|
|
|
tij
|
9
|
12
|
18
|
8
|
12
|
5
|
12
|
10
|
|
1
|
dij7101561038735
|
|
|
|
|
|
|
|
|
|
|
kij
|
0,05
|
0,2
|
0,25
|
0,08
|
0,15
|
0,1
|
0,06
|
0,05
|
|
|
tij
|
10
|
13
|
24
|
9
|
11
|
17
|
10
|
15
|
|
2
|
dij
|
5
|
9
|
11
|
6
|
9
|
12
|
7
|
13
|
56
|
|
kij
|
0,08
|
0,25
|
0,1
|
0,15
|
0,3
|
0,2
|
0,08
|
0,4
|
|
|
tij
|
6
|
13
|
20
|
9
|
14
|
16
|
15
|
10
|
|
3
|
dij
|
5
|
10
|
16
|
7
|
11
|
13
|
12
|
7
|
40
|
|
kij
|
0,05
|
0,25
|
0,3
|
0,07
|
0,15
|
0,1
|
0,05
|
0,03
|
|
|
tij
|
19
|
10
|
35
|
18
|
20
|
9
|
22
|
17
|
|
4
|
dij
|
16
|
5
|
25
|
13
|
15
|
6
|
17
|
13
|
60
|
|
kij
|
0,25
|
0,07
|
0,1
|
0,2
|
0,13
|
0,15
|
0,06
|
0,4
|
|
|
tij
|
6
|
15
|
26
|
7
|
11
|
10
|
11
|
12
|
|
5
|
dij
|
5
|
13
|
20
|
5
|
9
|
7
|
8
|
9
|
50
|
|
kij
|
0,07
|
0,2
|
0,3
|
0,1
|
0,05
|
0,1
|
0,04
|
0,05
|
|
|
tij
|
10
|
18
|
16
|
12
|
7
|
13
|
11
|
10
|
|
6
|
dij7141210598742
|
|
|
|
|
|
|
|
|
|
|
kij
|
0,5
|
0,1
|
0,25
|
0,4
|
0,2
|
0,15
|
0,3
|
0,5
|
|
|
tij
|
9
|
18
|
21
|
7
|
12
|
19
|
20
|
9
|
|
7
|
dij
|
14
|
18
|
4
|
9
|
15
|
16
|
6
|
33
|
|
kij
|
0,2
|
0,25
|
0,15
|
0,4
|
0,3
|
0,12
|
0,2
|
0,2
|
|
|
tij
|
15
|
8
|
7
|
5
|
13
|
11
|
7
|
15
|
|
8
|
dij
|
12
|
5
|
4
|
3
|
10
|
8
|
4
|
12
|
47
|
|
kij
|
0,25
|
0,2
|
0,15
|
0,1
|
0,3
|
0,4
|
0,2
|
0,25
|
|
|
tij
|
13
|
22
|
19
|
17
|
10
|
25
|
12
|
13
|
|
9
|
dij
|
10
|
18
|
15
|
14
|
7
|
21
|
9
|
10
|
49
|
|
kij
|
0,3
|
0,1
|
0,05
|
0,2
|
0,4
|
0,2
|
0,25
|
0,3
|
|
|
tij
|
16
|
12
|
10
|
8
|
3
|
9
|
11
|
16
|
|
10
|
dij
|
10
|
7
|
6
|
5
|
2
|
7
|
9
|
10
|
29
|
|
kij
|
0,2
|
0,1
|
0,16
|
0,3
|
0,25
|
0,1
|
0,4
|
0,2
|
|
Решение варианта *.
1. Запишем все данные на
сетевой график.
По первоначальному условию tкр = 22, т.е. проект может быть выполнен за 22 ед. времени.
2. Составление
математической модели задачи.
Чтобы однозначно записать целевую
функцию, добавим на сетевом графике фиктивную работу (5,6).
Целевая функция имеет вид tкр
= tо56 (min).
Запишем ограничения задачи:
а) сумма вложенных средств не должна
превышать их наличного количества:
х12 + х13 + х14
+ х23 + х34 + х35 + х45 £ 47;
б) продолжительность выполнения
каждой работы должна быть не меньше минимально возможного времени:
tо12 - t н 12 ³ 3; tо34 - t н 34 ³ 5;
tо13 - t н 13 ³ 4; tо35 - t н 35 ³ 4;
tо14 - t н 14 ³ 1; tо45 - t н 45 ³ 2;
tо23 - t н 23 ³ 2; tо56 - t н 56 = 0;
в) зависимость продолжительности
работ от вложенных средств:
tо12 - t н 12 = 5 - 0,5x12; tо13 - t н 13 = 6 - 0,2x13;
tо14 - t н 14 = 2 - 0,3x14; tо23 - t н 23 = 4 - 0,25x23;
tо34 - t н 34 = 9 - 0,4x34; tо35 - t н 35 = 7 - 0,2x35;
tо45 - t н 45 = 4 - 0,1x45;
г) время начала выполнения каждой
работы должно быть не меньше времени окончания непосредственно предшествующей
ей работы:
t н 12 = 0; t н 13 = 0; t н14 = 0;
t н 23 ³ tо12;
t н 34 ³ tо13; t н 34 ³ tо23;
t н 35 ³ tо13; t н 35 ³ tо23;
t н 45 ³ tо14; t н 45 ³ tо34;
t н 56 ³ tо35; t н 56 ³ tо45;
д) условие неотрицательности
неизвестных:
t
н ij ³ 0, tоij ³ 0, xij ³ 0, (i, j) Î
.
сетевой математический
модель
5. Численное
решение задачи:
Табличную запись
математической модели см. табл. 2.4.
Решив данную задачу средствами EXCEL, получаем следующие
результаты:
t н12 = 0; tо12 = 3; t н13 = 0; tо13 = 3; t н14 = 0; tо14 = 2;
t н 23 = 3; tо23 = 3; t н 34 = 3; tо34 = 8; t н 35 = 3; tо35 = 10;
t н45 = 8; tо45 = 10; t н 56 = 10; tо56 = 10;
x12 = 20; x13 = 0; x23 = 0; x14 = 0; x34 = 10; x35 = 0; x45 =20,
tкр = 10.
5. Анализ полученных
результатов. При дополнительном
вложении 47 ден. ед., проект может быть выполнен за 10 ед. времени. При этом
средства распределятся следующим образом: 20 ден. ед. - в работу (1,2), 10 ден.
ед. - в работу (3,4) и 20 ден. ед. - в работу (4,5), что приведет к сокращению
продолжительности работы (1,2). Сокращение срока реализации проекта за счет
вложения дополнительных средств составит 8 ед. времени.