При исследовании, анализе и решении управленческих проблем, моделировании экономических объектов широко используются методы формализированного представления, являющегося предметом рассмотрения в дискретной математике. Широкое применение при решении таких задач получила теория графов благодаря своей наглядности и универсальности. Исследования показывают, что не менее 70% реальных задач математического программирования можно представить в виде сетевых моделей [3]. Приведём несколько конкретных примеров [1, 2].
- Проектирование газопровода, соединяющего буровые скважины морского базирования, с находящейся на берегу приёмной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода;
- Поиск кратчайшего маршрута между городами по соответствующей сети дорог;
- Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям;
- Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки;
- Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).
С геометрической точки зрения граф представляет непустое множество точек (вершин) и множество отрезков (рёбер), концы которых принадлежат данному множеству точек (рис. 1).
При изображении графов рёбра могут быть прямолинейны или криволинейны, длины рёбер и расположение вершин произвольны.
Примерами графов могут служить схемы железнодорожных и автомобильных дорог, метрополитена, формулы молекул, генеалогические деревья и т.п.
В приложениях граф обычно называют сетью (сеть автомобильных дорог, железнодорожная сеть, сеть магазинов, кабельная сеть и т.д.), а его вершины называют узлами. Каждому ребру (дуге) придают некоторое числовое значение, которое в зависимости от смысла задачи может обозначать расстояние, пропускную способность, время, стоимость и т.д. С каждым видом сети связан определённый тип потоков (например, поток нефти в нефтепроводах, автомобильные потоки в сети городских дорог).
На практике одно решение, как правило, приводит к необходимости принятия следующего решения и т.д. Графически подобные процессы могут быть представлены с помощью дерева решений. Дерево представляет собой связный граф без циклов, имеющий ствол и ветви, и облегчает описание многоэтапного процесса принятия управленческого решения в целом. Такое дерево даёт возможность рассмотреть различные ситуации, соотнести с ними результаты, скорректировать их в соответствии с приписанной им вероятностью, а затем сравнить альтернативы и выбрать наилучший вариант действий.
Составляя такое дерево решений, рисуют ствол и ветви, отображающие структуру проблемы. Располагают дерево решений слева направо. Ветви обозначают альтернативные решения, которые могут быть приняты, и вероятные исходы, возникающие в результате этих решений.
Квадратные узлы на дереве решений обозначают принимаемые решения, круглые — исходы. Так как влиять на исходы не представляется возможным, в круглых узлах вычисляют вероятности этих исходов. Когда все решения и исходы указаны на дереве, оценивается каждый из вариантов и проставляются соответствующие вычисления.
Пример [2]. Выпускник школы желает продолжить учёбу в ВУЗе. Он хочет оценить возможности получения диплома в области инженерного образования или в экономической сфере в одном из двух ВУЗов — Волжском политехническом институте (ВПИ) или Волгоградском государственном техническом университете (ВолгГТУ). Вероятности успешного окончания и предполагаемый доход по окончании обучения представлены в табл. 1.
Если выпускник не заканчивает ни один из этих ВУЗов, то его средний доход будет равен D0 = 180 (тыс. руб.)
Критерием при принятии решения является величина ожидаемого среднего дохода.
Выбранный факультет | Вероятность получения диплома | Годовой доход после окончания (тыс. руб.) | |
успех | неудача | ||
Факультет экономики и управления (ФЭУ) ВолгГТУ | 40% | 60% | D1 = 400 |
Автотракторный факультет (АТФ) ВолгГТУ | 70% | 30% | D2 = 350 |
Инженерно-экономический факультет (ФЭИ) ВПИ | 50% | 50% | D3 = 320 |
Автомеханический факультет (ФАМ) ВПИ | 95% | 5% | D4 = 300 |
Решение. Составим дерево всевозможных решений (рис. 2). Вычислим среднее значение ожидаемого дохода с учётом известных вероятностей для каждого случая.
Выбирая максимальный результат, приходим к выводу, что для данного выпускника предпочтительнее выбрать автотракторный факультет ВолгГТУ с ожидаемым доходом 350 тыс. руб.