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