Zagadnienia

12. Metoda podziału i ograniczeń

12.1. Metoda podziału i ograniczeń

Badamy problem optymalizacji

P: Maxfx|xQP

W przypadku gdy obszar dopuszczalny QP 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 P1,P2,,Pt, postaci Pi:Maxfx|xQPi, gdzie obszar dopuszczalny QP jest rozłączną sumą obszarów QPi.

Podsumowując, zamiast problemu P:Maxfx|xQ rozwiązujemy ciąg problemów P1,P2,,Pt, postaci Pi:Maxfx|xQPi, gdzie obszar dopuszczalny

QPi=1tQPi.

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 RPi problemu Pi jest sprzeczna, QRPi=, to problem Pi uznajemy za zamknięty.

KZ2 Jeżeli pewna relaksacja RPi problemu Pi ma rozwiązanie dopuszczalne p, pQP, to problem Pi 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 RPi problemu Pi ma rozwiązanie o mniejszej wartości funkcji celu, to problem Pi 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= .
Dodatkowo mamy sukcesor 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.
x^=w,fw lub
x^=
1)Test stopu:
 Jeżeli L= to stop,
 jeśli x^=w,fw to w jest punktem optymalnym, a fw jest rozwiązaniem,
jeśli x^= to zadanie jest sprzeczne.
2)  Wybór kandydata z listy:
 Wybieramy i usuwamy z listy L podproblem Pk.
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:wkf:fk 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 pi nie jest liczbą całkowitą to problem dzielimy na dwa. Tak zwany ”lewy” przez dodanie ograniczenia xipi i tak zwany ”prawy” przez dodanie ograniczenia xipi=pi+1.

Przykład 12.1

Rozwiązujemy zadanie P.

Maxx0=-9x1-6x2-2x3

-52x1-32x2+12x3+x4=52

4x1+3x2+2x3+x5=3

-2x3+x6=4

ixi0,xiZ

Jest to zadanie typu:

P:Maxx0=cx

xQP.

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

2) Budujemy pierwszą relaksację RP opuszczając warunki ixiZ.

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

3) Rozwiązujemy RP metodą sympleks.

x0x1x2x3x4x5x6ww196200000-52-32121005204320103000-20014

Otrzymana macierz jest tablicą sympleks pierwotnie i dualnie dopuszczalną więc opisuje wierzchołek optymalny relaksacji w1=0,0,0,52,3,4. Nie jest on dopuszczalny dla zadania P zatem dokonujemy podziału względem zmiennej x4.

4) Wydzielamy ze zbioru QRP 2 podzbiory, tak zwany ”lewy” i ”prawy” przez dodanie ograniczeń:

x452=2 lub x452+1=3 odpowiednio

Oczywiście QPQRPLQRPP gdyż wyrzuciliśmy tylko punkty u o współrzędnej x3 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 ixiZ.

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

RPL Dodajemy ograniczenie x42x4+x7=2

Warunek x4+x7=2 zastępujemy 52x1+32x2-52x3+x7=-12, który powstaje przez odjęcie pierwszego równania. Zatem ”lewa” relaksacja ma postać:

Maxx0=-9x1-6x2-2x3

-52x1-32x2+12x3+x4=52

4x1+3x2+2x3+x5=3

-2x3+x6=4

52x1+32x2-52x3+x7=-12

ixi0

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

96200000-52-32121000524320100300-2001045232-120001-12

Jedynym elementem nadającym się na centralny jest -12.

Po przekształceniach Gaussa - Jordana otrzymujemy:

191200004-200010012149001041-10-60001-46-5-31000-21

RPL ma rozwiązanie dopuszczalne p1=0,0,1,2,1,6,0 x0=-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 p1 i wartość x0=-2.

2) wybieramy problem ”prawy” RPP i ustalamy relaksację przez odrzucenie warunków ixiZ.

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

Dodajemy ograniczenie   x452+1=3

x4-x7=3-x4+x7=-3

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

-52x1-32x2+52x3+x7=-12

Zadanie ”prawe” zapisujemy w postaci tablicy sympleks:

96200000-52-32121000524320100300-200104-52-32120001-12

i rozwiązujemy dualną metodą sympleks. Liczymy Min9/52;5/32=185 więc elementem centralnym jest -52.

Po przekształceniach Gaussa - Jordana otrzymujemy:

035195000185-95000100-130351450108511500-200104135-15000-2515

Otrzymany wierzchołek optymalny p2=15,0,0,3,115,4,0 nie jest dopuszczalny więc problem dzielimy na nowe podproblemy względem zmiennej x5 i idziemy do 1).

1) Lista L zawiera podproblemy ”prawy,lewy”- PPL i ”prawy,prawy”'- PPP. Sukcesor zawiera punkt p1 i wartość x0=-2.

2) Wybieramy problem PPL i ustalamy relaksację przez odrzucenie warunków ixiZ.

3) Rozwiązujemy relaksację problemu PPL.

RPL Dodajemy ograniczenie x5115=2x4+x8=2.

Otrzymujemy zadanie opisane tablicą:

0351950001850-95000100-10303514501085011500-2001004135-15000-250150-35-145000-851-15

i rozwiązujemy dualną metodą sympleks. Liczymy Min35/35;195/145;185/85=35/35=1 więc elementem centralnym jest -35.

Po przekształceniach Gaussa - Jordana otrzymujemy:

00100021-2000100-10300001001200-200100410-3000-2100114300083-5313

Otrzymany wierzchołek optymalny p3=0,13,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 PPL ma wartość mniejszą niż sukcesor. Stosując kryterium KZ3 zamykamy problem. Idziemy do 1).

1) Lista L zawiera podproblem ”prawy,prawy”'- PPP. Sukcesor zawiera punkt p1 i wartość x0=-2.

2) Wybieramy problem PPP i ustalamy relaksację przez odrzucenie warunków ixiZ.

3) Rozwiązujemy relaksację problemu PPP.

RPL Dodajemy ograniczenie x5115+1=3x4-x8=3.

Otrzymujemy zadanie opisane tablicą:

0351950001850-95000100-10303514501085011500-2001004135-15000-25015035145000851-45

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 p1 i wartość x0=-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. Maxx0=a1x1+a2x2++anxnb1x1+b2x2++bnxn

xQ

TS=-cN0b0NIb

Niech t=i=1nbixi i rozwiązujemy zadanie dopisując równanie t do tablicy.

TS=[-cN0NIb0bb1x1+b2x2++bnxnt]

przekształcenia polegają na wyborze elementu centralnego Mini,αij>0tiαij,tbj=min

i dzielimy na dwa podproblemy

1) tbj<minbj - element centralny

2) tbjmin element centralny - jakiś z kolumny j

x^=fwt,w

Przykład 12.2

Rozwiązujemy zadanie P.

MaxM=-2x1+x2+32x1+3x2+x3+2

3x1+x2+x4=4

x1+2x2+x5=3

ixi0

Ustalmy parametr t=2x1+3x2+x3+2 i rozwiązujmy zadanie

Maxx0=-2x1+x2+3

3x1+x2+x4=4

x1+2x2+x5=3

2x1+3x2+x3=t-2

ixi0

Wtedy maksymalna wartość M jest równa maksymalnej wartości x0t i punkty optymalne obu zadań pokrywają się.

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

2-1000331010412001323100t-2

P1 Jeżeli t<2 to zadanie jest sprzeczne.

P2 Jeżeli 2t132 to element centralny leży w ostatnim wierszu.

2-1000331010412001323100t-2

i po przekształceniach Gaussa - Jordana otrzymujemy:

830130073+13t730-1310143-13t-130-2301133-23t231130013t-23

Punktem optymalnym jest p=0,13t-23,0,143-13t,133-23t, maksymalną wartością x0 jest 73+13t. Zatem M przyjmuje wartość M=x0t=73t+13. Wartość M rośnie ze wzrostem T i przyjmuje maksymalną wartość dla t=132 wynoszącą Mm=73+13132=92

P3

t>132 Tym razem elementem centralnym jest 2.

2-1000331010412001323100t-2

i po przekształceniach Gaussa - Jordana otrzymujemy:

52000129252001-125212100123212010-32-132+t

Punktem optymalnym jest p=0,32,-132+t,52,0, maksymalną wartością x0 jest 92. Zatem M przyjmuje wartość M=x0t=92t. Wartość M maleje ze wzrostem T i zawsze jest mniejsza niż 92.

Rozwiązanie zadania p=0,32,0,52,0, M=92 otrzymaliśmy w podproblemie P2.

Jako literaturę uzupełniającą do tego tematu polecamy książki [13] i [12]

Ćwiczenie 12.1

Stosując podział Dekina rozwiąż w liczbach całkowitych zadanie:

Min x0=x3+x4+3x5 , gdy

x1+12x3+2x4+32x5=72

x2+12x3+12x4+3x5=92

ixi0, xiZ.

Ćwiczenie 12.2

Stosując podział Dekina rozwiąż w liczbach całkowitych zadanie:

Maxx0=x1-2x2

-x1+x20

4x1-2x29

x13

ixi0xiZ

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.