Задача скачана с сайта www.MatBuro.ru

©МатБюро - Решение задач по высшей математике

Тема: Сетевое планирование

ЗАДАНИЕ.  Для заданной сетевой модели рис.1  некоторого комплекса работ определить время и критический путь. 

                                                                                                              Рис.1      

РЕШЕНИЕ. Рассмотрим прямой ход. Пусть T_j означает минимальное время окончания всех работ, конец которых изображается вершиной с номером j. Очевидно, T₁ =0, далее последовательно находим 

T_j = max (T_i + t_ij ), j = 2,N , где i – номер вершин сетевого графика, из которых выходят векторы, входящие в вершину с номером j; t_ij – длительность работ с началом в вершине i и концом в вершине j, N – количество вершин сетевого графика. При j=N получаем минимальное время графика Tкр=T_N .T_j являются ранними сроками начала (окончания) работ, конец (начало) которых изображается вершиной j. Итак, 

T₁^p = 0,

T₂^p = max(T₁^p +t₁₂ ) = 7, T₃^p = max(T₂^p +t₂₃) = 8,

T₄^p = max(T₁^p +t₁₄ ,T₂^p +t₂₄ ) = max(8,7) = 8, T₅^p = max(T₁^p +t₁₅ ) = 4,

T₆^p = max(T₅^p +t₅₆ ,T₄^p +t₄₆ ) = max(4,16) =16,

T₇^p = max(T₄^p +t₄₇,T₆^p +t₆₇) = max(17,21) = 21,  T₈^p = max(T₃^p +t₃₈ ,T₇^p +t₇₈ ,T₅^p +t₅₈ ) = max(12,24,16) = 24. Тогда Ткр =  24 - минимальное время графика. 

Рассмотрим обратный ход. Пусть T_iⁿ означает наибольшее время окончания всех работ, входящих в вершину i, Tкр=T_Nⁿ.  

T_i = min (T_jⁿ - t_ij ), i = N,2, где j – номер вершины, к которой направлены векторы, выходящие из вершины с номером i.

                                                                                  1

Задача скачана с сайта www.MatBuro.ru

©МатБюро - Решение задач по высшей математике

T₈ⁿ = 24,

T₇ⁿ = min(T₈ⁿ −t₇₈) = 21,

T₆ⁿ = min(T₇ⁿ −t₆₇ ) =16,

T₅ⁿ = min(T₈ⁿ −t₅₈ ,T₆ⁿ −t₅₆ ) = min(12,16) =12, T₄ⁿ = min(T₇ⁿ −t₄₇,T₆ⁿ −t₄₆) = min(12,8) = 8,

T₃ⁿ = min(T₈ⁿ −t₃₈ ) = 20,

T₂ⁿ = min(T₃ⁿ −t₂₃,T₄ⁿ −t₂₄ ) = min(19,8) = 8,             

T₁ⁿ = min(T₂ⁿ −t₁₂,T₄ⁿ −t₁₄,T₅ⁿ −t₁₅) = min(1,0,8) = 0.

T_iⁿ  - поздние сроки начала (окончания) работ, начало которых изображается вершиной i. 

Для определения критического пути составим таблицу. 

Здесь R_ij = T_jⁿ −T_i ^p −t_ij ,  r_ij = T_j^p −T_i ^p −t_ij , - полный и свободный резерв. Критический путь сетевого графика составляют работы, для которых R_ij=r_ij Получаем путь (1,4)-(4,6)-(6,7)-(7,8), время – 24 дня. 

                                                                                  2