Тема лекции : «Теория графов и ее экономические приложения»
Разделы лекции:
1. Элементы теории графов.
2. Природа потоков в сетях и принцип их сохранения.
3. Теорема о максимальном потоке и минимальном разрезе.
РАЗДЕЛ 1. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ.
ЧТО ТАКОЕ ТЕОРИЯ ГРАФОВ?
Большинство возникающих в экономике задач удобно представлять для восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как)? Наглядность и логическая обоснованность методов сетевого анализа позволяют выбрать довольно естественный подход к решению разнообразных экономических задач. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов – области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная известным математиком Леонардом Эйлером в 1736 году. Через реку Прегель, на которой стоял город Кенигсберг (в настоящее время – город Калининград), семь мостов (рисунок 1) связывали два острова друг с другом. Жителей Кенигсберга интересовал вопрос: можно ли в их городе совершить прогулку по замкнутому маршруту, проходя по каждому из семи мостов один и только один раз? Леонард Эйлер математически сформулировал и решил эту задачу.
В девятнадцатом столетии в Англии возникла другая трудноразрешимая математическая задача, имеющая прямое отношение к теории графов. Это задача о четырех красках: достаточно ли четырех цветов для такой раскраски карты, нанесенной на плоскость или сферу, чтобы на ней не оказалось двух смежных областей одинакового цвета? Эта задача впоследствии была решена.
На основе исследования движения тока в электрических цепях Д. К. Максвелл и Г. Р. Кирхгоф сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В двадцатом столетии теория графов прошла определенные стадии формирования и после 1930 года была признана самостоятельной дисциплиной. В 40-х годах XX века в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50-60-х годах XX века проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов.
МЕТОДЫ И МОДЕЛИ ТЕОРИИ ГРАФОВ И СЕТЕВОГО МОДЕЛИРОВАНИЯ. ОБЗОР ПРИМЕНЕНИЯ СЕТЕВЫХ МОДЕЛЕЙ.
Математический аппарат сетевых моделей базируется на теории графов. Используя простую терминологию, можно сказать, что граф характеризует отношения между множествами объектов, и теория графов направлена на исследование некоторых из многих возможных в заданном представлении свойств этих объектов. В рамках теории исследования операций рассматривается большое количество практических задач, которые можно сформулировать и решить как сетевые модели. Приведем несколько конкретных примеров.
1. Проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода.
2. Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог.
3. Определение максимальной пропускной способности трубопровода для транспортировки сырой нефти от буровых скважин до нефтеперерабатывающих заводов.
4. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.
5. Составление временного графика строительных и т.п. работ (определение дат начала и завершения отдельных этапов работ).
ПРИМЕР 1. Значительное место в сетевом моделировании занимают задачи, связанные с планированием и составлением расписания выполнения работ или операций. Например, на рисунке 2 изображена сетевая модель комплекса работ по переводу торгового предприятия на самообслуживание. Обычно время и ресурсы выполнения каждой работы задаются вначале. Кроме того, прежде чем работа может начаться, все предшествующие ей работы должны быть завершены. Например, доставка оборудования (событие 15) является предшествующей работой (или опорной) для работы по монтажу оборудования. Следовательно, при наличии полного перечня работ комплекса сеть можно построить, если точно установлены предшествующие операции для каждой работы. В таких случаях сетевая модель представляет собой отражение логической взаимосвязи всех входящих элементарных работ в комплекс от начала до конца. Сетевые графики представляют собой орграфы без контуров, дугам и вершинам которых приписаны числовые значения. Наибольшее распространение получил способ задания сетевых графиков в терминах дуги – операции, а вершины – события.
Исходное (1) — это такое событие, с которого начинается выполнение всего комплекса операций, а завершающее событие (32) соответствует достижению конечной цели. События обозначаются кружками, квадратами, ромбами или другими геометрическими фигурами.
ПРИМЕР 2. Одним из важных преимуществ сетевого моделирования является возможность построения сетевых моделей, наглядно отображающих процессы, например, коммерческой деятельности. Так, например, на рисунке 3 представлен ориентированный граф движения денежных потоков на счетах бухгалтерского учета, где в кружках указаны номера счетов бухгалтерского учета, а стрелками — проводки.
ПРИМЕР 3. ПЛАНИРОВАНИЕ РАБОТ КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ.
В коммерческой деятельности с целью исключения ущербов или неприятных неожиданностей необходимо составлять планы будущих работ, развернутых во времени. Любое множество работ связано отношениями предшествования. Причем каждая работа может быть начата, если все предшествующие ей работы будут завершены. В таких случаях сетевые методы позволяют решать как прямые, так и обратные задачи планирования работ коммерческой деятельности. В результате решения прямых задач определяется оптимальный план комплекса работ при заданной схеме организации работ. Решение обратной задачи связано с поиском оптимального плана схемы организации работ, обеспечивающего максимальную эффективность.
Множество возникающих задач коммерческой деятельности можно свести к одной из трех наиболее типичных постановок задач оптимизации.
1. Какое максимальное количество средств и каким образом может быть высвобождено при заданной организации работ при условии, что общее время выполнения всего комплекса работ не возросло?
2. Как наилучшим образом использовать выделенные ограниченные ресурсы, чтобы время выполнения всего комплекса работ не превысило заданной величины?
3. Как распределить выделенные ресурсы между работами, чтобы время выполнения всего комплекса работ было бы минимальным?
При этом в исходных данных задач параметры работ могут быть заданы совершенно точно (детерминированный случай) или с некоторой степенью определенности, вероятности (стохастический случай). Решение задач этого класса также может быть решено методами сетевого планирования.
Задачи, вытекающие из перечисленных примеров, можно сформулировать и решать как задачи линейного программирования. Однако специфическая структура этих задач позволяет разработать специальные сетевые алгоритмы, более эффективные, чем стандартный симплекс-метод. Постановку и решение подобных задач можно получить с помощью методов сетевого моделирования. Решение приведенных задач (как и многих других подобных задач) требует применения различных сетевых оптимизационных алгоритмов.
Перечислим наиболее известные сетевые оптимизационные алгоритмы.
1. Алгоритм нахождения минимального остовного дерева.
2. Алгоритм нахождения кратчайшего пути.
3. Алгоритм определения максимального потока.
4. Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью.
5. Алгоритм нахождения критического пути.
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.
Граф задается двумя множествами: непустым множеством X и множеством U, содержащим пары элементов из множества X. При этом элементы множества U могут повторяться, а также могут повторяться элементы в парах. Граф, заданный на множествах (X,U), обозначается G=(X,U). Если элементы в парах множества U не упорядочены, то граф называется неориентированным, в противном случае — ориентированным, или орграфом. Элементы множества X называют вершинами графа, а элементы множества U — ребрами для неориентированного графа и дугами для орграфа.
На плоскости граф задается в виде фигуры, состоящей из точек (вершин) и линий, соединяющих некоторые из них (ребер или дуг). Если на каждом ребре задается направление (т.е. каждая пара вершин, соединенная ребром, упорядочена), то граф называется ориентированным, в противном случае – неориентированным.
Неориентированный граф, изображенный на рисунке 4, имеет 7 вершин и 7 ребер. Для данного неориентированного графа множество вершин X и ребер U можно записать так: X={x1, x2, x3, x4, x5, x6, x7}; U={(x1, x1), (x1, x2), (x2, x3), (x3, x4), (x3, x5), (x4, x5), (x5, x6)}.
Ориентированный граф, изображенный на рисунке 5, имеет 4 вершины и 5 дуг. Множество вершин X и множество дуг U для данного графа (см.: рисунок 5) можно записать следующим образом: X={x1, x2, x3, x4}; U={(x1, x2), (x1, x3), (x3, x2), (x3, x3), (x3, x4)} (или U={U1, U2, U3, U4, U5}, где U1≡(x1,x2), U2≡(x1,x3), U3≡(x3,x2), U4≡(x3,x3), U5≡(x3,x4)).
Вершины графа называются смежными, или соседними, если существует ребро, их соединяющее.
Например, на рисунке 4 смежными являются следующие вершины: x1 и x2; x2 и x3; x3 и x4; x3 и x5; x4 и x5; x5 и х6; вершины x3 и x6 — несмежные.
Маршрутом, или путем, соединяющим вершины A и B графа, называется такая последовательность его ребер, в которой каждые два соседних ребра имеют общую концевую точку, причем первое ребро выходит из вершины A, а последнее входит в вершину B .
В этом случае вершины A и B называются связанными.
Маршрут называется цепью, если каждое ребро графа встречается в нем не более одного раза (вершины в цепи могут повторяться и несколько раз).
Граф называется связным, если любая пара его вершин связана .
Граф, представленный на рисунке 4, связный, а на рисунке 5 – несвязный, поскольку не существует цепи, соединяющей вершину x7 с остальными.
Число ребер в маршруте определяет его длину.
Например, на рисунке 6 изображен маршрут, длина которого равна 4.
Простой цепью называется цепь, в которой все вершины различны.
Простая цепь, начальная и конечная вершина которой совпадают, называется простым циклом.
Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно.
Вершина A на рисунке 11 четна — в ней сходятся 4 ребра, а вершина B нечетна — в ней сходятся 5 ребер.
Ребро графа, начало и конец которого совпадают, называется петлей.
Например, на рисунке 4 изображена петля (x1, x1).
Число ребер, сходящихся в вершине графа, называется степенью (порядком) этой вершины.
Степень вершины х обозначим через d(x).
Например, на рисунке 4: d(x2)= 2; d(х3) = 3; d(x4)= 2; d(х5)=3; d(x6)=1.
Вершина x, степень которой равна нулю: d(х) =0, называется изолированной вершиной (на рисунке 4 имеем: d(x7)=0).
Вершина x, степень которой равна единице: d(x) = 1, называется висячей, или тупиковой (на рисунке 4 имеем: d(x6)=1).
Граф называется регулярным степени q, если все его вершины имеют степень q.
Регулярный граф, все вершины которого имеют степень 1, называется паросочетанием.
Граф называется двухдольным, если множество его вершин X может быть разделено на два непересекающихся подмножества Y и Z таким образом, что каждое ребро графа соединяет вершины из двух разных подмножеств Y и Z.
Расстоянием между вершинами A и B связного графа называется длина самой короткой цепи, соединяющей данные вершины.
Диаметром графа называется максимальное расстояние между его вершинами.
Граф называется конечным, если множество его ребер конечно. Примером бесконечного графа может служить прямоугольная сетка, заданная на всей плоскости.
ТЕОРЕМА (Эйлер). В любом конечном связном графе, все вершины которого четны, существует цикл, в котором каждое ребро графа участвует ровно один раз.
Такой цикл называют эйлеровым циклом, а граф, все вершины которого четны (и, значит, существует эйлеров цикл), — эйлеровым графом.
Важный класс графов составляют так называемые деревья.
Деревом называется связный граф, который не имеет циклов.
Число B вершин дерева и число P его ребер различаются на единицу: B = P+1.
Таким образом, дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями.
Например, на рисунке 13 изображено дерево, имеющее 12 вершин и 11 ребер, где вершина x1 является корнем дерева.
Лесом называется граф без циклов, представляющий собой совокупность деревьев .
Граф называется взвешенным, если каждому его ребру поставлено в соответствие некоторое число, называемое весом ребра, например расстояние между городами, стоимость или время проезда между ними.
Подграфом графа G называется граф G1 с множеством вершин X1 и множеством ребер U1 такой, что Х1ÎX, U1ÎU. Для графа, изображенного на рисунке 5, подграфом может быть граф G1=(X1, U1), где X1=(x1,x2, х3, x4, х5), а U1={(x1, x2), (x1, x3), (x3, x4), (x3, x5)}.
Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа.
Например, граф, изображенный на рисунке 4, имеет две компоненты связности.
Вершина графа, удаление которой увеличивает число компонент связности, называется точкой сочленения. Под удалением вершины понимается удаление самой вершины и всех инцидентных ей ребер.
Точкой сочленения является, например, вершина x3 (см.: рисунок 4), удаление которой приводит к появлению третьей компоненты связности.
Граф называется полным, если каждая вершина этого графа соединена ребром с любой другой его вершиной.
Гамильтоновой цепью называется простая цепь, содержащая все вершины графа ровно один раз.
Например, для графа (рисунок 15) цепь, проходящая последовательно через вершины: (6, 1, 5, 4, 3, 2, 8, 9, 10, 11, 12, 13, 14, 15, 20, 19,18, 17, 16, 7), является гамильтоновой.
Гамильтоновым циклом называется гамильтонова цепь, начало и конец которой совпадают.
Например, если в конец предыдущей цепи добавить ребро, соединяющее вершину 7 с вершиной 6, получим гамильтонов цикл.
Достаточные условия гамильтоновости неориентированного графа содержатся в следующей теореме.
ТЕОРЕМА (Дирак). Если в неориентированном графе G=(X,U) с n вершинами (n≥3) степень каждой вершины x не меньше чем n/2 (deg x ≥n/2, "xÎX), то граф G является гамильтоновым.
Термин «гамильтонов» связан с именем ирландского математика У. Гамильтона, который в 1859 году предложил игру «Кругосветное путешествие». Каждой из двенадцати вершин додекаэдра (см.: рисунок 13) соответствует один из городов мира. Необходимо, переезжая из города в город по ребрам додекаэдра, посетить каждый город только один раз и вернуться назад. Эта задача сводится к поиску простого цикла, проходящего через каждую вершину графа.
Задачи, касающиеся эйлеровых и гамильтоновых цепей и циклов, часто встречаются на практике. Например, стоимость выполнения комплекса коммерческих операций, работ существенно зависит от последовательности, в которой они выполняются.
Например, задачу коммивояжера можно представить как в виде ориентированного (контур), так и неориентированного (цикл) графа.
Предложенный вариант решения задачи коммивояжера представляет собой кольцевой маршрут, где каждый город посещается только один раз, начиная с любого населенного пункта.
ЗАМЕЧАНИЕ. Для ориентированных графов используется термин контур (вместо термина цикл для неориентированного графа), термин дуга (вместо термина ребро для неориентированного графа). Последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей, называется путем. Длина пути определяется количеством в нем дуг. Путь называется простым, если в нем каждая дуга не встречается дважды, в противном случае он является составным. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Путь, который начинается и заканчивается в одной и той же вершине, называется контуром.
Для ориентированного графа вместо степени вершины вводится понятие полустепеней исхода и захода. Если вершина является началом дуги, то дуга называется исходящей из вершины, если концом, то — заходящей. Полустепенью исхода вершины (d-(x)) называется число дуг, исходящих из этой вершины, полустепенью захода (d+(x)) называется число дуг, заходящих в вершину.
Например, для графа, изображенного на рисунке 5, можно записать:
(d-(x2))=0, d-(x1)=2, (d+(x2))=2, (d+(x1))=0.
Известно несколько типов матриц, позволяющих задавать граф: матрица смежности, матрица инцидентности, матрица пропускных способностей.
ЧТО ТАКОЕ МАТРИЦА СМЕЖНОСТИ?
Матрица смежности графа с конечным числом вершин n представляет собой квадратную матрицу A=||aij|| порядка n, строки и столбцы которой соответствуют вершинам графа; и каждый элемент аij которой определяется по следующим формулам.
Для неориентированного графа значение элемента aij=k, где k -число ребер, соединяющих вершины xi и xj. В частности, если вершины xi и xj не соединены ни одним ребром, то aij=0.
Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.
Матрица смежности A неориентированного графа симметрична. Следовательно, все собственные значения матрицы A являются действительными числами, и существует базис из собственных векторов.
Множество собственных значений матрицы смежности A неориентированного графа называется спектром графа и является основным предметом изучения спектральной теории графов.
Матрицы смежности для неориентированных графов являются основными структурами данных, которые используются для представления графов в компьютерных программах.
Для ориентированного графа элемент aij матрицы смежности A равен числу дуг, направленных от вершины i к вершине j .
Для неориентированного графа, представленного на рисунке 4, матрица смежности симметрична, имеет порядок 7 и записывается в следующем виде.
Слева и сверху проставлены номера вершин.
Для ориентированного графа, изображенного на рисунке 17, матрица смежности квадратная порядка 6, и записывается в следующем виде.
Матрицу смежности чаще применяют для задания неориентированного графа в компьютерных программах. Для задания ориентированного графа лучше использовать матрицу инцидентности.
ЧТО ТАКОЕ МАТРИЦА ИНЦИДЕНТНОСТИ?
Матрица инцидентности графа – одна из форм представления графа, в которой указываются связи между инцидентными элементами графа: вершинами и ребрами (дугами) графа. Строки матрицы инцидентности B соответствуют вершинам, а столбцы – ребрам (дугам).
Матрицей инцидентности B ориентированного графа с n вершинами и m дугами называется матрица B=||bij|| размера (n x m) с n строками и m столбцами, элементы которой bij определяются по следующим формулам.
Столбец, соответствующий дуге (i,j) графа, заполняется следующим образом: в строке, соответствующей вершине i, ставится (- 1), в строке, соответствующей вершине j, ставится 1, в остальных ячейках ставится 0.
То есть bij= - 1, если вершина является началом дуги (i,j);
bij = 1, если вершина является концом дуги (i, j);
bij=0, если вершина и дуга не инцидентны.
Для неориентированного графа элемент bij=1, если вершина и ребро инцидентны, и bij=0 в противном случае.
Ненулевое значение в соответствующей ячейке матрицы инцидентности указывает связь между вершиной и ребром (дугой) графа – их инцидентность.
В каждом столбце матрицы инцидентности B ориентированного графа обязательно должны стоять (-1) и 1 (остальные элементы равны 0, если граф имеет более 2-х вершин).
В каждом столбце матрицы инцидентности B неориентированного графа обязательно должны стоять две единицы (остальные элементы равны 0, если граф имеет более 2-х вершин).
Направленный граф – это ориентированный граф, в котором любые две вершины соединены не более чем одной дугой.
Взвешенный ориентированный граф без петель, в котором выделено k вершин, называемых полюсами, называется k-полюсной цепью.
Среди сетей особо выделяется двухполюсная транспортная сеть (рисунок 17) S = (N, U) с множеством вершин N и множеством дуг U, для которых выполняется следующее условие:
1) существует только одна вершина sÎN сети S, в которую не заходит ни одна дуга. Эта вершина называется входом, или истоком (источник), сети;
2) существует только одна вершина tÎN сети S, из которой не выходит ни одной дуги сети. Эта вершина называется выходом, или стоком, сети;
3) каждой дуге uÎU сети S поставлено в соответствие неотрицательное число c(u), называемое пропускной способностью дуги.
Сетью будем называть ориентированный конечный связный граф без циклов и петель, имеющий начальную вершину (источник) и конечную вершину (сток).
Примерами вершин сети могут быть пересечения автострад, электростанции, телефонные узлы, железнодорожные узлы, аэропорты, водохранилища, товарные склады. Примерами дуг сети могут быть дороги, линии электропередачи, телефонные линии, авиалинии, водные магистрали, нефте- и газопроводы и т.д.
РАЗДЕЛ 2. ПРИРОДА ПОТОКОВ В СЕТЯХ И ПРИНЦИП ИХ СОХРАНЕНИЯ.
Сходство сетевых представлений наблюдается в природе, технике и различных сферах деятельности человека. Так, например, с высоты птичьего полета или самолета можно наблюдать сетевую модель формирования реки, например Волги, от ее истоков маленькие ручейки и реки, соединяясь во взаимосвязанные артерии, объединяются в одно большое русло, по которому потоки воды устремляются в Каспийское море. Такие же аналогии представляют собой сети железных дорог, по которым транспортные потоки направляются из пунктов отправления в пункты назначения, осуществляя перевозку потоков грузов и пассажиров. Совокупность линий электропередач также представляют собой энергетическую сеть, по которой потоки электроэнергии от электростанций по проводам поступают к потребителям. Автомобильные дороги как в масштабе города, района, области, так и в более крупных масштабах страны или, например, континента, представляют собой сети, по которым движутся потоки автомобилей. Нефте- и газопроводы в совокупности представляют собой сети трубопроводов, по которым потоки нефти или газа поступают от источников к потребителям. Водопроводные сети обеспечивают движение потоков воды по трубопроводам от источников к потребителям. Аналогичные сети представляют собой маршруты движения кораблей и самолетов, обеспечивающие перемещение потоков пассажиров и грузов по планете. Такие же аналогии представляют собой телефонные, радио- и телекоммуникационные сети, по которым циркулируют информационные потоки, например компьютерные сети связи различного назначения. Особый интерес представляют сети, образованные движением товарных и финансовых потоков, изучение которых может пояснить очень многие явления нашей жизни.
Перечисленные сетевые аналогии потоковых процессов имеют динамический характер, связанный с перемещениями различных по своей природе масс в пространстве: электроэнергии, нефти, газа, воды, воздуха, железнодорожного, воздушного, автомобильного транспорта, товаров, финансов, пешеходов, информации и т.п. Причем существование этих потоков необходимо для обеспечения и поддержания жизнедеятельности человека. Сетевое представление взаимодействия и циркуляции потоков необходимо, чтобы оценить и вычислить разные характеристики, описывающие условия существования и поведения потоков в таких средах. Множество возникающих в таких случаях задач может быть решено с помощью теории потоков в сетях. В этой теории в качестве основы рассматриваются движения в сетях потоков любой природы от источника s к стоку t.
ОПРЕДЕЛЕНИЕ. Потоком в сети S=(N,U) от входа sÎN к выходу tÎN называется неотрицательная функция φ=φ(i,j), определенная на множестве дуг (i,j)ÎU сети S, со следующими свойствами:
1) ВЕЛИЧИНА ПОТОКА ПО КАЖДОЙ ДУГЕ НЕ ДОЛЖНА ПРЕВОСХОДИТЬ ЕЕ ПРОПУСКНОЙ СПОСОБНОСТИ: 0≤φ(i,j)≤c(i,j); (i,j)ÎU;
2) ВЕЛИЧИНА ПОТОКА, ВХОДЯЩЕГО В КАЖДУЮ ВЕРШИНУ СЕТИ, ЗА ИСКЛЮЧЕНИЕМ ВХОДА И ВЫХОДА, РАВНА ВЕЛИЧИНЕ ПОТОКА, ВЫХОДЯЩЕГО ИЗ ЭТОЙ ВЕРШИНЫ:
∑ φ-(i,j) – ∑ φ+(j,i) = 0, i≠s, j≠t,
jÎNi jÎNi
где Ni — множество вершин, инцидентных дугам, направленным от вершины i (исходящие из вершины i дуги);
Ni - множество вершин, инцидентных дугам, направленным к вершине i, (входящие в вершину i дуги).
Из определения потока следует, что величина потока не исчезает и не накапливается в вершинах сети.
Следовательно, количество потока из входа s равно количеству потока, заходящему в выход t. ЭТО ЗНАЧЕНИЕ НАЗЫВАЕТСЯ ВЕЛИЧИНОЙ ПОТОКА V.
Таким образом, поток в сети сохраняется, а величина потока V равняется сумме значений потоков, выходящих из вершины s: ∑φ-(s,j), или входящих в вершину t: ∑φ+(j,t). То есть
V = ∑ φ-(s,j) = ∑ φ+(j,t),
jÎNs jÎNt
где Ns – множество вершин, инцидентных дугам, направленным от источника s (исходящие из источника s дуги);
Nt – множество вершин, инцидентных дугам, направленным к выходу t, (входящие в сток t дуги).
На рисунке 18 изображена сеть автомобильных потоков, которая представляет ориентированную сеть S = (N, U) имеющую множество вершин N = {1, 2, 3, 4} и множество дуг U ={(1, 2); (2,3); (2, 4); (1,3); (3,4)}.
Количественные характеристики дуг сети, а также взаимосвязь между ее вершинами могут быть представлены с помощью матрицы расстояний L=||lij|| или матрицы стоимостей C=||cij||.
Для ориентированной сети, представленной на рисунке 18, матрица смежности имеет следующий вид.
Матрица инцидентности ориентированной сети, изображенной на рисунке 18, имеет следующий вид.
На рисунке 18 стрелками показано направление одностороннего разрешенного движения потоков автомобилей. От одного перекрестка i до другого перекрестка j пропускная способность c(i, j) по дуге (i, j) по каждой улице ограничена и определяется максимально допустимой скоростью движения, например, 60 км/ч. В связи с этим мощность автомобильного потока φ(i,j) не может превысить допустимую – пропускную способность c(i,j). Таким образом, должно выполняться первое свойство потока, условие существования статического или устойчивого потока для каждой улицы:
0≤φ(i,j)≤c(i,j); (i,j)ÎU.
Рассматривая взаимодействие ограничений по каждой улице и в совокупности по всем перекресткам (вершинам сети), условие сохранения потока в этой сети запишем следующим образом:
∑ φ-(i,j) – ∑ φ+(j,i) =0; i≠s; j≠t.
jÎNi jÎNi
Для источника сети при i=s нет входящих потоков, следовательно,
V= ∑ φ-(s, j).
jÎNs
Для стока при j=t нет выходящих потоков, следовательно,
V = ∑ φ+(j,t).
jÎNt
ПРИМЕР 4. Рассмотрим пример анализа сети S = (N,U), представленной на рисунке 19. N= {s, 1, 2, 3, 4,..., t}; U = {(s, 1); (s,3); (1,2); (1,3); (2,t); (3,2); (3,4); (4,t)}.
Величина потока в сети.
Пропускная способность указана над каждой дугой, где рядом в скобках указано значение существующего потока. Свойства потока в данном случае выполняются, поскольку указанные величины не превышают пропускных способностей дуг в каждой вершине, отличной от входа и выхода, поток сохраняется. Например, в вершину 2 заходят 4 единицы потока по дугам (1, 2) и (3, 2) и выходят 4 единицы по дуге (2,t). Величина потока в сети составляет V=3+4=7 и сохраняется.
РАЗДЕЛ 3. ТЕОРЕМА О МАКСИМАЛЬНОМ ПОТОКЕ И МИНИМАЛЬНОМ РАЗРЕЗЕ.
Пусть в ориентированной сети S= (N, U) от источника к стоку протекает поток, величина которого равна V. Поскольку пропускная способность каждой дуги c(i, j) является величиной конечной, то максимальная величина допустимого потока всей сети тоже ограничена. Максимальный поток сети определяется на основе одного из основных понятий теории сетей — понятия разреза. Введем понятие разреза.
Множество вершин N сети S=(N,U) можно разбить на два непересекающихся подмножества Np и Np, которые соединяются между собой дугами, образующими МНОЖЕСТВО ДУГ РАЗРЕЗА Up, Причем исток s принадлежит множеству вершин Np: sÎNp, а сток t принадлежит множеству Np: tÎNp. Тогда величина потока из множества Np во множество Np, протекающего по дугам Up, не может быть больше, чем сумма пропускных способностей дуг этого множества, что можно записать таким образом:
Этот барьер для потока, отделяющий множество вершин Np, от множества вершин Np, называется разрезом и обозначается (Np, Np).
Разрез представляет такое множество дуг Up, исключение которых отделяет вход s от выхода t сети, и, следовательно, отделяет множество Np от Np сети S=(N,U) таким образом, что существование потока в таком случае невозможно и тогда величина потока в сети V = 0. Причем начало дуги разреза принадлежит множеству Np, а конец - Np. Таким образом, в разрез входят дуги, соединяющие вершины этих множеств.
Величина максимального потока от источника s к стоку t ограничена сверху величиной разреза C(Np, Np), определяемой суммой пропускных способностей всех входящих в него дуг множества Up. Следовательно, V≤ C(Np, Np).
Минимальным разрезом сети называется разрез, имеющий минимальную величину C(Np,Np).
В соответствии с теоремой о максимальном потоке и минимальном разрезе, сформулированной Фордом и Фалкерсоном, величина максимального потока Vmax от входа s (источника) в выход t (сток) равна величине минимального разреза, отделяющего вход и выход сети.
Следовательно,
Vmax = min C(Np, Np).
UpÎU
Таким образом, разрез определяет множество дуг, при удалении которых из сети полностью прекращается поток от источника к стоку. Пропускная способность разреза равна сумме пропускных способностей «разрезанных» дуг. Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.
Рассматриваемые сети являются сетями с ограниченной пропускной способностью и имеют распространение в реальной жизни. Это послужило поводом к появлению и постановке задач о максимальном потоке разной природы, связанных с определением максимально допустимой величины Vmax при соблюдении условий, записанных в виде системы уравнений и неравенств.
В сформулированной выше задаче для сохранения потока автомобилей (см.: рисунок 18), например, через перекресток (3) необходимо, чтобы поступающие потоки автомобилей к этой вершине (3) φ(1, 3) и φ(2, 3) равнялись величине потока, вытекающего из этой вершины φ(3, 4), что можно записать так:
φ(1,3) + φ(2,3)≤φ(3,4).
Аналогичные уравнения можно записать для остальных вершин сети. Поскольку задача заключается в определении максимально возможного потока в сети, то необходимо последовательно вычислить потоки через все разрезы и выбрать из них минимальный.
Разрез (А, А) на рисунке 18 отделяет источник (1) от стока (4), в данном случае вершину (4) от остальных вершин (1, 2, 3). Величина разреза определяется пропускной способностью входящих в него дуг (2, 4) и (3, 4) и соответственно равна: С(2, 4) + С(3, 4)=2+8=10. Затем можно определить все другие возможные варианты разрезов (В,В) (D,D) и (С,С). Тогда величина максимального потока от источника к стоку равна величине минимального разреза:
Vmax= min {(A,A), (B,B), (C,C), (D,D)}= min {10; 12; 19; 5} = 5.
Из рисунка 18 видно, что после удаления дуг разрезов перестают существовать пути движения потока от входа сети s к выходу t. Разрезы имеют различные пропускные способности. Разрез, имеющий минимальную пропускную способность, называется минимальным разрезом сети.
Приведенный вариант анализа фрагмента сети автомагистрали указывает на возможность применения приведенного принципа сохранения потока в коммерческой деятельности. Это позволит своевременно принимать оптимальные управленческие решения и облегчить оперативное вмешательство по регулированию не только автомобильных, но и финансовых или товарных потоков.
Рассмотренные алгоритм и примеры моделирования позволяют решать аналогичные по своей природе задачи, например по бесперебойному снабжению потоками электричества, бензина, газа, мазута, нефти, воды, продовольственными и непродовольственными товарами населенных пунктов, и таким образом предупредить появление критических ситуаций.
ПРИМЕР 5 (ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ).
Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперерабатывающих заводов. Для перекачки нефти предусмотрены магистральные насосные станции. Каждый сегмент трубопровода имеет свою пропускную способность. Сегменты трубопровода могут быть как однонаправленные (осуществляют перекачку нефти только в одном направлении), так и двунаправленные. В однонаправленных сегментах положительная пропускная способность предполагается в одном направлении и нулевая в другом. На рисунке 20 показана типовая сеть нефтепроводов. Как определить максимальную пропускную способность (т.е. максимальный поток) между нефтяными скважинами и нефтеперерабатывающими заводами? При решении данной задачи исходную сеть необходимо свести к сети с одним источником и одним стоком. Этого можно достигнуть путем введения дополнительных дуг с бесконечной пропускной способностью от источника к скважинам и от нефтеперерабатывающих заводов к стоку (на рисунке 20 эти дуги показаны пунктирными линиями).
Задача о максимальном потоке.
Математическая модель задачи о максимальном потоке выглядит следующим образом.
Рассмотрим двухполюсную сеть S = (N, U) с одним входом (источником) sÎN и одним выходом (стоком) tÎN. Дуги сети (i,j)ÎU и имеют ограниченную пропускную способность cij. Задача о максимальном потоке заключается в поиске таких потоков φ(i,j) по дугам (i,j) сети, что результирующий поток из источника s в сток t является максимальным.
Требуется найти такие значения потоков φ(i,j), при которых
V= ∑ φ+(s,j) = ∑ φ-(j,t) →max,
j j
при ограничениях:
0≤φ(i,j)≤cij,
∑ φ(i,j) – ∑ φ(j,i)=0.
j j
Для решения этой задачи может быть использован метод построения увеличивающих цепей.
ПРИМЕР 6. ЗАДАЧА О ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ.
Задача нахождения потока наименьшей стоимости в сети с ограниченной пропускной способностью обобщает задачу определения максимального потока по следующим направлениям.
1 . Все ребра допускают только одностороннее направление потока, т.е. являются (ориентированными) дугами.
2. Каждой дуге поставлена в соответствие (неотрицательная) стоимость прохождения единицы потока по данной дуге.
3. Дуги могут иметь положительную нижнюю границу пропускной способности.
4. Любой узел сети может выступать как в качестве источника, так и стока.
В рассматриваемой задаче необходимо найти потоки по дугам, минимизирующие общую стоимость прохождения потока по сети; при этом должны удовлетворяться ограничения на пропускные способности дуг и на величины предложений и спроса отдельных (или всех) узлов.
Математическая модель задачи имеет следующий вид.
Пусть дана двухполюсная сеть S=(N,U) с источником s и стоком t. Для каждой дуги (i,j)ÎU заданы пропускная способность сij и стоимость доставки по ней единицы потока rij. Необходимо найти поток от источников в сток заданной величины V, имеющей минимальную стоимость доставки. Очевидно, при этом поток V не должен превышать максимальной величины Vmax.
Требуется минимизировать функцию R:
R =∑∑rij•φij → min
i j
при ограничениях:
ПРИМЕР 7. ТРАНСПОРТНАЯ ЗАДАЧА.
Транспортная задача является одной из первых потоковых задач, которая была сформулирована и решена в 1941 году Ф. Хичкоком, а затем стала применяться в различных задачах перевозки и распределения. В этой задаче рассматриваются предложение грузов (товаров) от m поставщиков в объемах a1, a2, ... , am и спрос от n покупателей в объемах b1, b2,..., bn, затраты на перевозку единицы груза от i-го поставщика к j-му покупателю составляют cij, а объемы перевозимых грузов соответственно составляют хij, которые необходимо определить. Математическая модель имеет следующий вид.
Определить такие объемы перевозок
хij = ?, i=1, …, m, j=1, …, n,
которые при условиях-ограничениях:
обеспечивали бы минимальные затраты на перевозку в соответствии с целевой функцией:
Модель этой задачи может быть представлена в виде сети, если вершинам поставить в соответствие поставщиков и покупателей, а ориентированным дугам — пути для перевозки грузов.
Эта задача является частным случаем задачи поиска потока минимальной стоимости. В то же время частным случаем транспортной задачи являются задачи о назначениях, например задача оптимального распределения по населенным пунктам торговых агентов или маркетологов для изучения рынка. Подробный разбор данной задачи мы провели на лекции 3 «Оптимальные решения в линейных задачах управления производством и цепями поставок».