По данным, представленным в таблице, требуется:
а) построить сетевой график (длина работы tij);
б) определить критический путь и найти его длину;
в) определить резервы времени каждого события;
г) найти резервы времени всех работ и коэффициенты напряженности работ, не лежащих на критическом пути;
д) выполнить оптимизацию сетевого графика по времени (В – ограничение на затраты; to – ограничение на время; dij – минимально возможное время выполнения работы; kij – технологические коэффициенты использования дополнительных средств).
Работы tij
dij
kij
Вариант 4
1,2 9 5 0,1
1,3 15 11 0,1
2,3 7 4 0,4
2,4 9 3 0,8
3,4 4 2 0,9
3,5 6 5 0,2
4,5 11 8 0,7
to =18
Решение
А) Построенный сетевой график представлен на рисунке 1.
Рисунок 1 – Сетевой график
б) определим критический путь и найдём его длину.
tр(2) = tр(1) + t(1,2) = 0 + 9 = 9
tр(3) = max{tр(1) + t(1,3); tр(2) + t(2,3)} = max{15; 16} = 16
tр(4) = max{tр(2) + t(2,4); tр(3) + t(3,4)} = max{18; 20} = 20
tр(5) = max{tр(3) + t(3,5); tр(4) + t(4,5)} = max{22; 31} = 31
Длина критического пути равна раннему сроку свершения завершающего события 5: tkp = tp(5) = 31.
Критический путь: (1,2)(2,3)(3,4)(4,5).
в) определим резервы времени каждого события.
tп(5) = 31
tп(4) = tп(5) - t(4,5) = 31 - 11 = 20
tп(3) =min{tп(4) - t(3,4); tп(5) - t(3,5)} = min{16; 25} = 16
tп(2) =min{tп(3) - t(2,3); tп(4) - t(2,4)} = min{9; 11} = 9
tп(1) =min{tп(2) - t(1,2); tп(3) - t(1,3)} = min{0; 1} = 0
Резерв времени R(i) i-ого события определяется как разность между поздним и ранним сроками его свершения: R(i) = tп(i) - tp(i)
i
tр(i) tп(i) R(i)
1 0 0 0
2 9 9 0
3 16 16 0
4 20 20 0
5 31 31 0
Схема с выделенным критическим путём и расчётом резервного времени представлена на рисунке 2.
Рисунок 2 – сетевой график с рассчитанным резервным временем.
г) найти резервы времени всех работ и коэффициенты напряженности работ, не лежащих на критическом пути;
Коэффициентом напряженности КH работы Pi,j называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим – критический путь:
Кн=tLmax-t1kptkp-t1kp,
где t(Lmax) – продолжительность максимального пути, проходящего через работу Pi,j, от начала до конца сетевого графика;
tkp – продолжительность (длина) критического пути;
t1kp – продолжительность отрезка рассматриваемого максимального пути, совпадающего с критическим путем.
Работа Путь t(Lmax) Совпадающие работы t1кр
Кн
(1,3) 1-3-4-5 30 (3,4)(4,5) 15 30-1531-15=0,9375
(2,4) 1-2-4-5 29 (1,2)(4,5) 20 29-2031-20=0,8182
(3,5) 1-2-3-5 22 (1,2)(2,3) 16 22-1631-16=0,4
д) выполнить оптимизацию сетевого графика по времени (ограничение на время to =18); dij – минимально возможное время выполнения работы; kij – технологические коэффициенты использования дополнительных средств.
Математическая запись задачи:
Fx=xij(min)
tn-1,n0≤to, tij0-tijH≥dij, tij0-tijH=fij, trjH≥tir0,
tij0≥0, tijH≥0
В сетевой график добавляем еще одну работу.
Тогда целевая функция запишется в виде x12+x13+x23+x24+x34+x35+x45→min
Запишем ограничения задачи:
a) Ограничение на время
t560≤18
Задать вопрос
на новый заказ в Автор24.
