Построение алгоритмов сечений эффективного фронта аффинными подпространствами в методологии Анализа Среды Функционирования тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Сафин, Михаил Масхутович

• Сафин, Михаил Масхутович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Сафин, Михаил Масхутович

Введение

Глава 1. Основные положения методологии АСФ.

1.1 Множество производственных возможностей.

1.2 Модель ВСС.

1.3 Обобщенная модель ВСС.

1.4 Оптимальность по Парето применительно к методологии

Глава 2. Визуализация множества производственных возможностей модели ВСС.

2.1 Построение двумерных сечений эффективного фронта.

2.1.1 Алгоритм построения обобщенной производственной функции

2.1.2 Алгоритм построения произвольного двумерного сечения многомерного эффективной гиперповерхности.

2.2 Построение трехмерных сечений эффективного фронта.

2.2.1 Алгоритм изменения границы выпуклого многогранного множества в трехмерном пространстве при добавлении новой точки

2.2.2 Алгоритм построения трехмерного сечения по двух входным и одному выходному параметрам

Глава 3. Построение сечений эффективного фронта обобщенной модели ВСС аффинными подпространствами произвольной размерности.

3.1 Алгоритм построения выпуклой оболочки конечного набора точек и векторов направлений в многомерном пространстве.

3.2 Алгоритм построения сечения политопа аффинным подпространством произвольной размерности.

3.2.1 Определение базисных точек и размерности сечения

3.2.2 Уточнение граней искомого сечения

3.3 Алгоритм построения сечения выпуклого многогранного множества аффинным подпространством произвольной размерности.

3.4 Сложность вычислений.

Глава 4. Применение сечений эффективного фронта для социально-экономической диагностики субъектов Южного Федерального округа.

4.1 Выбор агрегированных параметров и построение модели

4.2 Анализ результатов моделирования.

Введение диссертации (часть автореферата) на тему «Построение алгоритмов сечений эффективного фронта аффинными подпространствами в методологии Анализа Среды Функционирования»

Методология Анализа Среды Функционирования (АСФ)1 возникла как обобщение простых коэффициентов анализа деятельности объектов [1-5] на многомерный случай, т.е. когда деятельность сложного объекта описывается набором входных параметров (xi,.,xm) и набором выходных параметров (уь.,уг). Для корректности и содержательности такой постановки рассматривается множество подобных сложных объектов. Тогда математически такой подход сведется к решению большого семейства оптимизационных задач. Основоположниками данного подхода были известные американские ученые А.Чарнес и В.Купер [6-8].

В последнее время начался настоящий бум по применению методологии АСФ для анализа деятельности отраслей экономики, регионов, крупных компаний и муниципальных организаций. Число публикаций^ по данной тематике в международных журналах составляет несколько тысяч единиц (см., например, ссылки в [8]). Мировые конгрессы и конференции проводят по вопросам методологии АСФ отдельные секции, данному подходу посвящаются специальные конференции.

Подход методологии АСФ к анализу деятельности сложных систем оказался плодотворным и конструктивным. В настоящее время методология, АСФ охватывает гораздо более широкий спектр понятий и возможностей, чем просто вычисление и анализ эффективности сложных объектов. Она позволяет строить многомерное пространство множества производственных возможностей, находить оптимальные пути развития в нем, вычислять важнейшие количественные и качественные характеристики поведения объектов, моделировать

1 Англоязычное название методологии - Data Envelopment Analysis (DEA) различные ситуации. При реализации данной методологии используются современные достижения в области математического программирования, теории и методов решения задач оптимизации большой размерности, многокритериальной оптимизации, выпуклого анализа, а также компьютерного моделирования [9-34].

Актуальность проблемы. В работах многих классиков [6-8, 3559] утверждалось, что в рамках методологии Анализа Среды Функционирования (АСФ) необходимо развивать методы представления и визуализации рассчитанных результатов. Это не только дает возможность лицу, принимающему решения, лучше ориентироваться в многомерном пространстве параметров, но и помогает в создании и модификации самих моделей методологии АСФ. Так, например, обобщенную модель, предложенную в? статьях [36-38], было бы сложно применить на практике, если бы не существовало средств визуального представления множества производственных возможностей.

Многомерное множество производственных возможностей можно визуально представить единственных способом - при помощи двумерных и трехмерных сечений, поскольку человеческий глаз воспринимает пространства именно такой размерности. Такое представление позволяет свести анализ сложных систем в рамках методологии АСФ к изучению хорошо известных функций в математической экономике: производственная функция, изокванта по входным параметрам, изокванта по выходным параметрам, изокоста, изопрофита. [60-67]. Тем самым построение сечений множества производственных возможностей в рамках методологии АСФ вносит существенный вклад и в развитие анализа деятельности сложных социальных и экономических систем.

В научной литературе рассматривались методы визуализации многомерных выпуклых множеств [63-64, 68-71], но все они носили исключительно теоретический характер или были применимы для узкого множества задач с жесткими ограничениями на размерность сечения, форму множества производственных возможностей и относительного положения плоскости сечения.

В работе [68] предложен алгоритм построения сечения на основе описания всех граней эффективного фронта в исходном многомерном пространстве параметров. Но в большинстве случаев размерность множества производственных возможностей значительно больше, чем размерность сечения, поэтому предложенный алгоритм является неэффективным. Это связано с тем, что сложность алгоритма описания всех граней зависит экспоненциально от размерности множества производственных возможностей [69]. По этим причинам не.подходят для решения поставленной задачи и прямое использование алгоритмов построения выпуклых оболочек, применяемых в вычислительной геометрии [69-70], а также методы визуализации Парето эффективных границ [71].

Параметрические алгоритмы построения двумерных сечений [63] были реализованы на практике, но эти алгоритмы обладают низкой производительностью и не достаточной точностью вычисления. Поэтому развитие данных алгоритмов для построения трехмерных сечений [64] сталкиваются со значительными трудностями при практической реализации. Кроме того, предложенные параметрические методы не имеют достаточной гибкости. Они привязаны к определенному виду множества производственных возможностей и типу сечения. Поэтому их применение для обобщенных моделей методологии АСФ становится затруднительным.

Исходя из вышесказанного, можно сделать вывод, что необходим новый подход к визуализации множества производственных возможностей. Такой подход должен быть надежным, гибким и практически применимым.

Основной целью работы является разработка математического аппарата, позволяющего строить сечения множества производственных возможностей в моделях методологии АСФ при помощи аффинных подпространств произвольной размерности.

Задачи работы:

• усовершенствовать алгоритмы построения двумерных сечений многомерного эффективного фронта для модели ВСС;

• разработать алгоритмы построения трехмерных сечений многомерного эффективного фронта для модели ВСС;

• обобщить алгоритмы построения двумерных и трехмерных сечений эффективного фронта на случай сечений произвольной размерности;

• развить алгоритмы построения сечений для модели ВСС на случай обобщенной модели методологии АСФ.

Научная новизна диссертации состоит в реализации качественно нового подхода к построению алгоритмов сечений эффективного фронта в моделях методологии АСФ:

• предложены новые алгоритмы построения двумерных сечений множества производственных возможностей для модели ВСС в методологии АСФ, превосходящие существующие алгоритмы в скорости и точности вычислений;

• впервые разработан алгоритм построения трехмерных сечений множества производственных возможностей для модели ВСС в методологии АСФ, который реализован на практике;

• предложенные методы построения сечений обобщены для сечения эффективного фронта аффинными подпространствами произвольной размерности;

• впервые созданы алгоритмы построения сечений множества, производственных возможностей для обобщенной модели методологии АСФ;

• все предложенные алгоритмы реализованы в программном комплексе «EfflVision» и применяются на практике

Предложенный в диссертационной работе подход позволяет избежать большинства недостатков существующих параметрических алгоритмов построения сечений. Суть предлагаемых алгоритмов заключается в объединении идей построения сечений при помощи параметрических алгоритмов [63-64], упомянутых выше, и методов построения выпуклой оболочки произвольной размерности, развиваемых в выпуклом анализе и вычислительной геометрии. Это позволило эффективно работать с любыми выпуклыми многогранными множествами и с сечениями произвольной размерности, повысить точность и скорость вычислений.

Практическая ценность работы состоит в реализации предложенных алгоритмов в программном комплексе «EffiVision» [72], который применяется в управлении, сложными техническими, экономическими и социальными системами. Программный комплекс «EffiVision» используется для анализа банковской, деятельности Центральным банком РФ, для анализа регионов и муниципальных образований страны Счетной Палатой РФ, для анализа тарифной политики и экологической деятельности в РАО «ЕЭС России» и его смежных предприятий.

Апробация работы и публикации. Основные результаты работы докладывались на международных конференциях «4th International Symposium of DEA» (Англия, 2004), «The Ninth European Workshop on Efficiency and Productivity Analysis (EWEPA IX)» (Бельгия, 2005), «Системный анализ и информационные технологии» (Переславль-Залесский, 2005), «5th International Symposium on DEA and Performance Management» (Индия, 2007), «22nd European Conferencer on Operational Research» (Чехия, 2007), на семинарах кафедры «Нелинейных динамических систем и процессов управления» факультета вычислительной математики и кибернетики Московского Государственного Университета им. М.В. Ломоносова. По теме диссертации опубликовано 11 печатных работ [36-38,72-79].

Структура и объем работы: диссертационная ^работа состоит из введения, четырех глав, заключения и списка использованной литературы. Содержит 128 страницы текста, 35 рисунков, 4 таблицы. Список использованной литературы содержит 96 наименования. В данной диссертации формулы, теоремы, рисунки и т.д. нумеруются по главам.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Сафин, Михаил Масхутович

Заключение

В диссертационной работе предлагаются новые алгоритмы и методы в рамках методологии Анализа Среды Функционирования, позволяющие расширить возможности этой методологии для оценки эффективности функционирования сложных систем. В ходе проведенных исследований получены следующие основные результаты.

1. Разработаны алгоритмы построения двумерных сечений многомерного множества производственных возможностей в моделях ВСС, которые повысили скорость и точность вычислений существующих алгоритмов.

2. Разработан алгоритм построения трехмерного сечения по двум входным и одному выходному показателям в моделях ВСС.

3. Доказана возможность выделения в отдельную подзадачу нахождение векторов направлений, принадлежащих многомерным сечениям для обобщенной модели методологии АСФ.

4. Предложенные алгоритмы построения двумерных и трехмерных сечений развиты и обобщены на случай построения сечений аффинными подпространствами произвольной размерности в обобщенных моделях методологии АСФ.

5. Доказана сходимость предложенных алгоритмов.

6. Предложенные алгоритмы реализованы в программном комплексе оптимизационного моделирования «EffiVision».

7. Программный комплекс «EffiVision» внедрен и применяется для анализа технических, экономических и, социальных систем во многих государственных и коммерческих организациях.

Список литературы диссертационного исследования кандидат физико-математических наук Сафин, Михаил Масхутович, 2008 год

1. Вэриан Х.Р. Микроэкономика. Современный подход. Москва, «Юнити», 1977.

2. Иванилов Ю.П., Лаптев А.В. Математические модели в экономике. Москва, «Наука», 1979.

3. Гальперин В.М., Игнатьев С.М., Моргунов В.И. Микроэкономика. Том 1,2. Москва, «Высшая школа экономики», 1997.

4. Panzar J.C., Willig R.D. Eonomics of scale in multi-output production: The Quarterly Journal of Economics, Vol. XCI, №3, 1977, pp. 481-493.

5. Starrett D.A. Measuring returns to scale in the aggregate, and scale effect of public goods: Econometrica, Vol. 45, №6, 1977, pp. 1439 1455.

6. Charnes A., Cooper W.W., Rhodes E. Measuring of efficiency of decision making units: European Journal of Operational Research. 1978. V. 2. №6. P. 429-444.

7. Banker R.D., Charnes A., Cooper W.W. Some models for estimating technical and scale efficiency in data envelopment analysis. Management Science. 1984. V. 30. №9. P. 1078-1092.

8. Cooper W.W, Seiford L.M., Tone K. Data Envelopment Analysis. -Boston: Kluwer Academic Publishers, 2000.

9. Мину M. Математическое программирование: теория и алгоритмы. — М., Наука, 1990.

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

11. Карманов В.Г. Математическое программирование. М. Наука, 1975.

12. Лэсдон Л.С. Оптимизация больших систем. М., Наука, 1975.

13. Карлин С. Математические методы в теории игр программировании и экономике. М,. МИР 1964

14. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. — М.: Наука, 1975.

15. Энкланд И., Теман Р. Выпуклый анализ и вариационные проблемы.-М: Наука, 1979

16. Вайнберг М.М. Вариационный метод и метод монотонных операторов. — М. : Наука, 1972.

17. Иоффе А.Д. Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1975.

18. Зуховицкий С.И. Нелинейное и выпуклое программирование. М.: Наука, 1967.

19. Бирюков С.И. Методы оптимизации. М.,: МФТИ, 1991.

20. Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М.,: Мир, 1991.

21. Данциг Д. Линейное программирование, его обобщения и применение. -М.,: Прогресс, 1966.

22. Емельянов С.В., Калашников В.В. Исследование сложных систем с помощью моделирования. В кн.Техническая кибернетика. М., 1981, т. 14, с 158-209.

23. Емельянов С.В. , Коровин С.К, Мамедов И.Г. Структурные преобразования и пространственная декомпозиция дискретных регулируемых систем. Техническая кибернетика, № 6 , 1986, с. 118 — 128.

24. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

25. Вагнер Г. Основы исследования операций. 1,11,111 тома. М.: Мир, 1972.

26. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978.

27. Васильев Ф.П. Численные методы решения задач экстремальных задач.-М.: Наука, 1980.

28. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование, М.,Наука. 1969.

29. Жуковский В.И., Молоствов B.C. Многокритериальное принятие решений в условиях неопределенности.-М.:1988.

30. Евтушенко Ю.Г. Численные методы оптимизации / Ю.Г. Евтушенко, В.Г. Жадан; отв. ред. А.С. Антипин; ВЦ им. А.А. Дородницына РАН. М.: Наука, 2005. - 36 л.

31. Бушенков В.А., Лотов А.В. Методы и алгоритмы анализа линейных систем на основе построения обобщенных множеств достижимости // Ж. вычисл. матем. и матем. физ. 1980. Т. 20. №5. С. 1130-1141.

32. Лотов А. В. Введение в экономико-математическое моделирование. М.: Наука, 1984.

33. Бушенков В.А., Гусев Д.В., Каменев Г.К., Лотов А.В., Черных О.Л. Визуализация множества Парето в многомерной задаче выбора // Докл. РАН. 1994. Т. 335. №5. С. 567-569

34. Черников С.Н. Линейные нераверства. М.,: Наука, 1968

35. Yu G., Wei Q., and Brockett P. A generalized data envelopment analysis model: a unification and extension of existing methods for efficiency analysis of decision making units: Annals of Operation Research, 1996. V. 66. P. 47-89.

36. Кривоножко B.E., Уткин О.Б., Сафин M.M., Лычев А.В. О трансформации эффективной гиперповерхности в анализе эффективности сложных систем: Дифференциальные уравнения, 2007. Вып.43, №8, с.1174-1175

37. Сафин М.М. и др. Оптимизационное моделирование целевых программ и проектов// глава 2 книги Системный аудит использования национальных ресурсов и управление по результатам. Выпуск 3.

38. Charnes, A., Haag, S. , Jaska, P.&Semple, J.(1992), "Sensitivity of efficiency classifications in the additive model of data envelopment analysis. Int;J.Systems■ Sci., pp.789 798.

39. Charnes, A., Cooper, W.W. , Huang, Z.M. and Sun, D.B. (1990) "Polyhedral cone ratio DBA models with illustrative5 application ■ to; large commercial banks," Journal of Econometrics Oct.-Nov. 46, 73 -91.

40. Charnes, A., Cooper, W.W. and Thrall, R.M. (1986) "A structure for classifying andJ characterizing efficiencies and in efficiencies in data;, envelopment analysis", Operation Research Letters 5, 105-110.

41. Taylor, W.M. , Thompson, R. G., Thrall, R.M. (1997) "DEA/AR efficiency and profitability of Mexican Banks: A total income model", European Journal of Operation Research 98, 346 363.

42. Banker, R.D. (1984)"Estimating most productive size using data envelopment analysis", European Journal of Operation Research 17, 35-44.

43. Dula, J.H. (1997) "Equivalenciesn between Data Envelopment Analysis and the theory of redundancy", European Journal of Operation Research 101,51-64.

44. Susan X. Li (1998) "Stochastic models and variable returns to in data envelopment analysis", European Journal of Operation Research 104, 532 -548.

45. Charnes, A. And Cooper, W.W. (1984)"The non-Archimedean CCR ratio for efficiency analysis: A rejoinder to Boyd and Fare", European Journal of Operation Research 15, 333 334.

46. Boyd, G and Fare, R. (1984) "Measuring the efficiency of decision making units: A comment", European Journal of Operation Research 15, 330-332.

47. Brockett, P.L. , Charnes, A., Cooper, W.W., Huang, Z.M. and Sun, D.B. (1997) "Data transformation in DEA cone ratio envelopment approaches for monitoring bank performance", European Journal of Operation Research 98, 250 268.

48. Thrall, R.M. (1996), "Duality classifications and slacks in DEA," in W.W.Cooper, R.G. Thompson and R.M. Thrall, eds., Extensions and New Developments in DEA, Annals of Operation Research 66.

49. Charnes, Л., Cooper, W.W., Lewin, Д., and Seiford, L.M. (1995) "Data Envelopment Analysis: Theory, Methodology, Applications", Kluwer Academic Publishers.

50. Charnes, A. Rousseau, J., and Semple, J. (1993) "An effective non-Archimedean anti-degeneracy/cycling linear programming method especially for Data Envelopment Analyses and: like methods", Annals of Operation Research 47, 271 278.

51. Thompson;, R.G., Brinkmann, E.J., Dharmapala, P.S., Diaz, J.,Gonzalez-Lima, M.D., and Thrall, R.M. (1997) "DEA/AR profit ratios and sensitivity of 100 large US banks. European Journal Operation Research, 98, pp.213-229.

52. Кривоножко B.E., Уткин О.Б., Сеньков P.В. Параметрические методы: в; анализе эффективности, сложных систем: //Нелинейная динамика и управление. Сборник трудов ИСА РАН под ред. Емельянова С.В. и Коровина С.К. М.:1999. С. 49-69.

53. Krivonozhko V.E., Utkin О.В., VolodinA.V. and Sablinl.A. Interpretation of Modeling Results in Data Envelopment Analysis //Managerial Finance, Volume 28, Number 9, 2002, pp. 37^8.

54. Dvorkovich A.V., Krivonozhko V.E. and Utkin O.B. Modeling of Large-Scale Systems Development //Encyclopedia of Life Support Systems, www.eolss.net, Eolss Publishers, Oxford, 2004, pp. 1-25.

55. Gang Yu, Quanling Wei, Brockett P., Li Zhou. Construction of all DEA efficient surfaces of the production possibility set under the Generalized Data Envelopment Analysis Model: European J. Operat. Res. V.95. №3.1996. P.491-510.

56. Preparata D.R. and Shamos M. Computational Geometry. An Introduction: Springer-Verlag, 1985.

57. Barber C.B., Dobkin D.P., and Huhdanpaa H.T., The Quickhull algorithm for convex hulls, ACM Trans, on Mathematical Software, V. 22, №4, P. 469-483, 1996.

58. Lotov A.V., Bushenkov V.A., and Kamenev G.K. Interactive Decision Maps. Approximation and Visualization of Pareto Frontier: Kluwer Academic Publishers, 2004.

59. Кривоножко B.E., Уткин О.Б., Сафин M.M., Лычев А.В. Программный комплекс "EffiVision" для анализа деятельности сложных систем //Информационные технологии и вычислительные системы, №3, 2005.

60. Кривоножко В.Е., Уткин О.Б., Сафин М.М., Лычев А.В. Проблемы отображения множеств в анализе эффективности сложных систем //Нелинейная динамика и управление, вып.5, под ред. Емельянова С.В. и Коровина С.К., М.: Физматлит, 2007, с. 285-303

61. Кривоножко В.Е., Сафин М.М., Лычев А.В., Малинов С.Е. О сравнении различных подходов к оценке деятельности сложных систем //Дифференциальные уравнения 2008. Вып.44, №2, с.277-278.

62. Krivonozhko V.E., Utkin О.В., Safin М.М., Lychev A.V. On the equivalence of the generalized DEA model to the BCC model //5th International Symposium on DEA and Performance Management, Hyderabad, India, January 5-7, 2007.

63. Krivonozhko V.E., Utkin O.B., Safin M.M., Lychev A.V. On the equivalence of the generalized DEA model to the BCC model 22nd European Conference on Operational Research, Prague, Czech Republic, July 8-11,2007.

64. Shepard R.W. Theory of cost and production functions. New Jersey: Princeton University Press. 1970.

65. Charnes A., Cooper W.W. Golany В., Seiford L., Stutz J. Foudations of data envelopment analysis for Pareto-Koopmans efficient productions functions // Journal of Econometrics. 1985. V. 30. P. 91-107.

66. Krivonozhko V. E., Utkin O.B., Volodin V. E., Sablin I. A. About Structure of Boundary Points in DEA. // Proceedings of International DEA Symposium 2002. Moscow, 2002. P. 18-25.

67. Farrell M.J. The measurement of productive efficiency: J. Roy. Stat. Soc. 1957. V. 120. P. 253-281.

68. Kuhn H.W. and Tucker A.W. (eds.) Linear Inequalities and Related Systems. London, New York, 1956.

69. Chang K.P., Guh Y.Y. Linear production functions and the DEA // European Journal of Operational Research. 1991. V. 52. P. 215-223.

70. Pitaktong U., Brockett P.L., Mote J.R., Rousseau J.J. Identification of Pareto-efficient facets in DEA // European Journal of Operational Research. 1998. V. 109. P. 559-570.

71. McMullen D. and Shephard G.C. Convex Polytops and the Upper Bound Conjecture: Cambridge University Press, Cambridge, England, 1971.

72. Kallay M., Convex hull algorithms in higher dimensions, unpublished manuscript. Dept. Mathematics, Univ. of Oklahoma, Norman, Oklahoma, 1981 (see Preparata & Shamos 1985)

73. Grunbaum B. Measures of symmetry for convex sets. In Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity, 1961, P. 233-270.

74. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры: Учеб. для вузов. 8-е изд., перераб. - М.: Физико-математическая литература, 2000.

75. Krivonozhko V.E., Utkin О.В., Volodin A.V., Sablin I.A. Efficiency analysis of production systems: Progress Industr. Math, at ECMI 2000. Springer, 2002. P. 584-591.

76. Krivonozhko V.E., Utkin O.B., Volodin A.V., Sablin I.A. Interpretation of modelling results in data envelopment analysis: Managerial Finance. 2002. V. 28. № 9. P. 37-47.

77. Кривоножко B.E., Уткин О.Б., Сеньков P.B. и др. Анализ эффективности финансовых институтов в экономике переходного периода: Нелинейная динамика и управление. М.: Физматлит, 2001. С. 363-374.

78. Уткин О.Б., Кривоножко В.Е., Сеньков Р.В., Володин А.В. АСФ: Презентация новых технологий системного анализа: Нефть, газ и бизнес. 2000. №6. С. 37-41.

79. Триф А.А., Уткин О.Б., Кривоножко В.Е. и др. Устойчивость функционирования финансовых институтов: Банковские технологии. 1999. №9. С. 26-31.

80. О.Б. Уткин, В.Е. Кривоножко, Д.А. Рыжих. Анализ деятельности городов России на основе технологии АСФ в рамках концепции устойчивого развития. Экономика развития региона: проблемы, поиски, перспективы, Ежегодник, выпуск 4, Волгоград 2004.