Проверка канонической сети на наличие тупиков, событий, в которые не входит не одна работа, работ с одинаковыми шифрами, замкнутых контуров
Присваиваем для первой работы матрицы Tpq значения номеров начального и конечного событий (i1:=1, j1:=2), счетчика номеров событий (z:=3) и номера очередной работы (l:=2). Конечному событию данной работы (Ai) присваиваем номер, соответствующий значению указателя (Yi:=l). Значение указателя номера увеличиваем на единицу (l:=l+1). Устанавливаем номер конечного события рассматриваемой работы (jl… Читать ещё >
Проверка канонической сети на наличие тупиков, событий, в которые не входит не одна работа, работ с одинаковыми шифрами, замкнутых контуров (реферат, курсовая, диплом, контрольная)
Вывод: как видно из приведенного выше графа, в канонической сети отсутствуют тупики, события, в которые не входит не одна работа, работы с одинаковыми шифрами, замкнутые контуры.
Построение топологической схемы:
описание алгоритма;
таблица построения топологической схемы.
Алгоритм «Топологическая схема» .
Шаг 1.
Начальному и конечному событию первой работы (Ai, i=1) присваиваем X1:=1, Y1:=2. Указатель значения номера устанавливаем равным трем (l=3).
Шаг 2.
Переходим к рассмотрению следующей работы из списка работ (i:=i+1).
Шаг 3.
Если для рассматриваемой работы (Ai) списка предшествующих работ совпадают с какой-либо ранее рассмотренной работой (Aj), т. е.
r-1(Ai)=r-1(Aj):j.
Шаг 4.
Начальному событию рассматриваемой работы присваиваем номер, соответствующий значению указателя (Xi:=l). Значение указателя номера увеличиваем на единицу (l:=l+1).
Шаг 5.
Если для рассматриваемой работы в списке предшествующих работ
(r-1(Ai)) содержаться пронумерованные ранее работы (r-1(Ai):j
Шаг 6.
Если рассматриваемая работа (Aj) встречалась в списках предшествующих работ, пронумерованных ранее (r-1(Aj):j
Шаг 7.
Конечному событию данной работы (Ai) присваиваем номер, соответствующий значению указателя (Yi:=l). Значение указателя номера увеличиваем на единицу (l:=l+1).
Шаг 8.
Если множество работ не исчерпано, то переходим к шагу 2.
Шаг 9.
Конец вычислений по алгоритму.
№ варианта. | № п/п. | Список работ. | Список непосредственно предшествующих работ. | Длительность. | Трудоемкость. | Нумерация работ. | |
F1. | F14 F19 F21 F25. | 1−2 23. | |||||
F2. | F10. | 3−4 19. | |||||
F3. | F20 F12. | 5−6 25. | |||||
F4. | ФН. | 7−8 15. | |||||
F5. | F23 F8 F11. | 9−10 25. | |||||
F6. | ФН. | 7−11 14. | |||||
F7. | F18 F16. | 12−13 23. | |||||
F8. | F6. | 14−9. | |||||
F9. | F4. | 15−16 21. | |||||
F10. | ФН. | 7−3. | |||||
F11. | F24. | 17−9. | |||||
F12. | F18 F16. | 12−5. | |||||
F13. | ФН. | 7−18 22. | |||||
F14. | F4. | 15−1. | |||||
F15. | F17 F2. | 19−20 23. | |||||
F16. | F4. | 15−12. | |||||
F17. | F6. | 14−19. | |||||
F18. | F9. | 21−12. | |||||
F19. | F13. | 22−1. | |||||
F20. | F9. | 21−5. | |||||
F21. | F10. | 3−1. | |||||
F22. | F7 F1 F15. | 23−24 25. | |||||
F23. | F17 F2. | 19−9. | |||||
F24. | F6. | 14−17. | |||||
F25. | F6. | 14−1. | |||||
ФК. | F3 F22 F5. | 25−26. | |||||
Построение сети неправильного вида.
Построение сети правильного вида:
описание алгоритма;
таблица характеристик сети правильного вида.
Алгоритм «Нумерация событий работ» .
Шаг 1.
Формируем матрицу топологической схемы G=G (X, Y, H (X, Y))T=T[X, Y].
Шаг 2.
Заполняем базисную матрицу расчетов, дополняя матрицу топологической схемы четырьмя нулевыми столбцами вычислений пометок, номеров начальных и конечных событий T=T[X, Y] To=To[X, Y,0p, 0q, 0i, 0j].
Шаг 3.
Устанавливаем начальное состояние счетчика номеров рангов в 1 (S:=1).
Шаг 4.
Рассматриваем пометки (Pxy) для тех работ, начальные события которых не находят себя в списке конечных событий, т. е. являются начальными усеченной матрицы работ (Pxy:=S).
Шаг 5.
Определяем ранги помеченных работ (qxy) при условии, что имеет место несовпадение конечного события с событиями из списка конечных событий непомеченных работ qxy:=Pxy; Pxy:=0, где — список конечных событий непомеченных работ.
Шаг 6.
Формируем усеченную базисную матрицу To=To[X, Y,0p, 0q, 0i, 0j] и упорядоченную по возрастанию ранга матрицу работ: Tpq=Tpq[X, Y,0p, 0q, 0i, 0j], последовательно перенося в нее работы с установленными рангами.
Шаг 7.
Если не всем работам установлен ранг, то увеличиваем счетчик номеров на единицу (S:=S+1) и переходим к шагу 4.
Шаг 8.
Присваиваем для первой работы матрицы Tpq значения номеров начального и конечного событий (i1:=1, j1:=2), счетчика номеров событий (z:=3) и номера очередной работы (l:=2).
Шаг 9.
Если начальное событие (xl) встречалось ране в списке начальных событий (xl, k.
Шаг 10.
Если начальное событие (xl) встречалось ране в списке начальных событий (yk, k.
Шаг 11.
Присваиваем начальному событию рассматриваемой работы (il) номер начального события, равный счетчику номеров (il:=z) и увеличиваем счетчик номеров на единицу (z:=z+1).
Шаг 12.
Если конечное событие (yl) встречалось ранее в списке конечных событий ((yk, k.
Шаг 13.
Устанавливаем номер конечного события рассматриваемой работы (jl) в соответствии со счетчиком номеров (jl:=z) и увеличиваем последний на единицу (z:=z+1).
Шаг 14.
Если не все работы пронумерованы в правильном порядке, то переходим к следующей работе из матрицы работ (T= Tpq), т. е. l:=l+1, и возвращаемся к шагу 9.
Шаг 15.
Выполняем поиск количественных характеристик по значениям первоначальных номеров (X, Y) для каждой из работ и записываем их в соответствующие позиции матрицы сетевого графа G=G (X, Y, H (X, Y))G=G (I, J, H (I, J)).
Шаг 16.
Конец вычислений по алгоритму.
Алгоритм «Упорядочение»
Шаг 1.
Присваиваем каждой работе из списка работ сетевой модели число (так называемый совокупный шифр работы), определяемое соотношениями:
S (i, j)=i*10i+j, l=mink (10k>N), где.
i — номер начального события работы;
j — номер конечного события работы;
l — минимальный показатель степени;
N — максимальный номер события в сетевом графе.
Шаг 2.
Ранжируем все работы в порядке возрастания совокупного шифра.
Шаг 3.
Конец вычислений по алгоритму.
Расчеты по алгоритму смотри в Приложении № 1
Работы. | Длительность. | Трудоемкость. | ||
i. | j. | |||
Построение сети правильного вида.