Дискретно-непрерывная математика (стр. 96 )

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

Упражнение 15. Пусть на рис. 6.12 т = п = 8 и каждый Si соединяется дугой с каждым Тj, все Ai=1, а Вj = 2 и Uij=i,j. Найти максимальный допустимый поток от источника к стоку, имеющий минимальную стоимость.

9.11. Задачи о многопродуктовых потоках

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

Пусть теперь мы имеем К продуктов, и среди вершин сети имеется 2К различных вершин уi, zi (i= 1, 2,..., k) таких, что в сети одновременно существует k потоков, каждый из которых является потоком из yi в zi (для не­которого i) и имеет заданную величину Qi.

Чтобы различать продукты, обозначим через fkij по­ток k-го продукта из вершин vi и вершину vi, положив при этом, что fkji =— fkij. Пусть Сij обозначает пропускную способность (в любом направлении) дуги, соединяющей вершины vi и vj. Возникает задача: приписать каждой дуге (i, j) целое число fkij для каждого продукта k таким образом, чтобы для любого фиксированного k множество потоков по дугам Fk = { fkij } являлось потоком величи­ны Qk из yi и в zi и чтобы для каждой дуги

(i, j) выпол­нялось неравенство

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

Для двухпродуктового случая, т. е. когда k=2, Xy получил теоретический результат, аналогичный теореме о минимальном разрезе — максимальном потоке, и дал вычислительную процедуру для решения постав­ленной задачи. Для иллюстрации этой процедуры рас­смотрим сеть, изображенную на рис.6.13.

Рис. 6.13.

Предположим, что каждая дуга имеет (симметричную) пропускную спо­собность, равную 2, и что Q1= Q2=2.

Прежде всего пренебрежем продуктом 2 и будем искать любой допустимый поток величины Q1=2 товара 1 из z1 в y1, используя описанный ранее однопродуктовый метод. В результате мы можем получить, например, поток, показанный на рис. 6.14.

Рис. 614.

Если такого потока не существует, то, очевидно, зада­ча не имеет решения. Если же, как в нашем случае, хотя бы один такой поток существует, то на следующем шаге мы уменьшаем пропускные способности дуг на величины |f1ij| и повторяем весь процесс уже только для второго продукта. Уменьшенные пропускные способности для данного примера показаны на рис. 6.15.

Рис. 6.15.

Очевидно, что здесь не существует допустимого потока продукта 2, так как все дуги, инцидентные источнику у2, имеют нулевую остаточную пропускную способность. Отсюда мы дела­ем вывод, что перед тем, как пытаться пропустить поток продукта 2, нужно изменить маршрут движения потока для продукта 1.

Ху предложил следующую процедуру для изменения маршрутов. Найдем прежде всего (если возможно) неко­торую цепь Сi, ориентированную от у1 к z2 и обладаю­щую тем свойством, что, по крайней мере, одна единица продукта 1 может быть добавлена к каждой дуге в на­правлении, определяемом ориентацией цепи. Затем нахо­дим (если возможно) некоторую цепь С2, ориентирован­ную от Z2 к у2 и имеющую то же самое свойство. (Цепи С1 и C2 могут содержать некоторые одинаковые дуги.) Цепи, удовлетворяющие названным условиям, показаны на рис. 6.16.

Рис. 6.16.

Увеличим теперь поток продукта 1 в обеих цепях на единицу (на практике в некоторых случаях можно использовать и большие приращения потока). В результате получим, как показано на рис. 6.17, изме­ненный поток продукта 1.

Рис. 6.17,

Наконец увеличим поток продукта 2 вдоль цепи С1 и обращенной цепи С2 на единицу и получим потоки, изображенные пунктиром на рис. 6.18.

Рис. 6.18.

В данном примере мы получили решение задачи, так как нам удалось обеспечить два одновременных потока разных продуктов величины 2. Если бы поток продукта 2 был меньше чем Q2, то нужно было бы искать другую пару цепей С1 и С2, соответствующее изменение маршру­та продукта 1 и увеличение потока продукта 2. Можно показать, что если задача имеет решение, то продолже­ние процесса выбора пар цепей в конечном счете приво­дит к увеличению потока продукта 2 до величины Q2 (при сохранении величины потока продукта 1 на уровне Q1).

Пусть А1 и А2 обозначают соответственно пропускные способности минимальных разрезов, отделяющих у1 от z1 и у2 от z2, а А12 — пропускная способность минимального разделяющего множества, которое пересекает все цепи, соединяющие у1 с z1 и у2 с z2. Тогда двухпродуктовый аналог теоремы о минимальном разрезе и максимальном потоке формулируется следующим образом.

Теорема 6.9. Потоки F1 и F2 (из у1 в z1 и из у2 в z2 соответственно), имеющие величины Q1 и Q2, совместно допустимы тогда и только тогда, когда выполнены сле­дующие три условия:

Необходимость условий очевидна.

6.12. Стохастические потоки в сетях

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

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

Сеть с ожиданием состоит из множества взаимо­связанных специализированных каналов обслуживания, соединенных последовательно и параллельно. Перед каждым каналом обслуживания (или множеством кана­лов обслуживания, если они соединены параллельно) име­ется линия ожидания (длина которой может равняться ну­лю) готовых требований, поступивших для обслуживания в этих каналах. Выход одного канала обслуживания может являться входами другого. Если каждому появ­лению требования в очереди поставить в соответствие одну вершину, а выбытию из очереди — другую и сое­динить эти вершины дугой, соответствующей факту об­служивания, то получим некоторый граф. Этот граф будет обыкновенным, если каждая очередь состоит из единственного канала и единственной линии. Если, на­пример, существуют несколько параллельных каналов обслуживания, имеющих одну и ту же линию ожидания и один и тот же выход, то такая часть сети изобража­ется графом типа рис. 6.19.

Рис 6.19.

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

Рис. 6.20.

Случай, когда часть параллельных каналов может иметь выход на другие последовательные каналы или стоки, представлен рис. 6.21.

Рис. 6.21.

В качестве источника берется начальная совокупность заявок на обслуживание, а в качестве стока та же совокупность (после удовлетворения спроса).

В теории массового обслуживания поток состоит из дискретных объектов, например покупателей. В обычных же сетевых задачах потоки рас­сматриваются как непрерывные величины. Однако часто интерес представляют целочисленные пото­ки, которые можно интерпретиро­вать как дискретный поток. Отме­тим, что в задачах со стохастиче­скими пропускными способностя­ ми дуг могут возникнуть две ситуации. Поток может «потеряться» в начальной вершине, если дуга уже полностью насыще­на текущим по ней потоком или он может задержаться, ожидая входа. Интересующая нас теорема для диск­ретного потока применима к сетям с ожиданием, в кото­рых потоки обрабатываются в течение длительного вре­мени и исследуется установившееся состояние, т. е. асимптотическое поведение потока при t→∞.