4551
правка
Лес Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Прямо-двойственный алгоритм
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Двойственная задача для релаксации линейного программирования (IP) включает переменную <math>y_S \;</math> для каждого разреза Штейнера <math>S \in \mathcal{S} \;</math>. Существует ограничение: для каждого ребра <math>e \in E \;</math> полная двойственная задача, присвоенная множествам <math>S \in \mathcal{S} \;</math>, содержащим | Двойственная задача для релаксации линейного программирования (IP) включает переменную <math>y_S \;</math> для каждого разреза Штейнера <math>S \in \mathcal{S} \;</math>. Существует ограничение: для каждого ребра <math>e \in E \;</math> полная двойственная задача, присвоенная множествам <math>S \in \mathcal{S} \;</math>, содержащим ровно одну конечную точку e, имеет стоимость не более c(e): | ||
(D) максимизировать <math>\sum_{S \in \mathcal{S}} y_S</math> | (D) максимизировать <math>\sum_{S \in \mathcal{S}} y_S</math> | ||