[ Pobierz całość w formacie PDF ]
.Zbiór wszystkich rozwiązań (D) dzieli się sukcesywnie na mniejsze podzbiory (podział) a dla każdego podzbioru oblicza się kres dolny czyli oszacowanie z dołu wartości funkcji celu (minimalizacja).W kolejnych krokach dokonujemy podziału tych zbiorów, które mają najmniejszą wartość kresu dolnego (minimalizacja).Podział postępuje do chwili znalezienia rozwiązania dopuszczalnego, dla którego wartość funkcji celu jest nie większa niż najmniejsze dolne ograniczenie wszystkich nie podzielonych podzbiorów (ograniczenie).W najgorszym przypadku należy sprawdzić wszystkie rozwiązania, co przesądza o wykładniczej złożoności obliczeniowej tej metody.Dla wyliczenia kresów dolnych (minimalizacja) należy zdefiniować funkcję ograniczającą „w”.Musi ona spełniać następujące warunki (minimalizacja):Efektywność metody podziału i ograniczeń zależy od jakości oszacowań kresów dla każdego podzbioru.Im te oszacowania są dokładniejsze, tym mniej potrzeba podziałów.Idealna funkcja ograniczająca jest następująca:Metodę podziału i ograniczeń wykorzystuje się z powodzeniem do rozwiązywania szerokiej klasy zadań o charakterze kombinatorycznym: programowanie całkowitoliczbowe, szeregowanie zadań niepodzielnych, problem komiwojażera, problem lokalizacji, problem plecakowy, problem przydziału i inne.lAlgorytmlNiech D będzie skończonym zbiorem rozwiązań dopuszczalnych.Przez L(D') oznaczymy dolną granicę wartości funkcji celu f na pewnym podzbiorze D' zbioru rozwiązań D (w szczególności D'=D) a przez k numer kroku podziałowego.Krok 1.Oblicz L(D).Jeśli uda się znaleźć takie rozwiązanie x, że f(x)=L(D), to x jest rozwiązaniem optymalnym.W przeciwnym razie podziel według określonego sposobu zbiór D na skończoną liczbę podzbiorów:podstaw k:=1 i przejdź do kroku 2.Krok 2.Oblicz.Jeśli przy tym uda się znaleźć takie rozwiązanie x, że dla danego r (1<=r<=rk) i , i=1.rk, to x jest rozwiązaniem optymalnym.W przeciwnym razie wybierz podzbiór według zasady:i podziel go na skończoną liczbę (zwykle rozłącznych) podzbiorówKrok 3.Wszystkie nie podzielone dotąd podzbioryoznacz przezpodstaw k:=k+1 i wróć do kroku 2.Do realizacji opisanego schematu metody podziału i ograniczeń jest konieczne skonkretyzowanielzasady podziałullwyznaczania dolnych ograniczeńllznajdowania rozwiązanialNależy zwrócić uwagę na sposób realizacji zasady wyboru podzbioru do podziału (krok 2).Zamiast sprawdzania dolnych ograniczeń wszystkich nie podzielonych podzbiorów, można ograniczyć się do podzbiorów wynikających z ostatniego podziału.Zaletą pierwszego sposobu (na ogół) jest mniejsza liczba podziałów, potrzebny jest jednak większy obszar pamięci do przechowywania informacji o wszystkich nie podzielonych podzbiorach.Drugi sposób to na ogół większa liczba podziałów lecz mniejsza zajętość pamięci.lPrzykładlDany jest zbiór „m” różnych wyrobów, z których każdy może być produkowany na jednym z „m” stanowisk produkcyjnych.Każde ze stanowisk ma różną wydajność przy produkcji każdego z wyrobów.Wydajność i-tego stanowiska przy produkcji j-tego wyrobu jest równa cij, a ponadto każde ze stanowisk ma produkować dokładnie jeden wyrób i każdy z wyrobów ma być produkowany na dokładnie jednym stanowisku.Należy przydzielić wyroby do stanowisk, by łączna wydajność była maksymalizowana.Problem ten nazywa się problemem przydziału i można zapisać go formalnie w sposób następujący:Problem przydziału jest szczególnym przypadkiem problemu transportowegoWYRÓB / STANOWISKO1234A21097B154148C13141611D415139lProblem komiwojażera - Algorytm Little'alMetoda podziału i ograniczeń może być zastosowana dla rozwiązania problemu komiwojażera.Algorytm został podany przez Little'a.Zbiór rozwiązań (wierzchołek w drzewie poszukiwań) będziemy rozbijać na dwa podzbiory:lzawierający wyróżniony łuk <i,j>llnie zawierający łuku <i,j>lPodział będzie dokonywany z pewną zasadą heurystyczną, opisaną poniżej.Po wykonaniu podziału liczone są kresy dolne na drodze redukcji macierzy kosztów przejść.Podzbiory rozwiązań mające wartości kresów dolnych większe lub równe długości najkrótszego dotychczas znalezionego rozwiązania będą pomijane (ograniczamy w ten sposób przestrzeń poszukiwań).Przykład:Dana jest macierz kosztów przejść „C” („∞” oznacza koszt o nieskończonej wartości):Macierz C12341∞27327∞85394∞64385∞Niech G0 oznacza początkowy zbiór rozwiązań [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl centka.pev.pl
.Zbiór wszystkich rozwiązań (D) dzieli się sukcesywnie na mniejsze podzbiory (podział) a dla każdego podzbioru oblicza się kres dolny czyli oszacowanie z dołu wartości funkcji celu (minimalizacja).W kolejnych krokach dokonujemy podziału tych zbiorów, które mają najmniejszą wartość kresu dolnego (minimalizacja).Podział postępuje do chwili znalezienia rozwiązania dopuszczalnego, dla którego wartość funkcji celu jest nie większa niż najmniejsze dolne ograniczenie wszystkich nie podzielonych podzbiorów (ograniczenie).W najgorszym przypadku należy sprawdzić wszystkie rozwiązania, co przesądza o wykładniczej złożoności obliczeniowej tej metody.Dla wyliczenia kresów dolnych (minimalizacja) należy zdefiniować funkcję ograniczającą „w”.Musi ona spełniać następujące warunki (minimalizacja):Efektywność metody podziału i ograniczeń zależy od jakości oszacowań kresów dla każdego podzbioru.Im te oszacowania są dokładniejsze, tym mniej potrzeba podziałów.Idealna funkcja ograniczająca jest następująca:Metodę podziału i ograniczeń wykorzystuje się z powodzeniem do rozwiązywania szerokiej klasy zadań o charakterze kombinatorycznym: programowanie całkowitoliczbowe, szeregowanie zadań niepodzielnych, problem komiwojażera, problem lokalizacji, problem plecakowy, problem przydziału i inne.lAlgorytmlNiech D będzie skończonym zbiorem rozwiązań dopuszczalnych.Przez L(D') oznaczymy dolną granicę wartości funkcji celu f na pewnym podzbiorze D' zbioru rozwiązań D (w szczególności D'=D) a przez k numer kroku podziałowego.Krok 1.Oblicz L(D).Jeśli uda się znaleźć takie rozwiązanie x, że f(x)=L(D), to x jest rozwiązaniem optymalnym.W przeciwnym razie podziel według określonego sposobu zbiór D na skończoną liczbę podzbiorów:podstaw k:=1 i przejdź do kroku 2.Krok 2.Oblicz.Jeśli przy tym uda się znaleźć takie rozwiązanie x, że dla danego r (1<=r<=rk) i , i=1.rk, to x jest rozwiązaniem optymalnym.W przeciwnym razie wybierz podzbiór według zasady:i podziel go na skończoną liczbę (zwykle rozłącznych) podzbiorówKrok 3.Wszystkie nie podzielone dotąd podzbioryoznacz przezpodstaw k:=k+1 i wróć do kroku 2.Do realizacji opisanego schematu metody podziału i ograniczeń jest konieczne skonkretyzowanielzasady podziałullwyznaczania dolnych ograniczeńllznajdowania rozwiązanialNależy zwrócić uwagę na sposób realizacji zasady wyboru podzbioru do podziału (krok 2).Zamiast sprawdzania dolnych ograniczeń wszystkich nie podzielonych podzbiorów, można ograniczyć się do podzbiorów wynikających z ostatniego podziału.Zaletą pierwszego sposobu (na ogół) jest mniejsza liczba podziałów, potrzebny jest jednak większy obszar pamięci do przechowywania informacji o wszystkich nie podzielonych podzbiorach.Drugi sposób to na ogół większa liczba podziałów lecz mniejsza zajętość pamięci.lPrzykładlDany jest zbiór „m” różnych wyrobów, z których każdy może być produkowany na jednym z „m” stanowisk produkcyjnych.Każde ze stanowisk ma różną wydajność przy produkcji każdego z wyrobów.Wydajność i-tego stanowiska przy produkcji j-tego wyrobu jest równa cij, a ponadto każde ze stanowisk ma produkować dokładnie jeden wyrób i każdy z wyrobów ma być produkowany na dokładnie jednym stanowisku.Należy przydzielić wyroby do stanowisk, by łączna wydajność była maksymalizowana.Problem ten nazywa się problemem przydziału i można zapisać go formalnie w sposób następujący:Problem przydziału jest szczególnym przypadkiem problemu transportowegoWYRÓB / STANOWISKO1234A21097B154148C13141611D415139lProblem komiwojażera - Algorytm Little'alMetoda podziału i ograniczeń może być zastosowana dla rozwiązania problemu komiwojażera.Algorytm został podany przez Little'a.Zbiór rozwiązań (wierzchołek w drzewie poszukiwań) będziemy rozbijać na dwa podzbiory:lzawierający wyróżniony łuk <i,j>llnie zawierający łuku <i,j>lPodział będzie dokonywany z pewną zasadą heurystyczną, opisaną poniżej.Po wykonaniu podziału liczone są kresy dolne na drodze redukcji macierzy kosztów przejść.Podzbiory rozwiązań mające wartości kresów dolnych większe lub równe długości najkrótszego dotychczas znalezionego rozwiązania będą pomijane (ograniczamy w ten sposób przestrzeń poszukiwań).Przykład:Dana jest macierz kosztów przejść „C” („∞” oznacza koszt o nieskończonej wartości):Macierz C12341∞27327∞85394∞64385∞Niech G0 oznacza początkowy zbiór rozwiązań [ Pobierz całość w formacie PDF ]