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

NovaInfo 46, с.35-38
Опубликовано
Раздел: Физико-математические науки
Просмотров за месяц: 18
CC BY-NC

Аннотация

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

Ключевые слова

ГРАФЫ, СЕТИ

Текст научной работы

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

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

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

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

Граф.
Рисунок 1. Граф

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

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

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

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

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

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

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

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

Таблица 1. Вероятности успешного окончания и предполагаемый доход

Выбранный факультет

Вероятность получения диплома

Годовой доход после окончания (тыс. руб.)

успех

неудача

Факультет экономики и управления (ФЭУ) ВолгГТУ

40%

60%

D1 = 400

Автотракторный факультет (АТФ) ВолгГТУ

70%

30%

D2 = 350

Инженерно-экономический факультет (ФЭИ) ВПИ

50%

50%

D3 = 320

Автомеханический факультет (ФАМ) ВПИ

95%

5%

D4 = 300

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

Дерево решений.
Рисунок 1. Дерево решений

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

Читайте также

Список литературы

  1. Агишева Д. К., Зотова С. А., Светличная В. Б., Матвеева Т. А. Методы принятия оптимальных решений. Ч. 1: учебное пособие / ВПИ (филиал) ВолгГТУ: ИУНЛ ВолгГТУ, 2011. -155 с.
  2. Агишева Д. К., Зотова С. А., Светличная В. Б., Матвеева Т. А. Транспортные и сетевые модели управления. Часть 2: учебное пособие/ С. А. Зотова, Д. К. Агишева, В. Б. Светличная, Т. А. Матвеева / ВПИ (филиал) ВолгГТУ. – Волгоград: ИУНЛ ВолгГТУ, 2012. – 160 с.
  3. Таха, Хемди А. Введение в исследование операций, 7-издание. Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 912 с.: ил. – Парал. Тит. англ.

Цитировать

Агишева, Д.К. Приложения теории графов / Д.К. Агишева, С.А. Зотова. — Текст : электронный // NovaInfo, 2016. — № 46. — С. 35-38. — URL: https://novainfo.ru/article/6397 (дата обращения: 21.01.2022).

Поделиться