Podręcznik: Iteracyjny proces poszukiwania rozwiązania: zawężanie oszacowań

2. Metoda podziału i oszacowań

2.1. Iteracyjny proces poszukiwania rozwiązania: zawężanie oszacowań

W pojedynczej iteracji znajdujemy się w konkretnym węźle drzewa B&B, gdzie rozwiązujemy zrelaksowane zadanie z dodatkowym ograniczeniem obszaru dopuszczalnego po to, aby uzyskać lokalne oszacowanie LB. Analizując LB oraz UB mamy dwie możliwości:

podzielenie węzła, czyli dodanie ograniczeń, gdy aktualne, lokalne LB < globalne UB (jest szansa, że w danym obszarze znajdziemy lepsze rozwiązanie od tego, które mamy do tej pory), a następnie wybór części (węzła) do eksploracji;
zamknięcie węzła i powrót poziom wyżej, co następuje w 3 przypadkach:

rozwiązanie sprzeczne -- ograniczenie w tym węźle powoduje, że obszar dopuszczalny staje się pusty;
rozwiązanie całkowitoliczbowe -- staje się nowym UB jeśli wartość lokalnego LB< globalne UB dotychczasowe;
aktualne, lokalne LB > globalne UB -- zrelaksowane rozwiązanie w podproblemie gorsze niż najlepsze rozwiązanie do-tej-pory (nie ma szans, aby w danym obszarze znaleźć lepsze rozwiązanie od tego, które mamy do tej pory).

Zależności między LB i UB przedstawia poniższy rysunek.

Zależności między LB i UB

W kolejnych iteracjach metody B&B obserwuje się stopniowe zawężanie zakresu między LB i UB, aż do zrównania tych wartości w punkcie optymalnym. Prześledźmy ten proces na przykładzie.

Rozważmy zadanie minimalizacji, w którym mamy trzy zmienne całkowitoliczbowe i trzy ograniczenia:
x

$\min 39x + 30y + 12z\\ p.o.:\ \ \ \ \ \ \ \ 3x + 3y + 18z \geq 93\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 17x + 12y + 0z \geq 64\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 8x + 10y + 3z \geq 28\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x,y,z \ge 0$

Węzeł 0
Pierwszy węzeł (root node) jest relaksacją LP problemu.
- UB ma wartość nieskończoność (de facto mogłoby by być np. 39*31= 1209 = 39*max{93/3; 64/17; 28/8})
- LB ma wartość minus nieskończoność (de facto mogłoby być 0)
Rozwiązanie, tj. wartości zmiennych decyzyjnych, nie są całkowitoliczbowe, dzielimy wierzchołek, a LB=209 (wszystkie współczynniki f. celu są całkowitoliczbowe, więc bezpiecznie można zaokrąglić wynik). Zauważmy, że zaokrąglając wartości zmiennych w górę moglibyśmy zaktualizować też UB=258=39*2+30*4+12*5.
Wybieramy zmienną do podziału, w najprostszym przypadku może być to pierwsza zmienna o wartości rzeczywistej, czyli $x$ w naszym przykładzie. Otrzymujemy dwa nowe podproblemy, wybieramy do dalszej eksploracji pierwszy z lewej.
Węzeł 1
Dzielimy kolejny wierzchołek ze względu na zmienną $y$ , co dla ograniczenia $y \leq 3$ prowadzi do problemu sprzecznego. Wracamy poziom wyżej i eksplorujemy teraz prawą gałąź.
Węzły 3--7
Kontynuujemy rozgałęzianie, aż w iteracji 7 (dla $z \leq 4$ ) otrzymujemy rozwiązanie całkowitoliczbowe, które daje wartość UB=258.
Węzeł 8
Okazuje się, że w kolejnej iteracji (dla $z \geq 5$ ) otrzymujemy lepsze rozwiązanie całkowitoliczbowe, więc UB=240.
Koniec
Kolejne rozwiązanie całkowitoliczbowe uzyskujemy w kolejnych krokach. To poprawia aktualny UB z 240 na 219. Po rozwiązaniu problemu w prawej gałęzi, wychodzącej z wierzchołka 0 uzyskujemy LB=220, co pozwala nam zamknąć poszukiwania, gdyż LB>UB.

Rozwiąż powyższy problem metodą B&B, przy zamienionych współczynnikach cen w funkcji celu:

$\min 12x + 39y + 30z$ .