Аннотация результатов, полученных в 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 работают корректно и надежно.

Аннотация результатов, полученных в 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 функция стоимости имеет ступенчатую форму, и предложенный алгоритм построения таких функций сходится за конечное число шагов. Проведено тестирование на реальных данных методов трёхмерной визуализации, предложенных в предыдущий период выполнения проекта, с использованием параллельных вычислений. Как оказалось, параллельные алгоритмы хорошо подходят для такого рода задач, они позволяют существенно сократить время решения и увеличить размер решаемых задач.