Методы оптимизации
Автор: Svetlana6 • Июль 19, 2023 • Контрольная работа • 1,693 Слов (7 Страниц) • 101 Просмотры
Вариант 2
Даны работы и их длительность:
t(1, 2)=3, t(1, 4)=11, t(1,3)=4, t(1,6)=8, t(2,4)=7, t(2,5)=9, t(2,7)=7, t(3, 4)=9, t(3, 6)=2, t(3, 7)=4, t(4, 8)=3, t(4, 9)=3, t(5, 8)=5, t(6,7)=5, t(6,9)=8, t(6,10)=9, t(7,8)=4, t(7,10)=8, t(7,11)=5, t(8,11)=11, t(9, 10)=4, t(9, 12)=5, t(10, 11)=4, t(10, 12)=3, t(11, 12)=2.
Необходимо построить сетевую модель, разбить по слоям вершины и дуги, найти критический путь и вычислить все резервы событий и работ.
Решение
Таблица 1
Работа (i, j) | Время вып tij | Работа (i, j) | Время вып tij | Работа (i, j) | Время вып. tij |
(1;2) | 3 | (3;6) | 2 | (7; 8) | 4 |
(1;3) | 4 | (3;7) | 4 | (7;10) | 8 |
(1;4) | 11 | (4;8) | 3 | (7;11) | 5 |
(1;6) | 8 | (4;9) | 3 | (8;11) | 11 |
(2;4) | 7 | (5;8) | 5 | (9;10) | 4 |
(2;5) | 9 | (6;7) | 5 | (9;12) | 5 |
(2;7) | 7 | (6;9) | 8 | (10;11) | 4 |
(3;4) | 9 | (6;10) | 9 | (10;12) | 3 |
(11;12) | 2 |
Составим матрицу смежности (первые 13 столбцов таблицы 2, вместо нулей оставлены пустые места).
Таблица 2
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | V0 | V1 | V2 | V3 | V4 | V5 | V6 | |
1 | 1 | 1 | 1 | 1 | 4 | 4 | 4 | 4 | 4 | 2 | 0 | ||||||||
2 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 1 | 0 | х | |||||||||
3 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 2 | 0 | х | |||||||||
4 | 1 | 1 | 2 | 2 | 2 | 1 | 0 | х | х | ||||||||||
5 | 1 | 1 | 1 | 1 | 0 | х | х | х | |||||||||||
6 | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 0 | х | х | |||||||||
7 | 1 | 1 | 1 | 3 | 3 | 2 | 0 | х | х | х | |||||||||
8 | 1 | 1 | 1 | 0 | х | х | х | х | |||||||||||
9 | 1 | 1 | 2 | 1 | 1 | 0 | х | х | х | ||||||||||
10 | 1 | 1 | 2 | 1 | 0 | х | х | х | х | ||||||||||
11 | 1 | 1 | 0 | х | х | х | х | х | |||||||||||
12 | 0 | х | х | х | х | х | х |
Затем вычислим столбец V0, каждый элемент которого есть сумма по соответствующей строке элементов матрицы смежности и припишем этот столбец справа к матрице смежности.
Столбец V0 имеет ноль в строке 12. Значит, вершина 12 не имеет потомков и является завершающей. Вершину 12 поместим в слой номер 1 (разбивка по слоям идет с конца). Далее вычислим столбец V1 , вычитая из столбца V0 столбец 12 матрицы смежности (столбец 12 соответствует вершине, вошедшей в первый слой).
...