Деревья

Граф является деревом, если в его множество Features входит флаг Tree (Tree in Features = True). Указание на то, что граф является деревом (Directed in Features = True), позволяет упростить работу с древовидными структурами. Одна из вершин дерева помечается как корень. Для того, чтобы сделать вершину корнем, надо присвоить свойству IsRoot вершины значение True или, что то же самое, присвоить свойству Root графа указатель на эту вершину. Каждая вершина дерева, кроме корня, содержит ссылку на родительскую вершину (Parent). Для построения дерева следует использовать метод TVertex.AddChild.

Транспортные сети

Транспортная сеть (Network in Features = True) - это ориентированный граф с двумя выделенными вершинами: истоком (TGraph.NetworkSource) и стоком (TGraph.NetworkSink). Исток обладает тем свойством, что в него не входит ни одна дуга; из стока, напротив, не исходит ни одна дуга. Каждой дуге сети приписано неотрицательное вещественное число - максимальный поток, который может быть пропущен через эту дугу. Одной из наиболее известных задач на сетях является задача нахождения максимального потока в сети. В библиотеке реализовано решение этой задачи; для этого необходимо построить граф - транспортную сеть, указать с помощью свойств графа NetworkSource и NetworkSink исток и сток сети (то же самое можно сделать, присвоив значение True свойствам IsNetworkSource и IsNetworkSink соответствующих вершин сети), задать максимальные потоки на дугах сети с помощью свойства TEdge.MaxFlow и вызвать метод TGraph.FindMaxFlowThroughNetwork. Если построенная сеть корректна (IsNetworkCorrect = True), то этот метод возвращает значение максимального потока в сети и устанавливает свойства TEdge.Flow в значения потоков на дугах, при которых достигается максимальный поток.

Взвешенные графы

Взвешенный граф (Weighted in Features = True) - неориентированный или ориентированный граф, ребрам (дугам) которого поставлено в соответствие вещественное число, называемое весом. Вес ребра доступен с помощью свойства TEdge.Weight. Классической задачей на взвешенном графе является задача нахождения кратчайшего пути (пути с минимальной суммой весов входящих в этот путь ребер или дуг) между заданными вершинами, либо между всеми парами вершин. Задача нахождения кратчайшего пути между заданными вершинами во взвешенном графе с неотрицательными весами решается в библиотеке методами TGraph.FindMinWeightPathCond / TGraph.FindMinWeightPath, в которых используется алгоритм Дейкстры. В библиотеке реализован также алгоритм Флойда (TGraph.CreateMinWeightPathsMatrix), позволяющий найти кратчайшие пути между всеми парами вершин. Алгоритм Флойда применим к ографам с дугами отрицательного веса; при наличии контуров отрицательной длины алгоритм их обнаруживает.

Геометрические графы

В геометрических графах для каждой вершины графа определены вещественные координаты: двумерные (X, Y) или трехмерные (X, Y, Z) (соответственно, Geom2D или Geom3D). В настоящее время в библиотеке определен только ряд вспомогательных методов для работы с такими графами, однако в будущем планируется реализовать алгоритмы визуализации графов.

7. Реализованные алгоритмы

В библиотеке AGraph реализованы алгоритмы решения многих теоретико-графовых задач, в том числе:

· поиск путей с минимальным количеством промежуточных вершин между заданными вершинами графа;

· поиск путей минимальной длины во взвешенном графе;

· определение связности графа;

· определение отношения ребра к кольцевым системам;

· нахождение компонент связности графа;

· нахождение сильных компонент ориентированного графа;

· построение матрицы связности и обобщенной матрицы связности графа;

· построение матрицы достижимости графа;

· построение матрицы расстояний графа;

· поиск максимальных независимых множеств вершин графа;

· поиск системы независимых минимальных колец графа (исключая петли), покрывающих все кольцевые ребра графа;

· построение графа, дополнительного к заданному графу;

· построение реберного графа для заданного графа;

· построение кратчайшего остовного дерева для заданного взвешенного графа;

· поиск максимального потока в транспортной сети;

· поиск хроматического числа и оптимальной вершинной раскраски графа;

· поиск эйлерова цикла в графе;

· поиск гамильтоновых циклов в орграфе;

· решение задачи почтальона для взвешенного графа с неотрицательными весами ребер;

· определение планарности графа;

· распознавание изоморфизма графов с учетом атрибутов.

В качестве источников алгоритмов использовались монографии и статьи по теории графов. При решении задач, для которых известны алгоритмы полиномиальной сложности, использовались, в основном, алгоритмы, которые являются асимптотически оптимальными среди всех известных алгоритмов решения данной задачи, или близки к оптимальным. Для некоторых из задач, решаемых библиотекой, алгоритмы полиномиальной сложности не существуют или неизвестны. В таком случае приходится использовать переборные алгоритмы, приближенные алгоритмы или алгоритмы, обеспечивающие эффективное решение для частных случаев задачи. Библиотека AGraph предоставляет ряд алгоритмов, которые относятся ко второй и третьей из этих категорий (например, приближенный алгоритм вершинной раскраски графов). В то же время, основное внимание в библиотеке уделялось реализации универсальных алгоритмов. Для некоторых "трудных" задач переборные алгоритмы были реализованы самостоятельно; для решения других в библиотеку были перенесены наиболее эффективные программные реализации, которые удалось найти (разумеется, в том случае, когда авторы программ допускают такое использование). Так, функция распознавания изоморфизма графов основана на программе, разработанной М. Венто; функция нахождения хроматического числа и оптимальной вершинной раскраски графа основана на программе, разработанной М. Триком.

Важнейшей проблемой при разработке программного обеспечения является обеспечение его корректности. Необходимой составляющей для достижения корректности является использование корректных алгоритмов, однако правильная и эффективная реализация алгоритмов также является нетривиальной задачей. При создании библиотеки AGraph принимались различные меры для обнаружения и исправления ошибок. Во-первых, в отладочном режиме методы классов библиотек AGraph и Vectors выполняют проверки предусловий и правильности передаваемых параметров; в случае обнаружения ошибки возбуждается исключительная ситуация (exception). Во-вторых, все изменения активно тестируются как в ручном, так и в автоматическом режиме, для чего были созданы соответствующие программные тесты. Разумеется, все эти методы не гарантируют отсутствие ошибок, однако их использование позволило значительно повысить надежность библиотеки.

С технологической точки зрения алгоритмы можно разделить на две категории: первые из них реализованы в виде методов класса TGraph (модуль graphs.pas), вторые - в отдельных модулях. Реализация алгоритмов в модуле graphs.pas позволяет достичь максимальной эффективности за счет доступа к деталям внутреннего представления графа (т.е. к защищенным полям и методам классов TVertex, TEdge и TGraph), поэтому таким способом реализованы, в основном, "базовые" алгоритмы: поиск путей, определение компонент связности графа и т.д.

8. Ввод вывод графов

Одной из проблем при создании средств работы с помеченными графами является выбор внешнего файлового формата для хранения графов. До недавнего времени каждая программная система использовала свой собственный, уникальный формат, что приводило к сложностям при организации обмена данными. Относительно недавно разработчики системы Graphlet предложили универсальный переносимый формат файла для представления помеченных графов - GML (Graph Modelling Language) [7]. В настоящее время GML-формат поддерживается многими прикладными программами и библиотеками для работы с графами.

GML-файл состоит из пар ключ-значение. Примерами ключей являются стандартные ключи graph, node и edge. Значениями могут быть целые и вещественные числа, строки и списки; в свою очередь, списки также содержат пары ключ-значение, в том числе вложенные списки. Важным достоинством формата GML является его открытость и расширяемость: любой разработчик имеет право определять свои ключи для хранения необходимой информации. В настоящее время этот формат поддерживается многими прикладными программами и библиотеками для работы с графами. Библиотека AGraph также поддерживает запись и чтение графов в GML-формате, но с некоторыми ограничениями (для хранения строк не используется кодировка ISO 8859).

Наряду с форматом GML, библиотека поддерживает запись графов в поток и чтение их из потока с использованием двоичного формата (методы TGraph.WriteToStream и TGraph.ReadFromStream). Данный способ обеспечивает более высокую скорость записи/чтения графов и приводит к созданию файлов меньшего размера, однако не является переносимым.

9. Создание специализированных классов графов

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

Примером специализированного класса графов является класс TChemGraph, предназначенный для работы с молекулярными графами. Данный класс является непосредственным потомком класса TGraph и поддерживает работу с молекулярными графами на уровне атомов и связей (см. пример 8). Для хранения необходимых данных используются атрибуты, но в целях ускорения доступа к ним вместо методов используется доступ по смещениям. TChemGraph обеспечивает также запись и чтение молекулярных графов с использованием распространенных MOL- и SDF-форматов.

// создание молекулярного графа

G:=TChemGraph.Create;

// добавление атомов и связей

A:=G.AddAtom(CarbonAtom); // добавить 'C'

G.AddAtom(AtomTbl.SearchName('N')); // добавить 'N'

G.AddAtom(AtomTbl.SearchName('Cl')); // добавить 'Cl'

G.AddBond(A, G[1], DoubleBond);

G.AddBond(A, G[2], SingleBond);

// свойства и методы, специфичные для молекулярных графов

G.Atom[1]:=CarbonAtom; // заменить 'N' на 'C'

S1:=G.AtomName[1]; // S1 = 'C'

S2:=G.BruttoFormula; // S2 = 'С2Сl1'

Пример 8. Использование класса TChemGraph.

10. Эффективность

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

Для оценки эффективности средств библиотеки AGraph было осуществлено решение ряда тестовых задач; те же задачи решались с помощью библиотеки LEDA. Поскольку данные библиотеки используют разные внутренние представления графов, различные методы привязки атрибутов к вершинам и ребрам графа, а также способы передачи параметров и возвращения результатов, прямое сравнение результатов этих испытаний не совсем корректно. Тем не менее, результаты показывают, что скоростные характеристики библиотек AGraph и LEDA являются, по крайней мере, сопоставимыми (см. таблицу 1).

При тестировании использовались следующие программные и аппаратные средства.

· ЭВМ: персональный компьютер на процессоре AMD K6-2 400 (частота системной шины 100 MHz), кэш второго уровня 512 Kb, ОЗУ 64 Mb.

· ОС: Windows 95 OSR 2.1.

· Версии библиотек: AGraph v.990915, LEDA 3.8.

· Компиляторы: для AGraph - Delphi 3.0, для LEDA - MS Visual C++ 5.0 (в обоих случаях отладочные проверки были выключены, использовалась максимальная оптимизация).

	AGraph	LEDA
количество вершин |V|=100000, количество ребер |E|=200000*
нахождение пути минимальной длины	0.4 с	0.6 с
нахождение пути минимального суммарного веса (граф интерпретировался как неориентированный)	1.5 с (вещественные веса)	1.9 с (целые веса); 3.2 с (вещественные веса)
нахождение пути минимального суммарного веса (граф интерпретировался как ориентированный)	1.3 с (вещественные веса)	1.1 с (целые веса); 1.9 с (вещественные веса)
нахождение связных компонент	0.6 с	0.4 с
нахождение сильных компонент (граф интерпретировался как ориентированный)	0.7 с	ошибка времени исполнения (переполнение стека)
Построение минимального остовного дерева	5.8 с	4.8 с

В библиотеке AGraph хранение графа такого размера потребовало около 26 Мб оперативной памяти и 21 Мб на диске в формате GML.

ГЛАВА II Алгоритмы и программы решения задач оптимизации на графах

2.1 Задачи оптимизации на графах

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

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

Задача нахождения оптимальных покрывающих деревьев;

Задача нахождения кратчайшего пути в графе:

Задача нахождения критического пути в сетевом графе:

Задача нахождения максимального потока в графе;

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

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

2.1.2 Общая характеристика задач оптимизации на графах

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

2.1.3 Математическая постановка задачи оптимизации на графах

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

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

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

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

2.1.4 Основные методы решения задач оптимизации на графах

Хотя общая математическая постановка задачи оптимизации на графах (2.1.3 7.11) не дает никакой информации относительно возможных методов ее решения, тем не менее, все методы решения таких задач можно условно разделить на два класса.

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

2. Задачи оптимизации на графах могут быть решены с использованием специальных алгоритмов, которые учитывают специфические особенности тех или иных объектов графа и конечную мощность множества допустимых альтернатив. В этой связи задачи оптимизации на графах концептуально оказываются тесно связанными с задачами комбинаторной оптимизации. Хотя для нахождения точного решения задач оптимизации на графах могут использоваться общие алгоритмы типа метода ветвей и границ и метода динамического программирования, наиболее эффективными с вычислительной точки зрения оказываются специальные алгоритмы. Именно такие алгоритмы решения типовых задач оптимизации на графах рассматриваются в настоящей главе и положены в основу разработки программ на VBA, которые представлены в данной главе.

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

Поскольку программa MS Exsel позволяет находить точное решение задач целочисленного и булева программирования, тем самым имеется возможность решения с ее помощью и задач оптимизации на графах. При этом общий порядок подготовки исходных данных и поиска решения аналогичен рассмотренному ранее для решения других типовых задач оптимизации. Для оценки точности получаемых решений целесообразно выполнить сравнение поученных различными способами оптимальных решений отдельных практических задач. Именно с этой целью в данной главе приводится описание способов решения задач о максимальном и минимальном покрывающем дереве в графе и задачи о кратчайшем пути.

2.2 Максимальное покрывающее дерево графа и его графическое изображение

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

2.2.1 Программа нахождения максимального покрывающего дерева графа

Для записи текста программы нахождения максимального покрывающего дерева графа воспользуемся модулем Module 1, который был ранее создан и имеется в книге с именем Программирование задач. В данном модуле введем следующий текст программы, оформленной в виде отдельной функции с именем MaxTree, которая использует единственный входной параметр для спецификации матрицы весов ребер исходного графа (листинг 2.2.1).

Листинг 2.2.1 Программа нахождения максимального покрывающего дерева графа

Function MaxTree (C As Variant) As Variant

Dim I, J, K, Im ,Jm As Integer

Dim Dis (), Tree (), Vlink () As Integer

Dim S As String

N = c. Columns. Count

ReDim Dis (N,N), Tree (N, N), Vlink(N)

`--Подготовка исходных массивов

For I =1 To N

Vlink (I) = 0 `--< этот массив хранит номера вершин, добавляемых к дереву

For J =1 To N

Dis (I, J) = C (I, J)

Tree (I, J) = 0 `--этот массив хранит структуру оптимального дерева

Next J

Next I

K=1

Vlink (1) = 1

`--Нахождения ребра с максимальным весом

While K <=N

Rec = 0

For I = 1 To N

For J = 1 To N

If Dis (I,J)<>0 And Rec <Dis (I, J) And Vlink (I)=1 And Vlink (J)=0 Then

Rec = Dis (I, J)

Im = I

Jm = J

End If

Next J

Next I

`--Добавление найденной вершины к покрывающему дереву

Vlink (Jm)=1

Tree (Im, Jm) = 1

Tree (Jm, Im) = 1

K = K+1

Wend

`--Расчет значения суммы весов ребер оптимального дерева и структуры дерева

Rec = 0

K = 0

S = “”

For I =1 To N-1

For J = 1+1 To N

If Tree (I, J) = 1 Then

K = K+1

S = S+”(“+CStr(I)+”,”+ CStr(J)+”),”

Rec = Rec + Dis (I,J)

End If

Next J

Next I

S = “Максимальное покрывающее дерево:”+ S+” Fmax = “ + CStr (Rec)

MaxTree = S'возвращаемое функцией значение

Erase Dis, Tree, Vlink `--уничтожаем все динамические массивы

End Function



Данная программа практически не требует пояснений, поскольку отличается от программы функции MinTree() буквально парой операторов. После выполнения необходимых действий алгоритма массив Tree (N, N) будет содержать ребра, которые входят в максимальное покрывающее дерево графа. В качестве результата данная функция возвращает в выбранную ячейку строку текста S, содержащего список ребер, образующих максимальное покрывающее дерево исходного графа, и оптимальное значение соответствующей целевой функции.

После написания текста программы соответствующая функция может быть вызвана из любого рабочего листа этой книги. Для удобства тестирования в книге программирования задач создадим новый рабочий лист с именем Максимальное дерево, в который скопируем ячейки A1:H9 с рабочего листа Изображение графа (Рис116)

Далее из любой свободной ячейки следует вызвать мастер добавления функции и в списке функций, определенных пользователем, выбрать созданную функцию MaxTree(). Выбор данной функции и спецификация значений ее аргументов выполняется аналогично ранее рассмотренной функции MinTree(). А именно в качестве единственного аргумента этой функции следует выделить диапазон ячеек B3:H9, в которых содержатся значения матрицы весов ребер исходного графа.

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

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

граф алгоритм оптимизация функция



Рис.2.2.1 Результат решения задачи нахождения максимально покрывающего дерева графа

2.2.2 Программа изображения максимального покрывающего дерева графа

Для изображения структуры максимального покрывающего дерева графа также следует дополнить матрицу весов ребер исходного графа значениями координат вершин. Поскольку структура рассматриваемого графа уже изображалось ранее, можно скопировать ячейки I1:J9 с координатами вершин из рабочего листав Изображение графа в соответствующие ячейки рабочего листа с именем Максимальное дерево либо ввести соответствующие данные заново.

Для записи текста программы изображения структуры максимального покрывающего дерева графа в Module 2 введем следующий текст программы, оформленной в виде отдельной подпрограммы с именем MaxTreePainter без входных параметров (листинг 2.2.2)

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

Рис. 2.2.2 Результат изображения максимального покрывающего дерева графа подпрограммой MaxTreePainter

Программа изображения структуры максимального покрывающего дерева графа использует в качестве исходных данных матрицу весов ребер графа и координаты его вершин. После написания текста программы она может быть запущена из данного рабочего листа MS Excel с помощью специального диалогового окна программы MS Excel, которое вызывается посредством выполнения операции главного меню: Сервис Макросы или нажатия комбинации клавиш: <Alt>+<F8> (рис.2.2.2.)

Как можно заметить, изображение максимального покрывающего дерева графа, полученное с помощью подпрограммы MaxTreePainter, полностью совпадает со структурой дерева, найденного ранее с помощью программы MS Excel .

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

2.3 Задача о максимальном потоке в сети

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

2.3.1 Математическая постановка задачи

Пусть G = (V, E, h) - ориентированный граф, в котором V={} конечное множество вершин, E ={}- конечное множество дуг, h:E - весовая функция дуг, которая интерпретируется как пропускная способность дуги. Дополнительно в графе фиксируется две вершины: Начальная вершина , которая называется исток, и конечная вершина , которая называется сток. В предположении, что исходный граф G является связным, т.е. вершина потенциально достижима из , и не содержит циклов, требуется определить поток максимального объема, протекающий из начальной вершиныв конечную вершину.

Введем в рассмотрение следующие неотрицательные целочисленные переменные - , которые интерпретируются как величина потока, проходящего по дуге (). Тогда в общем случае математическая постановка задачи о максимальном потоке в сети может быть сформулирована следующим образом:

(2.3.1)

Где множество допустимых альтернатив формируется следующей системной ограничений типа неравенств:

(2.3.2)

При этом первое ограничение (2.3.1) требует выполнение следующего условия: величина потока, выходящего из вершины (истока), должна быть равна величине потока, входящего в вершину (сток). Вторая группа ограничений (2.3.2) гарантирует выполнение следующего условия: любой частичный поток, входящий в каждый промежуточную вершину графа, должен быть равен потоку, выходящему из этой вершины. Общее количество ограничений (2.3.1) и (2.3.2) равно n -1. Третья группа ограничений (2.3.2) требует выполнения следующего условия: величина потока, протекающего по дуге (,), должна быть неотрицательной и не должна превышать пропускной способности этой дуги .

Наконец, последнее ограничение (2.3.2) требует, чтобы все переменные принимали только неотрицательные целочисленные значения. Напомним также, что ориентированный связный граф, не содержащий циклов, принято называть сетью.

Примечание

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

2.3.2 Решение задачи о максимальном потоке в сети с помощью программы MS Excel

Для решения задачи о максимальном потоке в сети с помощью программы MS Excel необходимо задать конкретные значения параметрам индивидуальной задачи. С этой целью рассмотрим задачу нахождения максимального потока в сети, которая представляет модель системы магистральных трубопроводов, связывающих источник добычи некоторого жидкого продукта (нефти, сжиженного газа) с предприятием по его промышленной переработке. Данная модель может быть представлена в виде схемы, формально представляющей собой ориентированный связный граф без циклов, состоящий из 6 вершин и 10 дуг (рис.2.3.2). Предельные значения пропускной способности каждого участка рассматриваемой системы между двумя соседними компрессорными станциями, выраженные, например, в m/час, равны значению весовой функции для каждой дуги, которые указаны рядом с изображением этой дуги в графе.

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

Размещено на http://www.allbest.ru/

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

Переменными математической модели данной индивидуальной задачи о максимальном потоке в сети являются 10 переменных

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

(2.3.2 7.5.6)

Где множество допустимых альтернатив формируется следующей системой ограничений типа равенств и неравенств:

(2.3.2 7.5.7)

Заметим, что те переменные, для которых весовая функция дуг h не определена или равна 0, не входят в математическую постановку рассматриваемой задачи (2.3.2).

Для решения данной индивидуальной задачи с помощью программы MS Excel создадим в книге с именем Оптимизация на графах новый рабочий стол с именем максимальный поток. После этого следует выполнить следующие действия:

1. Внесем необходимые надписи на ячейки A1:F1 (рис. 2.3.3). Следует отметить, что конкретное содержание этих надписей не оказывает влияния на решение рассматриваемой задачи.

2. В ячейки A2:A11 введем индексы начальных вершин, а в ячейки B2:B11--индексы начальных вершин, всех имеющихся дуг исходного графа.

3. В ячейки C2:C11 введем значения пропускных способностей дуг исходного графа.

4. В ячейку F2 введем формулу:

= СУММ(D2:D3), которая представляет целевую функцию (2.3.2)

6. В ячейку E2 введем формулу

7. = СУММ(D2:D3)-СУММ (D10:D11), которая представляет собой левую часть первого ограничения (2.3.2)

8. В ячейку E3 введем значение левой части второго ограничения

= D2- СУММ (D4: D6)

9. В ячейку E4 введем значение левой части третьего ограничения:

= D3- СУММ (D7: D8)

10. В ячейку E5 введем значение левой части четвертого ограничения

= СУММ (D5: D7) - СУММ (D9: D10)

11. И, наконец, в ячейку E6 введем значение левой части пятого ограничения:

= СУММ (D6; D8: D9) - D11

Внешний вид рабочего листа MS Office Excel 2003 с исходными данными для решения задачи о минимальном пути в графе имеет



Рис. 2.3.2 7.21. Исходные данные для решения задачи о максимальном потоке в сети

Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис Поиск решения.

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $F$2.

2. Для группы Равной: выбрать вариант поиска решения - максимальному значению.

3. В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $D$2: $D$11.

4. Задать первых 5 ограничений для рассматриваемой задачи. С этой целью выполнить следующие действия:

· Для задания этих ограничений в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· В появившемся дополнительном окне выбрать диапазон ячеек $E$2:$E$11, который должен отобразиться в поле с именем Ссылка на ячейку;

· В качестве знака ограничения из выпадающего списка выбрать равенство “=”;

· В качестве значения правой части ограничения ввести с клавиатуры значение 0;

· Для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить.

5. Задать первое из 10 ограничений на пропускные способности дуг (7.5.7).С этой целью выполнить следующие действия:

· Для задания ограничения в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· В появившемся дополнительном окне выбрать ячейку $D$2, которая должна отобразиться в поле с именем Ссылка на ячейку;

· В качестве знака ограничения из выпадающего списка выбрать нестрогое равенство “<= ”;

· В качестве значения правой части ограничения в появившемся дополнительном окне выбрать ячейку $C$2, которая должна отобразиться в поле с именем Ссылка на ячейку;

· Для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить.

6. Аналогичным образом добавить остальные 9 ограничений (7.5.7), используя в качестве исходных ячеек $D$3: $D$11 и $C$3: $C$11.

7. Задать ограничение на целочисленные значения переменных. С этой целью выполнить следующие действия:

· В исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· В появившемся дополнительном окне выбрать диапазон ячеек $D$2: $D$11, который должен отобразиться в поле с именем Ссылка на ячейку;

· В качестве знака ограничения из выпадающего списка выбрать строку “цел”;

· В качестве значения правой части ограничения в поле с именем Ограничение: оставить без изменения вставленное программой значение “целочисленные”;

· Для добавления ограничения в дополнительном окне нажать кнопку с надписью Добавить.

8. В окне дополнительных параметров поиска решения выбрать отметки Линейная модель и Неотрицательные значения.

Рис. 2.3.2 Ограничения значений переменных и параметры мастера поиска решения для задачи о максимальном потоке в сети

Общий вид диалогового окна спецификации параметров мастера поиска решения показан на рис. 2.3.2

После задания ограничений и целевой функции можно приступить к поиску численного решения, для чего следует нажать кнопку Выполнить. После выполнения расчетов программой MS Excel будет получено количественное решение, которое имеет следующий вид (рис. 2.3.2).

Результатом решения задачи о максимальном потоке в сети являются найденные оптимальные значения переменных

остальные переменные равны 0. Найденному оптимальному решению соответствует значение целевой функции:

Анализ найденного решения показывает, что максимальный поток в сети (см.рис. 2.3.2), проходящий из вершины 1 в вершину 6, протекает последующим дугам: по дуге (1, 2) в количестве 2 m/час, по дуге (1,3)в количестве 4 m/час, по дуге (2,4)в количестве 2 m/час, по дуге (3,4) в количестве 3 m/час , по дуге (3,5) в количестве 1 m/час, по дуге (4,5)в количестве 2 m/час, по дуге (4,6) в количестве 3 m/час, по дуге (5,6)в количестве 3 m/час.

Тем самым найден оптимальный план транспортировки продукта от пункта его добычи до пункта его переработки (рис. 2.3.2). При этом общая величина потока транспортируемого продукта для рассматриваемой сети будет максимальна и равна 6 m/час.

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

Например, множество дуг {(2,4),(2,5), (3,4) и (3, 5)} удовлетворяет определению разреза, поскольку их удаление разделяет исходный граф на две несвязные части. Имеет место, следующее свойство, которому должен удовлетворять максимальный поток в сети: максимальный поток в сети равен потоку, протекающему по дугам любого разреза этой сети, отделяющего исток от стока. При этом поток по дугам, проходящий в направлении от истока к стоку, учитывается со знаком “+”, а поток по дугам, проходящий в направлении от стока к истоку, учитывается со знаком “-”.

Для проверки этого условия применительно к найденному решению задачи о максимальном потоке в сети (см. рис. 2.3.3) рассмотрим некоторый разрез, например, {(2,4),(2,5), (3,4) и (3, 5)}. Нетрудно убедиться в том, что величина потока, проходящего через дуги этого разреза, равна 6, что в точности равно величине найденного максимального потока. Для дополнительной проверки получаемых с помощью программы MS Excel решений данной типовой задачи оптимизации на графах можно воспользоваться специальным алгоритмом пометок Форда - Фалкерсона, который рассматривается в разделе 7.5.3.

2.4 Создание пользовательской функции для вычисления двумерной экспоненциальной функции

Простейшей задачей, которая может быть решена с помощью языка программирования VBA, является создание дополнительных функций пользователя. Хотя программа MS Excel содержит большое количество встроенных функций, в целом ряде случаев в MS Excel либо отсутствует, либо требует для своего вычисления ручного заполнения ячеек рабочего листа при подготовке исходных данных.

Неоспоримым достоинством программы MS Excel и среды VBA является тот факт, что разработанные функции пользователя на языке VBA можно вызывать с помощью мастера функций так же, как и обычные встроенные функции программы MS Excel

В качестве примера создания дополнительной функции рассмотрим двумерную экспоненциальную функцию, которая отсутствует в числе встроенных функции программы MS Excel.

Напомним, что в разделе 2.5 было рассмотрено решение с помощью программы MS Excel задачи нелинейной оптимизации с двумерной экспоненциальной целевой функцией, которая задается выражением (2.5)

При построении графика данной функции с целью визуального анализа найденного решения возникает техническая трудность, связанная с трудоемкостью записи формулы вычисления значений этой функции для некоторого диапазона значений независимых переменных . Действительно при вычислении отдельного значения двумерной экспоненциальной целевой функции для фиксированной пары значений переменных () согласно формуле (2.5) необходимо выполнить последовательное суммирование для возрастающих значений параметра а, начиная 0,1 и заканчивая значением 1 с интервалом изменения данного параметра, равным 0,1. Эта задача может быть эффективно решена с помощью специальной программы на VBA.

Для решения данной задачи с помощью программы MS Excel создадим новую книгу с именем Программирование задач и изменим имя ее первого листа на Экспоненциальная функция.

Для написания текста пользовательской функции, в данном случае ---для написания текста программы вычисления двумерной экспоненциальной целевой функции, следует выполнить следующие действия:

1. Выполнить операцию главного меню: Сервис/Макрос/Редактор Visual Basic или нажать клавиши <Alt> + <F11>, в результате чего откроется дополнительное окно редактора VB.

Примечание

Следует заметить, что при первоначальном обращении к редактору VB можно не обнаружить соответствующего пункта в главном меню Сервис. Это означает, что компонент программирования на VB в программе MS Office Excel 2003 не установлен. Хотя компонент Microsoft Visual Basic для приложений, как правило, устанавливается по умолчанию, в отдельных случаях этого может не произойти. Поэтому для продолжения работы необходимо убедиться, что данный компонент установлен. С целью можно воспользоваться инструментом Установка и удаление программ ОС Windows и проверить состав установленных компонентов пакета MS Office System2003. В случае отсутствия компонента MS Excel VB для приложений следует его установить, для чего потребуется установочный диск пакета MS Office System 2003.

2. Первоначально рабочая книга программы MS Excel не содержит никаких модулей с текстами программ VBA. Поэтому необходимо создать новый модуль, для чего необходимо выполнить в редакторе Visual Basic операцию главного меню: Insert (Вставка) / Module (Модуль). В результате выполнения этой операции в редакторе Visual Basic появиться рабочее окно с пустым содержимым созданного модуля, которому по умолчанию будет присвоено имя Module 1.

9. В созданный модуль введем следующий текст, программы вычисления двумерной экспоненциальной функции (листинг 2.4..1).

Листинг 2.4.1 Программа вычисления двумерной экспоненциальной функции

Function ExpFunc(x1,x2)

S = 0

For I =0.1 To 1 Step 0.1

S = S + ((Exp(-I*x1)-Exp(-I*x2))-(Exp(-I)-Exp(-10*I)))^2

Next I

ExpFunc2 = S' возвращаемое функцией значение

End Function

Хотя данный текст программы можно непосредственно ввести в окне программного кода редактора, для задания новых функции или процедур модуля целесообразно использовать специальное окно добавления процедуры. Это окно можно вызвать посредством операции главного меню: Insert (Вставка) / Procedure (Процедура), после чего ввести имя функции и ее область видимости (рис. 3.1.1). После нажатия кнопки ОК будет создан текст с объявлением данной функции в выбранном модуле. В этом случае пользователю остается лишь написать текст ее реализации.

Данная программа задает пользовательскую функцию ExpFunc2, которая имеет два формальных параметра: х1 и х2. Текст программы пользовательской функции начинается с помощью стандартного оператора объявления функции:

Function, после которого указывается имя функции ExpFunc2 и ее формальные параметры в скобках. Ввиду простоты данной функции типы переменных не объявляются. То есть используются по умолчанию тип Variant.

Собственно вычисления значения двумерной экспоненциальной функции для двух значений независимых переменных х1 и х2 реализуется с помощью цикла For-To-Step, который выполняется последовательно с помощью переменной I. Для вычисления обычной экспоненциальной функции применяется встроенная функция Exp с единственным аргументом. Оператор VBA Next указывает на конец этого цикла, а оператор ExpFunc2=S задает возвращаемое данной функцией значение. Наконец, последний оператор End Function. Служит для указания конца текста функции.

После записи текста программы в редакторе Visual Basic пользовательская функция с именем ExpFunc2 становиться доступной для использования в качестве формулы в ячейках рабочего листа программы MS Excel. Никаких дополнительных действий по компиляции данной программы не требуется. Если программа имеет значительный размер или при наличии в ней ошибок, может оказаться необходимой ее предварительная отладка.

Если текст данной программы не содержит ошибок, то соответствующая функция ExpFunc2 может быть непосредственно вызвана из ячеек рабочего листа данной книги. При этом особенности вызова данной формулы из ячеек полностью аналогичны встроенным формулам программы MS Excel, которые были рассмотрены в разделе 2.3.3.

2.5 Построение графика функции двух переменных

Общая последовательность выполнения действий в программе MS Excel, необходимых для построения графика функции двух переменных, была описана в разд. 2.4.2. В данном разделе рассматривается конкретизация этих действий при построении графика поверхности двумерной экспоненциальной функции.

Напомним, что для построения графика поверхности, которая представляет двумерную экспоненциальную функцию (3.1),предварительно необходимо определить диапазон значений независимых переменных и соответствующее множество значений зависимой (функциональной) переменной. После этого также следует воспользоваться мастером построения диаграмм программы MS Excel для изображения графика заданной функциональной зависимости.

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

Для построения графика двумерной экспоненциальной функции двух переменных следует выбрать интервал их изменения, например



(0,2) и х2(0,15) и выполнить следующие практические действия:

В ячейку А1 рабочего листа с именем Экспоненциальная функция книги Программирование задач введем текст Значение переменных Х1 и Х2:.

С помощью операции автозаполнения зададим значение первой переменной в ячейках В1:L1,а значение второй переменной --в ячейках А1:А17.Заметим, что для построения графика данной функции с учетом результатов решения соответствующей задачи нелинейной оптимизации целесообразно рассмотреть последовательный диапазон значений первой переменной от 0 до 2 с интервалом их изменения, равным 0,2 и диапазон значений второй переменной от 0 до 15 с интервалом их изменения, равным 1.

Далее в ячейку В2 введем формулу: =ExpFunc2(B$1;$A2), которую с помощью автозаполнения скопируем в ячейки С2:L2. При задании данной формулы необходимо выбрать функцию ExpFunc2 в группе Определенные пользователем мастера задания функций, после чего указать ячейки, содержащие значения независимых переменных.

Предварительно выделив диапазон ячеек В2:L2, также с помощью автозаполнения скопируем соответствующие данные в ячейки В3:L17. Результат выполнения данной последовательности операции по подготовке исходных данных будет иметь следующий вид (рис.2.4)

Для построения графика функции двух переменных также следует воспользоваться мастером диаграмм, который может быть вызван с помощью кнопки стандартной панели инструментов (см.табл.2.1) или операции главного меню : Вставка / Диаграмма. При этом последовательность выполнения действии в программе MS Excel , необходимых для построения трехмерного графика функции двух переменных , аналогична описанной в разделе 2.4.2 и поэтому здесь не приводиться. В результате выполнения этих действий с использованием мастера диаграмм будет получен график двумерной экспоненциальной функции (рис.2.5).

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

2.5.1 Программа изображения структуры неориентированного графа

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

Основное неудобство при изображении графа связано с тем обстоятельством, что пользователю предварительно необходимо задать некоторые координаты на плоскости каждой из вершин исходного графа. Дело в том, что программа MS Excel не в состоянии самостоятельно определить размещение вершин графа на плоскости. Идея расположить все вершины графа в вершинах соответствующего правильного многоугольника также не подходит для общего случая, поскольку этот способ является менее наглядным для большинства практических задач.

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

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

В ячейки A1,I1, A3:A9, B2:J2 данного рабочего листа ввести соответствующий текст, конкретное содержание которого не влияет на результат решаемой задачи.

В ячейки B3:H9 следует ввести значения матрицы весов ребер исходного неориентированного графа, структуру которого следует изобразить на плоскости. В качестве такого графа используется граф, который изображен на рис.7.1 и использовался в качестве исходного для решения рассмотренных задач оптимизации на графах.

В ячейки I3:J9 следует ввести значения координат вершин изображаемого графа. При этом в ячейки I3:J9 записываются горизонтальные координаты вершин, а в ячейки I3:J9 -вертикальные координаты вершин. Следует отметить, что координаты вершин отсчитываются от левого верхнего угла данного рабочего листа. Для выполнения этих действий желательно предварительно сделать набросок графа на листе бумаги.