Двухполюсная подсеть
Cтраница 2
В первую группу двухполюсных подсетей включим все дуги исходной сети: действительно, каждую дугу можно рассматривать как двухполюсную подсеть. [16]
При агрегации сети важную роль играет поиск простых двух-полюсных подсетей в свернутой сети. Для нахождения простых двухполюсных подсетей необходимо сначала найти все пары узлов сети, связанных между собой более чем одним путем ( направленной цепью), а затем, выбрав пару узлов с минимальным числом связывающих путей, составить список узлов, входящих в простую двухполюсную подсеть, для которой выбранная пара узлов является полюсами, если такая подсеть существует для данной пары узлов. Эта операция осуществляется с использованием матриц смежности и достижимости свернутой сети. [17]
 |
Две двухполюсные подсети. [18] |
Таким образом, во всей сети находятся одна или несколько непересекающихся минимальных двухполюсных подсетей, в совокупности содержащих все секции сети. Если все секции сети заключаются в одной минимальной двухполюсной подсети, то последняя может совпадать с самой сетью ( так было бы, например, для сети, отличающейся от представленной на рис. VI-6 отсутствием дуг ab и ag); здесь мы сталкиваемся с единственным случаем, когда никакое упрощение задачи о максимальном потоке не достигается. Если же выделяются минимальные двухполюсные подсети с секциями, которые меньше полной сети, то для каждой из них решается задача о максимальном потоке, после чего минимальная двухполюсная подсеть заменяется одной дугой найденной пропускной способности, и мы приходим к сети без секций, максимальный поток в которой можно затем найти по алгоритму расстановки пометок Форда - Фалкерсона. [19]
Если сеть все же содержит секции с числом полюсов больше двух, то и тогда можно сделать попытку снизить размерность задачи линейного программирования и добиться существенного сокращения времени вычислений. Чтобы пояснить предлагаемый подход, введем понятие о минимальной двухполюсной подсети, содержащей секцию: этим термином будем называть такую двухполюсную подсеть исходной сети, которой принадлежат все вершины секции и которая имеет минимальное число вершин среди всех двухполюсных подсетей, обладающих этим свойством. [20]
Если оно не выполняется, значит, помимо узлов и и у в рассматриваемой подсети имеется еще один узел, являющийся полюсом. Следовательно, узлы и и v не являются полюсами двухполюсной подсети, они исключаются из рассмотрения и алгоритм переходит к рассмотрению следующей пары узлов по матрице достижимости. [21]
Свернутая сеть не имеет последовательно-параллельных подсетей, относящихся ко второй группе двухполюсных подсетей. Для свернутой сети составляется ее описание, позволяющее затем приступить к отысканию в ней простых двухполюсных подсетей. [22]
Если сеть все же содержит секции с числом полюсов больше двух, то и тогда можно сделать попытку снизить размерность задачи линейного программирования и добиться существенного сокращения времени вычислений. Чтобы пояснить предлагаемый подход, введем понятие о минимальной двухполюсной подсети, содержащей секцию: этим термином будем называть такую двухполюсную подсеть исходной сети, которой принадлежат все вершины секции и которая имеет минимальное число вершин среди всех двухполюсных подсетей, обладающих этим свойством. [23]
В разделе 3 главы IV мы показали, как расчет производственной мощности ХТС сводится к расчету пропускной способности потоковой сети, которая служит моделью ХТС, а в разделе 4 главы IV изложили метод агрегации этой потоковой сети. Полученная в результате агрегации сеть состоит из так называемых агрегированных дуг, каждой из которых в исходной сети соответствует последовательно-параллельная подсеть или двухполюсная подсеть иного вида, приведенная изложенными в разделе 3 главы IV методами к последовательно-параллельной. Вычислив пропускную способность каждой из агрегированных дуг ( на горизонте планирования это будет ступенчатая функция времени), можем перейти к вычислению пропускной способности агрегированной сети. [24]
Если сеть все же содержит секции с числом полюсов больше двух, то и тогда можно сделать попытку снизить размерность задачи линейного программирования и добиться существенного сокращения времени вычислений. Чтобы пояснить предлагаемый подход, введем понятие о минимальной двухполюсной подсети, содержащей секцию: этим термином будем называть такую двухполюсную подсеть исходной сети, которой принадлежат все вершины секции и которая имеет минимальное число вершин среди всех двухполюсных подсетей, обладающих этим свойством. [25]
При агрегации сети важную роль играет поиск простых двух-полюсных подсетей в свернутой сети. Для нахождения простых двухполюсных подсетей необходимо сначала найти все пары узлов сети, связанных между собой более чем одним путем ( направленной цепью), а затем, выбрав пару узлов с минимальным числом связывающих путей, составить список узлов, входящих в простую двухполюсную подсеть, для которой выбранная пара узлов является полюсами, если такая подсеть существует для данной пары узлов. Эта операция осуществляется с использованием матриц смежности и достижимости свернутой сети. [26]
Свернутая сеть не имеет последовательно-параллельных подсетей, относящихся ко второй группе двухполюсных подсетей. Для свернутой сети составляется ее описание, позволяющее затем приступить к отысканию в ней простых двухполюсных подсетей. [27]
 |
Две двухполюсные подсети. [28] |
Таким образом, во всей сети находятся одна или несколько непересекающихся минимальных двухполюсных подсетей, в совокупности содержащих все секции сети. Если все секции сети заключаются в одной минимальной двухполюсной подсети, то последняя может совпадать с самой сетью ( так было бы, например, для сети, отличающейся от представленной на рис. VI-6 отсутствием дуг ab и ag); здесь мы сталкиваемся с единственным случаем, когда никакое упрощение задачи о максимальном потоке не достигается. Если же выделяются минимальные двухполюсные подсети с секциями, которые меньше полной сети, то для каждой из них решается задача о максимальном потоке, после чего минимальная двухполюсная подсеть заменяется одной дугой найденной пропускной способности, и мы приходим к сети без секций, максимальный поток в которой можно затем найти по алгоритму расстановки пометок Форда - Фалкерсона. [29]
Страницы: 1 2