<< Предыдущая

стр. 5
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

? a i ? N1
i=1

l ?1
Определяем u c = N 1 ? ? a i , t i = min(? i ? ? l +1 )
i< l
i =1


? a?
? = min? T1 ; t 1 ; (? l ? ? l +1 ) l ? ,
? ul ?

и полагаем

?Wi ? ?a i , i = 1, l ? 1
?
x i1 = ?Wl ? ?u l , i = l .
?
?0 , i = l + 1 , m

Все операции с одинаковыми ?i снова объединяем в одну и
рассматриваем второй интервал аналогичным образом, и т.д.




28
3. ОПТИМИЗАЦИЯ ГРАФИКА
ФИНАНСИРОВАНИЯ МУЛЬТИПРОЕКТА


Пусть зависимости fi(ui) являются вогнутыми функциями количества
ресурсов ui. В этом случае при заданном общем объеме финансирования
на отрезке [0, T] максимум объема выполненных работ достигается при
равномерном поступлении средств. Чтобы доказать этот факт, рассмотрим
два периода длительности T1 и T2 с уровнями финансирования в них,
соответственно, N1 и N2. Пусть u1 = {ui1} и u2 = {ui2} - распределение
ресурсов в этих периодах. Соответственно по i-ому проекту будет
выполнен объем работ
fi(ui1) ?T1 + fi(ui2) ?T2.
Пусть теперь финансирование в объеме N1T1 + N2T2 осуществляется
равномерно на отрезке [0; T1+T2] с уровнем финансирования в единицу
времени
N 1T1 + N 2 T2
N= .
T1 + N 2
Рассмотрим следующее распределение ресурсов N по проектам
T1 T2
ui = u1 + u2 ,
T1 + T2 T1 + T2
i i


то есть, распределение ресурсов u есть выпуклая линейная комбинация
распределений u1 и u2. В силу вогнутости функций fi(ui) имеем:
? T1 2?
() ()
T2 T1 T2
fi (u i ) = fi ? ui + ui ? ? f i u1 +
1
f i u i2 .
? T1 + T2 T1 + T2 ? T1 + T2 T1 + T2
i


Таким образом, объем работ, выполненных в двух периодах при
равномерном поступлении средств fi(ui)(T1 + T2) не меньше (строго больше
при строго вогнутых зависимостях) объема работ при неравномерном
поступлении средств. Доказанный факт позволяет оптимизировать график

29
поступления ресурсов, делая поступления ресурсов более равномерными.
Это достигается за счет сдвига финансирования на более поздние
периоды.
Так, если N1 > N2, то ресурс в количестве
T1 N 1 + TN 2 T
(N1 ? N 2 )
?N = N 1 ? =
T1 + T T1 + T
целесообразно перенести из первого периода во второй. Здесь T -
неизвестная продолжительность мультипроекта во втором периоде.
Опишем алгоритм выравнивания графика поступления ресурсов в k

{}
периодах при заданных величинах Tq , q = 1, k .

1 шаг. Находим период p, начиная с которого количество ресурса
уменьшается от периода к периоду до некоторого периода l, то есть
Np-1 < Np > Np+1 > ... > Nl < Nl+1.
Определяем
l

? N q ? Tq
N ( p 1 l) =
q=p
l

? Tq
q=p


и полагаем N q = N( p 1l) для всех q = p, l . Все периоды с равными N q
˜ ˜

объединяем в один. Для нового графика процедуру повторяем, если
найдется участок с уменьшающимися уровнями Nq.
Пример. Пусть k = 5. Значения Nq, q = 1, 5 , приведены ниже:
1 2 3 4 5
q
15 10 7 9 12
Nq
2 3 4 3 2
Tq




30
1 шаг. Участок с уменьшающимися уровнями Nq включает периоды
с 1 по 3. Вычисляем:
30 + 30 + 28 7
N(1, 3) = =9 .
9 9
Получаем следующий график поступления ресурсов (после объединения
периодов с 1 по 3 в один):
1 2 3
q
97 9 12
Nq 9


9 3 2
Tq


2 шаг. Находим новый участок с уменьшающимися уровнями Nq.
Это участок из двух периодов 1 и 2. Вычисляем:
88 + 27 7
N(1, 2) = =9 .
12 12
Окончательно оптимизированный график расхода средств имеет вид:
1 2
q
7
9 12 12
Nq
12 2
Tq


Рассмотрим задачу оптимального распределения ресурсов с учетом
выравнивания графика их расхода. Сначала решаем задачу для исходного
графика поступления ресурса. Определяем минимальное время ?0
завершения мультипроекта. Производим оптимизацию графика
поступления ресурса и с новым графиком снова решаем задачу
?1
оптимального распределения ресурса. Пусть минимальная
продолжительность мультипроекта в этой задаче. Если ?1 < ?0, то
процедуру повторяем.



31
Пример (случай степенных зависимостей). Как было показано ранее,
в случае степенных зависимостей можно определить эквивалентный объем
мультипроекта
?
?n 1?
Wэ = ? ? Wi ? ? .
? i =1 ?
Пусть число периодов равно 2, причем T1 = 7, T2 = 9, N1 = 25, N2 = 9.
Возьмем ? = 1/2 и Wэ = 62. Продолжительность мультипроекта, как
нетрудно проверить, ?0 = T1 +T2 = 16.
Определяем график с равномерным поступлением ресурса на
отрезке [0, ?0]. Уровень ресурса равен:
T1 N 1 + T2 N 2
N (0, ? 0 ) = = 16 .
T1 + T2
Определяем новую продолжительность проекта:
Wэ 62
?1 = = = 15,5 .
N (0, ? 0 ) 4

Строим график с равномерным поступлением ресурса на отрезке [0, ?1]:
T1 N 1 + ( ? 1 ? T1 )N 2 175 + 8,5 ? 9 7
N (0, ? 0 ) = = = 16 .
?1 15,5 31
Новая продолжительность мультипроекта :
Wэ 62 31
?2 = = .
N (0, ? 0 ) 503

Описанный алгоритм можно представить графически (рис. 3.1).
На рисунке 3.1 изображены два графика. Один дает зависимость
продолжительности мультипроекта ? от уровня ресурса N (при его
равномерном использовании):
Wэ 62
?= = ,
N N
а второй - уровень равномерного поступления ресурса на отрезке [0, ?]:

32
25 ? T1 + 9 ( ? ? T1 ) 112
N= = 9+ .
? ?


N


16,5




16

?
15 15,3 15,5 16
Рис. 3.1.


Пересечение этих графиков определяет минимальную продолжительность
проекта и уровень равномерного использования ресурса при этой
продолжительности. Толстыми линиями показаны шаги приведенного
алгоритма. Как видно на рисунке 3.1, процесс сходится к оптимальному
решению с достаточной для практики скоростью.
Пример (линейный случай).
Для линейного случая выравнивание использования ресурса
целесообразно, если имеются периоды его неполного использования, то
есть
n

?ai < Nk .
i =1




33
Очевидно, что этот неиспользуемый ресурс необходимо перенести на
более поздние периоды, в которых ресурса не достаточно. Пусть,
например, графики поступления ресурса имеют вид:
1 2 3 4 5
k
2 3 3 2 4
Tk
2 18 5 4 6
Nk
4 54 15 8 24
TkNk


Данные о проектах приведены ниже:
1 2 3 4 5 6
i
10 15 8 7 12 18
Wi
2 3 1 1 3 2
ai
?i 5 5 8 7 4 9


Видно, что во втором периоде имеется избыток ресурса в объеме (18
- 12)?3 = 18. Переносим его в третий период, добавляя к уровню N3
величину 18/3 = 6. В процессе распределения ресурса, когда некоторые
операции уже выполнены, ситуация избытка ресурса может возникнуть
снова. Этот избыток также переносится на более поздние периоды, в
которых имеется дефицит ресурса.

<< Предыдущая

стр. 5
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>