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

Учреждение Российской академии наук Институт Системного Анализа РАН

На правах рукописи Мхс^ик

Сафин Михаил Масхутович

□03172302

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

Специальность 05 13 01 Системный анализ, управление и обработка

информации (информационно-вычислительное обеспечение)

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

'е по;; г:

Москва-2008

003172302

Работа выполнена в Учреждении Российской академии наук Институте Системного Анализа РАН в лаборатории «Методов системной оптимизации»

Научный руководитель: доктор физико-математических наук

Кривоножко Владимир Егорович

Официальные оппоненты: доктор физико-математических наук

Жадан Виталий Григорьевич

кандидат физико-математических наук Молоствов Виталий Серафимович

Ведущая организация Факультет вычислительной математики

и кибернетики Московского Государственного Университета им МВ Ломоносова

Защита диссертации состоится 30 июня 2008г в 14-00 на заседании диссертационного совета Д 002 086 02 при Учреждении Российской академии наук Институте Системного Анализа РАН по адресу 117312, г Москва, пр-т 60-летия Октября, 9

С диссертацией можно ознакомиться в научной библиотеке Учреждения Российской академии наук Института системного анализа РАН (г Москва, пр-т 60-летия Октября, 9)

Отзывы на автореферат, заверенные печатью, просим направлять по адресу 117312, г Москва, пр-т 60-летия Октября, 9, диссертационный совет Д-002 086 02

Автореферат разослан 29 мая 2008г

Ученый секретарь диссертационного совета доктор технических наук, профессор

уПропой А И

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы Методология Анализа Среды Функционирования (на английском языке методология называется Data Envelopment Analysis) возникла как обобщение простых коэффициентов анализа деятельности объектов на многомерный случай, те когда деятельность сложного объекта описывается набором входных параметров (xt, ,хт) и набором выходных параметров (yi, ,у,) Для корректности и содержательности такой постановки рассматривается множество подобных сложных объектов Тогда математически такой подход сведется к решению большого семейства оптимизационных задач Основоположниками данного подхода были известные американские ученые А Чарнес и В Купер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По результатам исследований, проведенных в диссертационной работе, на защиту выносится

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

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

3 алгоритмы построения трехмерного сечения по двум входным и одному выходному показателю в модели ВСС,

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

5 применение разработанных алгоритмов для анализа эффективности технических, социальных и экономических систем

Практическая ценность работы состоит в реализации предложенных алгоритмов в программном комплексе «EffiVision», который применяется в управлении сложными техническими, экономическими и социальными системами Программный комплекс «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 Conference on Operational Research» (Чехия, 2007), на семинарах кафедры «Нелинейных динамических систем и процессов управления» факультета вычислительной математики и кибернетики Московского Государственного Университета им Ломоносова По теме диссертации опубликовано 11 печатных работ

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность работы, описаны решаемые проблемы, представлена практическая значимость работы

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

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

Рассмотрим множество из п наблюдаемых производственных объектов, деятельность которых необходимо оценить Каждый ПО потребляет т входных продуктов и производит г выходных продуктов Таким образом, пусть X, = , х„_,) > 0 является вектором входных параметров (затрат), а ^ = (у^, , уа) > О,,п, будет вектооом выходных параметров (выпуска) Предполагается, что каждый ПО имеет, по крайней мере, один положительный вход и один положительный выход

Множество производственных возможностей Т определяется как множество таких векторов (Х,У), что вектор выпуска У может быть произведен при векторе затрат X, те Т-{(X,У) / выходной вектор У> 0 может быть получен при входном векторе Х> 0}

На основе наблюдаемых векторов (Х^У]), }=1, , п, множество производственных возможностей Г эмпирически задается следующими постулатами

Постулат 1 (Выпуклость) Если (Х,У)еТ и <Х',У)еТ; тогда (XX + (1 -Л)Х' ЛУ + (1-Л)У)еТ дчя всех Яе[0,1]

Постулат2 (Монотонность) Если (Х,У) е ТиХ'>Х, Г<Т, тогда (Х',Г)еТ Постулат 3 (Минимальная экстраполяция) Множество Т является пересечением всех множеств Т, удовлетворяющих Постулатам 1 и 2, при условии, что (Л^У,)е7"' для всех

Таким образом, множество Т строится как расширение по наблюдаемым производственным векторам (Х^У^, }=1, ,п, и опредетяет возможные экономически допустимые векторы выпуска У по векторам затратХ

В алгебраическом виде множество производственных возможностей Г запишется как

Т = {(Х,У)1 х><Гх}л,, У = 1, > 0, у = 1, ,«} (1)

Одной из основных моделей методологии АСФ является ВСС модель, название модели получается из первых букв фамилий авторов Banker, Chames, Cooper

Модель ВСС, ориентированная по входным параметрам, задается в следующем виде

mm в

при ограничениях

в

- X xkj Я J - s¡ = 0 , к=1. , т, (2)

У-1

П

ХуЛ~s' = У>о, .г,

J-1

Áj,s¿,s?> О,

здесь Art, и у,j представляют собой наблюдаемые параметры входных величин к-1, ,т и выходных величин i-1, ,г для производственных объектов }~¡, ,п Вектор (Xa,Y0) соответствует одному из производственных объектов j-1, ,п, который в данный момент оценивается

Существует много различных оптимизационных моделей в рамках методологии АСФ Но модель ВСС является основной, поскольку обобщенная модель ВСС аппроксимирует все основные модели АСФ, такие как CCR, ВСС, IRS, GRS и DRS Рассмотрим обобщенную модель ВСС

minö

при ограничениях

J" 1 »6/ ш

I ni kej

=1,

J=l leí

Л> О, J = \, ,п, ¡и, >0, iel, рк> 0, keJ,

(3)

здесь (£>,6;),/е/, где / - множество искусственных производственных объектов, множество лучей, добавленных в задачу

Множество производственных возможностей для модели (3) запишется в виде:

2 ;7 + =1, Л^о, = ..,я, д > 0, /е/, Л>0,

;Г:/

Задачу (3) можно рассматривать как модель ВСС (2), в которую добавлены

Рис.1. Множество производственных возможностей обобщенной модели ВСС

Таким образом, множество Та (4) определяется как векторная сумма двух множеств: выпуклой комбинации реальных и искусственных производственных объектов и многогранного конуса, задаваемого неотрицательной комбинацией лучей (см. рис. 1 для двумерного случая).

О

/

X

о

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

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

Введем двумерную плоскость в пространстве £™+г следующим образом

Р1(Хо. Го, (¡1, ¿Ц = (Ха Уа) + аа, + ¡Х2, (5)

где (ХоуУо) е Т, а и рявляются любыми действительными числами, векторы направлений ¿¡, б £т<г, пусть при этом векторы и Аг не параллельны

Теперь определим пересечения эффективного фронта с двумерной плоскостью, проходящий через выбранный объект, ось абсцисс является вектором входных параметров данного объекта, а ось ординат - вектор выходных параметров Данные пересечения носят тот или иной экономический смысл, поэтому интересны для рассмотрения

У0)= {(X, Г) | (X, У)е РЦХо, Уа <4 <Ц) п Т} (6)

где а, = (Хс 0) е Е"*г, <12 = (О, У„) е Е"*г Пересечение (6) является обобщенной производственной функцией выбранного объекта в многомерном экономическом пространстве

Дадим общую схему параметрических алгоритмов для построения обобщенной производственной функции в многомерном пространстве параметров Данное сечение

характерно тем, что нам изначально известна его структура Это кусочно-линейная кривая, которая начинается лучом ВА (рис 2), параллельным оси ординат, продотасается выпуклой ломанной, соединяющей точки В и С и заканчивается лучом СР, параллельным оси абсцисс

Таким образом, для полного описания сечения нам необходимо знать упорядоченную последовательность вершин сечения, которая начинается точками А и В, а заканчивается точками С и О Обозначим эту последовательность как 51

Информация о том, какую форму имеет сечение, значительно упрощает процедуру его построения Суть нахождения границы сечения заключается в счедующем Вначале находим «угловые вершины сечения», точки В и С на рисунке 2 Данные вершины характерны тем, что, зная их, мы можем построить первое приближение искомого сечения, граница которого образуют кусочно-линейную кривую АВСИ Далее итерационным процессом уточняем границу сечение, постепенно приближая его к искомому сечению

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

Шаг 1 Определяем «угловую вершину сечения», лежащую на граничном луче, параллельном оси ординат (точку на рисунке 3) Для этого решаем следующие задачи линейного программирования

1) Задача А найти тш /?, при условии (Да', + Ргс1г) е Т

01 Рг

В результате нахождения оптимального значения задачи А определяется некоторая точка г, =(Д'(/1 + /32'^2)еГ, лежащая на граничном луче, паралчельном оси ординат (рисунок 2 3) Здесь Д' и ¡}\ - оптимальные значения переменных Д и в задаче А

2) Задача В найти тах Д при условии (2\ + Т

В результате нахождения оптимального решения задачи В определяется «угловая вершина сечения» = (2\ + (%с1г)еТ, лежащая на граничном луче, параллельном оси ординат

Рис 3 Иллюстрация выполнения алгоритма, шаги 1 и 2

Шаг 2 Аналогично определяется «угловая вершина сечения» 2г е Т, лежащая на граничном луче, параллельном оси абсцисс (рисунок 3) Для этого решаются следующие оптимизационные задачи

1) Задача С найти шах Р2 при условии

Р-. Рх

В результате решения задачи находится точка 2г = 03* с/, + /?2 ¿г)

2) Задача О найти тщ Д при условии

&

В результате решения задачи находится точка 2г = (2 г + /?3 ) После выполнения первых двух шагов алгоритма становится известно первое приближение границы сечения - кусочно-линейная кривая 2\1^2гЪ1 Причем с достоверностью можно сказать, что участки 2\2Х и 2г2г принадлежат искомому сечению Но существуют ребра кусочно-линейной кривой, про которые такое утверждение сделать нельзя, например ребро Множество таких ребер обозначим М

ШагЗ Есчи точка 2с заданной точностью совпадает с Z1,тo искомой границей сечения будет кусочно-линейная кривая 2и выполнение алгоритма на этом останавливается

В противном случае задаем первое приближение искомого сечения Упорядоченная последовательность вершин X, описывающая искомое сечения, состоит из последовательности точек 2,, 2г и 2г Множество Мсостоит из ребра

Шаг 4 Из множества М выбираем произвольное ребро Пусть это будет некоторое ребро /,/2, где и 1г - вершины, принадлежащие последовательности .У Выбранное ребро удаляем из множества М

Шаг 5 Определяем точку С, среднюю между 1\ и Ь {С ~ ) Опредетяем вектор

г, параллельный вектору 12 -7, Также определим вектор л, перпендикулярный к вектору г, лежащий в плоскости сечения и направленный в сторону повышения меры эффективности (см рис 4 )

Рис 4 Иллюстрация выполнения алгоритма, шаги 5 и 6

Шаг 6 Найдем следующую вершину V, принадлежащую искомому сечению Для этого решаем следующую задачу линейного программирования Задача Е найти тах Д при условии (С + Д п + Д, т) е Т

Если оптимальное значение целевой функции задачи > 0, то вершина определена Это точка V = (С + /?, п + Р1т)еТ В последовательность 5 добавим новую вершины V между вершинами Л и 1г Во множество М добавим ребра и VI2

Есчи оптимальное значение целевой функции задачи Д* = 0, то можно утверждать, что ребро /,/2 принадлежит искомому сечению

Шаг 7 Если множество М не пусто, переход к шагу 4 В противном случае алгоритм завершен

В результате выполнения алгоритма 1 получим упорядоченную последовательность вершин полностью описывающую сечение (6) Справедливость этого утверждения в диссертации доказывается при помощи следующей теоремы

Теорема 1 Пусть для любого ребра /,/2 из 5 оптимальное значение целевой функции задачи Е равно нулю, то точка Р е принадлежит границе сечения 5ес/(Ха У„) тогда и только тогда, когда она принадлежит

Сложность выполнения алгоритма 1 показывается в следующей теореме

Теорема 2 Все вершины границы сечения ЯесДХ,» У„) (6) могут быть найдены при помощи алгоритма 1 в худшем случае решением 3 V задач линейного программирования, где V- количество вершин границы сечения 5ес1(Х0, У0)

Точность алгоритма 1 можно описать при помощи теоремы 3

Теорема 3. Если при построении сечения Бес^Хо, У0) (6) при помощи алгоритма 1 выполняются следующие условия

1) расстояние от любой вершины V, вычисленной при помощи оптимизатора отличается от реальной вершины Vю1, принадлежащей границе сечения не более чем на 6 Те ¡К-Г™'(| <5,

2) оптимальное значение целевой функции задачи Е считается нулевым, если

то тогда расстояние от любой точки Р, принадлежащей границе сечения вес^Х,0, У0) (6), до кусочно-линейной кривой в, полученной в результате выполнения алгоритма 1, меньше 25

Для построения произвольного двумерного сечений мы не всегда можем знать, как выглядит то или иное сечение, при различных сочетаниях <1\ и (¡г Поэтому процедуру нахождения первого приближения сечения необходимо модифицировать

В задачах анализа среды функционирования известны все точки в многомерном пространстве, которые образуют выпуклую гиперповерхность множества производственных возможностей Данный факт всегда позволяет оценить размер двумерного исходного сечения, то есть задать квадрат ЛВСй, внутри которого будет находиться интересующий нас выпуклый участок сечения (см рис 5)

После того, как определена граница искомого двумерного сечения, необходимо найти крайние точки пересечения данной границы с множеством производственных возможностей (на рисунке 5 эти точки обозначены 21 и22), после чего можно переходить к ачгоритму 1 построения сечения

Идея построения трехмерного сечения похожа на идею построения двумерного сечения Строится первое приближения, а потом при помощи задач линейного программирования находятся новые вершины, принадлежащие границе сечения, которые уточняют приближенное сечение После конечного числа итераций приближенное сечение доводится его до искомого Но при построении трехмерного сечения возникают сложности при добавлении новой вершины к приближенному сечению Во-первых, границей сечения является не кусочно-линейная кривая, а трехмерное многогранное множество Во-вторых в приближенном сечении не гарантируется, что ребра многогранного множества принадлежат

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

В диссертационной работе предлагается алгоритм изменения границы выпуклого трехмерного многогранного множества при добавлении новой вершины, основанный на доказанной в работе следующей теореме Для ее описания потребуются некоторые опредепения

Определение 1 Точка Р явчяется внутренней для грани Г выпуклого многогранного множества, если при проведении касательной гиперплоскости через грань Г точка Р и многогранное множество будут лежать по одну сторону от этой гиперплоскости Определение 2 Две грани являются соседними, если они имеют общее ребро ОпредетениеЗ Дтя некоторого множества граней I выпуклого многогранного множества ребро Я называется граничным, если оно принадлежит одной из граней мьожества I и не является соседним для тобой пары граней из I

Теорема 4 Пусть М - выпуклое многогранное множество в трехмерном евклидовом пространстве Еу, а V - точка в Е1 Грань Г принадлежит многогранному множеству Лf=conv(Л/,^0, если

1) грань Г принадлежит множеству Л/ и точка Кявляется внутренней для нее

2) грань /"является выпуклой обо точкой вершины К и ребра Я Где К - граничное ребро множества граней многогранного множеств М, дтя которых точка V является внешней

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

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

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

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

Идея построения сечения произвольной размерности остается такой же, как для двумерных и трехмерных сечений Строится первое приближения сечения, а потом при помощи задач линейного программирования уточняется до тех пор, пока не совпадет с искомым Как и в случае с трехмерным сечением, для построения произвольного сечения необходима процедура добавления новой точки к выпуклому многогранному множеству В общем случае эта процедура сводится к алгоритму построения выпуклой оболочки конечного набора точек и векторов направтений в пространстве произвольной размерности В данной главе для решения этой задаче предлагается алгоритм, который является развитием известного в вычислительной геометрии алгоритма построения выпуклой оболочки конечного набора точек, под названием «под-над» (ВепеагЬ-Веуопй), на случай выпуклой оболочки конечного набора точек и векторов направлений

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

Во второй главе предлагался алгоритм построения сечения, когда его вид был неизвестен Это нахождение границ сечений в пределах заданного большого квадрата Но данный способ подходит для двумерного случая В многомерном случае необходимо искать другие способы построения Вся сложность поставленной проблемы заключается в том, что при работе с произвольным выпуклым многогранным множеством оптимизационная задача может не иметь решения Поэтому необходимо выносить нахождение векторов направлений сечения в отдельную подзадачу, а после ее решения аккуратно находить вершины сечения

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

Опишем основные идеи метода «под-над» На содержательном уровне этот метод последовательно обрабатывает по одной точке, назовем ее р, и если р - внешняя точка но отношению к текущей оботочке Р, то из точкир сгроится опорный «конус» к Г и удаляется часть оболочки Р, затеняемая этим конусом

Развитие этого метода на спучай выпуклой оболочки конечного набора точек и векторов направлений основан на следующей теореме, являющейся модификацией теоремы Грюнбаума для выпуклого многогранного множества

Теорема 5 Пусть М - выпуклое многогранное множество, а v - вектор направления или точка в пространстве tf Введем обозначение М'= Conv(M и v) Тогда дтя каждой грани М' справедливо одно из дву\ утверждений

1) Грань / выпуклого многогранного множества М явтяется также гранью М'тогда и только тогда, когда существует гипергрань F выпуклого многогранного множества М такая, что / с F и v находится под F1,

2) Если / - грань выпуклого многогранного множества М, то /' = Сот>(/ u v) является гранью М'тогда и только тогда, когда тибо

a) среди гиперграней выпуклого многогранього множества М, содержащих f, и\<еется по крайней мере одна такая, что v находится под ней, и по крайней мере одна такая, что v находится над ней, либо

b) vc äff (/), где afjff) - минимальное аффинное множество, содержащее грань/

Рассмотрим частный случай алгоритма построения сечений эффективного фронта -алгоритм построения сечения политопа

Пусть задано множество из п точек X, = (xi„ , хД г = 1, ,п в многомерном пространстве образующие выпуклую оболочку

1 В диссертационной работе вводится определение нахождения вектора направления под гипергранью выпуклого многогранного множества

и й-мерное (hsd) аффинное подпространство, заданное уравнением

где С = (ci, , сd) - точка в через которое проходит аффинное подпространство, а Rk-(Xik, /л), к = 1, ,А — независимая комбинация направлений аффинного подпространства в

-матрица d х h, столбцами которой являются вектора Ri, , а величины рк, fc = 1, ,h — любые действительные числа

Тогда искомое сечение будет пересечением выпуклой оболочки Т и аффинного подпространства AffiC.R)

Sec(C,R) = Tr\Aff(C,R) (9)

Алгоритм можно разбить на две части В первой части алгоритма определяются базисные точки и размерность сечения Обратим внимание, что размерность сечения многомерной выпуклой оболочки аффинным подпространством может быть любой, от -1 (пустое множество) до размерности аффинного подпространства Знание размерности сечения критично для определения нормалей к граням во второй части алгоритма Вторая часть алгоритма опирается на знание базисных точек, определенных в первой части По этим точкам строится симплекс, который является первым приближением искомого сечения Далее производится последовательное уточнение всех гранений приближенного сечения при помощи решения задач линейного программирования и добавление найденных новых вершин в выпуклую оболочку сечения при помощи алгоритма «под-над»

Определение 4 Пусть задан ^-мерный политоп Множество q+1 точек, принадлежащих политопу, называются базисными для этого политопа, если все точки множества могут образовать q-мерный симплекс

Алгоритм 2 Определение базисных точек и размерности сечения Данный алгоритм не представляет большой сложности для сечения политопа, поэтому не будем останавливаться на нем более подробно

После того, как определена размерность сечения, целесообразно производить построение сечения в пространстве именно этой размерности, а уже потом перевести его в подпространство Aff(C,R)

Пусть Е? ■ евклидовое пространство размерности q Точки в этом пространстве будем обозначать буквой F = (v,, ,vq) А переход от пространства jE? в подпространство Aff(C,R) будет осуществляться по следующей формуле

Aff{C,R)4x\X = C+Y.PbR

о»)

где Д, к = 0, - точки, принадлежащие сечению и образующие симплекс размерности д

Для упрощения записи обозначим Л = Лс - Ро, к = 0, ,д, и введем матрицу J размерности Л х ¡7, столбцами которой являются вектора Л Тогда формута (16) перепишется как

Р = + (II)

В пространстве

Е? уже известно первое приближение искомого сечения, являющееся выпуклой оболочкой базисных векторов е\, к = 0, и нучевой точки Обозначим эту выпуклую оболочку как и А все гиперграни этой выпуклой оболочки разобьем на два множества А к В Множество Л будет содержать неуточненные гиперграни оболочки У, т е гиперграни, которые могут не принадлежать окончательному сечению, а множество В будет содержать уточненные гиперграни V, т е гиперграни которые останутся неизменными при дальнейшей работе алгоритма Первоначально все гиперграни принадлежат множеству А

Пусть Г одна из гиперграней оболочки V, принадлежащая множеству А Так как гипергрань Г имеет размерность то в пространстве Е? существует единственная гиперплоскость, содержащая эту гипергрань Зададим эту гиперплоскость в виде следующего уравнения

где Д) - произвольная точка, принадлежащая гиперплоскости, .£>* - векторы направлений гиперплоскости

Кроме того, в пространстве Е? существует единственная внешняя нормаль N к гиперграни Г относительно выпуклой оболочки И

Приняв эти обозначения, алгоритм построения сечения записывается следующим образом

Атгоритм 3 Построения сечения политопа аффинным подпространством Шаг 1. Определяем при помощи алгоритма 2 размерность сечения д и базисное множество £ Если д=-\, то сечением явчяется пустое множество, если д=0, то сечением является точка Рц И в том и другом случае выполнение алгоритма завершается

Шаг 2 Определяется пространство Е? размерности содержащее искомое сечение и строится первое приближение искомой выпуклом оболочки £7 Вводятся два множества гиперграней Множество А, содержащее все гиперграни С/и пустое множество В

Шаг 3. Выбираем произвольную гипергрань Г, принадлежащую множеству А и решаем для нее задачу 1

тахг0

при ограничениях

С + ВД + J(D0 + г0Л' + £ zkDk)) = X Л,Х,,

1-1

¿4=1, Д >0,/ = 1, л

ы\

г,-любые,к = 0, jq-1

Шаг 4 Если оптимальное значение целевой функции задачи 1 равно нулю, то гипергрань Г из множества А перемещаем во множество В Если оптимальное значение целевой функции

больше нуля, то при помощи алгоритма «под-над» точку V = D0 + i0N + ^ikDk добавляем в

U, при этом изменяется только множество А

Шаг 5 Если множество А не пустое, то переходим к шагу 3 В противном случае описание сечения Sec{C,R) -U из пространства Е? переводим в аффинное подпространство Äff (C,R) На этом выполнение алгоритма завершается

В диссертационной работе доказано, что в результате выполнения алгоритма получится искомое сечение

Теорема 3 Пусть в пространстве Е? задан политоп U размерности q Если для любой гиперграни этого политопа оптимальное значение целевой функции задачи 1 равно нулю, то данный политоп является сечением выпуклой оболочки Т (7) и аффинного подпространства Aff(C,R)(i)

Также показывается, что алгоритм конечен (т е что он рано или поздно остановится) Для этого дополнительно вводится определение и две леммы

Определение 5. Пусть пространству Е? полностью принадлежит сечение Sec(C,R) выпуклой оболочки Т (7) и аффинного подпространства Aff(C,R) 8) и задано некоторое приближение U этого сечения Назовем грань (размерность грани может быть от 0 до q-1) сечения Sec(C,R) свободной, если ни одна из точек, принадлежащих этой грани, не принадлежит U

Лемма 1 Если в результате выполнения алгоритма 3 оптимальное значение целевой

ч-1

функции задачи 1 больше нуля, то добавляемая точка V = Д> + г0Л' + ^ ¿VА прьнадлежит

хотя бы одной из свободных граней искомого сечения &с(С,Д)

Лемма 2 При добавлении точки, принадлежащей одной из свободных граней искомого сечения &с(С,Д), в политоп !7, чисто свободных граней уменьшается

Теорема 6 Алгоритм построения сечения многомерного выпуклого политопа аффинным подпространством конечен

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

Пусть в многомерном пространстве Е? задано множество из п точек X, - (х;„ , 1 = 1 ,п и т векторов нагграв тений У] = О'У/, У = А образующих конус АГ Выпуклое многогранное множество, образованное векторной суммой выпуклой оболочки п точек и конуса К имеет следующий вид

Т = \Х\Х-+ где^А, =!,Я, >0,^ >0

ы ] 1 ы

(12)

Применение алгоритма построения сечения ограниченного потитопа для выпуклого многогранного множества в общем случае один в один невозможно, потому что решаемые задачи линейного программирования могут давать неограниченные решения Но есть возможность задачу построения сечения выпуклого многогранного множества в общем виде разбить на две подзадачи В первой подзадачи мы будем искать все вектора направлений, принадлежащие сечению, а во второй - все точки, принадлежащие сечению Каждую из этих подзадач можно свести к построению сечения ограниченного выпуклого многогранника Покажем, как это можно сделать Введем следующие множества

= (13)

Н

= = (И)

где Л -матрица с? хй, столбцами которой являются вектора направлений аффинного подпространства Д;, ,11),

Теорема 7. Ненулевой вектор направления Y принадлежит сечению Sec(C,R) многогранного множества Г (12) аффинным подпространством Aff(C,R) (8) тогда и только тогда, когда существует положительное число к такое, что вектор У =кУ принадлежит сечению Sec'(R) множества 7"'(13) множеством Äff '(R) (14)

Таким образом, согласно теореме 7 в качестве векторов направлений Wj,J-1, искомого сечения Sec(C,R) могут служить вершины сечения Sed(R) Такое сечение находится при помощи алгоритма построения сечения ограниченного выпуклой оболочки аффинной гиперплоскостью, поскольку V имеет вид ограниченной выпуклой оболочки, a Ajf'{R) - вид аффинной гиперплоскости Положительное число к не является существенным, потому что любой ненулевой вектор, умноженный на положительную константу, будет характеризовать то же самое направление

После этого общий алгоритм записывается следующим образом

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

Шаг1. Определяются при помощи алгоритма 3 вершины сечения Sec'(R), которые могут служить в качестве векторов направления W ,j = 1, .in искомого сечения Sec(C,R)

Шаг 2 При помощи алгоритма 2 определяется размерность сечения q и базисное множество S Если q=-1, то сечением является пустое множество, если q=0, то сечением является точка Ро И в том и другом случае выполнение алгоритма завершается

ШагЗ. Определяется пространство размерности q, содержащее искомое сечение и строится первое приближение искомой выпуклой оболочку U В выпуклую оболочку U добавляем вектора направлений Wpj = \, ,т Вводятся 2 множества гиперграней Множество А, содержащее все гиперграни U и пустое множество В Шаг 4 Переход к шагу 3 алгоритма 3

В диссертационной работе показывается, что практическая сложность вычисления предложенного алгоритма равна 0(vi(n,m)+v[<i21+1), где п - количество производственных объектов в модели методологии АСФ, ш - количество параметров модели, d - размерность сечения, v - количество вершин и векторов направлений сечения L(n,m) - сложность решения задачи линейного программирования с горячего старта с количеством переменных равных п, и количеством ограничений равных т

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

Четвертая глава посвящена применению сечений эффективного фронта для социально-экономической диагностики субъектов Южного Федерального округа (ЮФО) Российской Федерации Показывается широкий спектр возможностей применения различных обобщенных производственных функций и их визуализации для глубокого анализа объектов социально-экономической сферы, какими и являются регионы страны Демонстрируется вся мощь данного подхода не тотько применительно к анализу уже существующей модели функционирования субъектов ЮФО, но и к возможностям модификации самой модели, выявлению объектов, функционирующих в особых экономических условиях, а также параметров, влияние которых на итоговый результат деятельности оказывается незначительным

Разработанный подход и алгоритмы легли в основу программного продукта «ЕШУгсюп» и применяются дтя анализа различных производственных, экономических и социальных систем Разите тьным примером применения развитых в работе методов может служить социально-экономическая диагностика субъектов Южного Федерального округа Российской Федерации В ходе анализа, для более корректной оценки эффективности, выбранная модель была модернизирована С помощью построения экономических функций было выявлено, что один из регионов Южного Федерального округа работает не в тех же экономических устовиях, что остальные субъекш данного округа Последующий детальный анализ региона гоказал, что он является оффшорной зоной и поэтому в модели участвовать не может Кроме того, удалось выяснить, что ранее участвующий в моделе параметр грузооборот является не существенным, и был исключен из расчетов Были продемонстрированы методы, как с помощью экономических зависимостей можно модернизировать множество производственных возможностей в зависимости от тех или иных обстоятельств В основной части анализа для регионов Южного Федерального округа Российской Федерации были построены кривые динамики за рассматриваемый период Для двух регионов были построены сечения эффективного фронта и детально изучено положение регионов в многомерном социально-экономическом пространстве, было показано, каким образом каждому региону нужно менять свои входные и/или выходные показатели, чтобы стать эффективным

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

Список публикаций автора по теме диссертации

1 Кривоножко В Е, Уткин О Б, Сафин М М, Лычев А В Программный комплекс "EffiVision" для анализа деятельности сложных систем //Информационные технологии и вычислительные системы, №3,2005, с 85-95

2 Кривоножко В Е, Уткин О Б, Сафин М М, Лычев ABO трансформации эффективной гиперповерхности в анализе эффективности сложных систем Дифференциальные уравнения, 2007 Вып43,№8,с 1145-1146

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

4 Сафин М М и др Оптимизационное моделирование целевых программ и проектов// глава 2 в книге «Системный аудит использования национальных ресурсов и управление по результатам Выпуск 3 Методы анализа и социально-экономической диагностики» /под ред А А Пискунова-Ростов-на-Дону ЮРИФКА, 2007, с 90-113

5 Кривоножко В Е , Угкин О Б , Сафин М М , Лычев А В Трансформация эффективной гиперповерхности в анализе эффективности счожных систем//Нелинейная динамика и управление, вып 6, под ред Емельянова С В и Коровина С К, М Физматлит, 2008

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

7 Krivonozhko V Е, Utkin О В , Zharkov ID, Lychev А V and Safin М М Constructions of two-dimensions and three-dimensions cross-sections of the multidimensional frontier in DEA and prodactivity analysis of Russian banks //4th International Symposium of DEA, Abstracts, Birmingham, September 2004

8 Krivonozhko V E, Utkm О В , Safin M M , Lychev A V Modifications of the algorithms for visualization of the multidimensional frontier in DEA and efficiency analysis of Russian banks //The Ninth European Workshop on Efficiency and Productivity Analyse (EWEPA IX), Brussels, Belgium, June 29-July 2,2005

9 Кривоножко В E , Уткин О Б , Сафин М М , Лычев А В Анализ деятельности сложных многомерных систем на основе параметрических оптимизационных алгоритмов на примере российских банков //Международная конференция «Системный анализ и информационные технологии», Переслав чь-Залесский, 12-16 сентября, 2005

10 Krivonozhko VE, Utkm OB, Safin MM, Lychev AV On the equivalence of the generalized DEA model to the ВС С model //5th International Symposium on DEA and Performance Management, Hyderabad, India, January 5-7,2007

11 Krivonozhko V E, Utkm О В , 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

Подписано в печать 27 05 2008 г Печать трафаретная

Заказ № 483 Тираж 75 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (495) 975-78-56, (499) 788-78-56 www autoreferat m

Введение

Глава 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» внедрен и применяется для анализа технических, экономических и, социальных систем во многих государственных и коммерческих организациях.

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.