|
сокращать следует работу (1, 2). П ри сокращ ении работы (1 ,2 ) на две единицы, критическим и становятся работы ( 0 ,2) и (1, 3), рис. 3.8, длина критического пути Т] = 1 1 , стоимость проекта Si = 17. 47 Рис. 3.8. Д лина критического п ути T i = 11 2 ш аг. Чтобы сократить продолжительность проекта теперь следует сократить продолжительность всех критических путей. Д ля этого необходимо определить множество работ, таких что каж ды й крити че ски й путь содержит хотя бы одну работу из этого множества и сумма коэфф ициентов kj является минимальной. Это задача эквивалентна задаче определения разреза в сети, имею щ его минимальную п р оп ускн ую способность, которая является двойственной к задаче о потоке максимальной величины (коэф ф ициенты kj определяют пропускны е способности д уг, [9]). В нашем примере непосредственным перебором м ож но убедиться, что уменьш ение продолжительностей работ (О, 1) и (О, 2) дает минимальное увеличение стоимости проекта ( 8 единиц на каж д ую единицу уменьшения продолжительности. Уменьш аем продолжительности работ (О, 1) и ( 0 ,2) на 3 единицы. Больше нельзя, т.к. минимальная продолжительность работы ( 0 ,2) равна З.Длина критического пути становится равной Тз = 8 , стоимость проекта 8 г = 41. 3 ш аг. Теперь минимальное увеличение стоимости обеспечивается при уменьш ении продолжительностей работ (О, 1) и (2, 3). Уменьш аем продолжительности работ (О, 1) и (2 ,3 ) на единицу (при этом продолжительность работы (О, 1) становится минимальной). Д лина критического п у ти Тз = 7, стоимость проекта S3 = 50. |
Р О С С И Й С К А Я Г О С У Д А Р С Т В Е Н Н А Я Б И Б Л И О Т Е К А 2 шаг. Чтобы сократить продолжительность проекта теперь следует сократить продолжительность всех критических путей. Для этого необходимо определить множество работ, таких что каждый критический путь содержит хотя бы одну работу из этого множества и сумма коэффициентов к является минимальной. Это задача эквивалентна задаче определения разреза в сети, имеющего минимальную пропускную способность, которая является двойственной к задаче о потоке максимальной величины (коэффициенты ki определяют пропускные способности дуг, [ ]). В нашем примере непосредственным перебором можно убедиться, что уменьшение продолжительностей работ (0, 1) и (0, 2) дает минимальное увеличение стоимости проекта (8 единиц на каждую единицу уменьшения продолжительности. Уменьшаем продолжительности работ (О, 1) и (0 ,2) на 3 единицы. Больше нельзя, т.к. минимальная продолжительность работы (О, 2) равна З.Длина критического пути становится равной Тг = 8, стоимость проекта 82 = 41. 3 шаг. Теперь минимальное увеличение стоимости обеспечивается при уменьшении продолжительностей работ (0,1) и (2,3). Уменьшаем продолжительности работ (О, 1) и (2,3) на единицу (при этом продолжительность работы (О, I) становится минимальной). Длина критического пути Тз = 7, стоимость проекта S3= 50. 4 шаг. Заметим, что в сети имеются всего 2 критических пути (рис. 3.9). Сокращаем продолжительности работ (1,3) и (2,3) на 1. Продолжительность проекта становится равной Т4= 6, стоимость проекта S4= 60. 41 |