Однако ( 17) включает пропускные способности по всем разрезам между этими парами узлов, так что ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Лэсдон Л.С. Оптимизация больших систем


Однако ( 17) включает пропускные способности по всем разрезам между этими парами узлов, так что неравенств все же остается много. Конечно, для данного ( i, j) еГ, если минимальный разрез удовлетворяет ( 17), то все сделано, так как для любого множества дуг должны быть проверены только п - 1 ограничений. Однако то, какую п - 1 пару надо рассматривать, изменяется при изменении пропускных способностей. Для того чтобы увидеть, какие из различных подмножеств ограничений могут быть выбраны эффективно, напишем двойственную задачу, в которой выбор ограничений или строк, вводимых в исходной задаче, становится выбором столбцов, вводимых в двойственный базис.

(cкачать страницу)

Смотреть книгу на libgen

Однако ( 17) включает пропускные способности по всем разрезам между этими парами узлов,  так что неравенств все же остается много.  Конечно,  для данного ( i,  j) еГ,  если минимальный разрез удовлетворяет ( 17),  то все сделано,  так как для любого множества дуг должны быть проверены только п  -  1 ограничений.  Однако то,  какую п  -  1 пару надо рассматривать,  изменяется при изменении пропускных способностей.  Для того чтобы увидеть,  какие из различных подмножеств ограничений могут быть выбраны эффективно,  напишем двойственную задачу,  в которой выбор ограничений или строк,  вводимых в исходной задаче,  становится выбором столбцов,  вводимых в двойственный базис.