Зад лин прогр и мет их решения 16 12 08
.pdf270
t |
′′ |
(i) = Tпр |
− vi , |
П (i) = Tпр − Tкрит |
где vi – потенциалы, рассчитанные с конца.
tп(1)=42–39=3; tп(2)=42–29=13; tп(3)=42–24=18; tп(4)=42–23=19; tп(5)=42–13=29;
tп(6)=42–6=36; tп(7)=42–0=42.
Резервом R(i) события i называется разность его позднего и раннего сроков.
Для событий, лежащих на критических путях, резерв равен разности Tпр − Tкрит , для остальных событий – больше этой разности. Приведём все временные параметры событий.
Параметры событий |
Таблица 3 |
||||
|
|
|
|
|
|
|
i |
tP (i) |
tП (i) |
R(i) |
|
|
|
|
|
|
|
|
1 |
0 |
3 |
3 |
|
|
2 |
6 |
13 |
7 |
|
|
3 |
11 |
18 |
7 |
|
|
4 |
16 |
19 |
3 |
|
|
5 |
26 |
29 |
3 |
|
|
6 |
33 |
36 |
3 |
|
|
7 |
39 |
42 |
3 |
|
Найдем временные параметры работ.
Ранним началом работы ( i, j ) называется наименьшее время после начала
проекта, через которое работу можно начать выполнять. Работу можно начать, как только закончатся предшествующие работы, т.е. когда наступит событие i – событие начала. Отсюда
tРН (i, j) = tP (i) = yi .
Р1: tPH (5,6) |
= tр(5) |
= y5 = 26; |
Р5: tPH (1,3) = tр(1) |
= 0; |
Р9: tPH (5,7) = tр(5) = y5 = 26; |
||
Р2: tPH (1,2) |
= tр(1) |
= 0; |
Р6: tPH (1,4) = tр(1) |
= 0; |
Р10: tPH (3,7) |
= tр(3) |
= 11; |
Р3: tPH (2,3) |
= tр(2) |
= 6; |
Р7: tPH (2,5) = tр(2) |
= 6; |
Р11: tPH (6,7) |
= tр(6) |
= 33 |
Р4: tPH (4,7) |
= tр(4) |
= 16; |
Р8: tPH (4,5) = tр(4) |
= 16; |
|
|
|
Ранним окончанием работы ( i, j ) называется наименьшее время после начала проекта, через которое работу можно закончить. Работу можно рано закончить, если её рано начать, поэтому
tРO (i, j) = tP (i) + tij = yi + tij ,
где ti j – время работы.
|
|
|
|
271 |
|
|
|
Р1: tPО (5,6) |
= 26+7 = 33; |
Р5: tPО (1,3) |
= 0+5 |
= 5; |
Р9: tPО (5,7) = 26+3 = 29; |
||
Р2: tPО (1,2) |
= 0+6 |
= 6; |
Р6: tPО (1,4) |
= 0+16 = 16; |
Р10: tPО (3,7) |
= 11+24 = 35; |
|
Р3: tPО (2,3) |
= 6+5 |
= 11; |
Р7: tPО (2,5) |
= 6+8 |
= 14; |
Р11: tPО (6,7) |
= 33+6 = 39 |
Р4: tPО (4,7) |
= 16+10 = 26; |
Р8: tPО (4,5) |
= 16+10 = 26; |
|
|
||
Поздним окончанием работы ( i, j ) называется наибольшее время после
начала проекта, позже которого работу нельзя закончить (иначе сорвётся проектное время Tпр ). Событие j как раз означает окончание работ, заканчивающихся в j, в том числе работы ( i, j ), поэтому
|
|
tПO (i, j) = tП ( j) = Tпр − v j . |
|
|
Р1: tПО (5,6) |
= 42–6 = 36; |
Р5: tПО (1,3) = 42–24 = 18; |
Р9: tПО (5,7) = 42–0 = 42; |
|
Р2: tПО (1,2) |
= 42–29 = 13; |
Р6: tПО (1,4) = 42–23 = 19; |
Р10: tПО (3,7) |
= 42–0 = 42; |
Р3: tПО (2,3) |
= 42–24 = 18; |
Р7: tПО (2,5) = 42–13 = 29; |
Р11: tПО (6,7) |
= 42–0 = 42 |
Р4: tПО (4,7) |
= 42–0 = 42; |
Р8: tПО (4,5) = 42–13 = 29; |
|
|
Поздним началом работы ( i, j ) называется наибольшее время после начала проекта, позже которого работу нельзя начать (иначе сорвётся проектное время). Если работа поздно начинается, то она и поздно заканчивается, поэтому
tПH (i, j) = tПO (i, j) − ti j = Tпр − v j − ti j .
Р1: tПН (5,6) |
= 36–7 = 29; |
Р5: tПН (1,3) |
= 18–5 = 13; |
Р9: tПН (5,7) = 42–3 = 39; |
|
Р2: tПН (1,2) |
= 13–6 = 7; |
Р6: tПН (1,4) |
= 19–6 = 3; |
Р10: tПН (3,7) |
= 42–24 = 18; |
Р3: tПН (2,3) |
= 18–5 = 13; |
Р7: tПН (2,5) |
= 29–8 = 21; |
Р11: tПН (6,7) |
= 42–6 = 36 |
Р4: tПН (4,7) |
= 42–10 = 32; |
Р8: tПН (4,5) |
= 29–10 = 19; |
|
|
Полным резервом называется наибольшее время, на которое можно увеличить время работы (т.е. это прибавка по времени, запас), если предшествующие для (i,j) работы начинаются в ранние сроки, а последующие за ( i, j ) – в поздние сроки. Другими словами, полный резерв это запас времени в самом "благоприятном" для работы случае, когда предшествующие рано заканчиваются и дают работе возможность для раннего начала, а последующие поздно начинаются и дают работе возможность для позднего окончания. Коротко: "до нас – рано, после нас – поздно".
RП (i, j) = tП ( j) − tР (i) − ti j , или RП (i, j) = tПH (i, j) − tРH (i, j) = tПО (i, j) − tPO (i, j) . RП (i, j) ≥ 0 .
Р1: RП (5,6) = 36–33 = 3; |
Р5: RП (1,3) = 18–5 = 3; |
Р9: RП (5,7) = 42–29 = 13; |
274
4)Критические работы образуют непрерывную по времени цепочку отрезков, и по этому признаку могут быть найдены по диаграмме;
5)Самый правый из концов отрезков расположен в момент Tкрит .
вспомогательная
ось
6
7
4
5
1 |
|
4 |
5 |
|
6 |
|
|
4
7
1 
2
2
5
2
3
3 |
|
7 |
|
1 
3
t
6 |
11 |
14 |
16 |
|
26 |
33 |
|
39 |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
|
Ткрит
Ранняя диаграмма Ганта
Никитенков Владимир Леонидович Холопов Александр Алексеевич
Задачи линейного программирования и методы их решения
Учебное пособие
Редактор С.Б. Свигзова Компьютерный макет В.Л. Никитенкова, А.А. Холопова
Лицензия ЛР № 010183 от 25.02.1998. Подписано в печать 18.11.2008. Формат 60x84/16. Печать офсетная. Бумага офсетная.
Усл. п. л. 17.3. Заказ № 365. Тираж 500 экз.
ИПО СыктГУ.
167001. Сыктывкар, Октябрьский пр., 55
Никитенков Владимир Леонидович
(р. 27.11.52, г. Демидов, Смоленской области), ученый механик и математик, доктор технических наук,
профессор. Закончил мат-мех Ленинградского университета (1976). Заведующий кафедрой прикладной математики Сыктывкарского государственного университета. Ученик Е. И. Михайловского - известного ученого Ленинградской школы механики, созданной академиком В. В. Новожиловым. Научные интересы в области численных методов теории оболочек, прочности и автоматизации инженерных расчетов при проектировании горизонтальных аппаратов давления, целочисленных моделей исследования операций. Автор ряда учебных пособий.
Холопов Александр Алексеевич
(р. 13.06.52, с. Визинга, Республика Коми), ученый математик, кандидат физико-математических
наук. Закончил мат-мех Ленинградского университета (1974) и аспирантуру (1977).
Доцент кафедры геометрии, алгебры и математической статистики Сыктывкарского государственного университета. Научные интересы в области стохастических и непрерывных моделей в исследовании операций. Автор ряда учебных пособий.