Реферат Курсовая Конспект
Новый сетевой график - раздел Образование, Орграф без контуров с неотрицательными ...
|
S | |||||||
(is,js)) | (1, 2) | (1, 3) | (2, 4) | (3, 4) | (3, 5) | (4, 5) | (5, 6) |
τs |
Задача о кратчайшем сроке выполнения проекта
Алгоритм Форда
Для каждого события (вершины) i=1,…,6 полагаем ti = 0.
t’j s = max {tjs, tis+τ}.
Найти календарный план
t = (t1, t2, t3, t4, t5, t6) и λ(t) = t6 - t1 (кратчайший срок)
Шаг 1.
1. S =(1, 2): t’2 = max {t2, t1 + τ1 } = max {0, 0+3} = 3;
2. S =(1, 3): t’3 = max {t3, t1 + τ2 } = max {0, 0+5} = 5;
3. S =(2, 4): t’4 = max {t4, t2 + τ3 } = max {0, 3+7} = 10;
4. S =(3, 4): t’3 = max {t4, t3 + τ4 } = max {10, 5+0} = 10;
5. S =(3, 5): t’5 = max {t5, t3 + τ5 } = max {0, 5+4} = 9;
6. S = (4, 5): t’5 = max {t5, t4 + τ6 } = max {9, 10+6} = 16;
7. S = (5, 6): t’6 = max {t6, t5 + τ7 } = max {0, 16+3} = 19.
Шаг 2.
1. S =(1, 2): t’2 = max {t2, t1 + 3 } = max {3, 0+3} = 3;
2. S =(1, 3): t’3 = max {t3, t1 + 5 } = max {5, 0+5} = 5;
3. S =(2, 4): t’4 = max {t4, t2 + τ3 } = max {10, 3+7} = 10;
4. S =(3, 4): t’3 = max {t4, t3 + τ4 } = max {10, 5+0} = 10;
5. S =(3, 5): t’5 = max {t5, t3 + τ5 } = max {16, 5+4} = 16;
6. S = (4, 5): t’5 = max {t5, t4 + τ6 } = max {16, 10+6} = 16;
7. S = (5, 6): t’6 = max {t6, t5 + τ7 } = max {16, 16+3} = 19.
Конец работы алгоритма, т.к. ни одна из величин ti не изменилась.
Итак, определили ti - самые ранние сроки выполнения событий i =1,…,6 сетевого графика:
t = (0, 3, 5, 10, 16, 19) – календарный план и
λ(t) = t6 - t1 = 19 - минимальный срок выполнения проекта
Задача о нахождении наиболее поздних сроков наступлений событий
– Конец работы –
Эта тема принадлежит разделу:
Сетевая модель... вершины события завершение одних видов работ и начало других видов работ... дуги работы...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Новый сетевой график
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов