Введение

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

Постановка задачи

Пусть стоимость предприятия определяется формулой:

В данной формуле - средневзвешенные затраты на капитал, - свободный денежный поток за -й период, - ожидаемые темпы роста денежного потока, - число периодов.

Сформируем соответствующую задачу оптимизации:

Методы оптимизации, основывающиеся на интервальном анализе

Данные методы требуют преобразования искомой задачи, так как интервальный анализ работает не с вещественными числами, а с более сложными структурами - вещественными интервалами. Для этого преобразования необходимо переопределения всех операций. Такое усложнение позволяет быстрее обрабатывать исследуемые множества, поскольку анализ ведется не относительно каждой отдельно взятой точки, а относительно множества точек. Ценой такого прироста в скорости обработки является возникающая погрешность в оценке функции на этом множестве. Данный эффект называется эффектом обертывания. Будем называть те значения, которые составляют погрешность (они в принципе не могут достигаться функцией на исследуемом множестве) мнимыми, все остальные - реальными.

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

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

Необходимые определения и структуры

Задача (2) является задачей поиска безусловного глобального максимума.

Как видно из постановки задачи, каждая переменная целевой функции (1) принадлежит некоторому интервалу. Определим вектор переменных . Вектор, составленный из интервалов, называется параллелотоп. Определим параллелотоп как интервальный вектор, каждая компонента которого определяется областью изменения соответствующей координаты вектора (в дальнейшем множество параллелотопов размерности будем обозначать ),тогда параллелотоп будем называть областью поиска задачи (2). Для любого параллелотопа определена ширина - величина, определяемая следующим соотношением:

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

Инвертор - функция , которая по заданному параллелотопу , функции и параметру точности находит в исходной области поиска множество параллелотопов такое, что :

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

Таким образом, для исходной задачи определены основные понятия, необходимые для корректной работы методов дихотомии прямого образа и отсечки мнимых значений.

Схема метода дихотомии прямого образа

Шаг 1. Задать – область поиска, – параметр точности, отвечающий за размер параллелотопа во множестве , которое будет вырабатываться инвертором, и – параметр точности остановки алгоритма. Рекомендуется выбирать и одного порядка, так как в противном случае, точность ответа будет снижена вследствие того, что либо произойдет окончание работы алгоритма по критерию малости инвертируемого интервала, либо найденный параллелотоп, содержащий точку глобального минимума, будет слишком большим.

Шаг 2. С помощью естественной функции включения найти прямой образ функции на области поиска .

Шаг 3. Дихотомически разделить интервал на два интервала и .

Шаг 4. Инвертировать интервал . В ходе данного шага выработается множество параллелотопов .

Шаг 5. Если множество , вырабатываемое инвертором непустое, перейти к шагу 6, если пустое – к шагу 7.

Шаг 6. Если , то произвольный элемент из множества гарантированно содержит точку глобального минимума искомой функции. Если , то положить интервал равным и вернуться к шагу 3.

Шаг 7. Положить интервал равным и вернуться к шагу 3.

Схема метода отсечки мнимых значений

Шаг 1. Задать – область поиска, - параметр сетки (), - параметр разбиения и – параметр точности при инвертировании. Рекомендуется выбирать параметр сетки не превышающим 5, так как количество параллелотопов, образуемых на шаге 2 алгоритма равно , где – размерность параллелотопа. Параметры разбиения и точности при инвертировании определяются так же, как и в методе дихотомии прямого образа.

Шаг 2. Вследствие наличия зависимости количества мнимых значений от размера области поиска и структуры функции (промежутков монотонности, точек разрыва и т.п.) строится разбиение области поиска, для последующего сжатия множества мнимых значений, следующим образом:

Шаг 2.1. Создать множество параллелотопов , состоящее из единственного элемента .

Шаг 2.2. Если равно нулю, закончить построение разбиения и перейти к шагу 3. Иначе перейти к шагу 2.3.

Шаг 2.3. Создать временное множество параллелотопов .

Шаг 2.4. Для каждого параллелотопа из выполнить следующую процедуру:

Шаг 2.4.1. Поместить в параллелотоп точку (положение точки может определяться случайным образом или оговариваться заранее).

Шаг 2.4.2. Разделить относительно помещенной точки параллелотоп на непересекающихся параллелотопов. Пусть – точка разбиения, – делимый параллелотоп. Процедура деления состоит из n шагов. На первом шаге исходный параллелотоп делится на два параллелотопа и . На втором шаге каждый из полученных на первом шаге параллелотопов делится на два других. Получаем 4 параллелотопа: , , , . И так далее.

Шаг 2.4.3. Каждый из полученных параллелотопов добавить в множество .

Шаг 2.5. Заменить содержимое множества содержимым множества .

Шаг 2.6. Уменьшить на единицу и вернуться к шагу 2.2.

Шаг 3. Положить начальный образ .

Шаг 4. Последовательно перебирая все параллелотопы , выполнить: .

Шаг 5. Разбить образ на непересекающиеся интервалы шириной : , где – число полученных интервалов.

Шаг 6. Поочередно инвертировать каждый из полученных на шаге 5 интервалов (, ). Как только выработанное инвертором множество будет непустым, произвольный параллелотоп из полученного множества гарантированно будет содержать точку глобального минимума.

Решение модельного примера

Предположим, что на экономические параметры, определяющие стоимость предприятия наложены следующие ограничения (единица изменения денежного потока - млн. у.е.):

• ,
• ,
• ,
• .

Ниже приведена сводная информация по результатам работы алгоритмов (, , ):

Рис. 1. Результаты работы алгоритмов

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

Заключение

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

Литература

1. Л. Жолен, М. Кифер, О. Дидри, Э. Вальтер. Прикладной интервальный анализ. – М.-Ижевск: Институт компьютерных исследований, 2007. - 468с.
2. E. Hansen, G.W. Walster. Global optimization using interval analysis. – New York: Marcel Dekker, 2004. – 515c.
3. В.Н. Пановский. Применение аппарата интервального анализа для поиска глоабльного экстремума функций. Конкурс научно-технических работ и проектов "Молодежь и будущее авиации и космонавтики". Аннотации работ. - Спб.: Принт-салон, 2011, с.190.
4. В.Н. Пановский. Реализация методов глобальной оптимизации, использующих аппарат интервального анализа. 10-я Международная конференция "Авиация и космонавтика - 2011". 8-10 ноября 2011 года. Москва. Тезисы докладов. - Спб.: Мастерская печати, 2011, с.239-240.
5. В.Н. Пановский. Интервальный анализ. Прикладное применение алгоритмов обращения и оценивания образов функций//Конкурс научно-технических работ и проектов «Молодежь и будущее авиации и космонавтики - 2010». Москва. Аннотации работ. – СПб.: Мастерская печати, 2010. – 162с. – с.130-131.