Приложения теории графов

При исследовании, анализе и решении управленческих проблем, моделировании экономических объектов широко используются методы формализированного представления, являющегося предметом рассмотрения в дискретной математике. Широкое применение при решении таких задач получила теория графов благодаря своей наглядности и универсальности. Исследования показывают, что не менее 70% реальных задач математического программирования можно представить в виде сетевых моделей [3]. Приведём несколько конкретных примеров [1, 2].

1. Проектирование газопровода, соединяющего буровые скважины морского базирования, с находящейся на берегу приёмной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода;
2. Поиск кратчайшего маршрута между городами по соответствующей сети дорог;
3. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям;
4. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки;
5. Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).

С геометрической точки зрения граф представляет непустое множество точек (вершин) и множество отрезков (рёбер), концы которых принадлежат данному множеству точек (рис. 1).

При изображении графов рёбра могут быть прямолинейны или криволинейны, длины рёбер и расположение вершин произвольны.

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

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

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

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

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

Пример [2]. Выпускник школы желает продолжить учёбу в ВУЗе. Он хочет оценить возможности получения диплома в области инженерного образования или в экономической сфере в одном из двух ВУЗов — Волжском политехническом институте (ВПИ) или Волгоградском государственном техническом университете (ВолгГТУ). Вероятности успешного окончания и предполагаемый доход по окончании обучения представлены в табл. 1.

Если выпускник не заканчивает ни один из этих ВУЗов, то его средний доход будет равен D0 = 180 (тыс. руб.)

Критерием при принятии решения является величина ожидаемого среднего дохода.

Решение. Составим дерево всевозможных решений (рис. 2). Вычислим среднее значение ожидаемого дохода с учётом известных вероятностей для каждого случая.

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