Badamy problem optymalizacji
P:
W przypadku gdy obszar dopuszczalny 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 ”
” ( 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ą:
Podziałem problemu P nazywamy ciąg podproblemów , postaci
, gdzie obszar dopuszczalny
jest rozłączną sumą obszarów
.
Podsumowując, zamiast problemu rozwiązujemy ciąg problemów
, postaci
, gdzie obszar dopuszczalny
.
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 problemu
jest sprzeczna,
, to problem
uznajemy za zamknięty.
KZ2 Jeżeli pewna relaksacja problemu
ma rozwiązanie dopuszczalne
,
, to problem
uznajemy za zamknięty.
KZ3 Jeżeli znamy oszacowanie dolne zadania
, np. jest wartością funkcji celu w pewnym punkcie dopuszczalnym i pewna relaksacja
problemu
ma rozwiązanie o mniejszej wartości funkcji celu, to problem
uznajemy za zamknięty.
Dana jest lista kandydacka ![]() |
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 ![]() |
Dodatkowo mamy sukcesor ![]() |
dopuszczalnego i wartość funkcji na tym elemencie. W chwili |
początkowej sukcesor może być pusty. |
![]() |
![]() |
1)Test stopu: |
Jeżeli ![]() |
jeśli ![]() ![]() ![]() |
jeśli ![]() |
2) Wybór kandydata z listy: |
Wybieramy i usuwamy z listy ![]() ![]() |
Ustalamy jego relaksację ![]() |
3) Rozwiązujemy ![]() |
a) Jeżeli jest spełnione kryterium KZ2 i nie jest spełnione |
KZ3 to zmieniamy sukcesor ![]() ![]() |
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 ![]() |
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 relaksacji
, w którym i-ta współrzędna
równa
nie jest liczbą całkowitą to problem dzielimy na dwa. Tak zwany ”lewy” przez dodanie ograniczenia
i tak zwany ”prawy” przez dodanie ograniczenia
.
Rozwiązujemy zadanie P.
Jest to zadanie typu:
.
1) Lista zawiera tylko problem początkowy
. Sukcesor jest pusty.
2) Budujemy pierwszą relaksację opuszczając warunki
.
Teraz zbiór dopuszczalny pierwszej relaksacji jest wielościanem.
3) Rozwiązujemy metodą sympleks.
Otrzymana macierz jest tablicą sympleks pierwotnie i dualnie dopuszczalną więc opisuje wierzchołek optymalny relaksacji . Nie jest on dopuszczalny dla zadania
zatem dokonujemy podziału względem zmiennej
.
4) Wydzielamy ze zbioru 2 podzbiory, tak zwany ”lewy” i ”prawy” przez dodanie ograniczeń:
lub
odpowiednio
Oczywiście gdyż wyrzuciliśmy tylko punkty u o współrzędnej
z przedziału otwartego
. Idziemy do 1).
1) Lista zawiera podproblemy ”lewy” i ”prawy”. Sukcesor jest pusty.
2) Wybieramy problem ”lewy” i ustalamy relaksację przez odrzucenie warunków .
3) Rozwiązujemy relaksację problemu ”lewego”.
Dodajemy ograniczenie
Warunek zastępujemy
, który powstaje przez odjęcie pierwszego równania. Zatem ”lewa” relaksacja ma postać:
Budujemy tablicę sympleks. Jest ona dualnie dopuszczalna więc stosujemy dualną metodę sympleks.
Jedynym elementem nadającym się na centralny jest .
Po przekształceniach Gaussa - Jordana otrzymujemy:
ma rozwiązanie dopuszczalne
. 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 i wartość
.
2) wybieramy problem ”prawy” i ustalamy relaksację przez odrzucenie warunków
.
3) Rozwiązujemy relaksację problemu ”prawego”. .
Dodajemy ograniczenie
Teraz po dodaniu do pierwszego równania dodanego ograniczenia otrzymujemy nowe:
Zadanie ”prawe” zapisujemy w postaci tablicy sympleks:
i rozwiązujemy dualną metodą sympleks. Liczymy więc elementem centralnym jest
.
Po przekształceniach Gaussa - Jordana otrzymujemy:
Otrzymany wierzchołek optymalny nie jest dopuszczalny więc problem dzielimy na nowe podproblemy względem zmiennej
i idziemy do 1).
1) Lista zawiera podproblemy ”prawy,lewy”-
i ”prawy,prawy”'-
. Sukcesor zawiera punkt
i wartość
.
2) Wybieramy problem i ustalamy relaksację przez odrzucenie warunków
.
3) Rozwiązujemy relaksację problemu .
Dodajemy ograniczenie
.
Otrzymujemy zadanie opisane tablicą:
i rozwiązujemy dualną metodą sympleks. Liczymy więc elementem centralnym jest
.
Po przekształceniach Gaussa - Jordana otrzymujemy:
Otrzymany wierzchołek optymalny 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
ma wartość mniejszą niż sukcesor. Stosując kryterium KZ3 zamykamy problem. Idziemy do 1).
1) Lista zawiera podproblem ”prawy,prawy”'-
. Sukcesor zawiera punkt
i wartość
.
2) Wybieramy problem i ustalamy relaksację przez odrzucenie warunków
.
3) Rozwiązujemy relaksację problemu .
Dodajemy ograniczenie
.
Otrzymujemy zadanie opisane tablicą:
Otrzymaliśmy sprzeczność bo ostanie równanie nie ma dodatnich rozwiązań. Zamykamy problem stosując kryterium KZ1. Idziemy do 1).
1) Lista pusta. Sukcesor zawiera punkt
i wartość
. Rozwiązanie jest zawarte w sukcesorze.
Metoda podziału Dakina w przypadku gdy po usunięciu warunków całkowitoliczbowych otrzymujemy ograniczony obszar dopuszczalny.
Metoda podziału Dakina jest skuteczna gdy tylko część zmiennych jest całkowitoliczbowa.
Metodą 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.
Niech t= i rozwiązujemy zadanie dopisując równanie
do tablicy.
przekształcenia polegają na wyborze elementu centralnego
i dzielimy na dwa podproblemy
1) - element centralny
2) element centralny - jakiś
z kolumny j
Rozwiązujemy zadanie P.
Ustalmy parametr i rozwiązujmy zadanie
Wtedy maksymalna wartość jest równa maksymalnej wartości
i punkty optymalne obu zadań pokrywają się.
Budujemy więc tablicę sympleks i zadanie dzielimy na podproblemy w zależności od parametru .
Jeżeli
to zadanie jest sprzeczne.
Jeżeli
to element centralny leży w ostatnim wierszu.
i po przekształceniach Gaussa - Jordana otrzymujemy:
Punktem optymalnym jest , maksymalną wartością
jest
. Zatem
przyjmuje wartość
. Wartość
rośnie ze wzrostem
i przyjmuje maksymalną wartość dla
wynoszącą
Tym razem elementem centralnym jest 2.
i po przekształceniach Gaussa - Jordana otrzymujemy:
Punktem optymalnym jest , maksymalną wartością
jest
. Zatem
przyjmuje wartość
. Wartość
maleje ze wzrostem
i zawsze jest mniejsza niż
.
Rozwiązanie zadania ,
otrzymaliśmy w podproblemie
.
Stosując podział Dekina rozwiąż w liczbach całkowitych zadanie:
Min , gdy
,
.
Stosując podział Dekina rozwiąż w liczbach całkowitych zadanie:
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.