ПОИСК Статьи Рисунки Таблицы Вычисление пропускной способности двухполюсной сети произвольного вида из "Оперативно-календарное планирование" Сделанные в начале главы замечания относительно вычисления интегральной пропускной способности последовательно-параллельной сети на горизонте планирования позволяют сразу же перейти к изложению алгоритма, ориентированного на сокращение вычислительных операций, что достигается, разумеется, за счет повышенных затрат оперативной памяти при реализации алгоритма на ЭВМ. [c.187] Аргументами этих соотношений являются пропускные способности дуг или подсетей. [c.187] Расчету по приведенным формулам должно предшествовать описание топологии сети. [c.189] Такое описание не только характеризует топологию сети, но является также записью операций, которые необходимо выполнить, чтобы получить пропускную способность цепи в целом символу соединения -Ь должна соответствовать операция сложения пропускных способностей элементов сети, связанных этим символом, а символу у — операция выбора наименьшего значения из пропускных способностей связанных этим символом элементов. [c.189] В массиве параметров программы записываются вид операции над пропускными способностями элементов сети — сложение или выбор наименьшего значения адреса, по которым хранятся пропускные способности дуг или подсетей число одновременно обрабатываемых дуг адрес, куда направляется результат каждого расчета. Полученный массив в дальнейшем может быть многократно использован для интерпретации программы расчета сети данной структуры. [c.190] Действия такого алгоритма проследим на примере сети, приведенной на рис. VI- , описание которой дано строкой (VI.10). [c.190] что если бы пропускные способности дуг сети были неизменны на всех интервалах дискретности горизонта планирования, то не имело бы смысла строить такую программу с образованием массива параметров достаточно было бы вычисления пропускной способности сети непосредственно по описанию. Однако параметрическая программа имеет то преимущество, что позволяет многократно, на каждом шаге дискретности горизонта планирования, вычислять пропускную способность сети, часть дуг которой характеризуется переменной во времени пропускной способностью, уменьшающейся при ремонте соответствующего оборудования. [c.191] Вместе с тем очевидно, что если в сети имеются подсети, состоящие только из дуг, пропускная способность которых остается неизменной на всех щагах дискретности горизонта планирования, то это обстоятельство выгодно использовать, чтобы сократить число операций в рабочей программе, чего можно достигнуть, выполнив необходимые операции над пропускными способностями дуг при построении массива параметров программы, т. е. один раз. [c.191] При сокращении описания существенную роль играют вводимые ниже понятия верхней и нижней границы пропускной способности. [c.191] Алгоритм получения массива параметров построен так, что сначала он выделяет подсети, состоящие из дуг с постоянной для горизонта планирования пропускной способностью, выполняет все предусмотренные описанием операции сложения и выделения минимального значения, а полученную пропускную способность (если это возможно) корректирует с учетом соответствующей верхней и нижней границы. В результате получаем более короткое описание последовательно-параллельной сети его обработка выполняется быстрее, чем для первоначального описания. Назовем это сокращение предварительным свертыванием описания. [c.192] Черта под номерами 1 ж 6 показывает, что значения верхних и нцжних границ пропускной способности этих дуг откорректированы. [c.192] ТО -тый элемент (дуга или подсеть) относится к нелимитирующим и исключается из формального описания сети действительно, этот элемент ни на одном шаге дискретности горизонта планирования не ограничивает пропускную способность сети. Очевидно, что в результате исключения нелимитирующих элементов мы получаем более короткое описание пропускная способность сети по новому описанию остается той же, но в нем содержится меньшее число дуг. Это позволяет дополнительно увеличить быстродействие программы вычисления пропускной способности последовательно-параллельной сети. [c.193] Для унификации расчета каждая дуга исходной сети, имеющая на горизонте планирования более одного ремонта 1 1 рассматривается как подсеть, состоящая из последовательно соединенных одинаковых дуг, каждая из которых имеет один ремонт на горизонте планирования. Такое преобразование возможно, поскольку поля допустимых дат остановки на ремонт в этом случае никогда не пересекаются по условию их построения. [c.194] Выигрыш в числе операций, выполняемых для расчета пропускной способности подсети, определяется отношением всего числа шагов дискретности на горизонте планирования к среднему по всем дугам подсети числу шагов, на которых производится ремонт на горизонте планирования. [c.194] Пропускная способность подсети, состоящей только из тех подсетей, которые были образованы ранее в процессе предварительного свертывания, вычисляется по параметрической программе, реализующей соотношения (VI.8), ( 1.9). [c.194] Значительную часть ХТС можно представить последовательнопараллельной сетью, тем не менее встречаются и сложные ХТС, которые без ущерба для существенных деталей, а следовательно, и конечных результатов вычислений нельзя описать последовательно-параллельной сетью. В дальнейшем мы не будем налагать на сеть никаких ограничений, дополнительных по сравнению с определением, приведенным в разделе 1 главы III, т. е. будем рассматривать сеть произвольного вида. [c.196] Как было показано в вышеупомянутом разделе, задача о максимальном потоке имеет смысл только для двухполюсных подсетей в терминах ХТС это означает, что понятие производственной мощности имеет смысл только для двухполюсных ХТС. [c.196] Задача о максимальном потоке в сети легко сводится к задаче линейного программирования. Действительно, ее условия содержат ограничения двух идов (материальный баланс в узлах сети и наибольшее значение потока в каждой дуге) и критерий. [c.197] Однако решение задачи о максимальном потоке по общему алгоритму линейного программирования требует весьма значительного объема вычислений. Поэтому здесь целесообразно применить не общий, а специализированный алгоритм, в котором учитываются особенности задачи это позволит по возможности сократить время вычислений. Таким требованиям удрвлетворяет предложенный Фордом и Фалкерсоном [55, 66] эффективный алгоритм нахождения максимального потока, называемый алгоритмом расстановки пометок. Изложим сначала принцип его работы, а затем дадим формальное описание. [c.197] увеличив потоки во всех прямых дугах на е и уменьшив на эту же величину потоки в обратных дугах, ползучим поток, который будет удовлетворять соотношениям баланса в вершинах и ограничениям (VI.22), величина же потока из г/ в у увеличится на е. [c.198] Вернуться к основной статье