Zagadnienia

12.1 Metoda podziału i ograniczeń

12. Metoda podziału i ograniczeń

12.1. Metoda podziału i ograniczeń

Badamy problem optymalizacji

P: $Max\ \{\, f(x)\ |\ x\in Q(P)\}$

W przypadku gdy obszar dopuszczalny $Q(P)$ niewygodnie opisany, np. wymagamy by niektóre współrzędne punktów były liczbami całkowitymi, jedną z głównych metod rozwiązywania jest metoda podziału i ograniczeń zwana też metodą rozgałęzień i zamykania. Używać będziemy też skróconej nazwy angielskiej ” $B\& B$ ” ( Branch and Bound ). Nawet tak proste programy jak Solver w arkuszu kalkulacyjnym Excel są reklamowane jako używające tej metody. Podstawowymi pojęciami są:

Definicja 12.1

Podziałem problemu P nazywamy ciąg podproblemów $P_{1},P_{2},...,P_{t}$ , postaci $P_{i}:\ Max\ \{\, f(x)\ |\ x\in Q(P_{i})\}$ , gdzie obszar dopuszczalny $Q(P)$ jest rozłączną sumą obszarów $Q(P_{i})$ .

Podsumowując, zamiast problemu $P:\ Max\ \{\, f(x)\ |\ x\in Q\}$ rozwiązujemy ciąg problemów $P_{1},P_{2},...,P_{t}$ , postaci $P_{i}:\ Max\ \{\, f(x)\ |\ x\in Q(P_{i})\}$ , gdzie obszar dopuszczalny

$Q(P)\subset\bigcup _{{\, i=1}}^{{\, t}}\ Q(P_{i})$ .

Rozwiązanie problemu polega na rozwiązaniu wszystkich podproblemów. Operacje te nazywamy zamykaniem podproblemu. Posługujemy się następującymi kryteriami:

Kryteria zamykania podproblemów.

KZ1 Jeżeli pewna relaksacja $RP_{i}$ problemu $P_{i}$ jest sprzeczna, $Q(RP_{i})=\emptyset$ , to problem $P_{i}$ uznajemy za zamknięty.

KZ2 Jeżeli pewna relaksacja $RP_{i}$ problemu $P_{i}$ ma rozwiązanie dopuszczalne $p$ , $p\in Q(P)$ , to problem $P_{i}$ uznajemy za zamknięty.

KZ3 Jeżeli znamy oszacowanie dolne $w*$ zadania $P$ , np. jest wartością funkcji celu w pewnym punkcie dopuszczalnym i pewna relaksacja $RP_{i}$ problemu $P_{i}$ ma rozwiązanie o mniejszej wartości funkcji celu, to problem $P_{i}$ uznajemy za zamknięty.

Algorytm metody B&B.

Dana jest lista kandydacka $L$ zawierająca wszystkie niezamknięte

problemy. (L może np. zawierać tylko jeden problem początkowy).

Lista L będzie się rozszerzać przy dokonywaniu podziału i skracać

przy zamykaniu problemu. Celem jest osiągniecie $L=\emptyset$ .

Dodatkowo mamy sukcesor $\widehat{x}$ . Jest nim zbiór zawierający element ze zbioru

dopuszczalnego i wartość funkcji na tym elemencie. W chwili

początkowej sukcesor może być pusty.

$\widehat{x}=\left\{\left(w,f(w)\right)\right\}$ lub

$\widehat{x}=\emptyset$

1)Test stopu:

Jeżeli $L=\emptyset$ to stop,

jeśli $\widehat{x}=\left\{\left(w,f(w)\right)\right\}\neq\emptyset$ to $w$ jest punktem optymalnym, a $f(w)$ jest rozwiązaniem,

jeśli $\widehat{x}=\emptyset$ to zadanie jest sprzeczne.

2) Wybór kandydata z listy:

Wybieramy i usuwamy z listy $L$ podproblem $P_{{k}}$ .

Ustalamy jego relaksację $RPk$ .

3) Rozwiązujemy $RPk$ i testujemy kryteria zamykania:

a) Jeżeli jest spełnione kryterium KZ2 i nie jest spełnione

KZ3 to zmieniamy sukcesor $w:w_{{k}}$ , $f:f_{{k}}$ GO TO 1)

b) Jeżeli spełnione kryteria KZ1 lub KZ3 GO TO 1)

4) Jeżeli żadne kryterium zamykania nie jest spełnione to decydujemy, czy zacieśniamy relaksację

czy dokonujemy podziału:

Jeżeli zacieśniamy relaksację to GO TO 3)

Jeżeli dokonujemy podziału to powstałe podproblemy dodajemy do listy kandydackiej $L$ i GO TO 2).

Zobaczmy to na następującym przykładzie. Stosować w nim będziemy tak zwane podziały Dakina [5]. W sytuacji gdy otrzymaliśmy niedopuszczalne rozwiązanie $p$ relaksacji $RP$ , w którym i-ta współrzędna $p$ równa $p_{i}$ nie jest liczbą całkowitą to problem dzielimy na dwa. Tak zwany ”lewy” przez dodanie ograniczenia $x_{i}\leq\lfloor p_{i}\rfloor$ i tak zwany ”prawy” przez dodanie ograniczenia $x_{i}\geq\lceil p_{i}\rceil=\lfloor p_{i}\rfloor+1$ .

Przykład 12.1

Rozwiązujemy zadanie P.

$Max\quad\qquad x_{{0}}=-9x_{1}-6x_{2}-2x_{3}$

$\qquad-\frac{5}{2}x_{1}-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}+x_{4}=\frac{5}{2}$

$\qquad\qquad 4x_{1}+3x_{2}+2x_{3}+x_{5}=3$

$\qquad\qquad\qquad-2x_{3}+x_{6}=4$

$\qquad\qquad\forall _{i}\ x_{{i}}\geq 0,\ x_{{i}}\in Z$

Jest to zadanie typu:

$P:\qquad Max\quad x_{0}=c\bullet x$

$x\in Q(P)$ .

1) Lista $L$ zawiera tylko problem początkowy $P$ . Sukcesor jest pusty.

2) Budujemy pierwszą relaksację $RP$ opuszczając warunki $\forall _{i}\ x_{{i}}\in Z$ .

Teraz zbiór dopuszczalny pierwszej relaksacji jest wielościanem.

3) Rozwiązujemy $RP$ metodą sympleks.

$\qquad\left[\begin{array}[]{c|rrrrrr|c}x_{{0}}&x_{{1}}&x_{{2}}&x_{{3}}&x_{{4}}&x_{{5}}&x_{{6}}&ww\\ 1&9&6&2&0&0&0&0\\ \hline 0&-\frac{5}{2}&-\frac{3}{2}&\frac{1}{2}&1&0&0&\frac{5}{2}\\ 0&4&3&2&0&1&0&3\\ 0&0&0&-2&0&0&1&4\end{array}\right]$

Otrzymana macierz jest tablicą sympleks pierwotnie i dualnie dopuszczalną więc opisuje wierzchołek optymalny relaksacji $w_{1}=(0,0,0,\frac{5}{2},3,4)$ . Nie jest on dopuszczalny dla zadania $P$ zatem dokonujemy podziału względem zmiennej $x_{4}$ .

4) Wydzielamy ze zbioru $Q(RP)$ 2 podzbiory, tak zwany ”lewy” i ”prawy” przez dodanie ograniczeń:

$\qquad x_{{4}}\leq\left\lfloor\frac{5}{2}\right\rfloor=2\quad$ lub $\qquad x_{4}\geq\left\lfloor\frac{5}{2}\right\rfloor+1=3$ odpowiednio

Oczywiście $Q(P)\subset Q(RP_{L})\cup Q(RP_{P})$ gdyż wyrzuciliśmy tylko punkty u o współrzędnej $x_{3}$ z przedziału otwartego $(2,3)$ . Idziemy do 1).

1) Lista $L$ zawiera podproblemy ”lewy” i ”prawy”. Sukcesor jest pusty.

2) Wybieramy problem ”lewy” i ustalamy relaksację przez odrzucenie warunków $\forall _{i}\ x_{{i}}\in Z$ .

3) Rozwiązujemy relaksację problemu ”lewego”.

$RP_{L}$ Dodajemy ograniczenie $x_{4}\leq 2\Leftrightarrow x_{4}+x_{7}=2$

Warunek $x_{4}+x_{7}=2$ zastępujemy $\frac{5}{2}x_{1}+\frac{3}{2}x_{2}-\frac{5}{2}x_{3}+x_{7}=-\frac{1}{2}$ , który powstaje przez odjęcie pierwszego równania. Zatem ”lewa” relaksacja ma postać:

$Max\quad\qquad x_{{0}}=-9x_{1}-6x_{2}-2x_{3}$

$\qquad-\frac{5}{2}x_{1}-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}+x_{4}=\frac{5}{2}$

$\qquad\qquad 4x_{1}+3x_{2}+2x_{3}+x_{5}=3$

$\qquad\qquad\qquad-2x_{3}+x_{6}=4$

$\qquad\qquad\frac{5}{2}x_{1}+\frac{3}{2}x_{2}-\frac{5}{2}x_{3}+x_{7}=-\frac{1}{2}$

$\qquad\forall _{i}x_{{i}}\geq 0$

Budujemy tablicę sympleks. Jest ona dualnie dopuszczalna więc stosujemy dualną metodę sympleks.

$\left[\begin{array}[]{crrrrrr|r}9&6&2&0&0&0&0&0\\ \hline-\frac{5}{2}&-\frac{3}{2}&\frac{1}{2}&1&0&0&0&\frac{5}{2}\\ 4&3&2&0&1&0&0&3\\ 0&0&-2&0&0&1&0&4\\ \frac{5}{2}&\frac{3}{2}&(-\frac{1}{2})&0&0&0&1&-\frac{1}{2}\end{array}\right]$

Jedynym elementem nadającym się na centralny jest $-\frac{1}{2}$ .

Po przekształceniach Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{crrrrrr|r}19&12&0&0&0&0&4&-2\\ \hline 0&0&0&1&0&0&1&2\\ 14&9&0&0&1&0&4&1\\ -10&-6&0&0&0&1&-4&6\\ -5&-3&1&0&0&0&-2&1\end{array}\right]$

$RP_{L}$ ma rozwiązanie dopuszczalne $p_{1}=(0,0,1,2,1,6,0)$ $x_{{0}}=-2$ . Zapamiętujemy to rozwiązanie w sukcesorze.

Zamknęliśmy problem ”lewy” stosując kryterium KZ2.

1) Nasza lista kandydacka zawiera tylko problem ”prawy”. Sukcesor zawiera punkt $p_{1}$ i wartość $x_{{0}}=-2$ .

2) wybieramy problem ”prawy” $RP_{P}$ i ustalamy relaksację przez odrzucenie warunków $\forall _{i}\ x_{{i}}\in Z$ .

3) Rozwiązujemy relaksację problemu ”prawego”. .

Dodajemy ograniczenie $x_{4}\geq\left\lfloor\frac{5}{2}\right\rfloor+1=3$

$x_{4}-x_{7}=3\Leftrightarrow-x_{4}+x_{7}=-3$

Teraz po dodaniu do pierwszego równania dodanego ograniczenia otrzymujemy nowe:

$-\frac{5}{2}x_{1}-\frac{3}{2}x_{2}+\frac{5}{2}x_{3}+x_{7}=-\frac{1}{2}$

Zadanie ”prawe” zapisujemy w postaci tablicy sympleks:

$\left[\begin{array}[]{rrrrrrr|r}9&6&2&0&0&0&0&0\\ \hline-\frac{5}{2}&-\frac{3}{2}&\frac{1}{2}&1&0&0&0&\frac{5}{2}\\ 4&3&2&0&1&0&0&3\\ 0&0&-2&0&0&1&0&4\\ (-\frac{5}{2})&-\frac{3}{2}&\frac{1}{2}&0&0&0&1&-\frac{1}{2}\end{array}\right]$

i rozwiązujemy dualną metodą sympleks. Liczymy $Min\left\{ 9/\frac{5}{2};5/\frac{3}{2}\right\}=\frac{18}{5}$ więc elementem centralnym jest $-\frac{5}{2}$ .

Po przekształceniach Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{rrrrrrr|r}0&\frac{3}{5}&\frac{19}{5}&0&0&0&\frac{18}{5}&-\frac{9}{5}\\ \hline 0&0&0&1&0&0&-1&3\\ 0&\frac{3}{5}&\frac{14}{5}&0&1&0&\frac{8}{5}&\frac{11}{5}\\ 0&0&-2&0&0&1&0&4\\ 1&\frac{3}{5}&-\frac{1}{5}&0&0&0&-\frac{2}{5}&\frac{1}{5}\end{array}\right]$

Otrzymany wierzchołek optymalny $p_{2}=(\frac{1}{5},0,0,3,\frac{11}{5},4,0)$ nie jest dopuszczalny więc problem dzielimy na nowe podproblemy względem zmiennej $x_{5}$ i idziemy do 1).

1) Lista $L$ zawiera podproblemy ”prawy,lewy”- $P_{{PL}}$ i ”prawy,prawy”'- $P_{{PP}}$ . Sukcesor zawiera punkt $p_{1}$ i wartość $x_{{0}}=-2$ .

2) Wybieramy problem $P_{{PL}}$ i ustalamy relaksację przez odrzucenie warunków $\forall _{i}\ x_{{i}}\in Z$ .

3) Rozwiązujemy relaksację problemu $P_{{PL}}$ .

$RP_{L}$ Dodajemy ograniczenie $x_{5}\leq\left\lfloor\frac{11}{5}\right\rfloor=2\Leftrightarrow x_{4}+x_{8}=2$ .

Otrzymujemy zadanie opisane tablicą:

$\left[\begin{array}[]{rrrrrrrr|r}0&\frac{3}{5}&\frac{19}{5}&0&0&0&\frac{18}{5}&0&-\frac{9}{5}\\ \hline 0&0&0&1&0&0&-1&0&3\\ 0&\frac{3}{5}&\frac{14}{5}&0&1&0&\frac{8}{5}&0&\frac{11}{5}\\ 0&0&-2&0&0&1&0&0&4\\ 1&\frac{3}{5}&-\frac{1}{5}&0&0&0&-\frac{2}{5}&0&\frac{1}{5}\\ 0&(-\frac{3}{5})&-\frac{14}{5}&0&0&0&-\frac{8}{5}&1&-\frac{1}{5}\end{array}\right]$

i rozwiązujemy dualną metodą sympleks. Liczymy $Min\left\{\frac{3}{5}/\frac{3}{5};\frac{19}{5}/\frac{14}{5};\frac{18}{5}/\frac{8}{5}\right\}=\frac{3}{5}/\frac{3}{5}=1$ więc elementem centralnym jest $-\frac{3}{5}$ .

Po przekształceniach Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{rrrrrrrr|r}0&0&1&0&0&0&2&1&-2\\ \hline 0&0&0&1&0&0&-1&0&3\\ 0&0&0&0&1&0&0&1&2\\ 0&0&-2&0&0&1&0&0&4\\ 1&0&-3&0&0&0&-2&1&0\\ 0&1&\frac{14}{3}&0&0&0&\frac{8}{3}&-\frac{5}{3}&\frac{1}{3}\end{array}\right]$

Otrzymany wierzchołek optymalny $p_{3}=(0,\frac{1}{3},0,3,2,4,0,0)$ nie jest dopuszczalny. Wartość funkcji celu w tym punkcie jest taka sama jak w sukcesorze. Ponadto nad kreską nie ma ”niebazowych” zer więc jest to jedyny punkt optymalny relaksacji. Oznacza to, że każdy punkt zadania $P_{{PL}}$ ma wartość mniejszą niż sukcesor. Stosując kryterium KZ3 zamykamy problem. Idziemy do 1).

1) Lista $L$ zawiera podproblem ”prawy,prawy”'- $P_{{PP}}$ . Sukcesor zawiera punkt $p_{1}$ i wartość $x_{{0}}=-2$ .

2) Wybieramy problem $P_{{PP}}$ i ustalamy relaksację przez odrzucenie warunków $\forall _{i}\ x_{{i}}\in Z$ .

3) Rozwiązujemy relaksację problemu $P_{{PP}}$ .

$RP_{L}$ Dodajemy ograniczenie $x_{5}\geq\left\lfloor\frac{11}{5}\right\rfloor+1=3\Leftrightarrow x_{4}-x_{8}=3$ .

Otrzymujemy zadanie opisane tablicą:

$\left[\begin{array}[]{rrrrrrrr|r}0&\frac{3}{5}&\frac{19}{5}&0&0&0&\frac{18}{5}&0&-\frac{9}{5}\\ \hline 0&0&0&1&0&0&-1&0&3\\ 0&\frac{3}{5}&\frac{14}{5}&0&1&0&\frac{8}{5}&0&\frac{11}{5}\\ 0&0&-2&0&0&1&0&0&4\\ 1&\frac{3}{5}&-\frac{1}{5}&0&0&0&-\frac{2}{5}&0&\frac{1}{5}\\ 0&\frac{3}{5}&\frac{14}{5}&0&0&0&\frac{8}{5}&1&-\frac{4}{5}\end{array}\right]$

Otrzymaliśmy sprzeczność bo ostanie równanie nie ma dodatnich rozwiązań. Zamykamy problem stosując kryterium KZ1. Idziemy do 1).

1) Lista $L$ pusta. Sukcesor zawiera punkt $p_{1}$ i wartość $x_{{0}}=-2$ . Rozwiązanie jest zawarte w sukcesorze.

Uwaga 12.1

Metoda podziału Dakina w przypadku gdy po usunięciu warunków całkowitoliczbowych otrzymujemy ograniczony obszar dopuszczalny.

Uwaga 12.2

Metoda podziału Dakina jest skuteczna gdy tylko część zmiennych jest całkowitoliczbowa.

Metodą $B\& B$ można rozwiązywać zadanie programowania liniowego z parametrem (pewne współczynniki nie są określone), na przykład zadania w których obszar dopuszczalny jest wielościanem ale funkcja celu jest wymierna.

np. $Max\quad x_{{0}}=\frac{a_{{1}}x_{{1}}+a_{{2}}x_{{2}}+...+a_{{n}}x_{{n}}}{b_{{1}}x_{{1}}+b_{{2}}x_{{2}}+...+b_{{n}}x_{{n}}}$

$x\in Q$

$TS=\left[\begin{array}[]{c|c|c}-c_{{N}}&0&b_{{0}}\\ \hline N&I&b\end{array}\right]$

Niech t= $\sum _{{i=1}}^{n}\, b_{i}x_{i}\$ i rozwiązujemy zadanie dopisując równanie $t$ do tablicy.

$\circ\qquad TS=\left[\begin{array}[]{c|c}\begin{array}[]{c|c}-c_{{N}}&0\\ \hline N&I\end{array}&\begin{array}[]{c}b_{{0}}\\ \hline b\end{array}\\ b_{{1}}x_{{1}}+b_{{2}}x_{{2}}+...+b_{{n}}x_{{n}}&t\end{array}\right]$

przekształcenia polegają na wyborze elementu centralnego $\underset{i,\alpha _{{ij}}>0}{Min}\left\{\frac{t_{{i}}}{\alpha _{{ij}}},\frac{t}{b_{{j}}}\right\}=min$

i dzielimy na dwa podproblemy

1) $\frac{t}{b_{{j}}}<min\rightarrow b_{{j}}$ - element centralny

2) $\frac{t}{b_{{j}}}\geq min\rightarrow$ element centralny - jakiś z kolumny j

$\qquad\widehat{x}=\left\{\left(\frac{f\left(w\right)}{t},w\right)\right\}$

Przykład 12.2

Rozwiązujemy zadanie P.

$Max\ M=\frac{-2x_{1}+x_{2}+3}{2x_{1}+3x_{2}+x_{3}+2}$

$\qquad 3x_{1}+x_{2}+x_{4}=4$

$\qquad\qquad x_{1}+2x_{2}+x_{5}=3$

$\qquad\qquad\forall _{i}\ x_{{i}}\geq 0$

Ustalmy parametr $t=2x_{1}+3x_{2}+x_{3}+2$ i rozwiązujmy zadanie

$Max\ x_{0}=-2x_{1}+x_{2}+3$

$\qquad 3x_{1}+x_{2}+x_{4}=4$

$\qquad\qquad x_{1}+2x_{2}+x_{5}=3$

$\qquad\qquad 2x_{1}+3x_{2}+x_{3}=t-2$

$\qquad\qquad\forall _{i}\ x_{{i}}\geq 0$

Wtedy maksymalna wartość $M$ jest równa maksymalnej wartości $\frac{x_{0}}{t}$ i punkty optymalne obu zadań pokrywają się.

Budujemy więc tablicę sympleks i zadanie dzielimy na podproblemy w zależności od parametru $t$ .

$\left[\begin{array}[]{ccccc|c}2&-1&0&0&0&3\\ \hline 3&1&0&1&0&4\\ 1&2&0&0&1&3\\ 2&3&1&0&0&t-2\end{array}\right]$

$P_{1}$ Jeżeli $t<2$ to zadanie jest sprzeczne.

$P_{2}$ Jeżeli $2\leq t\leq\frac{13}{2}$ to element centralny leży w ostatnim wierszu.

$\left[\begin{array}[]{ccccc|c}2&-1&0&0&0&3\\ \hline 3&1&0&1&0&4\\ 1&2&0&0&1&3\\ 2&(3)&1&0&0&t-2\end{array}\right]$

i po przekształceniach Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{ccccc|c}\frac{8}{3}&0&\frac{1}{3}&0&0&\frac{7}{3}+\frac{1}{3}t\\ \hline\frac{7}{3}&0&-\frac{1}{3}&1&0&\frac{14}{3}-\frac{1}{3}t\\ -\frac{1}{3}&0&-\frac{2}{3}&0&1&\frac{13}{3}-\frac{2}{3}t\\ \frac{2}{3}&1&\frac{1}{3}&0&0&\frac{1}{3}t-\frac{2}{3}\end{array}\right]$

Punktem optymalnym jest $p=(0,\frac{1}{3}t-\frac{2}{3},0,\frac{14}{3}-\frac{1}{3}t,\frac{13}{3}-\frac{2}{3}t)$ , maksymalną wartością $x_{0}$ jest $\frac{7}{3}+\frac{1}{3}t$ . Zatem $M$ przyjmuje wartość $M=\frac{x_{0}}{t}=\frac{7}{3t}+\frac{1}{3}$ . Wartość $M$ rośnie ze wzrostem $T$ i przyjmuje maksymalną wartość dla $t=\frac{13}{2}$ wynoszącą $M_{m}=\frac{7}{3}+\frac{1}{3}\frac{13}{2}=\frac{9}{2}$

$P_{3}$

$t>\frac{13}{2}$ Tym razem elementem centralnym jest 2.

$\left[\begin{array}[]{ccccc|c}2&-1&0&0&0&3\\ \hline 3&1&0&1&0&4\\ 1&(2)&0&0&1&3\\ 2&3&1&0&0&t-2\end{array}\right]$

i po przekształceniach Gaussa - Jordana otrzymujemy:

$\left[\begin{array}[]{ccccc|c}\frac{5}{2}&0&0&0&\frac{1}{2}&\frac{9}{2}\\ \hline\frac{5}{2}&0&0&1&-\frac{1}{2}&\frac{5}{2}\\ \frac{1}{2}&1&0&0&\frac{1}{2}&\frac{3}{2}\\ \frac{1}{2}&0&1&0&-\frac{3}{2}&-\frac{13}{2}+t\end{array}\right]$

Punktem optymalnym jest $p=(0,\frac{3}{2},-\frac{13}{2}+t,\frac{5}{2},0)$ , maksymalną wartością $x_{0}$ jest $\frac{9}{2}$ . Zatem $M$ przyjmuje wartość $M=\frac{x_{0}}{t}=\frac{9}{2t}$ . Wartość $M$ maleje ze wzrostem $T$ i zawsze jest mniejsza niż $\frac{9}{2}$ .