|
выполняющ иеся ресурсами jr o вида. О бозначим через Xjg —объем 1-ой работы, выполняемый в s -o m интервале, cjs максимальный объем 1-ой работы, которы й м ожно выполнить в S-OM интервале. Задача заключается в определении {х,,}, i = 1,п , S = 1,Т , так, чтобы 116 X . < С „ , i e P „ s = l, T Z x , < w , , i = i,n (1.1) где W i объем i -ой работы, seR. S X j , j = l , m , (1.2) a суммарный объем вы полненны х работ jr o вида (1-3) 5 -1Ic P ,, был максимален. О граничимся случаем независимых работ. Для реш ения задачи определим двудольный граф G (X ,Y ). В ерш ины i € X соответствую т работам, а верш ины S е Y соответствую т интервалам. П ропускны е способности верш ин i е X равны объектам W i соответствую щ их работ, А пропускны е способности верш ины S е Y равны объему работ, которы й м ож но будет вы полнить в соответствующ ем интервале, то есть Qs. П ропускны е способности д у г (i, s), i = l , n , s б R; равгш Cjj. Задача свелась к определению максимального потока в полученной сети, что соответствует минимальному объему работ, отдаваемых на субподряд. О пиш ем алгоритм определения потока максимальной величины, основанны й на методе сетевого программирования. 3.2. Задача о максимальном потоке Рассмотрим произвольную сеть без контуров на д угах (i, j), которой заданы пропускны е способности С ц> 0. К а к известно, потоком в сети, называ |
Выполняем работу 3 в первом интервале в полном объеме поскольку 2 Ьз < b j. Далее выполняем работу 1 в объеме 4— в первом интервале и завершаем ее во втором интервале. Также во втором интервале выполняем работу 2. Работы 4,5 и 6 начинать нельзя. Поэтому ресурсы использзтотся не полностью (вариант 1). 2 шаг Определяем а =21 = 1 -1 , N ,= 1 8 ^ . ‘ 60 30 ’ 2 В третьем интервале выполняем работу 4 объеме 18-^. В четвертом интервале завершаем работу 4 (в объеме 5-^) и выполняем работу 6 в объеме 13. В пятом интервале завершаем работу 6 в объеме 1 и выполняем работу 5 в объеме 17—, которую завершаем в шестом интервале в объеме 18^. 2 2 Учтем теперь ограничения С,, на максимальные объемы работ, выполняемых в интервалах. Ограничимся случаем независимых работ. Для решения задачи определим двудольный граф G(X,Y). Вершины ie X соответствуют работам, а вершины s s Y соответствуют интервалам. Пропускные способности вершин i 6 X равны объектам W. соответствующих работ, А пропускные способности вершины se Y равны объему работ, который можно будет выполнить в соответствующем интервале, то есть aQ ,. 72 Пропускные способности дуг (i, s), i = l,n , seR. равны С,,. Задача свелась к определению минимального а , такого что максимальный поток в полученной сети равен ^ W , , что соответствует выполнению всех работ I проекта. Опишем алгоритм определения потока максимальной величины, основанный на методе сетевого программирования. |