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

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

ОГЛАВЛЕНИЕ

Следующая >>


16
акционерного общества). В таких случаях кроме выбора пакета проектов и
определения объема финансирования каждого проекта, необходимо
определить схему его финансирования. Заметим, что под схемой
финансирования мы понимаем не только способы получения средств на
реализацию проекта (собственные средства, кредиты, выпуск ценных
бумаг и т.д.) но и приоритетность финансирования объектов по этим
способам. Рассмотрим простейшую задачу, когда имеется только один
способ финансирования и определен портфель финансируемых проектов.
Требуется определить приоритетность финансирования проектов в случае
нехватки средств. Обозначим Ф(S) - функцию распределения объема
финансовых ресурсов который можно использовать для финансирования
проектов, Si, как и ранее, объем финансирования i-го проекта. Если задана
приоритетность проектов (i1, i2, ... , im), то вероятность полного
финансирования проекта ik определяется выражением
?k ?
Pik = 1 ? Ф? ? S iq ? . (1.13)
? q =1 ?

Ожидаемый доход при этом равен
? ??
?k
m m

? Fiq Piq = ? Fik ?1 ? Ф? ? Siq ? ? .
? q =1 ? ?
? ?
?
q =1 k =1


Задача заключается в определении перестановки ? = (i1, i2, ... , im), такой
что величина
?k ?
m

? Fik ? Ф? ? S iq ?
? q =1 ?
k =1

минимальна. Эта задача аналогична задаче минимизации упущенной
выгоды. В линейном случае, когда Ф = a + bS, оптимальная перестановка
соответствует упорядочению по убыванию Fi /Si (удельный доход).




17
2. РАСПРЕДЕЛЕНИЕ РЕСУРСОВ
ПО НЕЗАВИСИМЫМ ОПЕРАЦИЯМ


Рассмотрим мультипроект из n независимых проектов. Каждый
проект в агрегированном виде описывается как операция двумя
характеристиками - объем проекта Wi и зависимость скорости реализации
проекта wi(t) = fi(ui(t)) от количества ресурсов ui(t) в момент t. Объем
проекта, скорость и момент его завершения Ti связаны соотношением:
Ti

? f i [ u i ( t )]dt = Wi (2.1)
0


Пусть задана величина ресурсов N(t) на реализацию мультипроекта.
Задача заключается в распределении этих ресурсов по отдельным
операциям так, чтобы мультипроект был реализован за минимальное
время T = max Ti . В случае, если N(t)=N в любой момент времени
i

(равномерное поступление ресурсов во времени) и fi(ui) - вогнутые
функции ui, задача распределения ресурсов детально исследована [1, 2, 3].
Показано, что оптимальное распределение ресурса имеет следующие
свойства:
а) каждая операция выполняется при постоянном уровне ресурсов
ui(t) = ui, i = 1?n, t?[0, T], а значит с постоянной скоростью;
б) все операции заканчиваются одновременно.
Если Т - момент завершения всех операций, то wi = Wi/T постоянная
скорость i-ой операции. Если обозначить через ?i(wi) - функцию, обратную
функции fi(ui), то ui = ?i(Wi/T) определяет количество ресурсов, требуемое
для завершения операции i за время T. Минимальное время T
определяется теперь из уравнения



18
? Wi ?
n
? ? T?
?i ? ? = N . (2.2)
i =1


Пример 1.1. Пусть fi(ui) = ui?, 0 < ? < 1, i = 1?n. Тогда ?i(wi) = wi1/? .
Уравнение (1.2) примет вид:
1
?
? Wi ?
n
?? T ? =N.
??
i =1

Решая это уравнение, получим:
?
?n 1?
? ? Wi ? ?
? i =1 ?
Tmin = .
N?
?
?n 1?
? ? Wi ? ?
Величина называется эквивалентным объемом
Wэ =
? i =1 ?

мультипроекта. Действительно, мультипроект можно представить в виде
одной операции объема Wэ с такой же зависимостью f(u) = u1/? .
Пример 1.2. Пусть fi(ui) = ui/(ui + a), i = 1?n. Уравнение (1.2) примет
вид:
n
Wa
? T ? iW =N.
i =1 i


В данном случае для определения Tmin применяются численные методы.
Для случая двух операций решение можно получить в аналитическом
виде, решая уравнение
W1 W2 N
+ =
T ? W1 T ? W2 a

Пусть N(t) - кусочно-постоянная функция времени, N(t) = Nk,
˜ ˜ ˜
t?[ Tk?1 , Tk ), k = 1, p , T0 = 0. Зафиксируем некоторые k и рассмотрим
˜
задачу о возможности реализации мультипроекта за время, не большее Tk .
Обозначим xiq объем i-ой операции, выполняемой в интервале q.
Очевидно, что



19
k
? x iq = Wi . (2.3)
q =1


Поскольку в интервале [Tq-1, Tq) ресурсы поступают равномерно, то
величины {xiq} в оптимальном решении связаны соотношением:
? x iq ?
n
? ? i ? T ? = N q , q = 1, k ? 1 , Tq = Tq ? Tq ?1
˜˜
? ?
? q?
i =1


а для последнего интервала имеет место следующее условие:
? x ik ?
n
? ? T ? = N k , T = T ? Tk ?1
˜˜
?i ?
?
i =1

где T - время завершения всех операций.
Для получения необходимых условий оптимальности, применим
метод множителей Лагранжа. Функция Лагранжа имеют вид:

? k ?1 ? n ?
˜ n ?k ? x iq ? ?n ?
?x ?
L = T ? ??i ?? ? x iq ? Wi ? + ? µ q ? ? ? i ? ? ? N q ? + µ k ? ? ? i ? ik ? ? N k ?
? ??
? ? ? ii =1 ? T ? ?
? q =1 ? ii =1 ? Tq ?
? q =1 ?
i =1

,
где ?i, µq - множители Лагранжа. Дифференцируя по xiq, получим
? x iq ?
µq
??? ? = ? i , q = 1, k ,
Tq i ? Tq ? (2.4)
? ?

при q = k, Tq = T.
Обозначим hq вектор, с компонентами hiq = ?i’(wiq), i = 1, n . Из (2.4)
следует, что
h q = ? q h 1 , q = 2, k , h 1 = {h i }, ? 1 = 1

то есть вектор h является в определенном смысле инвариантным во
времени (его направление не меняется от интервала к интервалу, а
меняется только его длина).
Разрешая уравнение hiq = ?i’(wiq) относительно wiq, получим
w iq = ? i ( h iq ) = ? i ( ? q ? h i )

[ ]
u ik = ? i ( w ik ) = ? i ? i ( ? k ? h i ) .

20
Полученное свойство оптимального решения позволяет свести задачу
распределения ресурсов к решению системы нелинейных уравнений с (n +
k) неизвестными {hi}, i = 1, n , {?q}, и T:


? ? i [? i ( ? q ? h i ) ] = N q ,
n
q = 1, k (2.5)
i =1

k ?1

? ? i ( ? q ? h i ) ? Tq + ? i (? k ? h i ) ? T = Wi , i = 1, n . (2.6)
q =1

Операции мультипроекта будем называть однотипными, если wi =
f(ui), то есть если все операции имеют одинаковые зависимости скорости
от ресурса.
ui
Пример1.1. Пусть w i = , i = 1, n , T1 = 10, N1 = 25, N2 = 60, w1 =
ui + 5
20, w2 = 26. Находим:
5w i
u i = ? i (w i ) = i = 1, n
,
1? wi
5
h i (w i ) = i = 1, n .
,
(1 ? w i ) 2



Заметим, что инвариантность по направлению вектора h
эквивалентна в данном случае инвариантности по направлению вектора (1-
w). Поэтому

(1 ? w ) = ? ? (1 ? w) ,
2



где через w обозначен вектор скоростей в первом интервале, а через ? -
значение ?q во втором интервале.
Выпишем систему уравнений:
5w 1 5w 2
+ = 25
1 ? w1 1 ? w 2




21
5 (1 ? ? (1 ? w 1 )) 5 (1 ? ? (1 ? w 2 ))
+ = 60
? (1 ? w 1 ) ? (1 ? w 2 )

10w 1 + T[1 ? ? (1 ? w 1 )] = 20

10w 2 + T[1 ? ? (1 ? w 2 )] = 26 .

Первые два уравнения после несложных преобразований
приводятся к виду:

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

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

ОГЛАВЛЕНИЕ

Следующая >>