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

два периода длительности T1 и T2 с уровнями финансирования в них,

1 12 2 соответственно, N1 и N2. Пусть u = {u. } и u = {u. } - распределение

ресурсов в этих периодах. Соответственно по i-ому проекту будет

выполнен объем работ

fi(u.1) -T1 + fi(u.2) -T2. Пусть теперь финансирование в объеме N1T1 + N2T2 осуществляется равномерно на отрезке [0; T1+T2] с уровнем финансирования в единицу времени

N1T1 + N2T2

N =

T + N2

Рассмотрим следующее распределение ресурсов N по проектам

Ti 1 Тт 2 u. = 1—uj + 2—u2,

. Т1 + Т2 . Т1 + Т2 .

то есть, распределение ресурсов u есть выпуклая линейная комбинация

12

распределений u и u . В силу вогнутости функций f.(u.) имеем:

Т1 /л Т

г Т 1 Т л

Т1 + Т2 v \' Т1 + Т

Ti + т2 т1 + т

fi (ui ) = fi ^"Vu1 +—1Vu2 ^-Vfi (ui )+zrVfi (u2

Va1^a2 А1 ^ а2 У а1 ^ а2 А1 ^ а2

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

поступления ресурсов, делая поступления ресурсов более равномерными. Это достигается за счет сдвига финансирования на более поздние периоды.

Так, если N, > N2, то ресурс в количестве

AN = N- -TNl+INI = (N, -N2)

1 T, + T T, + Tv 1 \'

целесообразно перенести из первого периода во второй. Здесь T - неизвестная продолжительность мультипроекта во втором периоде. Опишем алгоритм выравнивания графика поступления ресурсов в k периодах при заданных величинах {Tq}, q = 1, k.

1 шаг.

Np-i < Np > Np+i > ... > Ni < Ni+i.

Определяем

XXX Nq ¦ Tq

q=p

N(p-i) =

?

X Tq

q=p

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

объединяем в один. Для нового графика процедуру повторяем, если найдется участок с уменьшающимися уровнями Nq.

Пример. Пусть k = 5. Значения Nq, q = 1,5, приведены ниже:\r\nq 1 2 3 4 5\r\nNq 15 10 7 9 12\r\nTq 2 3 4 3 2\r\n

1 шаг. Участок с уменьшающимися уровнями Nq включает периоды с 1 по 3. Вычисляем:

N(1,3) = 30 + 30 + 28 = 97.

9 9

Получаем следующий график поступления ресурсов (после объединения периодов с 1 по 3 в один):\r\nq 1 2 3\r\nNq 97

у 9 9 12\r\nTq 9 3 2\r\n2 шаг. Находим новый участок с уменьшающимися уровнями Nq. Это участок из двух периодов 1 и 2. Вычисляем:

N(1,2) = 88±j2Z = 9^. 12 12

Окончательно оптимизированный график расхода средств имеет вид:\r\nq 1 2\r\nNq 9J- y 12 12\r\nTq 12 2\r\nРассмотрим задачу оптимального распределения ресурсов с учетом выравнивания графика их расхода. Сначала решаем задачу для исходного графика поступления ресурса. Определяем минимальное время D0 завершения мультипроекта. Производим оптимизацию графика поступления ресурса и с новым графиком снова решаем задачу оптимального распределения ресурса. Пусть D1 минимальная продолжительность мультипроекта в этой задаче. Если D1 < D0, то процедуру повторяем.

Пример (случай степенных зависимостей). Как было показано ранее, в случае степенных зависимостей можно определить эквивалентный объем мультипроекта

( n 1/ V Wэ =ly W/a .

V i=1 0

Пусть число периодов равно 2, причем Т1 = 7, Т2 = 9, N1 = 25, N2 = 9. Возьмем а = 1/2 и W^, = 62. Продолжительность мультипроекта, как нетрудно проверить, А0 = Т1 +Т2 = 16.

Определяем график с равномерным поступлением ресурса на отрезке [0, А0]. Уровень ресурса равен:

N(0, А0) = ^ = 16.

Т1 + Т2

Определяем новую продолжительность проекта:

А, = , W = 62 = 15,5.

Строим график с равномерным поступлением ресурса на отрезке [0, А1]:

T1N1 +(А 1 - Т1 )N2 175 + 85 • 9 7

N(0, А0) = 1 1 v 1 ^^ = \' = 16—.

А1 15,5 31

Новая продолжительность мультипроекта :

А = W., = 62У31 2 ~ 4N(0, А0) = л/503 .

Описанный алгоритм можно представить графически (рис. 3.1). На рисунке 3.1 изображены два графика. Один дает зависимость продолжительности мультипроекта А от уровня ресурса N (при его равномерном использовании):

л W 62

А = э -

vn vn\'

а второй - уровень равномерного поступления ресурса на отрезке [0, А]: 32

Рис. 3.1.

= 25 • T + 9 (А-T1) = 9 + 112 А А

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

Пример (линейный случай).

Для линейного случая выравнивание использования ресурса целесообразно, если имеются периоды его неполного использования, то есть

n

X ai < Nk.

i=1

Очевидно, что этот неиспользуемый ресурс необходимо перенести на более поздние периоды, в которых ресурса не достаточно. Пусть, например, графики поступления ресурса имеют вид:\r\nк 1 2 3 4 5\r\nтк 2 3 3 2 4\r\nNk 2 18 5 4 6\r\nTkNk 4 54 15 8 24\r\nДанные о проектах приведены ниже:\r\ni 1 2 3 4 5 6\r\nWi 10 15 8 7 12 18\r\nai 2 3 1 1 3 2\r\nti 5 5 8 7 4 9\r\nВидно, что во втором периоде имеется избыток ресурса в объеме (18 - 12)-3 = 18. Переносим его в третий период, добавляя к уровню N3 величину 18/3 = 6. В процессе распределения ресурса, когда некоторые операции уже выполнены, ситуация избытка ресурса может возникнуть снова. Этот избыток также переносится на более поздние периоды, в которых имеется дефицит ресурса.

1 шаг.

2 4

u3 = 3; u6 = 3.

Имеем:

= 2 = 2+4 = 31

Х31 = 3, Х61 = 2 + 3 = 33

2 шаг. Выполняем все проекты с максимальной скоростью. Имеем:

3 шаг. Поскольку N3 = 11, то все проекты выполняются с

максимальной скоростью wi = ai, кроме проекта 5, для которого u5 = 2. Полностью завершаются проекты 1, 2 и 5. Поэтому образуется избыток ресурса в объеме 8 ед., который переносим в четвертый период, увеличив N4 до N4 = 8.

и определяется моментами окончания 3-го и 6-го проектов.

4 шаг. В четвертом периоде также избыток ресурсов, поскольку не выполнены только проекты 3, 4 и 6. Время завершения комплекса равно