Multi-criteria computer optimization of the investment program's structure
Table of contents
Share
Metrics
Multi-criteria computer optimization of the investment program's structure
Annotation
PII
S265838870000194-6-1
DOI
10.33276/S0000194-6-1
Publication type
Article
Status
Published
Authors
Svetlana Sedova 
Occupation: Senior researcher
Affiliation: CEMI RAS
Address: Moscow, Nakhimovky prospect 47
Edition
Abstract
A variant of numerical realization of multi-criteria optimization model of partially integer linear programming with linear and fractional linear criteria is proposed. The number of fractional-linear criteria is limited only by the time required for calculations. The model is designed to form the structure of investment programs for the development of industries and regions, which determines the scope of its application. An appropriate computer system has been created for instrumental support of the model. Questions of adjustment of the course of calculations on a minimax method are discussed. The prospects of increasing the speed of the algorithms are outlined.
Keywords
multi-criteria optimization, minimax method, mixed integer programming, computer system, investment program.
Received
11.03.2019
Date of publication
11.03.2019
Number of characters
10222
Number of purchasers
3
Views
359
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

1 Статья посвящается памяти Евгения Григорьевича Гольштейна, выдающегося ученого в области теории и методов оптимизации. Евгений Григорьевич неоднократно консультировал автора настоящей статьи.
2 На основе многолетних исследований нашего коллектива [1-4] создана и постоянно развивается компьютерная система для формирования и оптимизации структуры инвестиционных программ развития отраслей и регионов (КС ОСИП). Главное окно системы представлено на рис. 1. Структура программы развития, в нашей постановке, определяется: 1) составом инвестиционных проектов, 2) объемами их финансирования, 3) временем запуска каждого проекта, 4) величинами финансовых средств, привлекаемых из бюджета программы в каждый период ее горизонта. Бюджет программы формируется из трех источников: средств Федерального бюджета (ФБ), реинвестируемой прибыли и кредитов банков.
3

Рис. 1. Главное окно КС ОСИП

4

КС ОСИП реализована на базе MS Excel с привлечением пакетов целочисленного линейного программирования и обеспечивает:

- хранение массивов данных о разрабатываемой программе и проектах-кандидатах на включение в программу;

- легкое формирование соответствующих поставленным целям оптимизационных задач частично целочисленного линейного программирования (ЧЦЛП);

- запись данных в формате, требуемом пакетом ЧЦЛП;

- представление результатов получаемого решения в удобном для пользователя виде;

- вычисление на основе результатов решения оптимизационной задачи оценочных экономических показателей и сравнение различных вариантов структуры программ;

- накопление построенных оптимизационных задач и полученных вариантов структуры программ.

5 Ядром представляемой КС является многокритериальная оптимизационная модель, которая позволяет рационально распределять финансовые ресурсы, собираемые в едином бюджете программы, между большим числом инвестиционных проектов, инициированных независимыми экономическими субъектами. Модель подробно описана в ряде наших работ, например [3-5]. Отметим, что в модели в каждый период действия программы происходит взаимная увязка объемов финансирования и сроков запуска проектов, с одной стороны, и потребности в средствах ФБ, реинвестируемой прибыли и кредите, с другой стороны.
6 Представим общий вид модели, являющейся задачей многокритериальной оптимизации ЧЦЛП с линейными и дробно-линейными критериями.
7

8 где x — вектор переменных, определяющих структуру программы; — функция, соответствующая линейному и дробно-линейному показателю l; — вес показателя l; L — множество номеров показателей; G — множество линейных ограничений.
9 В настоящей статье обсуждаются использованные в КС ОСИП методы численной реализации указанной мнококритериальной оптимизационной модели. Известно, что в отличие от однокритериального случая выбор оптимального решения в задаче многокритериальной оптимизации не является однозначным. Из множества эффективных точек [6] (вариантов) лицо принимающее решение (ЛПР) выбирает решения согласно своим предпочтениям. Другими словами, в ходе вычислений ЛПР анализирует множество вариантов и указывает направление улучшения решения. Таким образом, многокритериальную оптимизацию можно рассматривать, как человеко-машинную процедуру анализа различных вариантов с целью получить решения с желаемыми свойствами. Востребованность разработок такого рода в немалой степени зависит от быстродействия методов и алгоритмов численного анализа используемых моделей.
10

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

- метод весовых множителей;

- метод главного критерия (метод пороговых значений);

- метод справедливого компромисса;

- метод приближения к идеальному решению (в частности, метод минимизации суммы или квадрата расстояний от идеальной или заданной точки, минимаксный метод);

- метод последовательных уступок.

11

Выбор метода оптимизации определяется:

- наличием дополнительной информации о критериях (вес, возможность упорядочения по важности, пороговые (желаемые) значения);

- вычислительной сложностью, которая связана с ограничениями по времени решения;

- видом ограничений (выпукла или не выпукла область допустимых значений).

12 Опыт использования большинства из перечисленных методов представлен, например, в работах [7-11]. Наиболее фундаментальным, на наш взгляд, является исследование, посвященное минимаксному методу и изложенное в [7]. В этой работе приводится детальное описание диалоговой системы анализа многокритериальнных задач (ДИСАМЗ). ДИСАМЗ была создана коллективом сотрудников ЦЭМИ РАН под руководством Е.Г. Гольштейна в конце 80-х гг.
13 В связи с возможным использованием в процессе формирования структуры программ развития дробно-линейных критериев мы взяли за основу минимаксный подход из [7] и адаптировали его к особенностям нашей модели. Если ДИСАМЗ предназначалась для линейных и дробно-линейных задач с непрерывными переременными, наша модель формирования структуры инвестиционной программы представляет собой задачу со смешанными переменными. Кроме того, минимаксный метод не ограничивает число дробно-линейных критериев. Приведем схему минимаксного метода и некоторые детали его реализации в КС ОСИП.
14 Для удобства дальнейшего изложения введем обозначения. Пусть J - множество номеров проектов, из которых формируется программа, L1 - множество номеров линейных критериев, L2 - множество номеров дробно-линейных критериев, xj – признак включения проекта j в разрабатываемую программу, cjl и sjl – показатели проекта j, участвующие в образовании критерия l. Тогда линейные критерии записываются в виде
15

16 а дробно-линейные имеют вид
17

18 Не ограничивая общности, будем считать, что все критерии максимизируются. Обозначим значения критериев, получаемые при оптимизации каждого критерия на множестве G, через yl*=max{fl(x)/xG}. Точку y*=(yl*) принято называть идеальной.
19 В минимаксном методе минимизируется максимальное из нормированных расстояний до идеальной точки по отдельным критериям. Исходная задача заменяется задачей
20

21 Эта задача в свою очередь эквивалентна задаче
22

23 Если дробно-линейные критерии отсутствуют, то задача (1)-(3) получается линейной. При наличии дробно-линейных критериев такая задача в работе [7] решается с помощью итеративной процедуры по параметру t. Подобный подход реализован и в нашей компьютерной системе.
24 Задачу (1)-(3) можно сформулировать следующим образом. Найти минимальное значение параметра t=t0, при котором система нелинейных неравенств (2)-(3) окажется совместной.
25 Процедура нахождения параметра t0 реализована нами для случая, когда знаки знаменателей в дробно-линейных критериях на множестве G известны и не меняются. В используемых при разработке инвестиционных программ показателях это условие выполняется практически всегда. Например, в показателе "рентабельность инвестиций" знаменатель "объем дисконтированных вложений" всегда положителен, то же выполняется и для показателя доли перспективных проектов, где в знаменателе находится объем вложений.
26 В этом случае задача (1)-(3) при фиксированном параметре t=t0 легко сводится к задаче ЧЦЛП. Условия (2) с линейной fl(x) преобразуются к виду
27

28 а неравенства (2) с дробно-линейной fl(x) и положительными знаменателями - к виду
29

30 Всем ограничениям ставятся в соответствие дополнительные переменные, и их сумма минимизируется. Если в результате решения полученной таким образом задачи сумма дополнительных переменных оказывается равной нулю, то система (2)-(3) совместна при t=t0. Для поиска минимального t=t0 мы применили дихотомическую процедуру с задаваемой точностью.
31 Подчеркнем, что на каждом шаге описываемой процедуры в нашем случае приходится решать задачу ЧЦЛП. Для этого мы используем модуль, реализующий метод ветвей и границ, разработанный в ЦЭМИ РАН У.Х. Малковым.
32 Границы изменения параметра t легко оценить. Пусть t[t0;t1]. Очевидно, что t0=0, так как yl* - максимальные значения.
33 Обозначим через xl оптимальное решение задачи max{fl(x)/xG}, а через ylk (kL) - значение критерия k, получаемое при максимизации по критерию l, то есть ylk=fk(xl). Тогда
34

35 Различные решения можно получать при различных наборах весов критериальных показателей и использовании вместо y* других экспертно заданных точек. КС ОСИП так же, как и система ДИСАЗМ, допускает настройку хода решения - задание весов показателей целевой функции и желаемых значений показателей.
36 Здесь необходимо отметить следующее. В отличие от задач с непрерывными переменными, решавшихся в ДИСАМЗ, присутствие в нашей модели целочисленных переменных накладывает повышенные требования к быстродействию алгоритмов. Если общее число вариантов проектов, претендующих на включение в инвестиционную программу, меньше 300, вычисления занимают приемлемое время. Если таких вариантов более 500, даже нахождение идеальной точки требует ощутимых временных затрат. Поэтому в этом случае целесообразно вместо идеальной использовать либо экспертно заданную точку, либо точку, полученную при оптимизации так называемой непрерывной задачи по каждому критерию. Непрерывная задача получается из исходной при отказе от требования целочисленности переменных и является оценочной по отношению к исходной.
37 Заметно сократить время вычислений в итерационной по t процедуре в ряде случаев можно, заменяя задачу минимизации суммы дополнительных переменных ее непрерывным аналогом до тех пор, пока не будет найдено первое t, при котором система ограничений (2)-(3) окажется совместной. А затем сначала решать непрерывную задачу и только в том случае, если оптимальное значение ее целевой функции равно нулю, переходить к решению целочисленной.
38 Другим способом уменьшения трудоемкости вычислений по минимаксному методу, предложенным в [7], является сокращение размерности целевой функции за счет перевода части критериев в ограничения и задания для них порговых значений. В КС ОСИП предусмотрена соответствующая опция.
39 Кроме минимаксного метода, КС ОСИП позволяет реализовать метод пороговых значений. Для этого достаточно в окне описания критериев задать (оставить) основной, а в окне описания ограничений настроить ограничения на величины остальных целевых показателей.
40 Мы планируем продолжить работу в направлении увеличения быстродействия алгоритмов многокритериальной оптимизации, используемых в нашей компьютерной системе. Представляется перспективным создание вычислительной процедуры на базе генетических алгоритмов.

References

1. Tatevosyan G.M., Pisareva O.M., Sedova S.V, Toreev V.B. Metody obosnovaniya investitsionnykh programm (real'nyj sektor ehkonomiki). Preprint # WP/2009/260. M.: TsEhMI RAN. 2009, 59 s.

2. Braginskij O.B., Tatevosyan G.M., Sedova S.V. Metodologiya obosnovaniya investitsionnykh programm i ikh optimizatsiya pri ogranichennykh finansovykh resursakh (na primere khimicheskogo kompleksa) // Zhurnal Novoj ehkonomicheskoj assotsiatsii. № 3, 2014. S.130-151.

3. Braginskij O.B., Tatevosyan G.M., Sedova S.V., Magomedov R.Sh. Gosudarstvennye programmy otraslevogo i territorial'nogo razvitiya: problemy metodologii i praktiki upravleniya / Preprint # WP/2017/325. – M.: TsEhMI RAN, 2017. – 72 s.

4. Braginskij O.B., Tatevosyan G.M., Sedova S.V. Sovershenstvovanie gosudarstvennykh programm razvitiya // Ehkonomika i matematicheskie metody. T. 53. № 4, 2017. S. 3—12.

5. Sedova S.V. Model' formirovaniya struktury investitsionnykh programm // Ehkonomika i matematicheskie metody. № 2. 2015. S. 89—102.

6. Podinovskij V.V., Nogin V.D. Pareto-optimal'nye resheniya mnogokriterial'nykh zadach. M.: Nauka, 1982. 256 s.

7. Gol'shtejn E.G., Borisova Eh.P., Dubson M.S. Dialogovaya sistema analiza mnogokriterial'nykh zadach // Ehkonomika i mat. metody. T. 26,. Vyp. 4, 1990. S. 698-709.

8. Nogin V. D. Linejnaya svertka kriteriev v mnogokriterial'noj optimizatsii //Iskusstvennyj intellekt i prinyatie reshenij. – 2014. – №. 4. – S. 73-82.

9. Dubrovin V. I., Mironova H. A., Konoplya V. A. Mnogokriterial'naya optimizatsiya tekhnologicheskogo protsessa s ispol'zovaniem metoda analiza ierarkhij //Radіoelektronіka, іnformatika, upravlіnnya. – 2005. – №. 2 (14). S. 47-53.

10. Mel'kumova E. M. Mnogokriterial'naya optimizatsiya na osnove mery zavisimosti tselevykh funktsij //Izvestiya Tul'skogo gosudarstvennogo universiteta. Estestvennye nauki. – 2011. – №. 1. S. 177-187.

11. Tenenev V. A. Reshenie zadachi mnogokriterial'noj optimizatsii geneticheskimi algoritmami //Intellektual'nye sistemy v proizvodstve. – 2006. – №. 2. – S. 103-109.

12. Moor D. A., Mukhlisullina D. T. Analiz ehffektivnosti razlichnykh svertok kriteriev optimal'nosti v zadache mnogokriterial'noj optimizatsii //Nauka i obrazovanie: nauchnoe izdanie MGTU im. NEh Baumana. – 2010. – №. 04.