Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Информационные технологии в экономике
| Гламаздин Е.С., Новиков Д.А., Цветков А.В.. Управление корпоративными программами: информационные системы и математические модели, 2003 | |
2.7. Алгоритм решения задачи нижнего уровня. |
|
|
Текущим решением задачи верхнего уровня является набор проектов (с соответствующим выбором подрядчиков), реализация которых возможна при ограничении на общий объем инвестиций K = PVG+.
Для выбранного набора проектов необходимо определить возможность их реализации при ограничениях на состояние счета заказчика. Условие неотрицательности баланса счета заказчика формулируется следующим образом: t m t "t = 0,...,T XgV + XX(>j -s y > 0, к=0 i=1 к=0 t где X gkv - приведенная величина кредитного потока на момент к=0 m t времени t, XX(r'-' ~ c'-')v - суммарный баланс по всем проек- i=1 к=0 j 'Ji там на момент времени t. Текущее решение задачи верхнего уровня определяет следующие параметры: X0 = {x0}, i = 1, ..., m - вектор, элементы которого определяют распределение инвестиций в проект i; F0 = {f0}, i = 1, ..., m - вектор, элементы которого определяют m отдачу от инвестиций по проекту i; S = X fi - суммарная отдача i =1 от инвестиций - целевая функция задачи, J * = {j*,..., j*m} - номера вариантов, реализуемых по проекту i (в случае, если по проекту i выбран вариант с номером, j > j* е J *, а для остальных проектов номера вариантов принадлежат J* , то реализация такого набора проектов невозможна при заданных ограничениях на объем инвестиций). Если для решения (X0, F0, S, J *) выполняется условие неотрицательности баланса счета заказчика, то данное решение является решением задачи нижнего уровня и происходит возврат на верхний уровень. Заметим, что решение, характеристики которого заданы вектором J' = j ,..., jm }, где j\ < j* при "i = 1,...,n, также удовлетворяет ограничениям на общий объем инвестиций, так как элементы соответствующего вектора X' = {xV }, i = 1,...,m не превосходят элементы вектора X0 = {x0}, i = 1, ..., m, а элементы вектора F' = {f V } не превосходят элементы вектора F0 = {f0}. Таким образом, текущее решение задачи верхнего уровня (X0, F0, S, J *) определяет множество D допустимых решений при ограничении на общий объем инвестиций, причем решение (X0, F0, S, J *) является на множестве D лнаилучшим, так как сумма S является на данном множестве максимальной. В случае, если текущее решение задачи нижнего уровня (X0, F0, S, J ) не удовлетворяет ограничениям на состояние счета заказчика, необходимо решить задачу нижнего уровня, т.е. определить лнаилучшее решение (XFS, J') е D, на котором выполняется условие неотрицательности счета заказчика - решение, для которого значение S будет максимальным на множестве допустимых решений D. Решение (X', FS, J') е D будет являться решением соответствующей подзадачи верхнего уровня. Выбор оптимального решения задачи, на котором достигается максимум целевой функции, будет осуществляться с учетом соответствующего значения величины S . Задача нижнего уровня решается следующим образом. Вектор J ={j1,...,Jm} определяет фиксированный набор вариантов, из которых осуществляется выборка решения (X', FS, J') е D задачи нижнего уровня. В соответствии с начальными условиями заданы матрицы X = {x. } е Rmxmax(N(i)) и F = {A } е Rmxmax(N(')). Элементам строки i данных матриц соответствуют точки разрыва кусочно- постоянной функции fi(x). Так как функции fi(x) являются неубывающими, то элементы строк матрицы F = {f. } е Rmxmax(N(l)) упорядочены по возрастанию. Обозначим N ('), ' = 1,...,m - количество вариантов реализации, которые не были отброшены для проекта i на верхнем уровне: N (i) = J* . Тогда решение задачи верхнего уровня (X0, F0, S, J*) определяет выборку элементов матрицы X = {x. }е Rmxmax(N(i)) и F = {fj}еRmxmax(N(i)) при i = 1,...,m;j = 1,...,N'(i), где x. - величина инвестиций в проект i в случае выбора варианта реализации с номером J; f. - значение приведенной стоимости проекта i (отдача от инвестиций) в случае выбора варианта j. Обозначим J1 = {j1}, где j1 = j* -1 (i = 1,...,m): вектор, компоненты которого определяют величину инвестиций и отдачу от инвестиций в проект i в случае выбора варианта с номером Х* 1 J, -1 Введем вспомогательный вектор J2 = {j2), i = 1,...,m . Начальные условия: J2 = {J2} = 0. Обозначим S1 = {S1}, i = 1,...,m - вектор, компоненты которого определяют суммарную отдачу от инвестиций в случае, если для проекта i выбирается вариант с номером ji1 , а по остальным проектам выбираются варианты с номерами J*: s 1 = i = m, где S1 = x fkN-ik)+fNж (i) Х 1? k ? m,k * i Пусть Smax - максимальная суммарная отдача от инвестиций, Smax = max S,1, при этом i1 = (iLs1 = Smax) - номер проекта, при 1?i ? m котором достигается максимальное значение S1 . Определим: X' = {xi}, где Х, = x<0 при i = 1,ХХХ,mi * i'1, x- = xhN,(h)-15 F' = {fi,}> где f' = f0 пРи i = ^^m,i *i1, f = ANC,)-1, m S' = X // , S = Smax , J' = { j } , где Д = N' (i1) - 1. i=1 Тогда решение (X', F', S', J') является лнаилучшим на множестве D за исключением решения (X0, F0, S, J ). Проверим выполнение условия неотрицательности баланса счета заказчика для решения (X', F', S', J'): "t = 0,..., n t m t +ZK1;.- <>к > o. к=0 i=1 к=0 Если условие выполнено, то решение (XFSJ') является решением задачи нижнего уровня. Если условие не выполняется, то задача нижнего уровня разбивается на две подзадачи с измененными начальными условиями - происходит ветвление задачи: Левая ветвь: Считаем текущим решением задачи верхнего уровня решение (XFSJ'). При этом для решения (XFSJ') условие неотрицательности баланса счета заказчика не выполняется (условие проверено на предыдущем этапе). Тогда элементы матрицы F = {f. } е Rmxmax(N(l)); у, = o при k=1,...,N'('1)- j . Элементы матрицы X = {x.}еRmxmax(N(i)); x. . = 0 при к = 1, ..., N' ('1) - ji , N' ('1) = J\ , при ' * '1 вели- '1J'2 +k 1 1 чины N (') остаются прежними. Определяем вектора J1 = {j1}, S1 = {s1}: (' = 1,...,m) при данных начальных условиях: J1 = {j1} , при этом j1 = jf при J2 *^ Sl = К}: при ': J2 = ^ = X 2 fm,k) + Л,(0 1< к < m,k *';': J2 = 0 при ': j,2 * 0, s1 = 0. Определяем величины Smax = max s,1, i1 = ('Is1 = Smax). Если 1 S1 = {s1} = 0, то решение данной подзадачи не существует. Иначе в соответствии с вышеописанным алгоритмом вычисляем решение (X", F", S", J") (наилучшее решение на множестве D, которое определяется решением (XFSJ')). Проверяем выполнение условия неотрицательности баланса счета заказчика для решения (X'F",S", J'') . Если условие выполнено, то решение (X'F", S", J") является текущим решением задачи нижнего уровня.? - Если условие не выполнено, то необходимо осуществить дальнейшее ветвление задачи. Правая ветвь: считаем, что для проекта с номером i; рассматривается только вариант с номером j* . Изменяем вектор J2 = {J2) : J,2 = J* . Изменяем матрицы X = {x. } е Rmxmax(N(i)) и 77 ( -f T>m xmax(N(i)) ~ F = {Jij} е R , определяющие величину инвестиций и отдачу от инвестиций в проект i в случае выбора варианта реализации с номером J: fh; = f * , у.. = 0, J = 2, ..., J* - * xi 1 = xi j* , xi j = 0 , j = 2, ., ji - 1. 'l1 г;J* ' ';J ,J 1 Изменяем значения N(i): N'(i;) = 1, при i * i; величины N' (i) остаются прежними. При данных начальных условиях определяем вектора: J1 = {J1}, при этом J1 = j2 при J2 * 0, S1 = {S; }: при i: /2 = 0, S1 = У f , + J , при i: /2 * 0 K ' ' J kN (k) Х/,N(i) ^ 1?k ?m,k *,';,': j =0 s; = 0. Если "i = 1,...,m S1 = {S;} = 0 "i = 1,...,m , то решение данной подзадачи не существует. Иначе вычисляем значения величин Smax = и = (i'|S; = Smax). 1?i?m Определяем решение (X'', F", S", J" ) и проверяем для него условие неотрицательности баланса счета заказчика. Если условие выполнено, то решение (X'', F", S", J") является текущим решением задачи нижнего уровня. Если условие не выполнено, то необходимо осуществляется дальнейшее ветвление задачи. Результатом ветвления задачи нижнего уровня является множество Di решений вида (X', F', S', J'), для которых выполняется условие неотрицательности баланса счета заказчика. Решением задачи верхнего уровня является решение (X', F', S', J') е D;, для которого соответствующее значение S' является максимальным. 132 Примеры расчетов по приведенным в настоящем разделе алгоритмам можно найти в [24]. Таким образом, в настоящем разделе сформулирована и решена оптимизационная задача планирования, заключающаяся в выборе вариантов реализации корпоративных проектов. Имея результаты решения общей задачи согласования интересов (и выбора управляющей компании) в системе управления корпоративными программами (раздел 1) и задачи планирования (настоящий раздел), перейдем к постановке и решению задач оперативного управления процессом реализации корпоративных проектов и программ. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "2.7. Алгоритм решения задачи нижнего уровня." |
|
|