Аннотация результатов, полученных в 2017 году
Многомерные эффективные гиперповерхности играют важную роль при анализе деятельности и принятии управленческих решений в сложных объектах. Однако эффективная гиперповерхность, ограничивающая множество производственных возможностей, в явном виде не задана в моделях методологии DEA. Поэтому важнейшие характеристики деятельности производственных объектов (меры эффективности, эффект масштаба, предельные показатели и т.д.) приходится вычислять непрямыми методами с помощью решения дополнительных оптимизационных задач, что, с одной стороны, может приводить к ошибкам, а, с другой стороны, затрудняет аналитикам и экспертам использование методологии АСФ (модели DEA). Нашему коллективу удалось разработать, обосновать и применить специальные методы построения (визуализации) сечений многомерных множеств производственных возможностей. Как оказалось, полученные сечения являются обобщением известных функций в математической экономике (производственная функция, входные и/или выходные изокванты, изокосты и др.) Авторы опубликовали 21 статью на эту тему в журналах из списка WOS, на которые имеется 145 ссылок в международных журналах. Однако для невыпуклых множеств производственных возможностей (FDH модели) ситуация гораздо сложнее: эффективная граница множества имеет ступенчатую форму. При выполнении проекта удалось разработать и опробовать алгоритмы построения сечений (обобщенную производственную функцию, обобщенные входные и выходные изокванты) для невыпуклых FDH моделей на основе последовательного применения методов оптимизации. В алгоритме построения обобщенной производственной функции плоскость сечения задается входным и выходным вектором исследуемого объекта. Важным моментом алгоритма является использование малого параметра. Для корректности работы алгоритма величина малого параметра должна быть больше параметров точности, которые используются в алгоритмах оптимизации, и меньше величины точности исходных данных. Вычислительные эксперименты на реальных данных демонстрируют высокую эффективность разработанных алгоритмов. Для построения обобщенных изоквант по входным (или выходным) показателям для невыпуклых моделей FDH в качестве направлений сечения выбираются единичные векторы в пространстве входных (или выходных) показателей. Далее алгоритм работает таким образом, что последовательно решает оптимизационные задачи, в результате генерируются вершины и отрезки обобщенных (входных или выходных) изоквант. В данном алгоритме также существенную роль играет малый параметр, который позволяет избежать ошибок во время счета и сохраняет движение вдоль сечения. Разработанные алгоритмы были представлены на международных конференциях EWEPA2017 (Лондон, Англия), OPTIMA2017 (Петровац, Черногория), а также изложены в статьях. Производственная функция часто используется для определения эффекта масштаба в заданных точках кривой. Действительно, это важный показатель, как для практического использования, так и для теоретических оценок. Однако эффективная гиперповерхность в модели FDH не гладкая, она имеет ступенчатый вид. Поэтому использовать известные методы для определения эффекта масштаба для моделей FDH нельзя. В мировой научной литературе были предложены остроумные способы для определения эффекта масштаба негладких функций. Для этого вводятся две дополнительные модели: модель с невозрастающим эффектом масштаба (NIRS-FDH) и модель с неубывающим эффектом масштаба (NDRS-FDH). Далее эффект масштаба определяется посредством сравнения мер эффективности в заданной точке для этих трех невыпуклых моделей FDH. Но для этого требуется решить эти целочисленные нелинейные модели. В проекте разработаны методы для построения производственных функций для моделей NIRS-FDH и NDRS-FDH. Но удивительным оказалось то, что для определения эффекта масштаба в заданной точке совсем не обязательно решать две дополнительные модели. Нами было доказано, что достаточно проанализировать только производственную функцию с переменным эффектом масштаба, и из анализа будет ясно, каким эффектом масштаба обладает исследуемый объект. Тем не менее, невыпуклые модели FDH с невозрастающим или неубывающим эффектом масштаба имеют важное самостоятельное значение. Поэтому при выполнении проекта также были построены методы для построения сечений с невозрастающей и неубывающей производственной функцией. За основу берутся угловые точки функции, полученные при построении сечения с переменным эффектом масштаба. Далее, при построении функции с невозрастающим эффектом масштаба, выбираются все вершины с максимальным углом наклона к горизонтальной оси, если таких вершин окажется несколько, то берется вершина с максимальной координатой по горизонтали. Затем выбранные вершины запоминаются и удаляются из итераций, а процесс решения повторяется с оставшимися вершинами, пока они существуют. Сечение с невозрастающим эффектом масштаба для моделей FDH строится подобным образом, но с правого конца. Сначала вычисляется максимальный угол наклона для вершин по отношению к горизонтальной оси. Если таких вершин несколько, то берется вершина с минимальной горизонтальной координатой. Затем, найденные вершины запоминаются и удаляются из итерации, а процесс счета продолжается, пока еще есть вершины. Таким образом, как видно из описанных выше двух алгоритмов, построение двух сечений с неубывающим и невозрастающим эффектом масштаба требует всего несколько вспомогательных операций, если построено уже сечение с переменным эффектом масштаба для модели FDH. Также алгоритмы более эффективны, чем решение двух оптимизационных нелинейных/целочисленных моделей для всех точек кривой сечения, как это до сих пор делается. В мировой научной литературе не было работ по построению сечений (визуализации) невыпуклых (модели FDH) множеств производственных возможностей. Как оказалось, разработанные авторами проекта алгоритмы можно адаптировать для параллельных (распределенных) вычислений. Суть заключается в том, что исходная оптимизационная модель разбивается на вычислительные потоки. Затем каждый вычислительный поток независимо решает оптимизационную задачу. Если оптимальная опорная гиперплоскость совпадает с оптимальной гранью множества производственных возможностей, то вершины этой грани записываются в подмножество точек сечения. В противном случае происходит разделение вычислительного потока, и процесс решения продолжается, пока еще существуют вычислительные потоки. Суммарные подмножества точек сечения дают в итоге сечение эффективной гиперповерхности. Вычислительные эксперименты на реальных данных показали эффективность предложенных алгоритмов с параллельными (распределенными) вычислениями. Полученные результаты докладывались на международной конференции OPTIMA-2017 (Петровац, Черногория), а также представлены в виде статьи (Afanasyev A.P., Krivonozhko V.E., Lychev A.V., Sukhoroslov O.V. Algorithms for Multidimensional Frontier Visualization Based on Optimization Methods Using Distributed Computations // Proceedings of the VIII International Conference on Optimization Methods and Applications OPTIMA-2017, Petrovac, Montenegro, October 2 – 7, 2017, P.13-18, online http:// CEUR-WS.org/Vol-1987/paper3.pdf). Выпуклые (DEA) и невыпуклые (FDH) модели анализируют и оценивают поведение сложных объектов в заданный момент времени. Однако в реальной жизни необходимо оценивать поведение объектов в динамике. Поэтому одна из целей данного проекта состоит в разработке математических моделей и методов, которые позволили бы каждому объекту в отдельности или группе объектов переходить за конечное время в эффективную область, т.е. рассмотреть поведение сложных объектов в динамической среде функционирования. В основе разрабатываемого подхода лежат задачи терминального управления. В задачах терминального управления лежит идея выпуклости и, соответственно, необходимое и достаточное условие оптимальности. В отчетном году разработана концепция задач и методов терминального управления. Основные подходы изложены в статье (Antipin A., Khoroshilova E. Controlled dynamic model with boundary-value problem of minimizing a sensitivity function // Optimization Letters. DOI 10.1007/s11590-017-1216-8).

Аннотация результатов, полученных в 2018 году
При анализе деятельности сложных социально-экономических и производственных систем большую роль играют эффективные гиперповерхности. С их помощью вычисляют различные характеристики деятельности объектов (мера эффективности, эффект масштаба, эластичность, предельные показатели, и т.д.). Однако в явном виде эти гиперповерхности не заданы. Поэтому важнейшие показатели деятельности сложных объектов вычисляются либо непрямыми методами с помощью решения дополнительных оптимизационных задач, либо зависимости между показателями задаются чисто гипотетически, что естественно также приводит к различным неточностям в моделировании. Нашему коллективу удалось впервые в мире разработать, обосновать и применить методы визуализации (построения сечений) многомерных множеств производственных возможностей. Полученные сечения обобщают хорошо известные функции в системном анализе и математической экономике. Авторы опубликовали 28 статей на эту тему в журналах из списка WOS, на которые имеется 178 ссылок в международных журналах. Однако для невыпуклых моделей со свободной оболочкой FDH задача оказалась гораздо сложнее. Эти модели имеют ступенчатую поверхность, поэтому обычные методы анализа к ней неприменимы, точнее говоря, производные по направлению в точках поверхности принимают значения ноль или бесконечность, что, естественно, никак не решает задачу анализа для моделей FDH. В работах К Керстенса, Р Эккаута (1999) и В. Брика, Н.Лелю и К. Керстенса (2000) был предложен остроумный способ оценки эффекта масштаба для FDH моделей с помощью добавления в задачу еще (вспомогательных) моделей: с постоянным (CRTS), убывающим (DRTS) и возрастающим (IRTS) эффектом масштаба. Такая задача требует решения нелинейных смешанных целочисленных моделей даже для вычисления этих показателей в одной точке. Такой подход вызывает большое количество дополнительных вычислений. Работая над проектом, нашему коллективу удалось построить методы сечения для моделей 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. 2018. [принята к печати]). В процессе работы по проекту над алгоритмами сечения удалось показать, что алгоритмы можно распараллелить, что существенно сокращает время расчетов. Дело в том, что сечения являются кусочно-линейными и обычно строятся отрезками, один за другим. При построении сечений для выпуклых множеств производственных возможностей (DEA модели) нам удалось показать, что отдельные вычисления в процессе решения можно проводить параллельно. Тогда эффективная гиперповерхность будет строиться отдельными частями. Использовать данную идею нам помогла замечательная теорема Макмуллена и Шепарда (McMullen, P., Shephard, G.C. (1971). Convex polytopes and the upper bound conjecture, London Mathematical Society lecture note series, vol. 3. Cambridge University Press, Cambridge.), сформулированная для выпуклых многогранников. Нами подготовлен и опробован алгоритм. Результаты изложены в статье (Afanasyev A.P., Krivonozhko V.E., Lychev A.V., Sukhoroslov O.V. Multidimensional frontier visualization based on optimization methods using parallel computations // Journal of Global optimization. [находится на рассмотрении]). В процессе проведения вычислительных экспериментов нами было замечено, что большая часть неэффективных объектов проецируется на слабо эффективные грани (такие же наблюдения мы нашли у наших коллег за рубежом), что естественно противоречит теории, так как мера эффективности неэффективного объекта должна измеряться относительно эффективных объектов. Для преодоления указанных неточностей нами было предложено вводить в модель по определенным правилам искусственные объекты. Затем возник вопрос: а как при этом меняется гладкость эффективной гиперповерхности? В работе над проектом наш коллектив разработал количественную меру гладкости эффективной гиперповерхности, которая использует алгоритмы построения сечений. Результаты протестированы и изложены в статье (Krivonozhko V. E., Førsund F. R., Lychev A.V. Measuring the Smoothness of the DEA Frontier // Optimization letters. 2018. https://doi.org/10.1007/s11590-018-1329-8 [принята к печати]).

Аннотация результатов, полученных в 2019 году
Все разработанные и протестированные при работе по гранту методы и алгоритмы имеют общую методологическую основу. Однако алгоритмически они слабо связаны. Поэтому на третьем сроке выполнения проекта было решено протестировать все алгоритмы на реальных данных, а затем объединить их в единую вычислительную среду, чтобы сравнить скорость их работы. Для тестирования алгоритмов были собраны следующие наборы реальных данных: данные для оценки деятельности энергопредприятий; статистические данные по социальным и экономическим показателям регионов Российской Федерации; финансовые показатели деятельности отечественных банков. Кроме того, для полноты эксперимента потребовалось построить модель, которая имеет существенно дискретные показатели, в нашем случае это были рыболовные траулеры дальневосточного региона. Действительно, многие характеристики траулеров имеют дискретный характер: водоизмещение судна, число человек в команде, мощность двигателя. По этой причине эта модель была тоже включена в набор моделей для проведения вычислительных экспериментов. Результаты расчётов подробно описаны в подготовленном научно-аналитическом отчёте, там также дан фрагмент программной реализации алгоритма визуализации изокванты для модели FDH в единой вычислительной среде. Алгоритм был реализован на языке C# с использованием библиотеки .Net Framework. При выполнении вычислительных экспериментов с реальными данными нам удалось обнаружить удивительный факт: большая часть неэффективных объектов проецируется на слабо эффективные по Парето грани. Однако это наблюдение противоречит теории, так как неэффективные объекты должны сравниваться с эффективными (об этом ранее писал J. Dula, но этот факт оставался без комментариев в литературе). Для преодоления указанных неточностей мы предложили вводить в модель новые эффективные объекты, при этом должны соблюдаться следующие условия: все эффективные объекты должны оставаться эффективными; все терминальные объекты становятся обычными эффективными объектами; все неэффективные объекты проецируются на эффективные грани. В процессе тестирования было обнаружено, что алгоритм обладает достаточной гибкостью, в зависимости от заданных параметров он в результате может построить несколько различных эффективных фронтов. Поэтому для того чтобы охарактеризовать полученный результат, был введён коэффициент гладкости. Причём для корректности вычислений показатель гладкости должен удовлетворять следующим принципам: а) он не должен зависеть от единиц измерения показателей в моделях DEA; б) увеличение гладкости соответствует меньшей величине коэффициента сглаживания. Наши теоретические результаты подтверждаются вычислительными экспериментами на реальных данных. Результаты по данной теме докладывались на международной конференции в Праге (Krivonozhko V. E., Førsund F. R., Lychev A. V. On the concept and measurement of frontier smoothness in DEA models // 15th International Conference on Data Envelopment Analysis, Prague, Czech Republic, June 26 – 29, 2017. P.30). Теория и вычислительные эксперименты по данной теме подробно изложены в статье (Krivonozhko V.E., Førsund F.R., Lychev A.V. Measuring the smoothness of the DEA frontier // Optimization Letters. 2019. V. 13, № 8. P. 1871–1884).