Шаг 3. Подставляем значения pl,i = \„n в схему метода ветвей и границ, описанную ранее. В случае, если последовательность вьщеления финансовых средств остается прежней, то увеличиваем теперь уже значения
Д,/ = на величину f = 0.00001 *р , т.е. д" = р\ + 0.00001 * >9 ",/ = l..w. Подставляем опять значения д",/ = 1..« в схему метода ветвей и границ и
снова проверяем последовательность вьщеления средств. Продолжаем алгоритм до тех пор, пока последовательность вьщеления финансовых средств изменится по отношению к первоначальной. Предположим, что на шаге к = Z получили последовательность, отличную от первоначальной.
Тогда величина устойчивости = (z -1) * f = (z -1) * 0.00001 * р .
В четвертом случае прогнозные цены Д оценены интервально, то есть Д на момент времени Т могут принимать любые значения в интервале р],р} .
Как и ранее, пусть = jc.." - все допустимые решения задачи
(11.154а)-(11.156). В этом случае определим значения целевой функции на решении как {s) и /2* (£•), где величина fx {е) получена при прогнозном значении р], а величина fi {б) при прогнозном значении Д?. Если Д принимает все значения из ДД , то в силу непрерывной зависимости f {s) от параметров Д , f {б) принимает значения на ()>/{() (у = 1> ). Выберем среди функций / {s) следующие:
max/2(f) = /2), max/i() =/if),
(;=U7).
Из множества всех допустимых решений выберем те, у которых
/2Л)>/Г()(1Ы57)
Только решения, удовлетворяющие (11.157), могут быть оптимальными при каком либо значении параметра Д. ( / = 1 ,.п). Поэтому оставим
среди множества допустимых решений только те целевые функции, ко-
торые удовлетворяют условию (11.157), получим множество допустимых решений X = x...xyL<M, Используя методику, изложенную в [1],
получим, что п-мерный параллелепипед изменения цен на ценные бумаги в момент времени Т р = f] Д/,Д может быть разбит на конечное
число областей Mi,..Mi так, что при изменении Д (/ = 1..л) на множестве Mj оптимальным остается решение х- еХ. Область Mj в данном случае задается следующей системой неравенств относительно параметра Д :
д/<Д<Д/ = 1..г
I.xfViri>ixlVirnl = Wj /=1/=1
Оценив величину каждой из областей Mj (у = 1..L), при равновероятном распределении Д на интервалах fij.fif
.получим, что в качестве
оптимального решения jc (у = 1..Z,) может быть выбрано то, соответствующая область которого больше.
Очевидна практическая значимость получения количественной оценки верхней границы прогнозных цен, при которой сохраняется оптимальное решение. Зная эту оценку, портфельный менеджер имеет некоторый запас прочности по инвестициям. Кроме того, в зависимости от этой величины менеджер может принять решение о смене метода оптимизации или даже критерия оптимизации. Например, если при увеличении всех прогнозных цен на 10% и более от величины наименьшей прогнозной цены, оптимальное решение сохраняется, то можно говорить об относительно высоком запасе прочности инвестиций.
Глава 12
ОСНОВЫ ТЕОРИИ сложности АЛГОРИТМОВ
Используя информацию о ТОМ, к какому классу задач Р или NP принадлежит исследуемая задача, может быть определен наиболее эффективный метод приближенного или точного ее решения.
В предыдущих главах этой книги мы уже сталкивались с проблемой сложности алгоритмов при решении оптимизированных задач. Рассмотрим еще один пример, который может возникнуть на практике [21].
Предположим, вы занимаетесь исследовательской деятельностью на фирме, производящей продукцию в одной из отраслей промышленности. Однажды руководитель сообщает, что фирма собирается начать выпуск новой продукции в условиях жесткой конкуренции. По этой причине нужен хороший метод, выявляющий возможность (или невозможность) создания новых изделий или их комплектующих узлов с заданными технологическими характеристиками, и при этом метод должен вьщавать ответ для любого заданного набора характеристик (эта проблема может возникнуть при анализе задачи расширения или перепрофилирования производства, рассмотренной в главе 11). При этом в случае положительного ответа необходимо представить проект выпуска соответствующего изделия. Так как вы отвечаете за разработку алгоритмов в фирме, то вам предстоит разработать или отыскать соответствующий метод с соответствующим алгоритмом.
Получив необходимые разъяснения, вы принимаетесь за работу. Спустя несколько недель кабинет завален грудой скомканных черновиков, а энтузиазма у вас значительно поубавилось, так как не удалось придумать алгоритма существенно лучшего, чем перебор всех возможных вариантов. За это решение шеф вряд ли похвалит, так как только для одного набора характеристик компьютеру потребуется несколько лет непрерывной работы. Естественно, у вас нет желания возвращаться к шефу со словами: «Я не могу найти эффективного алгоритма, боюсь, что я для этого недостаточно умен».
Для вас бьшо бы гораздо лучше, если бы вы могли сказать, что поставленная задача в принципе трудна и ни один алгоритм не может ее