ПРИНЯТИЕ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ НА БАЗЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ТЕОРИЙ ГРАФОВ, «ДЕРЕВЬЕВ» И СЕТЕЙ

Принятие управленческих решений методами теории графов

Теория графов является разделом дискретной математики, исследующей свойства конечных множеств с заданными отношениями между их элементами. Начало теории графов было положено в 1736 г., когда Л. Эйлер предложил в то время уникальное решение задачи о кенигсбергских мостах. Результат решения этой задачи позволил Л. Эйлеру сформулировать некоторые правила:

  • 1) в графе, не имеющем вершин нечетных степеней, существует обход всех ребер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа;
  • 2) в графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой;
  • 3) в графе, имеющем более двух вершин с нечетной степенью, такого обхода не существует [24].

В истории известно решение еще одной задачи при помощи теории графов. Это задача, в которой требуется найти путь, проходящий через все вершины графа, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии (в честь ирландского математика У.Р. Гамильтона, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым и, если да, найти на нем все гамильтоновы линии.

Еще одна известная задача — «проблема четырех красок», появившаяся в середине XIX в., — легла в основу классического научного понимания теории графов. Попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. «Проблема четырех красок» составлена следующим образом: можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета? Было доказано и принято положительное решение. Однако в 1890 году было доказано другое утверждение, а именно о том, что любая плоская карта раскрашивается в пять цветов [41]. Сопоставляя с любой плоской картой двойственный ей плоский граф, получают эквивалентную формулировку задачи в терминах графов: верно ли, что хроматическое число любого плоского графа меньше либо равно четырем? Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году полученные 86 лет назад результаты были подтверждены при помощи ЭВМ. Следующая классическая топологическая задача — «задача об электро-, газо- и водоснабжении». В 1917 году Г.Э. Дьюдени продемонстрировал ученому миру ее решение [29].

Р. Карп в 1972 г. выдвинул и решил «задачу о клике». Также известны задачи «изоморфизм графов» (можно ли путем перенумерации вершин одного графа получить другой) и «планарность графа» (можно ли изобразить граф на плоскости без пересечений ребер (или с минимальным числом слоев, что находит применение при трассировке межсоединений элементов печатных плат или микросхем) [22; 41; 59].

Известны примеры использования методов теории графов в различных научных областях знаний. Приведем некоторые наиболее известные из них.

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

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

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

Занимаясь чисто практическими задачами органической химии, А. Кэли в 1857 г. открыл важный класс графов, называемых «деревьями». Он стремился перечислить изомеры предельных (насыщенных) углеводородов Сп Н2п+2 с данным числом п атомов углерода [8].

В 1936 году психолог К. Левин высказал предположение о том, что «жизненное пространство» индивидуума можно представить с помощью планарной карты. На такой карте области представляют различные типы деятельности человека, например то, что он делает на работе, дома, или же его хобби. Эта точка зрения привела психологов Научно-исследовательского центра групповой динамики к другой психологической интерпретации графа, в которой люди представляются вершинами, а их отношения — ребрами. Такими отношениями являются, например, любовь, ненависть, общение, подчинение [8].

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

Основой проектного менеджмента в первой половине XX в. стали сетевые модели СРМ и PERT, базирующиеся на теории графов. При помощи этих моделей в это же время развивался и производственный менеджмент.

Отдельный импульс развития получила теория графов в 1974 г. в направлении формирования и развития метода анализа иерархий Т. Саати [22].

Сам термин «граф» впервые был введен в 1936 г. Д. Кенигом [22].

Граф — это средство для наглядного представления состава и структуры какой-либо системы.

Граф состоит из вершин (узлов), связанных дугами (если линия направленная) или ребрами (если линия не имеет направления) (рис. 5.1). Две вершины, соединенные дугой или ребром, называются смежными. Граф, в котором все линии направленные, называется ориентированным (рис. 5.1а) (например, «дерево целей» или сетевой график).

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

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

Обозначение графа

Рис. 5.1. Обозначение графа:

а — ориентированный граф; б — неориентированный граф

Для закрепления базовых понятий и сущности теории графов предлагается решить несколько простых задач.

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

Задание № 1

Крупный поставщик интернет-трафика объявил тендер на строительство интернет-сети. Стоимость соединения различных городов оптико-волоконным кабелем приведена на рис. 5.2. Подряд на строительство интернет-сети получит та подрядная организация, которая предложит проект минимальной стоимости.

Поле решения задания № 1

Рис. 5.2. Поле решения задания № 1

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

Особые условия: интернет-трафик можно передать из одного горо - да в другой через любое множество городов-посредников.

В приложении 3, на рис. 31 ив табл. 31 представлены варианты для индивидуального решения задания.

Задание № 2

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

Матрица стоимости соединений узлов (городов)

Таблица 5.1

А

В

С

D

Е

F

G

Н

А

0

13

9

23

23

34

6

14

В

0

17

32

36

27

18

27

С

0

24

28

36

12

16

D

0

8

10

24

21

Е

0

20

37

29

F

0

30

29

G

0

15

Н

0

Требуется найти такую схему, которая позволит жителям любых двух городов связаться друг с другом по телефону. Для выполнения задания нужно вписать в узлы названия городов — А, В, С и т.д. — и соединить узлы ребрами, указав на ребрах стоимость соединения смежных узлов на рис. 53.

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

Поле решения задания № 2

Рис. 5.3. Поле решения задания № 2

В приложении 3, на рис. 32 и в табл. 32 представлены варианты для индивидуального решения задания.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >