Везде
Многокритериальная оптимизация в компьютерной системе формирования структуры инвестиционных программ
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
Многокритериальная оптимизация в компьютерной системе формирования структуры инвестиционных программ
Аннотация
Код статьи
S265838870000194-6-1
DOI
10.33276/S0000194-6-1
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Седова Светлана Владимировна 
Должность: Старший научный сотрудник
Аффилиация: Центральный экономико-математический институт РАН
Адрес: Москва, Нахимовский проспект, 47
Выпуск
Том 1 Выпуск 4
Аннотация
Предложен вариант численной реализации многокритериальной оптимизационной модели частично целочисленного линейного программирования с линейными и дробно-линейными критериями. Число дробно-линейных критериев ограничено только временем, которое требуется для вычислений. Модель предназначена для формирования структуры инвестиционных программ развития отраслей и регионов, что определяет область ее применения. Для инструментальной поддержки модели создана соответствующая компьютерная система. Обсуждаются вопросы настройки хода вычислений по минимаксному методу. Намечены перспективы повышения скорости работы алгоритмов.
Ключевые слова
многокритериальная оптимизация, минимаксный метод, частично целочисленное программирование, компьютерная система, инвестиционная программа
Классификатор
Получено
11.03.2019
Дата публикации
11.03.2019
Всего подписок
13
Всего просмотров
2601
Оценка читателей
0.0 (0 голосов)
Цитировать Скачать pdf
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 Мы планируем продолжить работу в направлении увеличения быстродействия алгоритмов многокритериальной оптимизации, используемых в нашей компьютерной системе. Представляется перспективным создание вычислительной процедуры на базе генетических алгоритмов.

Библиография

1. Татевосян Г.М., Писарева О.М., Седова С.В, Тореев В.Б. Методы обоснования инвестиционных программ (реальный сектор экономики). Препринт # WP/2009/260. М.: ЦЭМИ РАН. 2009, 59 с.

2. Брагинский О.Б., Татевосян Г.М., Седова С.В. Методология обоснования инвестиционных программ и их оптимизация при ограниченных финансовых ресурсах (на примере химического комплекса) // Журнал Новой экономической ассоциации. № 3, 2014. С.130-151.

3. Брагинский О.Б., Татевосян Г.М., Седова С.В., Магомедов Р.Ш. Государственные программы отраслевого и территориального развития: проблемы методологии и практики управления / Препринт # WP/2017/325. – М.: ЦЭМИ РАН, 2017. – 72 с.

4. Брагинский О.Б., Татевосян Г.М., Седова С.В. Совершенствование государственных программ развития // Экономика и математические методы. Т. 53. № 4, 2017. С. 3—12.

5. Седова С.В. Модель формирования структуры инвестиционных программ // Экономика и математические методы. № 2. 2015. С. 89—102.

6. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 с.

7. Гольштейн Е.Г., Борисова Э.П., Дубсон М.С. Диалоговая система анализа многокритериальных задач // Экономика и мат. методы. Т. 26,. Вып. 4, 1990. С. 698-709.

8. Ногин В. Д. Линейная свертка критериев в многокритериальной оптимизации //Искусственный интеллект и принятие решений. – 2014. – №. 4. – С. 73-82.

9. Дубровин В. И., Миронова H. А., Конопля В. А. Многокритериальная оптимизация технологического процесса с использованием метода анализа иерархий //Радіоелектроніка, інформатика, управління. – 2005. – №. 2 (14). С. 47-53.

10. Мелькумова Е. М. Многокритериальная оптимизация на основе меры зависимости целевых функций //Известия Тульского государственного университета. Естественные науки. – 2011. – №. 1. С. 177-187.

11. Тененев В. А. Решение задачи многокритериальной оптимизации генетическими алгоритмами //Интеллектуальные системы в производстве. – 2006. – №. 2. – С. 103-109.

12. Моор Д. А., Мухлисуллина Д. Т. Анализ эффективности различных сверток критериев оптимальности в задаче многокритериальной оптимизации //Наука и образование: научное издание МГТУ им. НЭ Баумана. – 2010. – №. 04.

Комментарии

Сообщения не найдены

Написать отзыв
Перевести