|
46 Если мы хотим сократить продолжительность проекта с минимальным увеличением стоимости, то, очевидно, что в первую очередь необходимо сокращать продолжительность работы, имею щ ей м иним альную величину коэффициента kj. Действительно, величина к, определяет увеличение стоимости проекта при уменьш ении продолжительности i-й работы на единицу. П родолжая таким образом, получим зависимость стоим ости проекта от его продолжительности. Рассмотрим на примере обобщение этого алгоритма на случай произвольного сетевого граф ика [5]. П р и м е р 3.2. П усть сетевой граф ик («верш ина — собы тие») имеет вид, изображенный на рис. 3.7. Рис. 3.7. Сетевой граф ик к примеру 3.2 Величины аь kj, d; и D j для всех работ приведены в табл. 3.1. Таблица 3.1. В еличины aj, kj, dj и D j для всех работ ai ki di Di (0 , 1) 2 0 3 2 6 (0 , 2 ) 45 5 5 8 ( 1 , 2 ) 7 1 1 4 (1 ,3 ) 23 4 1 5 (2 ,3 ) 2 0 6 1 3 1 ш аг. Полагаем х, = D ; для всех работ и определяем критический путь в сети. На рис. 3.7. в скобках у д у г указаны значения D j (первые числа) и k i (вторые числа) соответствую щ их работ. К ри ти чески й путь выделен толстыми дугами. Для критического п ути То = 13, стоимость проекта So = 15. Очевидно, что |
Для этого определим понятие «фронта работ», как максимального множества независимых работ, то есть таких, которые могут выполняться одновременно. В сети рис. 3.6. можно выделить три различных фронта работ: (1;2), (3;2), (3;4). Заметим, что эти фронты в определенном смысле упорядочены, а именно, фронт (1;2) расположен «левее» фронта (3;2), а последний «левее» фронта (3;4). Другими словами, для любых двух фронтов работы одного из них либо совпадают, либо предшествуют работам другого. Таким образом, сетям с упорядоченными событиями соответствуют сети с упорядоченными фронтами. Оптимизация по стоимости Задачи оптимизации комплексов работ по стоимости относятся к классу задач, для которых существуют достаточно эффективные алгоритмы. Сначала рассмотрим простой случай, когда сетевой график представляет собой последовательную цепочку работ. Примем, что зависимость стоимости от продолжительности является линейной для каждой работы: Si(Ti) = askjTi, dj < Ti £ Di, i = 1,n , где di минимально возможная продолжительность работы, Dj максимальная. Примем продолжительности всех работ равными максимальным ti = Di. При этом продолжительность проекта T = S D i i^t Если мы хотим сократить продолжительность проекта с минимальным увеличением стоимости, то очевидно, что в первую очередь необходимо сокращать продолжительность работы, имеющей минимальную величину коэффициента kj. Действительно, величина kj определяет 39 увеличение стоимости проекта при уменьшении продолжительности i-й работы на единицу. Продолжая таким образом, получим зависимость стоимости проекта от его продолжительности. Рассмотрим на примере обобщение этого алгоритма на случай произвольного сетевого графика [5]. Пример 3.2. Пусть сетевой график («вершина событие») имеет вид рис. 3.7. Величины kj, dj и D; для всех работ приведены в таблице. Таблица 3.1. Щ к. di Di (0, 1) 20 3 2 6 (0, 2) 45 5 5 8 (1, 2) 7 1 1 4 (1.3) 23 4 1 5 (2,3) 20 6 1 3 1 шаг. Полагаем Т = Dj для всех работ и определяем критический путь в сети. На рис. 3.7. в скобках у дуг указаны значения Dj (первые числа) и к[ (вторые числа) соответствующих работ. Критический путь выделен толстыми дугами. Для критического пути То = 13, стоимость проекта So = 15. Очевидно, что сокращать следует работу (1,2). При сокращении работы (1,2) на две единицы, критическими становятся работы (О, 2) и (1, 3), рис. 3.8, длина критического пути Ti = 11, стоимость проекта S = 17. 40 |