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: M⁢a⁢x⁢⁢⁢f⁢x⁢|⁢x∈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 P1,P2,…,Pt, postaci Pi:⁢M⁢a⁢x⁢⁢⁢f⁢x⁢|⁢x∈Q⁢Pi, gdzie obszar dopuszczalny Q⁢P jest rozłączną sumą obszarów Q⁢Pi.

Podsumowując, zamiast problemu P:⁢M⁢a⁢x⁢⁢⁢f⁢x⁢|⁢x∈Q rozwiązujemy ciąg problemów P1,P2,…,Pt, postaci Pi:⁢M⁢a⁢x⁢⁢⁢f⁢x⁢|⁢x∈Q⁢Pi, gdzie obszar dopuszczalny

Q⁢P⊂⋃⁢i=1⁢t⁢Q⁢Pi.

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 R⁢Pi problemu Pi jest sprzeczna, Q⁢R⁢Pi=∅, to problem Pi uznajemy za zamknięty.

KZ2 Jeżeli pewna relaksacja R⁢Pi problemu Pi ma rozwiązanie dopuszczalne p, p∈Q⁢P, 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 R⁢Pi 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,f⁢w lub

x^=∅

1)Test stopu:

Jeżeli L=∅ to stop,

jeśli x^=w,f⁢w≠∅ to w jest punktem optymalnym, a f⁢w 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ę R⁢P⁢k.

3) Rozwiązujemy R⁢P⁢k i testujemy kryteria zamykania:

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

KZ3 to zmieniamy sukcesor w:wk, f: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 R⁢P, 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 xi≤pi i tak zwany ”prawy” przez dodanie ograniczenia xi≥pi=pi+1.

Przykład 12.1

Rozwiązujemy zadanie P.

M⁢a⁢x⁢⁢⁢x0=-9⁢x1-6⁢x2-2⁢x3

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

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

⁢⁢-2⁢x3+x6=4

⁢⁢∀i⁢xi≥0,⁢xi∈Z

Jest to zadanie typu:

P:⁢M⁢a⁢x⁢⁢x0=c∙x

x∈Q⁢P.

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

2) Budujemy pierwszą relaksację R⁢P opuszczając warunki ∀i⁢xi∈Z.

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

3) Rozwiązujemy R⁢P metodą sympleks.

⁢x0x1x2x3x4x5x6w⁢w196200000-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 Q⁢R⁢P 2 podzbiory, tak zwany ”lewy” i ”prawy” przez dodanie ograniczeń:

⁢x4≤52=2⁢ lub ⁢x4≥52+1=3 odpowiednio

Oczywiście Q⁢P⊂Q⁢R⁢PL∪Q⁢R⁢PP 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 ∀i⁢xi∈Z.

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

R⁢PL Dodajemy ograniczenie x4≤2⇔x4+x7=2

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

M⁢a⁢x⁢⁢⁢x0=-9⁢x1-6⁢x2-2⁢x3

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

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

⁢⁢-2⁢x3+x6=4

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

⁢∀ixi≥0

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

R⁢PL 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” R⁢PP i ustalamy relaksację przez odrzucenie warunków ∀i⁢xi∈Z.

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

Dodajemy ograniczenie x4≥52+1=3

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

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

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

Zadanie ”prawe” zapisujemy w postaci tablicy sympleks:

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

i rozwiązujemy dualną metodą sympleks. Liczymy M⁢i⁢n⁢9/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”- PP⁢L i ”prawy,prawy”'- PP⁢P. Sukcesor zawiera punkt p1 i wartość x0=-2.

2) Wybieramy problem PP⁢L i ustalamy relaksację przez odrzucenie warunków ∀i⁢xi∈Z.

3) Rozwiązujemy relaksację problemu PP⁢L.

R⁢PL Dodajemy ograniczenie x5≤115=2⇔x4+x8=2.

Otrzymujemy zadanie opisane tablicą:

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

i rozwiązujemy dualną metodą sympleks. Liczymy M⁢i⁢n⁢35/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 PP⁢L ma wartość mniejszą niż sukcesor. Stosując kryterium KZ3 zamykamy problem. Idziemy do 1).

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

2) Wybieramy problem PP⁢P i ustalamy relaksację przez odrzucenie warunków ∀i⁢xi∈Z.

3) Rozwiązujemy relaksację problemu PP⁢P.

R⁢PL Dodajemy ograniczenie x5≥115+1=3⇔x4-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. M⁢a⁢x⁢⁢x0=a1⁢x1+a2⁢x2+…+an⁢xnb1⁢x1+b2⁢x2+…+bn⁢xn

x∈Q

T⁢S=-cN0b0NIb

Niech t=∑i=1n⁢bi⁢xi⁢ i rozwiązujemy zadanie dopisując równanie t do tablicy.

∘TS=[-cN0NIb0bb1⁢x1+b2⁢x2+…+bn⁢xnt]

przekształcenia polegają na wyborze elementu centralnego M⁢i⁢ni,αi⁢j>0⁢tiαi⁢j,tbj=m⁢i⁢n

i dzielimy na dwa podproblemy

1) tbj<m⁢i⁢n→bj - element centralny

2) tbj≥m⁢i⁢n→ element centralny - jakiś z kolumny j

⁢x^=f⁢wt,w

Przykład 12.2

Rozwiązujemy zadanie P.

M⁢a⁢x⁢⁢M=-2⁢x1+x2+32⁢x1+3⁢x2+x3+2

⁢3⁢x1+x2+x4=4

⁢⁢x1+2⁢x2+x5=3

⁢⁢∀i⁢xi≥0

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

M⁢a⁢x⁢⁢x0=-2⁢x1+x2+3

⁢3⁢x1+x2+x4=4

⁢⁢x1+2⁢x2+x5=3

⁢⁢2⁢x1+3⁢x2+x3=t-2

⁢⁢∀i⁢xi≥0

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 2≤t≤132 to element centralny leży w ostatnim wierszu.

2-1000331010412001323100t-2

i po przekształceniach Gaussa - Jordana otrzymujemy:

830130073+13⁢t730-1310143-13⁢t-130-2301133-23⁢t231130013⁢t-23

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

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=92⁢t. 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+3⁢x5 , gdy

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

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

∀ixi≥0, xi∈Z.

Ćwiczenie 12.2

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

M⁢a⁢x⁢⁢x0=x1-2⁢x2

-x1+x2≤0

4⁢x1-2⁢x2≤9

x1≤3

∀ixi≥0⁢xi∈Z

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

Optymalizacja I

Zagadnienia

12. Metoda podziału i ograniczeń

12.1. Metoda podziału i ograniczeń

Definicja 12.1

Algorytm metody B&B.

Przykład 12.1

Uwaga 12.1

Uwaga 12.2

Przykład 12.2

Ćwiczenie 12.1

Ćwiczenie 12.2