2.6. Алгоритм решения задачи верхнего уровня.

Определим при i = 1, ..., m на отрезке 0 < x < max xмини-

0< J < N (i) ;

мальную вогнутую функцию f (x) , для которой f (x) > f (x) при

Vx : 0 < x < max xH, и рассмотрим задачу максимизации функ-

0< jции X fi (xi) при ограничениях X xi < K , 0 < xi < max xn,

i=1 i=1 0i = 1, ..., m.

Заметим, что функции f (x) вогнуты и кусочно-линейны. Выбираем проект с номером i1, для которого функция f (x) имеет наибольший наклон первого звена ломаной графика.

Вкладываем в проект i1 величину средств a1 = min[ xi, K ], где

x1 - первая точка излома функции f (x) .

Если a1 < K, то оптимальное распределение средств найдено. Если a1 > K, то рассмотрим новую задачу с K = K - a1, где

f (x) = f (a1 + x) , а остальные функции остаются прежними.

Выбор проекта и величины вложения в него осуществляются аналогично и т.д.

Алгоритм завершает свою работу либо после исчерпания капитала K, либо после того, как вложение по каждому проекту i достигнет максимальной величины max xij .

0< jЕсли найденное решение x0,i = 1,...,m удовлетворяет условию f(x0) = f(x0), i = 1,..., m, то решение x0,i = 1,...,m будет

являться текущим решением исходной задачи, для которого рассчитывается значение целевой функции.

Для данного решения необходимо проверить условие неотрицательности баланса счета заказчика - решить задачу нижнего уровня (алгоритм решения задачи нижнего уровня приведен ниже в подразделе 2.7).

Предположим, что при некотором i1 выполнено строгое нера-венство f (x°) > f (X,0 ), и x° принадлежит минимальному отрезку [ x^, X,2 ], где x^, X,2 G Xi . Тогда исходная задача разбивается на две подзадачи с измененными ограничениями по проекту i1:

2

< xi < max xi j во второй.

1 0< j < N ft) 1

Каждая из подзадач решается указанным выше способом и так далее.

f (x0) = f (x0), i = 1,..., m, то оценка снизу для максимума целевой

функции возрастает.

Для реализации данного алгоритма введем следующие обозначения.

тг D r»mxmax(N(i))xn+1

Пусть заданы матрицы R = {r. }G R и

Cc Л ) nfflxmax(N(i))xn+1

= {Cj} G R , где m - количество инвестиционных

проектов, N(i) - количество вариантов реализации для каждого проекта, T - срок реализации каждого варианта.

Элементы rj матрицы R определяют величины возвратов для варианта j по проекту i в момент времени t = 0, ..., T.

Элементы ci матрицы C определяют величины затрат для варианта j по проекту i в момент времени t = 0, ., T.

Матрицы R = {rj } G Rm xmax( N (i ))x n+1 и C = {cj } G Rm xmax( N (i ))xn+1

mxmax(N(i))

определяют элементы матриц X = {x. }G R и

mxmax(N(i))

F = {Jij} G R , где x. - минимальная величина средств,

необходимых для реализации варианта j по проекту i, J. - значение приведенной стоимости проекта i в случае выбора варианта j. Матрицы X и F определяют значения кусочно-постоянной

0 < xi < x1 в первой подзадаче и xf < x, < max x, . во

0, 0 < x < xn

функции^): f ( x) =

fi, x. < x < x.+J, j = N(i) -1.

fiN(i), x — xiN(i)

Определим характеристики минимальной вогнутой функции fi (x), для которой f (x) — f (x) при Vx : 0 < x < max x..

0< j < N (i) J? Обозначим S = {S'j} - матрица, элементы которой определяют точки излома функции fi (x) . Элементы матрицы S = {s.}

вычисляются следующим образом.

Обозначим T = {t. } е Rmxmax( N (,)), где

ft ¦ ¦ "

;J = >' = !>•••>m;J =!>•••>NО - тангенсы угла наклона прямой,

xj

проходящей через начало координат и точку с координатами

( xiJ , f iJ ) - точку разрыва функции fi(x).

Обозначим Ji1 - позиция максимального элемента строки i матрицы T. Зафиксируем первый столбец матрицы S: si1 = Ji1 , i = 1, ..., m. Переместим начало координат в точку (x.4, _/4) и осуществим перерасчет элементов матрицы T:

t.1 = ^^, i = 1,..., m.; J = J1 +1,..., N (i).

xJ — xj]

Обозначим Ji2 - позиция максимального элемента строки i матрицы T. Зафиксируем второй столбец матрицы S: s, 2 = Jf, i = 1, ..., m, и т.д. Результатом вычислений является матрица S ={sj}.

Обозначим N'(i) - число итераций для строки i матрицы S = {S'j} - число элементов в строке i матрицы S. Обозначим

X' = {xi } е Rmxmax(N'(i)) и F' = {f} е Rmxmax(N'(i)), где x\} = xSJ ,

f \J = f'Sj , i = 1, m и J = 1, ..., N'(i).

Таким образом, матрицы X' = {xi } е Rmxmax(N(')) и

F' = {f} е Rmxmax(N (')) определяют функции fi (x) : f ' - f'

Г ,1 • x + f \,x'i < x < x'i+1, j = 1,...,N'(i) -1

-y- -y* j j j

x ij+1 x ij f ',1

f (x) =

x

• x,0 < x < x'. f iN'(i) , x — x iN'(i) )m xmax( N '(i))

f ij +1 f ij

Определим матрицу T' = {tV. } G R- ---- - характеризую-щую углы наклона звеньев графика функции fi (x) :

, i = 1,..., m; j = 1,..., N '(i) -1

x ij+1 x ij

^ =

0,i = 1,...,m; j = N'(i),...,max(N'(i)) -1;N'(i) < max(N'(i)) -1 Матрица T' = {t'. } G R

mxmax( N '(i))

определяет тангенсы углов наклона для графиков функций fi (x) . При этом в строке i элемент j матрицы T' определяет тангенс угла наклона для звена j графика функции fi (x) .

Определим векторы X0 = {x0} и F0 = {J,0}, i = 1, ..., m, где x,0 определяет общую величину инвестиций в проект i после каждой итерации алгоритма решения задачи верхнего уровня, fi - определяет отдачу от проекта i при инвестициях в размере xi0 .

Начальные условия: x,0 = 0 , f° = 0, i = 1, ... , m.

На первой итерации алгоритма определяем позицию максимального элемента в первом столбце матрицы T' = {tV. } . Обозначим i1 - номер строки, в которой находится максимальный элемент, i1 - номер проекта, для которого функция fi (x) имеет наиболь- ший наклон первого звена ломаной графика, xVj - первая точка излома функции fi ( x) .

Обозначим C = {с,},' = 1,...,m - вектор, элементом которого является номер рассматриваемого варианта для проекта i (номер варианта определяется в терминах матрицы X' - не совпадает с номерами вариантов для матрицы X: для перехода к номерам вариантов в исходных терминах задачи необходимо использовать матрицу S = {s.

На каждой итерации алгоритма индексируется номер варианта для соответствующего проекта i1. На первой итерации ct = 1, с, = 0,' Ф ' . Вкладываем в проект ii величину средств

a1 = min[x'. j, K], x° = x° + a1 - инвестиции в проект i1 увеличены на a1.

Если a1 < K , то f 0 = f ''ji - фиксируем увеличение отдачи от инвестиций и производим новую итерацию алгоритма с изменен-ными начальными условиями: K = K - a1 (уменьшаем размер свободного капитала), t\ . = t\ .+1, j = 1,..., N' ('1) — 1,

x'И = x'1 j+1—a1, J =1'...'N' ('1)—1, f ',1 J = Л J+1,

J = 1,..., N' ('1) — 1, (сдвигаем график функции fi (x) :

fi (x) = fi (a1 + x)), N' (' ) = N' ('1) — 1 (уменьшаем количество рассматриваемых вариантов по проекту i1).

Если a1 = K, то определено текущее распределение средств

X0 = {x0}; отдача от инвестиций F0 = {f°}; вектор

C = {с,-},' = 1,...,m .

Необходимо проверить, удовлетворяет ли распределение следующему условию: f (x0) = f'(x0)при всех i = 1, ..., m.

Из определения функций fx) и fi (x) следует, что равенство выполняется тогда и только тогда, когда элементы вектора

X0 = {x0} совпадают с точками разрыва функцииf(x) - элемента

ми строк матрицы X' = {xV. } G Rmxmax(N(i)). Таким образом,

ij

f (x0) = f (x0) о x, = x\ci Vi = 1,...,m.

Проверим выполнение данного условия:

Если x10 = x\c Vi = 1,...,m , то найдено текущее решение задачи нижнего уровня:

X0 = {x0} , i = 1, ..., m - распределение инвестиций;

F0 = {f0}, i = 1, ..., m - отдача от инвестиций;

m

S = X fi - суммарная отдача от инвестиций - целевая функ-

i =1

ция задачи;

J = {j1,..., jm} - номера вариантов, реализуемых по проекту i, где j* = sщ .

Для найденного решения необходимо осуществить проверку неотрицательности баланса счета заказчика - проверку существования решения задачи нижнего уровня.

Если x0 Ф x\c при i = i2, то распределение X0 = {x0} не является текущим решением задачи нижнего уровня.

Определим минимальный отрезок [x1, x2], которому принадлежит точка x, , где x1, x2 - точки разрыва функции f (x) .

Точки разрыва функции fi2 ( x) определяются матрицей X = {x. } G Rmx max( N (l)), следовательно x1, x2 совпадают с соответствующими элементами строки i2 матрицы X.

Пусть xl = x,2I1 , x2 = xi2 j+1 , где xi2I1 , xi2 j+1 - элементы матрицы X. Тогда исходная задача разбивается на две подзадачи с измененными начальными условиями - происходит ветвление:

Левая ветвь: N(i2) = j (уменьшаем количество рассматри-ваемых вариантов по проекту i2). Значения элементов матриц

X = {x,j} и F = {f'j} остаются прежними для i = 1, ..., m, J = 1,..., N (') (с учетом изменения количества вариантов по проекту '2).

Правая ветвь: x'2J = x'2J + j J = 1,..., N(i) — J1 — 1,

A J = f-2 j+J1+l, J =1'".'N (i) — J1 —1, (сдвигаем графики функций

f2(x) и f,2(x)), K = K — x'2j+j x° = x'2j+J1 +1 (вкладываем в проект i2 величину средств xi2.+, +1 : считаем выбор данного проекта приоритетным в начальный момент).

Для каждой ветви производится расчет матриц S = {s.},

X' = {xi } е Rmxmax(N'(l)) и F' = {f} е Rmxmax(N'(l)), определяющих соответствующие функции fi (x), и вычисляются вектора X0 = {x0} и F0 = {f0} (при этом для правой ветви элемент i2 вектора X0 = { xi0} - ненулевой).

Расчеты данных величин производятся аналогично вышеописанному алгоритму.

В случае если для распределения подзадачи не выполняется

условие x,0 = x\c , "' = 1,...,m , то происходит дальнейшее ветвление подзадачи.

Результатом ветвления является дерево, в листьях которого будут определены текущие решения (X0, F0, S, J *) каждой подзадачи, для которых проверяется существование решения задачи нижнего уровня.

Построение дерева и выбор оптимального решения, на котором достигается максимум целевой функции, осуществляется рекурсивно.