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