Podręcznik
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.
\( 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.
\(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.