Podręcznik: Idea metody płaszczyzn tnących

2. Metoda płaszczyzn tnących

2.2. Idea metody płaszczyzn tnących

W ogólnym przypadku trudno jest uzyskać najbardziej zwarty opis $X$ , bo liczb ograniczeń rośnie wykładniczo lub szybciej, ale można przybliżać uwypuklenie zbioru $X$ w pewnym otoczeniu punktu optymalnego.

Idea metody płaszczyzn tnących polega na stopniowym zawężaniu opis wielościennego $P$ w wyniku dodawania ograniczeń do już istniejących $Ax\leq b$ nowych o postaci $Dx \leq d$ , tak aby:

dodatkowe ograniczenia odcinały pewne rozwiązania $x \in P$ nie należące do $conv(X)$
poszukiwane rozwiązanie ZPLC stawało się punktem wierzchołkowym opis wielościennego $P^*=\{x: Ax \leq b, Dx \leq d, x \geq 0 \}$
funkcja celu ZPL osiągała maksimum na $P$ w punkcie wierzchołkowym całkowitoliczbowym

Dodatkowe ograniczenia nie powinny odcinać rozwiązań dopuszczalnych oryginalnego problemu. Tego typu ograniczenia nazwywamy nierównościami zgodnymi.

Nierówność

$d^Tx \leq d_0$ jest zgodna (valid inequality) dla zbioru

$X \in \mathbb{R}^n$ , jeżeli zachodzi

$d^Tx\leq d_0$ dla każdego

$x \in X$ .

Np. zgodne są pierwotne ograniczenia problemu lub ograniczenia opisujące $conv(X)$ .

Rozważmy proste ograniczenie

$x \leq 1,5$
Jeżeli

$x$ jest całkowitoliczbowe, to prawą stronę ograniczenia możemy zaokrąglić w dół

$x \leq 1$ .
Powstałem w ten sposób nowe ogranicznie jest ograniczeniem zgodnym.

Rozważmy nieco ciekawszych przykład ograniczenia

$x+2y+4z=4$
gdzie wszystkie zmienne

$x,y,z$ są binarne.
Ponieważ

$4z \geq 4 - sup(x+2y) \Rightarrow z\geq \frac{1}{4} \Rightarrow z \geq 1$
A to oznacza, że

$x=0, y=0, z=1$
Jak widać oryginalne ograniczenie można zastąpić trzema ograniczeniami zgodnymi ustalającymi wartości wszystkich trzech zmiennych.