Двухполюсная подсеть

Cтраница 1

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

Выделение двухполюсных подсетей по матрице достижимости начинается в блоке 3 алгоритма и состоит в выборе пар узлов и и и, для которых значение суммы о) ыо г эоц минимально ( но не меньше, чем 2) для всех не рассмотренных на данном этапе пар узлов. [2]

Две двухполюсные подсети. [3]

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

В первую группу двухполюсных подсетей включим все дуги исходной сети: действительно, каждую дугу можно рассматривать как двухполюсную подсеть. [5]

Двухполюсная сеть с секцией. 202. [6]

В заданной сети существует единственная минимальная двухполюсная подсеть, содержащая данную секцию. Действительно, допустим, что существуют две минимальные двухполюсные подсети G. [7]

Секции, относящиеся к третьей группе двухполюсных подсетей, в блоке 7 алгоритма также заменяются эквивалентной последовательно-параллельной подсетью. Такая замена возможна благодаря тому, что известный поток по любой дуге секции однозначно определяет потоки по всем остальным ее дугам. Эквивалентная подсеть, заменяющая исходную, строится в виде последовательного соединения всех входящих в исходную подсеть дуг. [8]

Теперь заменим дуги 1 и 2 произвольными двухполюсными подсетями, содержащими склады. [9]

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

Две двухполюсные подсети. [11]

Таким образом, во всей сети находятся одна или несколько непересекающихся минимальных двухполюсных подсетей, в совокупности содержащих все секции сети. Если все секции сети заключаются в одной минимальной двухполюсной подсети, то последняя может совпадать с самой сетью ( так было бы, например, для сети, отличающейся от представленной на рис. VI-6 отсутствием дуг ab и ag); здесь мы сталкиваемся с единственным случаем, когда никакое упрощение задачи о максимальном потоке не достигается. Если же выделяются минимальные двухполюсные подсети с секциями, которые меньше полной сети, то для каждой из них решается задача о максимальном потоке, после чего минимальная двухполюсная подсеть заменяется одной дугой найденной пропускной способности, и мы приходим к сети без секций, максимальный поток в которой можно затем найти по алгоритму расстановки пометок Форда - Фалкерсона. [12]

Агрегация исходной сети, описывающей ХТС, сопровождается эквивалентной заменой некоторых двухполюсных подсетей исходной сети G ( F, W) одной агрегированной дугой; тогда образуется новая сетевая модель, имеющая меньшее число дуг. В нашем случае подсеть, заменяемая агрегированной дугой, должна иметь структуру, при которой алгоритм расчета ее пропускной способности был бы сравнительно несложен. Этому требованию, как мы уже знаем, удовлетворяют подсети, имеющие последовательно-параллельную структуру. [13]

Последовательно-параллельная сеть, иллюстрирующая способ минимизации затрат. [14]

Как было показано в вышеупомянутом разделе, задача о максимальном потоке имеет смысл только для двухполюсных подсетей; в терминах ХТС это означает, что понятие производственной мощности имеет смысл только для двухполюсных ХТС. [15]

Страницы: 1 2