УДК 658.5 + 519.2
ББК 32.81
ГРАФЫ ПРИ МОДЕЛИРОВАНИИ
ПРОЦЕССОВ УПРАВЛЕНИЯ
ПРОМЫШЛЕННЫМИ ПРЕДПРИЯТИЯМИ
Орлов А.И. ,
(Московский государственный технический университет им. Н.Э. Баумана, Москва)
Рассмотрено использование различных видов графов при моде-лировании процессов управления организациями промышленно-сти, в частности, при оптимизации на графах, в экспертных технологиях. Найдены связи графов с другими видами объек-тов нечисловой природы – бинарными отношениями, матри-цами из 0 и 1, результатами парных сравнений. Исправлена неточность при анализе парных сравнений. При обсуждении проверки согласованности мнений экспертов и классификации экспертных оценок показана роль люсианов. С прикладной точки зрения роль теории графов определяется тем, что она - важная составная часть математического инструментария контроллинга и менеджмента высоких технологий.
Ключевые слова: математическое моделирование, теория графов, бинарные отношения, экспертные технологии, процессы управления, контроллинг.
1. Введение
Понятия теории графов применяются при моделировании различных процессов управления. Распространен термин: сете-вые модели управления, поскольку «сеть» и «граф» - в теории моделирования практически синонимы. В настоящей статье в соответствии с основными интересами нашего научного коллек-тива сосредоточимся на процессах управления промышленными предприятиями. Одна из целей работы – выявить, с какими понятиями и результатами теории графов необходимо знако-мить студентов, обучающихся по специальности «менеджмент высоких технологий».
При анализе прикладных задач разработки и принятия управленческих решений [1] возникает необходимость во вве-дении нескольких типов графов:
неориентированных (выделено множество вершин, некото-рые пары вершин соединены ребрами),
ориентированных (ребра имеют начало и конец и называ-ются дугами);
взвешенных ориентированных (дугам поставлены в соот-ветствие положительные числа, называемые весами).
Отметим, что третий тип графов, хотя реально использует-ся, но как самостоятельная сущность в теории графов обычно не выделяется. Можно было бы рассмотреть и четвертый тип: взвешенные неориентированные графы, однако польза для приложений таких математических объектов автору статьи не ясна, поэтому рассматривать их не будем.
2. Оптимизация на графах
При моделировании процессов управления промышленны-ми предприятиями широко используют взвешенные ориентиро-ванные графы. Приведем примеры [1].
Начнем с задачи коммивояжера: необходимо за минималь-ное время обойти все вершины и вернуться в исходную точку. Название задачи обманчиво. Она может быть проинтерпретиро-вана как задача выбора маршрутов ремонтника - при проверке работы ряда технических устройств, охранника – при контроле безопасности помещений, транспортного средства – при достав-ке грузов по нескольким адресам.
В задаче о максимальном потоке пропускная способность транспортной сети определяется взвешенным ориентированным графом. Эта задача, как и задача коммивояжера, решается с помощью специальных алгоритмов.
Транспортная задача состоит в нахождении взвешенного ориентированного графа, задающего маршруты и объемы пере-возок из исходных складов потребителям. С математической точки зрения она является задачей линейного программирова-ния.
Организационная структура предприятия описывается взвешенным ориентированным графом (деревом), в котором начала и концы дуг соответствуют подчиненности лиц и под-разделений, а веса – интенсивности взаимодействия. Совершен-ствование организационной структуры обычно осуществляют неформально, хотя уже есть и математические подходы [2].
При выявлении неформальной структуры малой группы также используют взвешенные ориентированные графы, хотя для интерпретации обычно избавляются от весов, сравнивая их с пороговым значением и оставляя ребро (дугу), если вес боль-ше или равен порога, отбрасывая в противном случае [3].
При проектировании корпоративных информационных сис-тем, например, документооборота, незаменимы ориентирован-ные графы, а при моделировании трафика – взвешенные ориен-тированные графы [3].
По сравнению с известной работой [4] мы подчеркиваем, что при моделировании часто используются именно взвешенные ориентированные графы, а не другие типы графов.
3. Графы, бинарные отношения, матрицы
При разработке и принятии управленческих решений ак-тивно используются технологии экспертных оценок [1]. С це-лью моделирования поведения экспертов рассмотрим три ряда понятий: графы - бинарные отношения - матрицы.
Бинарные отношения на конечном множестве – это под-множества декартова квадрата этого множества. Неориентиро-ванный граф можно описать бинарным отношением на множе-стве его вершин следующим образом: пара вершин входит в бинарное отношение тогда и только тогда, когда эти вершины соединены ребром. Та же пара вершин, упорядоченная противо-положным образом, также входит в рассматриваемое бинарное отношение. Для описания ориентированного графа надо исполь-зовать упорядоченные пары вершин: первая соответствует началу дуги, вторая – ее концу. Взвешенные ориентированные графы соответствуют метризованным бинарным отношениям, в которых каждая пара вершин, входящих в отношение, снабжена числом (весом) [5].
Бинарные отношения находятся во взаимно-однозначном соответствии с матрицами из 0 и 1. Это соответствие строится на основе нумерации элементов конечного множества. Упоря-дочим каким-либо образом то множество, на котором определе-но бинарное отношение: {a(1), a(2), …, a(k)}. Бинарному отно-шению поставим в соответствие матрицу ||b(i, j)|| из 0 и 1 порядка k следующим образом: b(i,j) = 1, если пара (a(i), a(j)) входит в отношение, и b(i, j) = 0 в противном случае. Метризо-ванному отношению естественно поставить в соответствие матрицу, в которой для входящей в отношение пары (a(i), a(j)) элемент матрицы b(i, j) равен тому числу, которым снабжена эта пара, и b(i, j) = 0 для пар, которые не входят в отношение.
Таким образом, неориентированные и ориентированные графы, бинарные отношения и матрицы из 0 и 1 находятся во взаимно-однозначном соответствии, равно как взвешенные ориентированные графы, метризованные отношения и матрицы описанного выше специального вида. Вести рассуждения можно на любом из трех языков – теории графов, бинарных отноше-ний, матриц из 0 и 1. Например, ставить прикладные задачи естественно на языке графов или бинарных отношений, а разра-батывать алгоритмы и проводить расчеты – на языке матриц.
Описанная выше общая схема взаимно-однозначных соот-ветствий развивает ту часть статистики нечисловых данных [6], в которой устанавливаются связи между различными видами объектов нечисловой природы. В многообразие объектов нечи-словой природы введены графы.
Как любая общая схема, в некоторых конкретных случаях она нуждается в уточнениях. Как быть, если в графе некоторые пары вершин соединены двумя или более ребрами или дугами? Для описания такого графа в терминах бинарных отношений придется ввести метризованное бинарное отношение специаль-ного вида, в котором веса – натуральные числа.
В качестве примера рассмотрим неориентированный граф, в котором каждые две вершины могут соединяться не более чем одним ребром. Он описывается матрицей из 0 и 1, симметрич-ной относительно главной диагонали. На главной диагонали стоит 1, если соответствующая вершина соединена ребром сама с собой, и 0 в противном случае. Неориентированные графы можно сопоставить с толерантностями – рефлексивными сим-метричными бинарными отношениями, которым соответствуют симметричные относительно главной диагонали матрицы из 0 и 1, на главной диагонали которых стоят 1.
Пользу языка теории графов при анализе бинарных отно-шений можно продемонстрировать на примере алгоритма со-гласования кластеризованных ранжировок [7], в котором стро-ится (неориентированный) граф противоречий, а затем в нем выделяются связные компоненты, упорядочение которых – результат работы алгоритма. Выделение связных компонент наиболее естественно проводится на языке графов.
В различных пространствах бинарных отношений можно ввести геометрическую структуру [6], в частности, выделить для каждого элемента совокупность ближайших соседей. Например, для упорядочения ближайшие соседи – те, которые отличаются от рассматриваемого одной инверсией. Введем граф ближайших соседей, в котором вершинами являются элементы рассматри-ваемого пространства бинарных соседей, а ребра соединяют ближайших соседей. Такой граф позволяет строить итеративные алгоритмы оптимизации, в которых одна итерация состоит в просчитывании значений оптимизируемого функционала для ближайших соседей бинарного отношения и переход к одному из ближайших соседей.
В частности, такой подход позволил В.Н. Жихареву по-строить новый алгоритм нахождения медианы Кемени в про-странстве ранжировок (упорядочений), использованный для изучения ее свойств (результаты включены в [6]). Этот алго-ритм отличается от ранее предложенного Б.Г. Литваком [5]. Отметим, что задача нахождения медианы Кемени имеет раз-ную сложность в зависимости от того, по какому множеству происходит оптимизация. Минимум элементарно находится (по правилу большинства), если минимизацию проводим по множе-ству всех бинарных отношений [6]. Алгоритмы сложны, если минимизацию проводим по множеству всех упорядочений (алгоритмы Б.Г. Литвака и В.Н. Жихарева), как это было пред-ложено в классической книге Дж. Кемени и Дж. Снелла [8].
4. Парные сравнения и бинарные отношения
Матрицами из 0 и 1 описываются результаты парных срав-нений. Сопоставим их с бинарными отношениями и исправим неточность изложения, допущенную в [6].
Парные сравнения применяют в двух разных формах.
Первый относится к признаку, измеренному в шкале на-именований. Результат парного сравнения – значения признака для двух объектов совпадают (код 0) или не совпадают (код 1).
Второй относится к признаку, измеренному в порядковой шкале. Результат парного сравнения – значения признака для первого объекта больше или равны, чем для второго (код 0) или значения признака для первого объекта меньше, чем для второ-го (код 1).
В обоих случаях результаты последовательности парных сравнений, проведенных определенным экспертом, - это после-довательность из 0 и 1, т.е. люсиан [9]. Проверка согласованно-сти экспертов – это проверка согласованности люсианов [6].
Пусть каждый объект сравнивается с каждым. Тогда ответы эксперта при использовании первой формы парных сравнений – рефлексивное симметричное отношение (толерантность). При использовании второй формы парных сравнений – рефлексив-ное антисимметричное отношение (квазитолерантность). Для заполнения главной диагонали нет необходимости обращаться к экспертам – по определению записи результатов процедуры парного сравнения во всех клетках должны стоять 1.
По заполнению 0 и 1 части матрицы, лежащий выше глав-ной диагонали, отличить квазитолерантность от толерантности невозможно. На главной диагонали стоят единицы. Квазитоле-рантность отличается от толерантности только по заполнению части матрицы, лежащей ниже главной диагонали. Для толе-рантности в симметричных клетках стоят одинаковые числа, для квазитолерантности – числа, в сумме составляющие 1.
Согласованность экспертов достаточно проверять для ле-жащих выше главной диагонали частей матриц, описывающих мнения экспертов. Следовательно, одинаковы алгоритмы про-верки согласованности для двух форм парных сравнений, опи-сывающихся толерантностями и квазитолерантностями соответ-ственно. Алгоритмы приведены в [6].
То, что квазитолерантность отличается от толерантности только по заполнению части матрицы, лежащей ниже главной диагонали, а эту часть мы не используем при проверке согласо-ванности, может послужить причиной отождествления толе-рантности и квазитолерантности [6]. Такое смешение понятий ошибочно, хотя и не приводит к каким-либо проблемам при расчетах.
Пусть цель обработки экспертных данных состоит в полу-чении ранжировки, отражающей групповое мнение. Однако согласно рекомендуемой процедуре экспертного опроса пусть эксперты не упорядочивают объекты, а проводят парные срав-нения (во второй форме), сравнивая каждый из рассматривае-мых объектов со всеми остальными, причем ровно один раз. Тогда ответ эксперта – квазитолерантность (рефлексивное антисимметричное отношение), но, вообще говоря, не ранжи-ровка, поскольку в ответах эксперта может нарушаться транзи-тивность.
Возможны два пути обработки данных. Первый - превра-тить ответ эксперта в ранжировку (тем или иным способом «спроектировав» его на пространство ранжировок), а затем проверять согласованность ранжировок с помощью известных критериев (например, коэффициента ранговой конкордации Кендалла и Б. Смита [10]). При этом от квазитолерантности перейти к ранжировке можно, например, так. Будем выбирать ближайшую (в смысле применяемого расстояния) матрицу к матрице ответов эксперта из всех, соответствующих ранжиров-кам без связей.
Второй путь - проверить согласованность случайных квази-толерантностей, а групповое мнение искать с помощью медиа-ны Кемени непосредственно по исходным данным, т.е. по ква-зитолерантностям. Групповое мнение при этом может быть найдено в пространстве ранжировок. Второй путь мы считаем более предпочтительным, поскольку при этом обеспечивается более адекватная проверка согласованности (с помощью теории люсианов) и исключается процедура укладывания мнения экс-перта в «прокрустово ложе» ранжировки.
5. Проверка согласованности мнений экспертов и классификация экспертных мнений
Практика применения экспертных технологий показывает, что мнения разных экспертов различаются. Важно понять, насколько велико это различие. Если мало - усреднение мнений экспертов позволит выделить то общее, что есть у всех экспер-тов, отбросив случайные отклонения в ту или иную сторону. Если велико - усреднение является чисто формальной процеду-рой. Так, если представить себе, что ответы экспертов равно-мерно покрывают поверхность бублика, то формальное усред-нение укажет на центр дырки от бублика, а такого мнения не придерживается ни один эксперт. Из сказанного ясна важность проблемы проверки согласованности мнений экспертов.
Разработан ряд методов такой проверки. Статистические методы проверки согласованности зависят от математической природы ответов экспертов. Соответствующие статистические теории весьма трудны, если эти ответы - ранжировки или раз-биения, и достаточно просты, если ответы - результаты незави-симых парных сравнений. Отсюда вытекает рекомендация по организации экспертного опроса: не старайтесь сразу получить от эксперта ранжировку или разбиение, ему трудно это сделать, да и имеющиеся математические методы не позволяют далеко продвинуться в анализе подобных данных. Например, рекомен-дуют проверять согласованность ранжировок с помощью коэф-фициента ранговой конкордации Кендалла-Смита. Но давайте вспомним, какая статистическая модель при этом используется. Как известно, в рамках методологии математической статистики проверяется нулевая гипотеза, согласно которой ранжировки независимы и равномерно распределены на множестве всех ранжировок. Если эта гипотеза принимается, то ни о какой согласованности мнений экспертов говорить нельзя. А если отклоняется? Тоже нельзя. Например, может быть два (или больше) центра, около которых группируются ответы экспер-тов. Нулевая гипотеза отклоняется. Но разве можно говорить о согласованности?
Эксперту гораздо легче на каждом шагу сравнивать только два объекта. Пусть он занимается парными сравнениями. Непа-раметрическая теория парных сравнений (теория люсианов) [6] позволяет решать более сложные задачи, чем статистика ранжировок или разбиений. В частности, вместо гипотезы рав-номерного распределения можно рассматривать гипотезу одно-родности, т.е. вместо совпадения всех распределений с одним фиксированным (равномерным) можно проверять лишь совпа-дение распределений мнений экспертов между собой, что есте-ственно трактовать как согласованность их мнений. Таким образом, удается избавиться от неестественного предположения равномерности.
При отсутствии согласованности экспертов естественно разбить их на группы сходных по мнению. Это можно сделать различными методами статистики объектов нечисловой приро-ды, относящимися к кластер-анализу, предварительно введя метрику в пространство мнений экспертов. Идея американского математика Джона Кемени об аксиоматическом введении мет-рик [8] нашла многочисленных продолжателей. Однако методы кластер-анализа обычно являются эвристическими. В частности, обычно невозможно с позиций статистической теории обосно-вать «законность» объединения двух кластеров в один. Имеется важное исключение - для независимых парных сравнений (лю-сианов) разработаны методы, позволяющие проверять воз-можность объединения кластеров как статистическую гипо-тезу. Это - еще один аргумент за то, чтобы рассматривать теорию люсианов как ядро математических методов экспертных оценок [1].
6. Практическое значение теории графов
Теория графов - важная составная часть математического инструментария контроллинга и менеджмента высоких техно-логий.
В нашей стране бурно развивается теория и практика кон-троллинга - современной концепции системного управления организацией, в основе которой лежит стремление обеспечить ее долгосрочное эффективное существование [11, 12]. Методы контроллинга – это методы информационно-аналитической поддержки принятия решений на предприятии (в организации). В XXI в. создано «Общество контроллеров» и журнал «Кон-троллинг», начата подготовка специалистов по контроллингу.
Теория графов как часть математического аппарата теории принятия решений широко используется при организационно-экономическом моделировании процессов управления промыш-ленными предприятиями. Роль рассмотренных в настоящей статье математических методов при постановке и решении задач контроллинга достаточно подробно раскрыта в работах [13, 14].
Контроллинг – часть менеджмента высоких технологий, предметом которого являются системы управления наукоемки-ми предприятиями и их объединениями. Экономико-математические методы, кибернетика, информационно-коммуникационные технологии составляют научный инстру-ментарий менеджмента высоких технологий. Как видно из [3], заметное место в этом инструментарии занимают математиче-ские методы, рассмотренные в настоящей статье.
Здесь рассмотрена лишь часть математических подходов и результатов, относящихся к тематике статьи, и еще меньшая часть прикладной тематике. Отметим, например, большое зна-чение теории графов, бинарных отношений, парных сравнений в социологических исследованиях и при моделировании социаль-ных процессов [15].
Литература
1. ОРЛОВ А.И. Теория принятия решений. – М.: Экзамен, 2006. – 576 с.
2. ГУБКО М.В. Математические модели оптимизации иерар-хических структур. – М.: ЛЕНАНД, 2006. – 264 с.
3. КОЛОБОВ А.А., ОМЕЛЬЧЕНКО И.Н., ОРЛОВ А.И. Ме-неджмент высоких технологий. Интегрированные произ-водственно-корпоративные структуры: организация, эко-номика, управление, проектирование, эффективность, ус-тойчивость. – М.: Экзамен, 2008. – 621 с.
4. БУРКОВ В.Н., ЗАЛОЖНЕВ А.Ю., НОВИКОВ Д.А. Теория графов в управлении организационными системами. - М.: Синтег, 2001. – 124 с.
5. ЛИТВАК Б.Г. Экспертная информация: методы получения и анализа. - М.: Радио и связь, 1982. – 184 с.
6. ОРЛОВ А.И. Организационно-экономическое моделирова-ние: учебник : в 3 ч. Часть 1: Нечисловая статистика. – М.: Изд-во МГТУ им. Н.Э. Баумана. – 2009. – 541 с.
7. ГОРСКИЙ В.Г., ГРИЦЕНКО А.А., ОРЛОВ А.И. Метод согласования кластеризованных ранжировок // Автоматика и телемеханика. - 2000. - №3. - С.179-187.
8. КЕМЕНИ ДЖ., СНЕЛЛ ДЖ. Кибернетическое моделирова-ние: Некоторые приложения. - М.: Советское радио, 1972. - 192 с.
9. ОРЛОВ А.И. Люсиан // Вероятность и математическая статистика: энциклопедия [под ред. Ю. В. Прохорова]. – М.: Большая Российская Энциклопедия, 1999. - С.293-293.
10. БОЛЬШЕВ Л.Н., СМИРНОВ Н.В. Таблицы математиче-ской статистики. – М.: Наука, 1983. - 416 с.
11. КАРМИНСКИЙ А.М., ОЛЕНЕВ Н.И., ПРИМАК А.Г., ФАЛЬКО С,Г. Контроллинг в бизнесе. Методологические и практические основы построения контроллинга в органи-зациях. - М.: Финансы и статистика, 1998. - 256 с.
12. ХАН Д.. Планирование и контроль: концепция контроллин-га: Пер. с нем. - М.: Финансы и статистика, 1997. - 800 с.
13. ОРЛОВ А.И.. Эконометрическая поддержка контроллинга // Контроллинг. - 2002. - №1. - С.42-53.
14. ОРЛОВ А.И., КУЛИКОВА С.Ю., МУРАВЬЕВА В.С. Орга-низационно-экономическое моделирование в контроллинге // Контроллинг. - 2009. - №5 (33). - С. 42-47.
15. ОРЛОВ А.И. Организационно-экономические методы и модели и их применение в социологических исследованиях // Математическое моделирование социальных процессов. Вып.10 : сб. ст. / Под ред. А.П. Михайлова. – М.: КДУ, 2009. – С.248 – 263.
NETWORK MODELS OF THE INDUSTRIAL CONTROL SYSTEMS
Alexander Ivanovich Orlov, the director of Institute of high statis-tical Technologies and Econometrics of Baumann Moscow State Technical University, DSc (technics), PhD (mathematics), full professor ((
prof-orlov@mail.ru,
http://orlovs.ru ).
Abstract: Use of various kinds of graphs is considered at modelling of managerial processes by the industry organizations, in particu-lar, by optimization on graphs., in expert technologies. Conformi-ties of graphs are found with other kinds of objects of the non-numerical nature - binary relations, matrixes from 0 and 1, results of pair comparisons. Discrepancy is corrected at the analysis of pair comparisons. At discussion of concordance testing of experts opinions and classification of expert estimations the role of ljusians is shown. From an applied point of view the role of the graph theory is defined by that it - the important component of mathematical toolkit of controlling and management of high technologies.
Keywords: mathematical modelling, graph theory, binary rela-tions, expert technologies, managerial processes, controlling.
Вход
Регистрация
FAQ
Поиск
Пользователи
