КАРТОЧКА
ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер 17-11-01353
НазваниеРазработка моделей и методов для анализа деятельности и визуализации поведения сложных многомерных объектов
РуководительКривоножко Владимир Егорович, Доктор физико-математических наук
Организация финансирования, регион Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский технологический университет "МИСИС", г Москва
Период выполнения при поддержке РНФ | 2020 г. - 2021 г. |
Конкурс Конкурс на продление сроков выполнения проектов, поддержанных грантами Российского научного фонда по приоритетному направлению деятельности Российского научного фонда «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами» (18).
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-203 - Теория оптимизации и исследование операций
Ключевые словаисследование операций, оптимизационное моделирование, системный анализ, анализ эффективности и продуктивности, анализ среды функционирования, распределенные вычисления
Код ГРНТИ28.29.15
СтатусУспешно завершен
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Методология анализа среды функционирования (АСФ) возникла как обобщение простых показателей деятельности объектов на многомерный случай, т.е. когда деятельность сложного объекта описывается набором простых показателей. Для корректности и содержательности такой постановки рассматривается множество подобных сложных объектов. Математически такой подход сводится к решению большого семейства оптимизационных задач. Основоположниками данного подхода были выдающиеся американские учёные А.Чарнес, Р.Купер, Е.Роудс и Р.Бэнкер (на английском языке данный подход называется Data Envelopment Analysis – DEA).
Модели со свободной оболочкой FDH (Free Disposal Hull) появились почти одновременно с моделями DEA в статьях Д.Депринса, Л.Симара и Г.Тулкенса (Deprins, D., Simar L., Tulkens H. Measuring Labor Efficiency in Post Offices / Marchand M., Pestieau P., Tulkens H. (eds.), The Performance of Public Enterprises: Concepts and Measurements. – Amsterdam: North Holland, 1984. – P.243-268).
В моделях DEA множество производственных возможностей является выпуклым множеством. Поэтому модели DEA стали развиваться быстрее, поскольку в этих моделях стали активно использоваться методы и программные средства оптимизации, которые к этому времени достигли значительного прогресса. Однако функциональные зависимости между переменными в моделях DEA в явном виде не заданы. Поэтому важнейшие характеристики деятельности объектов приходится вычислять непрямыми методами с помощью решения дополнительных оптимизационных задач, что существенно затрудняет экспертам и аналитикам использовать методологию DEA. Кроме того, такой непрямой путь также может давать некорректные результаты.
Сравнительно недавно в мировой научной литературе был предложен новый подход анализа моделей DEA с помощью построения явных зависимостей (визуализации) между переменными на основе построения сечений многомерных множеств. Такой подход оказался успешным. Авторам проекта удалось разработать и применить эффективный и надёжный подход для двух- и трёхмерной визуализации многомерных множеств в моделях DEA.
Однако невыпуклость ограничений и специфика моделей FDH сдерживали развитие и применение данной модели. Дж.Цезарони, К.Керстенс и И.Ван де Вайстайн в своей работе (Cesaroni G., Kerstens K., Van de Woestyne I. Global and local scale characteristics in convex and nonconvex nonparametric technologies: A first empirical exploration // European Journal of Operational Research. – 2017. – V.259, №2. – P. 576–586) указали, что в мировой литературе не было работ по построению (визуализации) многомерного фронта для невыпуклых моделей FDH.
Во время выполнения Проекта 2017 были предложены и протестированы методы двумерной визуализации (построения сечений) в невыпуклых моделях FDH.
Проект 2020 направлен на разработку моделей и методов трёхмерной визуализации для моделей с невыпуклыми множествами производственных возможностей (модели FDH), апробацию методов на реальных задачах, разработку методов поведения объектов в динамике, разработку алгоритмов сечения многомерных множеств с использованием параллельных (распределённых) вычислений.
Ожидаемые результаты
В результате выполнения проекта будут разработаны, обоснованы и протестированы на реальных данных методы и программы визуализации (построения сечений) для невыпуклых и смешанных множеств производственных возможностей:
1. метод трёхмерной визуализации с тремя входными переменными (входная изокванта) для невыпуклых моделей со свободной оболочкой (FDH модели);
2. метод трёхмерной визуализации с тремя выходными переменными (выходная изокванта) для невыпуклых моделей со свободной оболочкой (FDH модели);
3. метод трёхмерной визуализации с двумя входными и одной выходной переменной, с одной входной и двумя выходными переменными (обобщённая производственная функция) для невыпуклых моделей со свободной оболочкой (FDH модели);
4. метод трёхмерной визуализации для невыпуклых моделей с использованием параллельных (распределённых) вычислений;
5. метод двумерной визуализации для смешанных моделей с выпуклыми и невыпуклыми ограничениями;
6. метод улучшения фронта для невыпуклых моделей;
7. методы моделирования различных деловых ситуаций в многомерном пространстве с помощью программы визуализации;
8. метод визуализации с использование функции стоимости (cost function).
Цель работ по проекту состоит в разработке научно-обоснованных методов и программного инструментария для анализа деятельности и оценки функционирования сложных многомерных объектов (регионов, стран, финансовых институтов, муниципальных образований, университетов и т.д.). Следует отметить, что несмотря на высокую потребность, подобный анализ проводится до сих пор с помощью набора коэффициентов (рейтинговый подход). В нашей работе (Krivonozhko V. E., Piskunov A. A., Lychev A. V. On comparison of ratio analysis and data envelopment analysis as performance assessment tools // IMA Journal of Management Mathematics. 2011. V. 22, № 4. P. 357–370) было показано, что рейтинговый подход вносит искажения в оценку деятельности сложных объектов. Но самое существенное состоит в том, что с помощью рейтингового подхода нельзя найти пути улучшения деятельности объектов. Модели DEA и FDH возникли как обобщение простых показателей деятельности на многомерный случай, т.е. когда деятельность сложного объекта описывается набором простых показателей.
В своих предыдущих работах участники проекта разработали и протестировали на реальных данных (регионы, финансовые институты, учебные заведения и т.д.) методы анализа и визуализации в моделях DEA. В данном проекте авторы предполагают разработать и проанализировать на реальных данных поведение многомерных объектов с помощью трёхмерной визуализации невыпуклых моделей FDH и смешанных моделей.
Как отмечено в работе (Cesaroni G., Kerstens K., Van de Woestyne I. Global and local scale characteristics in convex and nonconvex nonparametric technologies: A first empirical exploration // European Journal of Operational Research. – 2017. – V.259, №2. – P. 576–586) в мировой литературе нет работ по построению многомерного фронта для невыпуклых моделей FDH. В Проекте 2017 участники впервые в мире разработали и обосновали двумерную визуализацию невыпуклых моделей FDH. В Проекте 2020 предполагается разработать, обосновать и протестировать на реальных данных трёхмерную визуализацию (построение сечений) многомерных множеств.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Аннотация результатов, полученных в 2020 году
С самого начала появления методологии анализа среды функционирования (АСФ) (англ. Data Envelopment Analysis – DEA) и модели Free Disposal Hull (FDH) всем казалось, что эти два направления внесут существенный вклад в визуализацию деятельности сложных многомерных объектов. Тем более, что к концу 20 века методы оптимизации достигли большого прогресса, как в теоретическом, так и в практическом плане. Однако развитие методов визуализации (построения сечений многомерных множеств) существенно сдерживалось. В наших статьях мы объяснили причину этого явления. Дело в том, что ограничения в оптимизационных задачах можно записать в двух видах: пересечение полупространств (постановка 1), и выпуклая сумма вершин и направляющих векторов неограниченных ребер (постановка 2).
Все мощные программы оптимизации были, в основном, написаны для первого случая. Существуют алгоритмы и программные реализации для перехода от одной формы представления к другой. Однако это вызывает существенное увеличение времени вычислений. В ряде международных журналов было показано, что число векторов, определяющих гиперплоскости существенно больше, чем вершин у многогранного множества. Более того, в наших работах было показано, что попытка использовать методы первой группы приводит к вырожденным базисам и появлению «ложных» вершин в процессе решения, что дает в результате некорректное решение. Тем не менее, в международных журналах появляются статьи, которые предлагают методы на основе постановки 1. Сравнительно недавно появилась работа [Mehdiloozad M., Mirdehghan S.M., Sahoo B.K., Roshdi I. On the identification of the global reference set in data envelopment analysis // European Journal of Operational Research. 2015. V. 245, № 3. P. 779-788], где авторы утверждают, что их метод более эффективен, чем другие существующие методы по нахождению объектов, формирующих минимальную грань. Этот метод, назовем его алгоритм 2, действительно представляет большой интерес, однако эффективность работы алгоритма показывается на примере с небольшим числом объектов, поэтому такой пример не дает возможности судить об эффективности алгоритма.
Поэтому коллектив проекта решил провести сравнение различных методов вычисления эффекта масштаба в нерадиальных моделях методологии АСФ. Для измерения зависимости времени вычисления каждого алгоритма от числа производственных объектов было необходимо сгенерировать наборы данных с различным числом производственных объектов. Эти наборы создаются из набора данных большего размера с помощью выбора заданного числа объектов случайным образом, затем выполняются расчеты и определяется время вычислений. Для надежности измерений подобные операции производятся десять раз и время вычислений усредняется. Графики зависимостей приводятся в статьях. Из этих графиков легко видеть, что время вычислений алгоритма 2 увеличивается значительно с ростом числа производственных объектов.
Для того чтобы выявить причины расхождений времени вычисления различных алгоритмов. Оказалось, что коэффициент обусловленности алгоритма 2 всегда больше, чем в нашем алгоритме. Это означает, что в процессе вычислений алгоритм 2 генерирует плохо обусловленные матрицы, тем самым процесс решения замедляется. Наша статья с подробными результатами вычислений сдана в журнал Доклады академии наук.
В статье [Кривоножко В. Е., Лычев А. В. Визуализация эффективного фронта для невыпуклых моделей на основе алгоритмов целенаправленного перебора // Доклады Академии наук, 2017, Т. 477, № 1, С. 22–25] разработаны методы визуализации эффективного фронта с использованием методов целенаправленного перебора, а в работе [Кривоножко В.Е., Лычев А.В. Визуализация эффективной гиперповерхности и измерение эффекта масштаба в невыпуклых моделях анализа среды функционирования // Журнал вычислительной математики и математической физики. 2019. Т. 59, № 3. С. 534–546] предложены алгоритмы для вычисления эффектам масштаба с использованием построения двумерных сечений. В этих статьях используется визуализация исключительно на основе построения двумерных сечений.
В 2020 году были разработаны и обоснованы алгоритмы для построения трехмерных сечений невыпуклого многомерного фронта с использованием методов целенаправленного перебора, в частности визуализации на основе построения трёхмерных сечений с тремя входными переменными. Данный вид сечения позволяет вычислять замещения между тремя ресурсами в моделях FDH при одновременном изменении сразу трех показателей.
Для построения сечения используется специальное представление множества производственных возможностей модели FDH в виде объединения выпуклых множеств более простого вида. Доказана сходимость алгоритма за конечное число шагов. По результатам работы подготовлена статья.
Проведено тестирование разработанного метода трехмерной визуализации с тремя входными переменными (входная изокванта) для модели FDH на статистических данных по финансовым институтам РФ. Для тестирования использовалась модель по надежности банков. Для расчётов были выбраны 200 самых крупных банков по размеру капитала на 1 января 2018 г. Вычислительные эксперименты показали, что разработанные алгоритмы построения трехмерных сечений в невыпуклых моделях FDH работают корректно и эффективно.
В отчетном году разработан и обоснован метод визуализации на основе построения трехмерных сечений с тремя выходными переменными (выходная изокванта) для модели FDH. Этот вид трехмерного сечения является обобщением известной в математической экономике выходной изокванты. В алгоритме построения используется свойство множества производственных возможностей T модели FDH, которое говорит, что множество T является объединением множеств Si, которые определены для каждого производственного объекта i. Множество Si представляет собой конус с тремя направляющими векторами (соответствующими трем выходным показателям), а вершиной конуса является сам производственный объект.
Процедура нахождения граней сечения основывается на утверждении о том, что трехмерное сечение модели FDH имеет не более 3N граней, где N - число вершин сечения. Доказана сходимость алгоритма за конечное число шагов. Алгоритм реализован в виде программного кода. По итогам работы написана статья.
Проведено тестирование разработанного метода трехмерной визуализации с тремя выходными переменными (выходная изокванта) для модели FDH на статистических данных по финансовым институтам РФ. Вычислительные эксперименты показали, что разработанные алгоритмы построения трехмерных сечений в невыпуклых моделях FDH работают корректно и строят сечения за приемлемое время.
В отчетном году разработан и обоснован метод визуализации на основе построения трехмерных сечений с двумя входными и одной выходной переменной, с одной входной и двумя выходными переменными для модели FDH. Доказано, что алгоритм сходится за конечное число шагов. Алгоритм протестирован на реальных данных. Подготовлена статья для публикации.
Разработан и протестирован метод визуализации для невыпуклых моделей с использованием параллельных (распределённых) вычислений. Для тестирования предложенного метода с использованием параллельных (распределённых) вычислений были использованы данные по рыболовным траулерам дальневосточного региона. Набор данных содержит 233 объекта, статистические данные представлены за 2003-2005 гг. В данной модели некоторые входные показатели имеют дискретный характер: водоизмещение, количество членов экипажа, мощность двигателя. Вычислительные эксперименты показали, что разработанные алгоритмы построения трехмерных сечений в невыпуклых моделях FDH работают корректно и надежно.
Публикации
1. Антипин А., Хорошилова Е. Saddle-Point Methods for Solving Terminal Control Problems with State Constraints and Boundary-Value Problems Journal of Global Optimization, - (год публикации - 2021)
2. Кривоножко В.Е., Форсунд Ф.Р., Лычев А.В. Implementation of the algorithm for improving the frontier in DEA models 7th International Conference on Control, Decision and Information Technologies CoDIT’20, Vol.1, P. 487-491 (год публикации - 2020) https://doi.org/10.1109/CoDIT49905.2020.9263777
3. Рожнов А.В. Investigation of new features of the virtual semantic environment prototype in the development and application of infrastructure of highly automated and intelligent transport systems 2020 2nd International Conference on Control Systems, Mathematical Modelling, Automation and Energy Efficiency (SUMMA), - (год публикации - 2020)
4. Рожнов А.В. Integration of Hybrid Intelligence Components Based on the Quadrant Enabled Delphi Method While Diversifying XBML Capabilities 2020 13th International Conference "Management of large-scale system development" (MLSD), pp.1-4 (год публикации - 2020) https://doi.org/10.1109/MLSD49919.2020.9247680
Аннотация результатов, полученных в 2021 году
В мировой научной литературе появлялись работы, в которых отмечалась необходимость визуализации многомерных множеств производственных возможностей, выпуклых и невыпуклых. Но такие работы носили, скорее всего, эвристический характер, не было строгого научного обоснования подобных методов. Более того, они не были проверены на реальных задачах. В работах авторов данной темы появились научно обоснованные и надёжные методы для визуализации сначала выпуклых моделей DEA (на русском языке этот термин звучит как анализ среды функционирования – АСФ), затем невыпуклых моделей FDH (Krivonozhko V.E., Lychev A.V. Frontier visualization and estimation of returns to scale in free disposal hull models // Computational Mathematics and Mathematical Physics. 2019. V.59, № 3. P. 501–511). За основу был взят тот факт, что задачи оптимизации можно записать в двух видах: пересечение полупространств и как комбинацию крайних точек и лучей. Все методы и разработанные на их основе программы оптимизации в мире используют первый вид представления. Авторы проекта стали разрабатывать методы визуализации на основе второго представления, такой подход позволил создать эффективные методы визуализации для выпуклых и невыпуклых моделей. Однако модели DEA и модели FDH являются двумя крайними случаями возможных моделей. В научной литературе стали появляться статьи, которые стремились частично ослабить ограничения выпуклости. В работах (Podinovski, V.V. Selective convexity in DEA models, European Journal of Operational Research, V.161, N.2, 2005, pp.552–563; Olesen, O.B., Petersen, N.C., Podinovski, V.V. Efficiency analysis with ratio measures, European Journal of Operational Research, V.245, N.2, 2015, pp.446–462; Olesen, O.B., Petersen, N.C., Podinovski, V.V. Efficiency measures and computational approaches for data envelopment analysis models with ratio inputs and outputs, European Journal of Operational Research, V.261, N.2, 2017, pp.640–655) вводится и изучается понятие смешанной выпуклости (selective convexity), а также выписываются нелинейные модели для нахождения мер эффективности в данных моделях.
Авторы разработали подход для построения методов двумерной визуализации в смешанных моделях, результаты были описаны и представлены в статье (Afanasyev A.P., Krivonozhko V.E., Lychev A.V., Sukhoroslov O.V. Constructions of input and output isoquants in DEA models with selective convexity // Applied and Computational Mathematics), которая принята к печати.
Предложенные методы двумерной визуализации для смешанных моделей с выпуклыми и невыпуклыми ограничениями были опробованы на тестовых и реальных задачах.
Визуализация позволяет строить траектории развития объектов, рассматривать объединение или разделение производственных объектов.
Способ улучшения эффективного фронта для невыпуклых моделей FDH является одним из важнейших моментов применения методов визуализации. Для улучшения фронта в моделях FDH необходимо вводить новые объекты на сечениях и строить новые сечения с учётом введённых производственных объектов. Предложенный подход хорошо себя зарекомендовал.
При разработке и апробации методов улучшения фронта для моделей со свободной оболочкой (FDH модели) авторы использовали методы визуализации, разработанные для этих моделей, причём использовались как двумерные, так и трёхмерные сечения.
Наибольшую пользу методы визуализации многомерных моделей дают при моделировании деловых ситуаций. Обнаружить случаи некорректностей в моделях и выявить их причины достаточно сложно, но с помощью методов визуализации такие ситуации выявляются достаточно быстро.
Разработаны и обоснованы алгоритмы для построения функции стоимости в невыпуклых моделях FDH с использованием методов целенаправленного перебора. Нами доказано, что для модели FDH функция стоимости имеет ступенчатую форму, и предложенный алгоритм построения таких функций сходится за конечное число шагов.
Проведено тестирование на реальных данных методов трёхмерной визуализации, предложенных в предыдущий период выполнения проекта, с использованием параллельных вычислений. Как оказалось, параллельные алгоритмы хорошо подходят для такого рода задач, они позволяют существенно сократить время решения и увеличить размер решаемых задач.
Публикации
1. Афанасьев А.П., Кривоножко В.Е., Лычев А.В., Сухорослов О.В. Constructions of input and output isoquants in DEA models with selective convexity Applied and Computational Mathematics, - (год публикации - 2022)
2. Афанасьев А.П., Кривоножко В.Е., Форсунд Ф.Р., Лычев А.В. Multidimensional Visualization of Data Envelopment Analysis Models Data Envelopment Analysis Journal, Vol. 5: No. 2, pp 339-361 (год публикации - 2021) https://doi.org/10.1561/103.00000040
3. Будко П.А., Гойденко В.К., Рожнов А.В., Винограденко А.М. The Integrated Statistical Control Method of Technical Condition of Radio-Electronic Equipment for Prototyping of Robotic Systems EPJ Web of Conferences, Vol. 248 . С. 02004 (1-4) (год публикации - 2021) https://doi.org/10.1051/epjconf/202124802004
4. Кривоножко В.Е., Форсунд Ф.Р., Лычев А.В. Methods of frontier visualization in Data Envelopment Analysis Models Data Envelopment Analysis Journal, - (год публикации - 2022)
5. Ратнер С.В., Лычев А.В., Рожнов А.В., Лобанов И.А. Efficiency Evaluation of Regional Environmental Management Systems in Russia Using Data Envelopment Analysis Mathematics, Vol. 9, No. 18, P. 2210 (год публикации - 2021) https://doi.org/10.3390/math9182210
6. Рожнов А.В Some Issues of Scientific and Methodological Support in the Aspect of Advanced Development of Heterogeneous Intelligent Transport Technologies 2021 3rd International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA), - (год публикации - 2021)
7. Рожнов А.В. Development and Research of Hybrid Intelligence Components Based on the Quadrant Enabled Delphi Method with the Associated Application of the Data Envelopment Analysis 2021 14th International Conference Management of large-scale system development (MLSD), P. 1-5 (год публикации - 2021) https://doi.org/10.1109/MLSD52249.2021.9600128
Возможность практического использования результатов
Данное направление характеризуется тем, что оно гармонично объединяет теорию (решение задач большой размерности, параллельные вычисления, визуализацию получаемых решений, использование различных моделей для оптимизации) и необходимость решения практических задач, которые, в свою очередь, дают возможность дальше развивать теорию и моделирование в конкретных областях экономики страны и социальной сфере.
Коллектив имеет большой опыт по решению практических задач.
1. Члены коллектива анализировали деятельность финансовых институтов страны по заказу Центрального банка.
2. В течение ряда лет коллектив сотрудничал со Счётной палатой РФ и выполнил ряд расчётов по анализу деятельности регионов страны.
3. Коллектив выполнял работы по анализу деятельности высших учебных заведений страны.
Кроме того, авторский коллектив участвовал в работах по оценке деятельности ряда крупных предприятий.
Интересно отметить, что многие предприятия и министерства в своей деятельности используют «простые» методы для оценки деятельности компаний, например, используют рейтинги. По этой причине авторы написали большую статью в международный журнал (Krivonozhko V. E., Piskunov A. A., Lychev A. V. On comparison of ratio analysis and data envelopment analysis as performance assessment tools // IMA Journal of Management Mathematics. 2011. V. 22, № 4. P. 357–370), где сравнили рейтинговый подход и оценку деятельности на основе подхода DEA. Статья вызвала большой интерес, до сих пор авторам приходят письма с просьбой ответить на ряд вопросов.
Авторы уверены, что проведённые исследования и сформированный большой научный задел приведёт к усовершенствованию применяемых технологий в анализе деятельности сложных социально-экономических систем, что в итоге будет способствовать экономическому росту и социальному развитию Российской Федерации.