Известия РАН. Теория и системы управления, 2022, № 6, стр. 65-76

Введение. Рассмотрены целочисленные однокритериальные и двухкритериальные оптимизационные задачи управления ограниченными финансовыми ресурсами в условиях неопределенности и риска и методы их решения. Учитывая, что данные задачи имеют существенно переборный характер, для их решения предложены методы ветвей и границ, основанные на разработанных авторами алгоритмах вычисления верхних, нижних и текущих верхних оценок. Авторами также предложены методы оценки устойчивости полученных оптимальных решений в ситуации изменения исходных данных задачи. Разработанный в статье математический инструментарий оптимального выбора на фондовом рынке является развитием классической теории Марковица–Шарпа, изложенной, например, в [1]. Непосредственное практическое применение этих моделей связано с выбором оптимальной производственной программы предприятия, определением структуры закупок материальных ресурсов промышленного предприятия, расчетом оптимального портфеля финансовых активов при условии, что активы, входящие в портфель, не допускают дробления. Классическая задача оптимизации на фондовом рынке заключается в выборе активов, общей стоимостью не выше бюджета инвестора, обеспечивающих максимальную доходность при ограничении на риск или, напротив, минимальный риск при ограничении на планируемую доходность. Под доходностью финансового актива понимается средняя доходность за наблюдаемый временной интервал, а под риском – среднеквадратичное отклонение (СКО) планируемой доходности от среднего значения. Эта мера риска основывается на законе больших чисел и неравенстве Чебышева, согласно которому чем меньше СКО доходности финансового актива, тем меньше вероятность ее отклонения от среднего значения.

Первоначально теория оптимального выбора, изложенная, например, в [1–5], разрабатывалась для портфелей финансовых активов, но впоследствии она все чаще стала применяться при анализе и оценке эффективности портфелей проектов в реальном секторе экономики, организации оптовых закупок разнородных товаров для торговых сетей, закупке материальных ресурсов производства и т.д. Эти подходы, в частности, изложены в публикациях [1, 6–8].

Стохастические методы и статистические данные позволяют дать оценку таких характеристик портфеля, как доходность и риск. В классических моделях портфельного выбора (модель Марковица, модель CAPM) предполагается, что финансовые активы, включаемые в портфель, бесконечно делимы, поэтому, получив доли покупки активов в оптимальном решении, задача формирования портфеля считалась решенной.

Такой подход приемлем в том случае, если цена акции (или лота однородных ценных бумаг) сравнительно мала по отношению к объему инвестиционного бюджета. Если это не так, то полученное решение может оказаться не только неоптимальным, но и недопустимым. Попытки аналитиков получить оптимальное решение путем округления компонент решения далеко не всегда приводят к желаемому результату. Последнее обстоятельство заставляет при анализе эффективности портфеля рассматривать не только непрерывные, классические модели, но и их целочисленные аналоги [9, 10].

Эта проблематика также рассматривалась рядом исследователей. Можно отметить публикации [7, 9, 11], а также работу [4], в которой показано, что дискретный вариант задачи оптимального инвестиционного портфеля сводится к так называемой NP-полной по Тьюрингу задаче. Исследования в рамках этой задачи были весьма актуальными в начале второй половины прошлого века в эпоху невысокой производительности используемой электронно-вычислительной техники и сопровождались высоким интересом исследователей к поиску конструктивных алгоритмов решения NP-полных задач. В наше время актуальность связана с необходимостью решения задач этого класса в условиях реального времени и внесения оперативных корректировок не только в информационную базу данных, но иногда и в применяемые алгоритмы и постановки задач.

Отметим, что в реальной практике оптимального выбора достаточно часто NP-полные проблемы, например нелинейная дискретная задача большой размерности, могут быть эффективно решены с учетом особенностей их постановок, критериев и ограничений, что отмечено, например, в [12, 13]. Проблематике определения точных и приближенных решений NP-трудных задач посвящены работы [14–16]. В статье продолжены исследования в этом направлении. Задачей предлагаемого исследования является разработка и верификация целочисленных вариантов моделей оптимального выбора, а также разработка инструментария для определения области устойчивости оптимальных решений целочисленных задач.

1. Математическая оптимизационная модель без учета риска. Вербальная постановка рассматриваемой ниже задачи состоит в следующем. Пусть инвестор обладает денежными средствами в объеме F на интервале времени [0; T], которые он может потратить на приобретение n видов ценных бумаг. Ценные бумаги можно приобретать лотами. В каждый лот входят ценные бумаги (акции) одного вида. Количество ценных бумаг в i-м, i = $\overline {1,n} $, лоте равно ${{V}_{i}}$. Исходная стоимость (в момент времени t = 0) одной ценной бумаги вида i составляет ${{\alpha }_{i}}$, а будущая стоимость этой ценной бумаги (в момент времени $t = T$) задана стохастически следующим образом: с вероятностью ${{P}_{j}}$, $j = \overline {1,k} $, ее стоимость составит $\gamma _{i}^{j}$. Необходимо купить такие лоты ценных бумаг, которые максимизируют прибыль, полученную после продажи приобретенных ценных бумаг в момент времени T. Формализация этой задач может быть задана следующим образом:

Если лот i приобретается, то ${{x}_{i}} = 1$, в противном случае ${{x}_{i}} = 0$. Задача (1.1)–(1.5) является обобщением известной задачи о рюкзаке [8].

Целевая функция рассматриваемой задачи состоит из двух слагаемых. Первое – выручка от реализации ценных бумаг по цене ${{\gamma }_{i}}$, а второе – остаток денежных средств после формирования портфеля ценных бумаг. Учитывая, что F не оказывает влияние на оптимальное решение, получаем следующую целевую функцию:

Предлагаемая оптимизационная задача (1.1)–(1.5) принадлежит классу задач дискретной оптимизации с булевыми переменными и является NP-трудной [8]. Для решения данной задачи может быть использована следующая схема метода ветвей и границ с разработанным авторами алгоритмом вычисления верхних, нижних и текущих верхних оценок:

1. Вычисление верхней оценки. Для всех лотов акций рассчитывается величина ${{\bar {\gamma }}_{i}}{\text{/}}{{a}_{i}}$. Перенумеруем все пакеты следующим образом: ${{\bar {\gamma }}_{1}}{\text{/}}{{a}_{1}} \geqslant {{\bar {\gamma }}_{2}}{\text{/}}{{a}_{2}} \geqslant $ … $ \geqslant {{\bar {\gamma }}_{n}}{\text{/}}{{a}_{n}}$. В дальнейшем финансовые ресурсы выделятся для приобретения ценных бумаг первого вида, потом второго и так до того момента, пока остатка финансовых средств станет недостаточно для приобретения полностью лота ценных бумаг вида l в объеме ${{V}_{l}}$. В этом случае не учитываются целочисленные ограничения на приобретение акций вида l и покупается максимально возможное количество ценных бумаг данного вида. Это количество ($V_{l}^{'}$) рассчитывается по следующей формуле:

где ${{F}_{{l - 1}}}$ – остаток денежных средств после приобретения первых l – 1 пакетов ценных бумаг ($l = \overline {1,n} $).

В итоге верхняя оценка рассчитывается как

где ${{Z}^{{{\text{верх}}}}}~$ – верхняя оценка.

2. Вычисление нижней оценки. Расчет нижней оценки осуществляется по формуле

где ${{Z}^{{{\text{ниж}}}}}~$ – нижняя оценка.

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

3. Вычисление текущих верхних оценок. Расчет текущей верхней оценки при анализе очередного варианта портфеля ценных бумаг производится каждый раз после выделения финансовых средств на приобретение очередного лота. Эта оценка складывается из прибыли от приобретения ценных бумаг, на которые уже выделены деньги, и прибыли от оставшихся ценных бумаг, полученной по правилу ${{Z}^{{{\text{верх}}}}}$. При этом если окажется, что $Z_{{{\text{тек}}}}^{{{\text{верх}}}} \leqslant {{Z}^{{{\text{ниж}}}}}$, то данный вариант формирования портфеля не рассматривается. В противном случае в портфель включается очередной лот акций и снова вычисляется $Z_{{{\text{тек}}}}^{{{\text{верх}}}}$. Здесь $Z_{{{\text{тек}}}}^{{{\text{верх}}}}$ – текущая верхняя оценка. В результате либо анализируемый вариант портфеля будет отвергнут, либо будет сформирован портфель, доходность которого больше ${{Z}^{{{\text{ниж}}}}}$. В этом случае в качестве нижней оценки принимаем значение целевой функции на последнем портфеле ценных бумаг и переходим к анализу нового варианта формирования портфеля. Работа алгоритма заканчивается или после перебора всех вариантов формирования портфеля, и тогда оптимальным будет тот вариант, которому соответствует последнее значение ${{Z}^{{{\text{ниж}}}}}$, или в случае, когда получен портфель, целевая функция на котором равна ${{Z}^{{{\text{верх}}}}}$.

Одной из проблем, возникающих при практическом использовании решения предложенной задачи, является достоверность прогноза стоимости ценных бумаг ${{\gamma }_{i}}$. Если известна функция распределения случайных величин, задающих возможную прибыль по каждому виду ценных бумаг, то выбирается портфель, максимизирующий математическое ожидание выигрыша либо минимизирующий риск финансовых потерь (СКО).

Еще одним подходом решения этой задачи в условиях неточного прогноза будущих цен активов является анализ устойчивости решения к изменению величин ${{\gamma }_{i}}$. Под устойчивостью задачи будем понимать оценку влияния изменения будущей стоимости ценных бумаг на решение и на значение целевой функции задачи (1.1)–(1.5). При этом возможны три подхода:

В первом случае считается, что известны минимальные значения ${{\gamma }_{i}}$ и необходимо вычислить, насколько могут быть увеличены эти значения, чтобы оптимальное решение задачи сохранилось. Другими словами, необходимо определить такое $\varepsilon {{{\text{\;}}}^{m}}$, чтобы при увеличении всех ${{\gamma }_{i}}$ на любое $\varepsilon \in (0;\varepsilon {{{\text{\;}}}^{m}})$ решение задачи сохранилось. Здесь $\varepsilon {{{\text{\;}}}^{m}}$ – правая граница изменения ε.

Будем считать множество X^j, $j = \overline {1,N} $, где N – число допустимых портфелей, множеством всех возможных решений задачи, и пусть эти значения упорядочены по возрастанию величины ${{W}_{q}}$:

Допустим, что вектор x_i является оптимальным при отсутствии возмущения. Тогда при увеличении ${{\gamma }_{i}}$ на величину возмущения ε возможно изменение оптимального решения. В этом случае в качестве новых решений могут быть только решения, у которых номер больше l. Вычисление границы изменения ε для оптимального решения ${{x}^{l}}$ производится из следующего соотношения:

Раскроем скобки и выразим ε через параметры ${{V}_{i}}$, ${{\gamma }_{i}}$, $x_{i}^{l}$, $x_{i}^{k}$, т.е. решим уравнение (1.9). Отсюда получаем

Пусть этот минимум достигается на каком-либо ${{l}_{1}} > l$, тогда процедура приращения ${{\varepsilon }^{{{{l}_{1}}}}}$ для решения ${{x}^{{{{l}_{1}}}}}$ повторяется. Это происходит до тех пор, пока через конечное число шагов оптимальным не станет решение из множества X с максимальным верхним индексом. Тогда дальнейшее увеличение всех значений ${{\gamma }_{i}}$ не приведет к новому решению.

Во втором случае будем полагать, что ${{\gamma }_{i}}$ с учетом возмущений меняются по правилу ${{\gamma }_{i}} + {{m}_{i}}~\varepsilon $. В данной ситуации схема рассуждений сохраняется, только упорядочение решений происходит по возрастанию величины ${{W}_{q}}$:

Соответственно формула для вычисления приращения ${{\varepsilon }^{l}}$, для которого остается оптимальным решение ${{x}^{l}}$, будет иметь следующий вид:

В третьем случае полагаем, что ${{\gamma }_{i}}$ может принимать все значения из интервала $[\gamma _{i}^{1};\gamma _{i}^{2}]$. В этой ситуации может быть предложена процедура разбиения множества, на котором изменяются значения $~\gamma = \left( {{{\gamma }_{1}},..,{{\gamma }_{n}}} \right)$, на подмножества ${{S}_{1}}, \ldots ,~{{S}_{k}}$. При этом при изменении $\gamma $ на любом из подмножеств ${{S}_{j}}$, $j = \overline {1,k} $, оптимальным на этом подмножестве остается решение ${{x}^{j}} \in X$.Рассмотрим для задачи, предложенной выше, ситуацию, когда ${{\gamma }_{i}} \in [\gamma _{i}^{1};\gamma _{i}^{2}],{\text{\;}}$ т.е. будущая ожидаемая стоимость i-го актива может принимать любые значения из интервала [$\gamma _{i}^{1};\gamma _{i}^{2}$]. В этом случае, вообще говоря, невозможно однозначно упорядочить все активы по степени убывания доходности. Поэтому можно сформировать все допустимые портфели и далее для каждого портфеля можно вычислить соответственно $F_{j}^{1},F_{j}^{2}$, $j = \overline {1,N} $. Здесь N – число допустимых портфелей, $F_{j}^{1}$ – значение целевой функции (1.6) при минимальном будущем значении стоимости i-го актива, $F_{j}^{2}$ – значение целевой функции (1.6) при максимально возможном значении будущей стоимости актива i. Далее расположим соответствующие значения целевой функции на оси доходности для различных инвестиционных портфелей.

Выберем портфели, которые могут при определенных значениях будущих стоимостей активов, входящих в них, быть оптимальными. Для этого из множества всех допустимых портфелей N выделим те, которые удовлетворяют следующим условиям: 1) ${\text{max}}F_{j}^{2} = F_{l}^{2}$, $j \in N$; 2) ${\text{max}}F_{j}^{1} = F_{k}^{1}$, $j \in N$; 3) исключим из множества N все портфели, для которых $F_{l}^{2} \leqslant F_{k}^{1}$.

Оставшееся множество портфелей обозначим через ${{N}_{1}}$. Очевидно, что только портфели множества ${{N}_{1}}$ могут быть оптимальными при изменении будущей стоимости активов в интервалах $~{{\gamma }_{i}} \in [\gamma _{i}^{1},\gamma _{i}^{2}]$, $i = \overline {1,n} $. Значение целевой функции для каждого допустимого портфеля j может быть представлено следующим образом:

где вектор с булевыми переменными ${{x}^{j}} = (x_{1}^{i}, \ldots ,x_{2}^{j})$ задает те лоты, которые вошли в портфель  j.

Если необходимо определить множество будущих стоимостей активов, при которых будет оптимальным j-й портфель, то очевидно, что оно может быть представлено следующей системой линейных неравенств:

Далее рассмотрим целочисленные модификации моделей портфельных инвестиций с учетом риска.

Следует отметить, что предлагаемые подходы для оценки устойчивости оптимизационных моделей, связанных с формированием инвестиционных портфелей, являются оригинальными и могут быть использованы как для дальнейших теоретических исследований, так и для практического применения. Во втором случае оценка области устойчивости позволит не осуществлять повторные расчеты по оптимизационной модели при локальном изменении параметров модели. Учитывая, что предлагаемая оптимизационная модель является NP-трудной, это сократит время реакции лица, принимающего решения на изменения внешней среды.

2. Оптимизационная целочисленная модель выбора с учетом риска. Далее будет рассмотрена целочисленная модель CAPM, непрерывная модификация которой изложена в [1]. Для определения оптимального целочисленного портфеля этой модели будет предложена схема метода ветвей и границ. Необходимость разработки такого метода связана с тем, что при переходе от непрерывного решения к целочисленному путем округления возможна существенная потеря точности.

Полагаем, что известен перечень лотов, в которые входят ценные бумаги одного вида. Объем ценных бумаг (количество акций каждого вида) задан числами ${{V}_{1}},{{V}_{2}}, \ldots ,~{{V}_{n}}$. Известна начальная стоимость каждой акции ${{\alpha }_{i}}$ в момент времени t = 0 и вероятностное распределение будущей стоимости акций каждого вида в момент времени $t = T$.

Будем считать, что $\beta $ – коэффициенты по каждому виду финансовых активов, которые обозначим через ${{\beta }_{i}}$, $i = \overline {1,n} $. Эти коэффициенты задают количественную оценку риска по каждому виду ценных бумаг. В этих условиях аналитик, обладая ограниченным объемом инвестиционных ресурсов F, хотел бы приобрести те лоты, продав которые в момент времени $t = T$, он получит максимальный ожидаемый прирост финансовых ресурсов $\Delta F$ с учетом ограничений на риск портфеля.

Сформируем оптимизационную задачу определения инвестиционного портфеля с учетом вышеприведенных предположений. Ниже будем считать, что будущая стоимость i-го актива задается распределением $\gamma _{i}^{l}, \ldots ,~\gamma _{j}^{m}~$ c вероятностями $p_{i}^{l}, \ldots ,~p_{j}^{m}~$. Тогда математическое ожидание будущей стоимости i-го актива есть величина ${{\bar {\gamma }}_{i}}$:

В этих обозначениях соответствующая оптимизационная задача выбора инвестиционного портфеля может быть представлена следующим образом:

Здесь ${{\beta }_{{{\text{гр}}}}}$ – граничное значение, определяющее максимально допустимое значение риска формируемого портфеля.

В задаче (2.1)–(2.4) ${{x}_{i}} = 0$, если лот ${{V}_{{i~}}}$ не вошел в инвестиционный портфель, и ${{x}_{i}} = l$, если лот ${{V}_{{i~}}}$ входит в инвестиционный портфель. Для получения оптимального решения задачи (2.1)–(2.4) необходимо выбрать такие лоты из множества ${{V}_{{i~}}}, \ldots ,{{V}_{n}}$, чтобы, не нарушая ограничений (2.2)–(2.4), максимизировать целевую функцию (2.1).

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

Шаг 1. Вычисление верхней оценки ${{F}_{{\text{в}}}}$ задачи (2.1)–(2.4). Для расчета верхней оценки заменим в задаче (2.1)–(2.4) ограничение (2.4) на ограничение вида

Тогда задача (2.1)–(2.3), (2.5) является задачей непрерывного линейного программирования, и ее оптимальное решение может быть получено с использованием, например, симплекс-метода.

Обозначим решение задачи (2.1)–(2.5) через ${{x}^{{{\text{опт}}}}}$, вычислим значение целевой функции (2.1) на решение ${{x}^{{{\text{опт}}}}}$ и запишем его через ${{F}_{{\text{в}}}}$. Здесь ${{x}^{{{\text{опт}}}}}$ – оптимальное решение задачи. Отметим, что ${{x}^{{{\text{опт}}}}}$, вообще говоря, не является допустимым решением исходной задачи (2.1)–(2.4) в силу того, что оно может быть нецелочисленным. Понятно, что значение целевой функции (2.1) задачи (2.1)–(2.4) на оптимальном решении не может превышать величину ${{F}_{{\text{в}}}}$.

Шаг 2. Вычисление нижней оценки задачи (2.1)–(2.4) ${{F}_{{\text{н}}}}$ осуществляется путем выбора некоторого допустимого решения задачи (2.1)–(2.4) и вычисления на этом решении значения целевой функции (2.1), которое и принимается за ${{F}_{{\text{н}}}}$. Необходимо отметить, что чем ближе значение ${{F}_{{\text{н}}}}$ будет к значению ${{F}_{{\text{в}}}}$, тем более эффективно будет работать в дальнейшем схема алгоритма, и если ${{F}_{{\text{н}}}} = {{F}_{{\text{в}}}}$, то выбранное выше решение и будет оптимальным. Если получено, что ${{F}_{{\text{н}}}} < {{F}_{{\text{в}}}}$, то переходим к следующему шагу метода.

Шаг 3. Анализ текущих верхних оценок формируемого портфеля.

Если выполняется соотношение ${{F}_{{\text{н}}}} < {{F}_{{\text{в}}}}$, то переходим к формированию очередного портфеля. В процессе формирования очередного портфеля происходит вычисление текущих верхних оценок:

Здесь K – множество лотов, которые уже вошли в портфель; N – множество всех лотов; $N{{\backslash }}К$ – множество неприобретенных лотов; ${{F}_{{\text{в}}}}$ – верхняя оценка задачи (2.1)–(2.4) на множестве лотов $N{{\backslash }}К$ и объеме финансовых ресурсов:

Дальнейшее формирование очередного портфеля происходит только в случае выполнения следующих условий:

В случае, если хотя бы одно из ограничений (2.7)–(2.8) не выполняется, переходим на формирование другого портфеля. Если (2.7) и (2.8) выполнены, то выбираем очередной лот для включения его в портфель и получаем множество приобретенных лотов K_l. Очевидно, что $K \in {{K}_{l}}$.

На множестве K_l вычисляем $F_{{\text{в}}}^{{{\text{тек}}}}\left( {{{K}_{l}}} \right)$ по формуле (2.6) и проверяем выполнение условий (2.6)–(2.7). Продолжая эту процедуру, в итоге получим, что либо формируемый портфель будет отбракован, либо остаток финансовых средств будет таков, что дополнительно ни один лот приобрести нельзя. В этом случае рассчитываем на полученном допустимом решении значение целевой функции (2.1). Обозначаем эту величину как F*. Если $F{\text{*}} > {{F}_{{\text{н}}}}$, то в дальнейшем полагаем ${{F}_{{\text{н}}}} = F{\text{*}}$ и перейдем к формированию очередного инвестиционного портфеля. Вычисления заканчиваются, если при очередной корректировке ${{F}_{{\text{н}}}}$ получим ${{F}_{{\text{н}}}} = {{F}_{{\text{в}}}}$, либо, если все варианты формирования портфелей рассмотрены. Тогда в качестве оптимального выбирается тот, который соответствует последнему (максимальному) значению ${{F}_{{\text{н}}}}$.

3. Оптимизационная целочисленная модель Марковица с критерием на минимум риска портфеля. В отличие от классической модели Марковица [1] будем предполагать, что активы можно приобретать только лотами, и определим значение

которое задает долю инвестиций для данного вида активов.

В этом случае задача Марковица на минимум риска, учитывая введенные ранее обозначения, может быть сформулирована следующим образом:

где $\sigma _{i}^{~}$ – СКО, $\sigma _{i}^{{2~}}$ – дисперсия, d_i – доля инвестиций для данного вида актива, ${{R}_{{ij}}} = {\text{cov}}\left( {i,j} \right)~$ – взаимная ковариация доходности актива i и актива  j.

В задаче (3.1)–(3.4) ${{y}_{i}} = 1$, если i-й лот включен в портфель, и ${{y}_{i}} = 0$, если этот лот в портфель не включен. Величина ΔF задает минимально возможный прирост инвестиционных ресурсов при продаже активов портфеля в момент времени $t = T$.

Дадим описание метода направленного перебора, реализующего схему метода ветвей и границ с разработанными авторами алгоритмами вычисления верхней, нижней и текущих нижних оценок для этой задачи.

Шаг 1. Вычисление верхней границы оптимального значения целевой функции (3.1). Для расчета этой оценки решается вспомогательная задача следующего вида:

Задача (3.5)–(3.7) является задачей линейного программирования с бинарными переменными, и значение целевой функции этой задачи на оптимальном решении и будет верхней оценкой ${{F}_{{\text{в}}}}$ задачи (3.1)–(3.7).

Обозначим значение целевой функции задачи (3.5)–(3.7) на оптимальном решении через ${{y}^{{{\text{опт}}}}}$ и сравниваем это значение с правой частью неравенства (3.3). Если оно меньше, чем $F + \Delta F$, то задача (3.1)–(3.4) решения не имеет. Если значение целевой функции (3.5) на оптимальном решении ${{y}^{{{\text{опт}}}}} > F + \Delta F$, то вычисляем на этом решении значение целевой функции (3.1) и его принимаем за величину верхней оценки ${{R}_{{\text{в}}}}$ задачи (3.1)–(3.4).

Шаг 2. В качестве нижней оценки выберем ноль, т.е. ${{R}_{{\text{н}}}} = 0$. Если ${{R}_{{\text{н}}}} < {{R}_{{\text{в}}}}$, то переходим к шагу 3. Если ${{R}_{{\text{н}}}} = {{R}_{{\text{в}}}}$, то оптимальное решение исходной задачи найдено.

Шаг 3. Вычисление текущих нижних оценок при анализе вариантов формирования портфелей. Расчет текущей нижней оценки формируемого портфеля производится по следующей схеме при условии, что в портфель уже вошли лоты множества K и выполняется соотношение

Упорядочиваем все лоты множества $N{{\backslash }}K$ по показателю доходности активов:

Далее проверяем выполнение условия:

Если неравенство (3.9) верно, то выбираем очередной лот из множества $N{{\backslash }}K$. Включаем его в формируемый портфель и образуем множество лотов ${{K}_{l}}\left( {K \in {{K}_{l}}} \right)$ и вычисляем текущую нижнюю оценку для лотов множества K_l.

Процесс формирования портфеля заканчивается, если при очередном включении нового лота в портфель не выполняется условие (3.9), либо остаток средств недостаточен для того, чтобы приобрести хотя бы один из оставшихся лотов, не включенных в портфель. В последнем случае проверяем значение целевой функции (3.1) на сформированном портфеле. Если оно меньше, чем ${{R}_{{\text{в}}}}$, то полагаем в дальнейшем, что ${{R}_{{\text{в}}}}$ равно полученному значению целевой функции (3.1).

Метод ветвей и границ прекращает работу в том случае, если при очередной корректировке ${{R}_{{\text{в}}}}$ получим ${{R}_{{\text{в}}}} = {{R}_{{\text{н}}}}$ или если после того, как просмотрены все дерево вариантов формирования портфелей. Тогда в качестве оптимального портфеля выбирается тот, которому соответствует последнее (минимальное) значение ${{R}_{{\text{в}}}}$.

4. Целочисленная модель с критерием на максимум доходности и ограничением на риск. Рассмотрим целочисленную модель Марковица на максимум ожидаемой доходности при ограничении на величину риска портфеля активов. С учетом введенных ранее обозначений она может быть сформулирована следующим образом:

Далее будем применять для решения целочисленной задачи (4.1)–(4.4) рассмотренную ранее схему метода ветвей и границ.

Шаг 1. Вычисление верхней оценки оптимального значения целевой функции задачи (4.1)–(4.4). Эта оценка может быть получена путем исключения ограничения (4.2) и замены ограничения (4.4) на ограничение

В этом случае максимум доходности портфеля задачи (4.1)–(4.3), (4.5) может быть определен, как указывалось ранее, путем упорядочения лотов по величине соотношения ${{\bar {\gamma }}_{1}}{\text{/}}{{a}_{1}}$, $i = \overline {1,n} $.

Перенумеруем лоты в порядке убывания величины ${{\bar {\gamma }}_{1}}{\text{/}}{{a}_{1}}$ и найдем ${{\bar {\gamma }}_{1}}{\text{/}}{{a}_{1}} \geqslant {{\bar {\gamma }}_{2}}{\text{/}}{{a}_{2}} \geqslant ... \geqslant {{\bar {\gamma }}_{n}}{\text{/}}{{a}_{n}}.$ Далее будем покупать лоты по убыванию величины ${{\bar {\gamma }}_{1}}{\text{/}}{{a}_{1}}$ до тех пор, пока не будут израсходованы все деньги в объеме F. Этот портфель, как легко видеть, будет оптимальным решением задачи (4.1)–(4.3), (4.5).

Если полученный портфель еще и удовлетворяет ограничениям (4.2) и (4.4), то он также будет и решением исходной задачи (4.1)–(4.4). Если последнее условие не выполняется, то переходим к шагу 2.

Шаг 2. Вычисление нижней оценки оптимального значения целевой функции задачи. В качестве нижней оценки ${{F}_{{\text{н}}}}$ задачи (4.1)–(4.4) можно принять значение целевой функции этой задачи на некотором допустимом ее решении.

Шаг 3. Вычисление текущих верхних оценок оптимального значения целевой функции при формировании инвестиционного портфеля. Расчет текущей верхней оценки для частично сформированного портфеля при условии, что в портфель вошли уже лоты множества K, происходит по следующей формуле:

Здесь ${{F}_{{\text{в}}}}$ – верхняя оценка задачи (4.1)–(4.4) на множестве лотов $N{{\backslash }}K$.

После того, как вычислены значения $F_{{\text{в}}}^{{{\text{тек}}}}\left( K \right)$, проверяется выполнение следующего неравенства:

В том случае если условие (4.7) верно, происходит выбор очередного приобретаемого лота и формируется инвестиционный портфель, в который входит множество лотов $K~\left( {K \in {{K}_{l}}} \right)$. Если на множестве K_l выполняется соотношения (4.7), то процесс формирования портфеля продолжается. В противном случае данный портфель отбраковывается и происходит переход к формированию нового инвестиционного портфеля.

В ситуации если удалось сформировать с учетом описанной выше процедуры портфель, на котором выполняются все ограничения (4.2)–(4.4) и значение целевой функции F* на этом портфеле больше, чем ${{F}_{{\text{н}}}}$, то полагаем ${{F}_{{\text{н}}}} = F{\text{*}}$ и переходим к формированию нового инвестиционного портфеля.

Завершающим шагом является тот, когда после очередной корректировки ${{F}_{{\text{н}}}}$ получено, что ${{F}_{{\text{н}}}}$ совпадает с ${{F}_{{\text{в}}}}$, либо когда все варианты формирования портфеля рассмотрены. В этом случае в качестве оптимального портфеля выбирается тот портфель, который соответствует последнему (наибольшему) значению ${{F}_{{\text{н}}}}$.

Рассмотренные в разд. 2–4 двукритериальные целочисленные модели оптимального выбора, а также предлагаемые авторами методы их решения являются оригинальными и позволяют оптимизировать портфели ценных бумаг в условиях неделимости входящих в портфель активов.

5. Альтернативные постановка и метод решения целочисленной задачи оптимального выбора с критериями доходности и риска. Рассмотрим целочисленный вариант модели Марковица, в котором неизвестными выступают не конкретные лоты включаемых в инвестиционный портфель однородных рисковых финансовых активов (такая постановка задачи представлена, например, в [17]), а непосредственно количество лотов ценных бумаг того или другого эмитента, включаемых в портфели, которые отличаются показателями доходности, риска и величиной инвестиционного бюджета.

Такая коррекция постановки задачи оптимального портфельного инвестирования потребовала и соответствующей коррекции используемых переменных и параметров. В дискретном варианте модели Марковица в качестве искомой величины выступают ${{x}_{i}}$ – количество лотов акций i-го эмитента в портфеле. Инвестиционные вложения ${{S}_{i}}$ в i-ю акцию определяются выражением

Здесь ${{c}_{i}}$ – цена покупки i-й акции.

Так как активы можно приобретать только лотами, то доли активов ценных бумаг, вложенных в портфель, задаются как

где ${{S}_{o}}$ – бюджет инвестора.

Проведем замену ${{x}_{i}}~{{c}_{i}} = {{\gamma }_{i}}$ (величина бюджета, которую инвестор планирует разместить на приобретение лотов акций i-го вида):

где ${{d}_{i}}~$ – средняя доходность i-го актива; $~{{\sigma }_{i}}$ – СКО доходностей i-го актива; $~{{r}_{{ij}}}$ – коэффициент корреляций доходностей i-го и j-го активов; $\sigma $ – пороговое значение риска портфеля.

Формальная постановка модели (5.3)–(5.6) позволяет сократить объем расчетов и вместо долей W_i акций эмитентов находить суммы ${{\gamma }_{i}}$, направляемые на покупку ценных бумаг. Однако в ней не учитывается фактор дискретности приобретаемых лотов. Введем ограничение на целочисленность переменных ${{x}_{i}}$ (количество приобретаемых лотов акций i -го эмитента) и получим вариант модели с учетом дискретности покупаемых лотов:

Задача (5.7)–(5.11) представляет собой задачу целочисленного нелинейного программирования, относящуюся к классу NP-полных по Тьюрингу проблем, для которых решение, как указано выше, не может быть найдено с помощью известных численных методов нелинейной непрерывной оптимизации. Более подробно этот аспект отражен, например, в [18].

Однако в нашем случае ограничение на риск (5.8) является выпуклым (представлено квадратичной формой), а критерий (5.7) – линейным. В связи с этим для поиска оптимального решения задачи в рассматриваемом варианте нами предложено использовать основную идею метода ветвей и границ. Эта идея связана с представлением области допустимых значений в виде прямой суммы непересекающихся выпуклых областей, для каждой из которых оптимальное решение целочисленной задачи может быть получено с применением известных методов оптимизации (например, сведением к линейной задаче).

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

Численный алгоритм включает следующие шаги [19].

Шаг 1. Решаем задачу в непрерывной постановке (с условием бесконечной делимости активов). Активы в полученном решении располагаем по убыванию доходности.

Шаг 2. Случайным образом округляем значения x_i в большую или меньшую сторону, проверяя допустимость решения (ограничения на инвестиционный бюджет и пороговый риск). Если решение оказалось недопустимым, то повторяем случайный эксперимент. Если получаем допустимый целочисленный портфель – переходим к шагу 3.

Шаг 3. Вокруг допустимого плана строим сферу единичного радиуса, рассматриваем возможные портфели, отличающиеся от “базового” (шаг 1) на единицу по каждому включенному в него активу, и ранжируем их в порядке убывания доходности до момента, когда получаемый набор активов теряет свойства недопустимости. “Лучший” из допустимых портфелей (так называемый квазиоптимальный) вновь подвергаем такой же процедуре.

Итерационный алгоритм завершается в случае, если вновь полученный портфель не отличается от предыдущего либо отличается не более чем на $\tau $ процентов, где $\tau $ – заранее выбираемый порог точности.

Этот порог, как показано в [19], растет с числом финансовых активов в портфеле. Чем больше число ценных бумаг, тем выше точность (в цитируемой работе рассматривается портфель возможных производственных программ предприятия, включающий изделия ассортиментного ряда, цены, и себестоимость которых определяются рынком и изначально могут быть заданы только интервальными значениями. Автором показано, что в случае программы выпуска с числом изделий (активов) более 100 погрешность квазиоптимального решения по сравнению с оптимальным решением целочисленной задачи, полученным простым переборным алгоритмом, составляет не более 5–7% и снижается с ростом объема портфеля заказов).

Целочисленные модификации модели Марковица сохраняют основные особенности классической постановки, за исключением, конечно, бесконечной делимости активов. Целочисленные модели позволяют рассмотреть влияние факторов дискретности, размера начального бюджета и ликвидности на оптимальную структуру портфеля инвестора, полученную по классической модели. В практических расчетах оценку влияния этих факторов на структуру портфеля авторы провели на основании данных Мосбиржи за период 01.03.2021 г.–20.11.2021 г. [20].

Заключение. Предлагаемые в работе методы оценки целочисленных моделей управления ограниченными ресурсами могут быть использованы в ситуации, когда активы, входящие в портфель, нельзя делить. Поэтому классические подходы, основанные на возможности дробления активов, неприемлемы. Применение предлагаемых методик целесообразно, в частности, при выборе совокупности неделимых проектов, оптовой закупке материальных ресурсов производства или формировании портфелей финансовых и материальных активов в ситуации, когда эти активы неделимы. Показано, что в этом случае для формирования оптимального портфеля по критериям “риск–доходность” могут быть использованы методы целочисленной оптимизации, в частности, разработанный авторами метод ветвей и границ. В ситуации, когда будущая стоимость активов задана интервально, предложен метод анализа устойчивости оптимального портфеля.