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.