Автор работы: Пользователь скрыл имя, 22 Марта 2013 в 13:22, контрольная работа
В задаче даны работы и их длительность. Необходимо построить сетевую модель, разбить по слоям вершины и дуги, найти критический путь и вычислить все резервы событий и работ.
по дисциплине
Методы оптимальных решений
8вариант
В задаче даны работы и их длительность. Необходимо построить сетевую модель, разбить по слоям вершины и дуги, найти критический путь и вычислить все резервы событий и работ.
Дано:
t(1,2)=3, t(1,3)=4, t(1,4)=5, t(2,5)=5, t(3,6)=8, t(4,7)=8, t(5,7)=7, t(5,8)=6, t(6,9)=4, t(7,8)=5, t(7,9)=6, t(8,10)=9, t(8,11)=3, t(9,11)=7, t(10,11)=5.
Решение:
Работа (i, j) |
Время вып. tij |
Работа (i, j) |
Время вып. tij | |
|
(1; 2) |
3 |
(6; 9) |
4 | |
(1; 3) |
4 |
(7; 8) |
5 | |
(1; 4) |
5 |
(7; 9) |
6 | |
(2; 5) |
5 |
(8; 10) |
9 | |
(3; 6) |
8 |
(8; 11) |
3 | |
(4; 7) |
8 |
(9; 11) |
7 | |
(5; 7) |
7 |
(10; 11) |
5 | |
(5; 8) |
6 |
|||
В проекте 11 событий (1,2,…11) и 15 связывающих их работы.
1. Сетевая модель, разбивка на слои.
Составим матрицу смежности графа.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
V6 | ||
|
1 |
1 |
1 |
1 |
3 |
3 |
3 |
3 |
2 |
1 |
0 | |||||||||
2 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
x | |||||||||||
3 |
1 |
1 |
1 |
1 |
0 |
x |
x |
x | |||||||||||
4 |
1 |
1 |
1 |
1 |
1 |
0 |
x |
x | |||||||||||
5 |
1 |
1 |
2 |
2 |
2 |
1 |
0 |
x |
x | ||||||||||
6 |
1 |
1 |
1 |
0 |
x |
x |
x |
x | |||||||||||
7 |
1 |
1 |
2 |
2 |
1 |
0 |
x |
x |
x | ||||||||||
8 |
1 |
1 |
2 |
1 |
0 |
x |
x |
x |
x | ||||||||||
9 |
1 |
1 |
0 |
x |
x |
x |
x |
x | |||||||||||
10 |
1 |
1 |
0 |
x |
x |
x |
x |
x | |||||||||||
11 |
0 |
x |
x |
x |
x |
x |
x | ||||||||||||
Заполним матрицу V для разбиения на слои. Получили 7 слоев.
Граф в соответствии со слоями с указанными длинами дуг:
Матрица предшествования дуг:
(1,2) |
(1,3) |
(1,4) |
(2,5) |
(3,6) |
(4,7) |
(5,7) |
(5,8) |
(6,9) |
(7,8) |
(7,9) |
(8,10) |
(8,11) |
(9,11) |
(10,11) | |
(1,2) |
|||||||||||||||
(1,3) |
|||||||||||||||
(1,4) |
|||||||||||||||
(2,5) |
1 |
||||||||||||||
(3,6) |
1 |
||||||||||||||
(4,7) |
1 |
||||||||||||||
(5,7) |
1 |
||||||||||||||
(5,8) |
1 |
||||||||||||||
(6,9) |
1 |
||||||||||||||
(7,8) |
1 |
1 |
|||||||||||||
(7,9) |
1 |
1 |
|||||||||||||
(8,10) |
1 |
1 |
|||||||||||||
(8,11) |
1 |
1 |
|||||||||||||
(9,11) |
1 |
1 |
|||||||||||||
(10,11) |
1 |
2. Критический путь.
Слой 1: вершина 1.
t1=0 - начало выполнения проекта.
Слой 2: вершина 2, в которую входит одна дуга (1,2).
t2=t1+t(1,2)=0+3=3
Слой 3: вершины 4 и 5, в которые входит по одной дуге.
t4=t1+t(1,4) = 0+5=5
t5=t2+t(2,5) = 3+5=8
Слой 4: вершины 3 и 7.
t3=t1+t(1,3) = 0+4=4
t7 = max{t4+t(4,7),t5+t(5,7)}=max{
Слой 5: вершины 6 и 8.
t6=t3+t(3,6) = 4+8=12
t8 = max{t7+t(7,8),t5+t(5,8)}=max{
Слой 6: вершины 9 и 10.
t9 = max{t7+t(7,9),t6+t(6,9)}=max{
t10=t8+t(8,10) = 20+9=29
Слой 7: вершина 11.
t11 = max{t8+t(8,11),t9+t(9,11),t10+
Время окончания проекта равно 34.
Критический путь единственный:
(1,2)(2,5)(5,7)(7,8)(8,10)(10,
3. Резервы времени событий.
Граничные сроки и резервы времени R(i):
4. Резервы времени работ.
Ранний срок начала работы .
Ранний срок окончания работы .
Поздний срок окончания работы .
Поздний срок начала работы .
Полный резерв работы .
Свободный резерв работы .
Независимый резерв работы .
Частный резерв работы .
Работа |
Время t(i,j) |
Ранний срок начала |
Ранний срок окончания |
Поздний срок окончания |
Поздний срок начала |
Полный резерв |
Свобод. резерв |
Независимый резерв |
Частный резерв |
|
(1,2) |
3 |
0 |
3 |
3 |
0 |
0 |
0 |
0 |
0 |
(1,3) |
4 |
0 |
4 |
15 |
11 |
11 |
0 |
0 |
11 |
(1,4) |
5 |
0 |
5 |
7 |
2 |
2 |
0 |
0 |
2 |
(2,5) |
5 |
3 |
8 |
8 |
3 |
0 |
0 |
0 |
0 |
(3,6) |
8 |
4 |
12 |
23 |
15 |
11 |
0 |
0 |
0 |
(4,7) |
8 |
5 |
13 |
15 |
7 |
2 |
2 |
0 |
0 |
(5,7) |
7 |
8 |
15 |
15 |
8 |
0 |
0 |
0 |
0 |
(5,8) |
6 |
8 |
14 |
20 |
14 |
6 |
6 |
6 |
6 |
(6,9) |
4 |
12 |
16 |
27 |
23 |
11 |
5 |
0 |
0 |
(7,8) |
5 |
15 |
20 |
20 |
15 |
0 |
0 |
0 |
0 |
(7,9) |
6 |
15 |
21 |
27 |
21 |
6 |
0 |
0 |
6 |
(8,10) |
9 |
20 |
29 |
29 |
20 |
0 |
0 |
0 |
0 |
(8,11) |
3 |
20 |
23 |
34 |
31 |
11 |
11 |
11 |
11 |
(9,11) |
7 |
21 |
28 |
34 |
27 |
6 |
6 |
0 |
0 |
(10,11) |
5 |
29 |
34 |
34 |
29 |
0 |
0 |
0 |
0 |
Информация о работе Контрольная работа по "Методам оптимальных решений"