• dom
  •  > 
  • Edukacja i nauka
  •  > 
  • Różnica w skróconej gałęzi i metodzie związanej. Model matematyczny problemu

Różnica w skróconej gałęzi i metodzie związanej. Model matematyczny problemu

Metoda rozgałęzienia i wiązania opiera się na idei sekwencyjnego podziału zbioru dopuszczalne rozwiązania na podzbiory. Na każdym etapie metody sprawdzane są elementy podziału w celu ustalenia, czy dany podzbiór zawiera rozwiązanie optymalne, czy też nie. Aby to zrobić, oblicz dolną granicę funkcja celu na tym podzbiorze.

Jeżeli dolne oszacowanie jest nie mniejsze niż rekord (znalezione najlepsze rozwiązanie), podzbiór może nie być już brany pod uwagę. Sprawdzony podzbiór można również odrzucić, jeżeli uda się w nim znaleźć najlepsze rozwiązanie. Jeżeli wartość funkcji celu w znalezionym rozwiązaniu jest mniejsza od rekordu, wówczas rekord ulega zmianie. Na końcu algorytmu rekordem jest wynik jego pracy. Jeśli możliwe jest odrzucenie wszystkich elementów partycji, wówczas rekord jest optymalnym rozwiązaniem problemu. W przeciwnym razie z nieodrzuconych podzbiorów wybierany jest najbardziej obiecujący (na przykład o najniższej wartości). niższy szacunek) i jest podzielony. Nowe podzbiory są ponownie sprawdzane itp. Obliczenie dolnej granicy to najważniejszy element tego schematu.

Dla każdego konkretnego zadania programowanie całkowite(innymi słowy optymalizacja dyskretna) metoda rozgałęzienia i powiązania jest implementowana na swój własny sposób. Istnieje wiele modyfikacji tej metody.

Rozważmy implementację metody rozgałęzienia i wiązania dla problemu komiwojażera i problemu plecakowego.

Rozważmy algorytm Little'a (metodą rozgałęzienia i wiązania) dla problemu komiwojażera. Pomysł można sformułować następująco. W każdym wierszu macierzy odległości znajduje się element minimalny i odejmuje się go od wszystkich elementów odpowiedniego wiersza. Rezultatem jest macierz zmniejszana wiersz po rzędzie. Matrycę pokazano podobnie w kolumnach. Wynikiem jest macierz przedstawiona w wierszach i kolumnach. Sumując elementy minimalne podczas redukcji, otrzymujemy stałą redukcji, która będzie dolną granicą zbioru wszystkich dopuszczalnych konturów Hamiltona. Następnie wyznaczane są stopnie zer dla danej macierzy (suma minimalnych elementów wiersza i kolumny odpowiadających temu zerowi) i wybierany jest łuk, dla którego stopień elementu zerowego osiąga maksymalna wartość. Zbiór wszystkich konturów Hamiltona jest podzielony na dwa podzbiory, z których jeden zawiera łuk, drugi nie zawiera tego łuku. Następnie podaje się powstałe macierze krzywych Hamiltona i porównuje dolne granice podzbioru krzywych Hamiltona w celu wybrania zbioru z mniejszą dolną granicą do dalszego podziału. Procesowi podziału zbiorów na podzbiory towarzyszy konstrukcja drzewa rozgałęzionego. Porównując długość konturu Hamiltona z dolnymi granicami zwisających gałęzi, do dalszego rozgałęziania wybierany jest podzbiór z dolną granicą mniejszą od powstałego konturu, aż do uzyskania trasy z najkrótsza długość lub nie staje się jasne, że taka trasa nie istnieje.



Przykład.

Niech problem komiwojażera będzie przedstawiony w postaci następującej macierzy kosztów podróży

Znajdujemy element minimalny w każdym wierszu macierzy i odejmujemy go od wszystkich elementów odpowiedniego wiersza. Otrzymujemy macierz redukowaną rząd po rzędzie z elementami

.

Jeśli macierz, podawana wiersz po wierszu, zawiera kolumny niezawierające zera, to redukujemy ją po kolumnie. Aby to zrobić, wybierz minimalny element w każdej kolumnie macierzy i odejmij go od wszystkich elementów odpowiedniej kolumny. Zdobądźmy macierz

,

każdy wiersz i kolumna zawierająca co najmniej jedno zero. Taka macierz nazywana jest zredukowaną przez wiersze i kolumny.

Sumując elementy i , otrzymujemy stałą redukcji:

.

Znajdujemy potęgi zer dla macierzy podanej w wierszach i kolumnach. Aby to zrobić, zastąp w pamięci zera w macierzy znakiem i znajdź sumę minimalnych elementów wiersza i kolumny odpowiadających temu zerowi. Piszemy to po prawej stronie górny róg komórki:

.

Wybieramy łuk, dla którego stopień elementu zerowego osiąga wartość maksymalną

Zbiór wszystkich prawidłowych tras dzielimy na dwa podzbiory:

– podzbiór zawierający łuk;

– podzbiór niezawierający łuku

Aby obliczyć kosztorys dla tras zawierających łuk, przekreślamy wiersz i kolumnę w macierzy, a element symetryczny zastępujemy znakiem . Otrzymaną macierz prezentujemy i obliczamy sumę stałych redukcji.

Metoda rozgałęziona i związana jest jedną z metod kombinatorycznych. W przeciwieństwie do metody Gomoriego ma ona zastosowanie zarówno do problemów całkowicie, jak i częściowo całkowitych.

Jego istota polega na uporządkowanym wyborze opcji i uwzględnianiu tylko tych z nich, które według określonych kryteriów okazują się przydatne do znalezienia optymalnego rozwiązania.

Pomysł metoda rozgałęziona i związana ma następującą postać: niech osłabiony problem zostanie rozwiązany bez ograniczenia liczby całkowitej i jest zmienną całkowitą, której wartość w planie optymalnym jest ułamkowa. Potem przerwa

nie zawiera dopuszczalnych rozwiązań o współrzędnych całkowitych . Dlatego prawidłową wartością całkowitą jest musi zadowolić

Lub
, Lub

Wprowadzenie tych warunków do problemu generuje dwa niezwiązane ze sobą problemy o tej samej funkcji celu, ale nie nakładających się na siebie obszarach dopuszczalnych wartości zmiennych. W tym przypadku mówi się, że zadanie zostało rozwidlone.

Oczywiście możliwy jest jeden z czterech poniższych przypadków.

    Jeden z problemów jest nierozwiązywalny, a drugi ma optymalny plan całkowity. Wtedy ten plan i wartość funkcji celu na nim dają rozwiązanie oryginalny problem.

    Jeden z problemów jest nierozwiązywalny, a drugi ma optymalny plan, którego składnikami jest liczby ułamkowe. Następnie rozważamy drugi problem i w jego optymalnym planie wybieramy jeden ze składników, którego wartość jest równa liczbie ułamkowej, i konstruujemy dwa problemy dotyczące nowych ograniczeń tej zmiennej, otrzymanych przez podzielenie jej wartości całkowitych najbliższych do rozwiązania.

    Obydwa problemy są do rozwiązania. Jeden z problemów ma optymalny plan całkowity, a optymalny plan drugiego problemu ma liczby ułamkowe. Następnie obliczamy wartości funkcji celu na tych planach i porównujemy je ze sobą. Dla pewności zakładamy tutaj i poniżej, że problem maksimum funkcji celu jest rozwiązany. Jeżeli na planie całkowitym optymalnym wartość funkcji celu jest większa lub równa jej wartości na planie, którego składowymi są liczby ułamkowe, to ten plan całkowity jest optymalny dla pierwotnego problemu i wraz z wartością funkcji celu na daje pożądane rozwiązanie.

Jeśli wartość funkcji celu jest większa w planie, którego składowymi są liczby ułamkowe, należy wziąć jedną z tych liczb i dla problemu, którego plan jest rozważany, rozgałęzić się wzdłuż zmiennej ułamkowej i skonstruować dwie nowe problemy.

    Obydwa problemy są rozwiązywalne, a optymalne plany dla obu problemów obejmują liczby ułamkowe. Następnie obliczamy wartość funkcji celu na tych optymalnych planach i rozważamy problem, dla którego wartość funkcji celu jest największa. W optymalnym planie tego problemu wybieramy jeden ze składników, którego wartość jest liczbą ułamkową i rozgałęziamy na dwa nowe problemy, dzieląc zakres zmian tej zmiennej na dwa, ograniczony liczbami całkowitymi po prawej i lewej stronie odpowiednio.

Zatem proces konstruowania coraz większej liczby nowych zadań można przedstawić na rysunku w postaci rozgałęzionego drzewa, z wierzchołkiem oznaczonym jako „zadanie 1” i gałęziami odchodzącymi od tego wierzchołka. Ta sekwencja działań podczas wyszukiwania optymalne rozwiązanie Problem programowania liczb całkowitych znajduje odzwierciedlenie w nazwie tej metody.

Pierwotny wierzchołek odpowiada optymalnemu planowi pierwotnego problemu 1, a każdy wierzchołek połączony z nim gałęzią odpowiada optymalnym planom nowych problemów skonstruowanych dla nowych ograniczeń jednej ze zmiennych, które mają wartość w postaci ułamka numer w optymalnym planie zadania 1.

Każdy z wierzchołków ma swoje gałęzie i na każdym kroku wybierany jest wierzchołek, dla którego wartość funkcji celu jest największa.

Jeśli na pewnym etapie otrzymany zostanie plan o wartościach całkowitych, a wartość funkcji na nim okaże się większa lub równa wartości funkcji na innych wierzchołkach możliwych do rozgałęzienia, to plan ten jest planem optymalnym dla pierwotnego problemu programowania liczb całkowitych i wartość funkcji celu na nim jest maksymalna.

Przykład. Znajdź rozgałęzione rozwiązanie problemu programowania liczb całkowitych

Rozwiązanie. Znalezienie optymalnego planu dla sformułowanego problemu metoda simplex bez uwzględnienia całkowitego charakteru zmiennych, a mianowicie rozwiązujemy problem 1.

Optymalny plan zadania 1 Programowanie liniowe

Na
.

Dla pierwotnego problemu, biorąc pod uwagę całkowity charakter zmiennych, otrzymane rozwiązanie nie jest optymalne.

Aby znaleźć rozwiązanie optymalne w liczbie całkowitej, dzielimy przedział zmienności zmiennej X 1 na dwa obszary, tj X 1  i X 1 = 10 i podzielmy to dane zadanie na dwa nowe zadania.

Konkluzja funkcja liniowa nie zostało zmienione: Z 0 = 0. Jeden z problemów, np. problem 3, rozwiązujemy metodą sympleksową. Uważamy, że przesłanki problemu są sprzeczne.

Zadanie 2 rozwiązujemy metodą simplex. Otrzymujemy optymalny plan całkowity dla zadania 2, który jest jednocześnie optymalnym planem dla zadania 1:

Na
.

Zatem w wyniku jednego rozgałęzienia problemu znaleziono jego optymalne rozwiązanie.

Poniżej znajduje się opis problemu i część tekstowa rozwiązania. Całe rozwiązanie jest formacie dokumentu w archiwum, możesz pobrać. Niektóre znaki mogą nie pojawiać się na stronie, ale dokument słowny wszystko jest wyświetlane. Więcej przykładów prac nad EMMM można obejrzeć

SFORMUŁOWANIE PROBLEMU

Wydawnictwo musi wykonać pracę maszynową w ciągu tygodnia (liczba dni m = 5) przy pomocy pracowników n kategorii (wysoka, średnia, poniżej średniej, niska). Należy określić optymalną liczbę pracowników według kategorii, która zapewni wykonanie pracy przy minimalnych wydatkach funduszu płac przy danych ograniczeniach. Dane wyjściowe przedstawiono w tabelach 1 i 2.

Tabela 1

Tabela 2

Zadanie należy rozwiązać przy użyciu metody programowania liniowego na liczbach całkowitych w programie Mathcad 2000/2001.

BUDOWA MODELU MATEMATYCZNEGO
ROZWIĄZANIAZADANIA

Aby obliczyć optymalną liczbę pracowników, zapewniającą minimalne wydatki funduszu wynagrodzeń, opracowuje się matematyczny model programowania liniowego liczb całkowitych, ponieważ liczba pracowników nie może być wartością ułamkową.

Rozwiązywanie problemu programowania liczb całkowitych odbywa się w dwóch etapach.

W pierwszym etapie realizowane jest zadanie programowania liniowego bez uwzględnienia liczby całkowitej.

Na drugim etapie jest on wykonywany proces krok po kroku zastąpienie zmiennych niecałkowitych najbliższą górną lub dolną wartością całkowitą.

Po pierwsze, problem rozwiązano bez uwzględnienia warunku całkowitego.

Funkcję celu określa wzór:

Gdzie Q- ogólny fundusz wynagrodzeń za wykonywanie pracy;

X 1 , X 2 , …, x rz- liczba pracowników według kategorii;

N - liczba kategorii pracowników;

C 1 , C 2 ,…, c n- stawka dziennego wynagrodzenia jednego pracownika według kategorii;

M- ilość dni roboczych w tygodniu, M = 5.

Funkcję celu można zapisać w postaci wektorowej:

Podczas rozwiązywania problemu należy przestrzegać następujących ograniczeń. Górna granica

X ≤ D (1)

określa maksymalną liczbę pracowników w poszczególnych kategoriach, gdzie d jest wektorem określającym liczbę pracowników w poszczególnych kategoriach.

W ograniczeniu

Bierze się pod uwagę, że łączna liczba pracowników nie powinna przekraczać k maks.

W ograniczeniu od dołu

R× x≥P(3)

przyjmuje się, że wszyscy pracownicy razem muszą wykonać określoną ilość pracy R.

Jako ostatnie ograniczenie zapisano warunek nieujemności wektora zmiennych

X≥0 (4)

Model matematyczny rozwiązanie problemu bez uwzględnienia warunku całkowitego obejmuje następujące wyrażenia:

X ≤ D

R× x≥P,

X ≥ 0 .

Model programowania liczb całkowitych musi zawierać wyrażenia (5), a także dodatkowe ograniczenia dotyczące zmiennych niecałkowitych X są zastępowane wartościami całkowitymi. Konkretne wyrażenia modelu ze zmiennymi całkowitymi zostały omówione w następnym podrozdziale.

ROZWIĄZANIE PROBLEMU OPTYMALIZACJI WMATHCAD

Dane źródłowe dla przykładu podano w tabeli. 1 i 2.

Aby rozwiązać problem, użyj pakietu Mathcad z funkcją Minimalizuj. Ta funkcja wyznacza wektor rozwiązania problemu:

X:= Minimalizuj ( Q, X),

Gdzie Q— wyrażenie funkcji celu wyznaczającej fundusz płacy minimalnej, X- wektor zmiennych.

Po pierwsze, problem rozwiązano bez uwzględnienia warunku całkowitego. Rozwiązanie to podano w Załączniku 1. Pierwsza linia zawiera zerowe wartości początkowe wektora X i funkcja celu Q(X) . Po słowie Biorąc i przed funkcją Minimalizuj wskazane są ograniczenia. W rezultacie uzyskano niecałkowitą optymalną liczbę według kategorii:

X =

z funduszem wynagrodzeń Q= 135 cu. mi.

Z ta decyzja usytuowany rozwiązanie całkowite metoda rozgałęziona i związana.

Najpierw powstałe rozwiązanie analizuje wartość ułamkową x 4 =
= 1,143. Można dla niego ustawić dwie wartości całkowite: x 4 = 1 i x 4 = 2. Rozpoczyna się konstrukcja drzewa decyzyjnego (Załącznik 2). Początkowy węzeł zerowy jest odkładany na drzewie decyzyjnym. Łączy się go wówczas pierwszym węzłem x4 i z tego węzła rysuje się dwie gałęzie odpowiadające więzom: x4 = 1 i x4 = 2.

Dla gałęzi z ograniczeniem x 4 = 1 rozwiązuje się zadanie programowania liniowego podane w Załączniku 1, biorąc pod uwagę to ograniczenie.

W rezultacie uzyskano rozwiązanie tego problemu. Zmienna x 1 stała się liczbą całkowitą, ale zmienna x 2 stała się liczbą ułamkową x 2 = 0,9.

Aby kontynuować rozgałęzienie, tworzone są węzeł x 3 i rozgałęzienie x 3 = 1. Problem programowania liniowego jest ponownie wykonywany ze wszystkimi trzema ograniczeniami: x 4 = 1, x 2 = 1, x 3 = 1. Przy tych ograniczeniach problem ma rozwiązanie x T =
= (1,938 1 1 1).

Aby kontynuować rozgałęzienie, tworzony jest węzeł x 1 i gałąź x 1 = 2. Problem programowania liniowego jest wykonywany ponownie ze wszystkimi trzema ograniczeniami: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2 Przy tych ograniczeniach problem ma rozwiązanie x T = = (2 1 1 1).

Proces konstruowania drzewa rozwiązań i wykonywania zadania programowania liniowego jest powtarzany aż do zbudowania wszystkich gałęzi.

Dodatek 2 przedstawia kompletne drzewo możliwych rozwiązań całkowitych, z którego wynika, że ​​problem ma 4 efektywne rozwiązania.

Spośród efektywnych wybiera się najlepsze i przyjmuje się je jako optymalne rozwiązanie całkowite całego problemu o wartości minimalnej Q(X) . W naszym przypadku mamy dwa optymalne rozwiązania całkowite

Q(X) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Dlatego do pisania tekstu organizacja wydawnicza musi zatrudnić dwóch pracowników wysokiej kategorii, jednego pracownika średniej kategorii, jednego pracownika niższej kategorii średniej i jednego pracownika niskiej kategorii. Możliwa jest również inna równoważna opcja przyciągnięcia pracowników: jeden pracownik wysokiej kategorii, jeden pracownik średniej kategorii, dwóch pracowników poniżej średniej kategorii i dwóch pracowników niskiej kategorii. W obu opcjach koszty będą minimalne i wyniosą 140 den. jednostki

Pobierz rozwiązanie problemu:


Nazwa pliku: 2.rar
Rozmiar pliku: 24,99 Kb

Jeśli pobieranie pliku nie rozpocznie się po 10 sekundach, kliknij


Wstęp

Duża klasa stosowanych problemów optymalizacyjnych sprowadza się do problemów programowania całkowitoliczbowego. Aby rozwiązać te problemy, powszechnie stosuje się metody kombinatoryczne oparte na uporządkowanym poszukiwaniu najbardziej obiecujących opcji. Metody rozwiązywania kombinatorycznych można podzielić na dwie grupy: metody Programowanie dynamiczne oraz metody rozgałęzione i powiązane.

Przy rozwiązywaniu problemów optymalizacji wielowymiarowej proponuje się łączne zastosowanie metod rozgałęzionych i powiązanych oraz programowania dynamicznego. W pierwszym etapie problem rozwiązuje się metodą programowania dynamicznego oddzielnie dla każdego z ograniczeń. Ciągi otrzymane w wyniku rozwiązania równania funkcyjnego programowania dynamicznego służą następnie do oszacowania górnej (dolnej) granicy funkcji celu. W drugim etapie problem rozwiązuje się metodą rozgałęzienia i wiązania. Przy stosowaniu tej metody określa się metodę podziału całego zestawu ważnych opcji na podzbiory, czyli metodę konstruowania drzewa możliwe opcje oraz sposób szacowania górnej granicy funkcji celu.

Zintegrowane zastosowanie programowania dynamicznego i metod rozgałęzionych pozwala na zwiększenie efektywności rozwiązywania dyskretnych problemów optymalizacyjnych. Przy rozwiązywaniu problemów wielowymiarowych, w celu zmniejszenia wyrazów optymalnej sekwencji, używamy dodatkowe warunki obrzynek.

1. Odniesienie historyczne

Metoda rozgałęzień i wiązań została po raz pierwszy zaproponowana przez Landa i Doiga w 1960 roku wspólne zadanie Całkowite programowanie liniowe. Zainteresowanie tą metodą, a właściwie jej „odrodzenie” wiąże się z pracami Little’a, Murthy’ego, Sweeneya i Carell’a nad problemem komiwojażera. Od tego momentu to się pojawiło duża liczba prace poświęcone metodzie rozgałęzionej i związanej oraz jej różnym modyfikacjom. Tak duży sukces tłumaczy się tym, że autorzy jako pierwsi zwrócili uwagę na szerokość możliwości metody, zwrócili uwagę na wagę wykorzystania specyfiki problemu i sami wykorzystali specyfikę problemu komiwojażera.

Metoda ta jest najbardziej ogólną spośród wszystkich metod programowania dyskretnego i nie ma zasadniczych ograniczeń w zastosowaniu. Algorytm rozgałęziony jest efektywną procedurą wyliczania wszystkich dopuszczalnych rozwiązań w postaci liczb całkowitych.

Metoda rozgałęziona i związana jest jedną z metod kombinatorycznych. Jego istota polega na uporządkowanym wyborze opcji i uwzględnianiu tylko tych, które według określonych kryteriów okażą się obiecujące, i odrzucaniu opcji mało obiecujących.

2. Opis metody

Metoda rozgałęzień i wiązania opiera się na idei sekwencyjnego dzielenia zbioru możliwych rozwiązań na podzbiory. Na każdym etapie metody sprawdzane są elementy podziału w celu ustalenia, czy dany podzbiór zawiera rozwiązanie optymalne, czy też nie. Weryfikację przeprowadza się poprzez obliczenie dolnego oszacowania funkcji celu na danym podzbiorze. Jeżeli dolna ocena jest nie mniejsza niż nagrywać- najlepsze znalezione rozwiązanie, wówczas podzbiór można odrzucić. Sprawdzony podzbiór można również odrzucić, jeżeli uda się w nim znaleźć najlepsze rozwiązanie. Jeżeli wartość funkcji celu w znalezionym rozwiązaniu jest mniejsza od rekordu, wówczas rekord ulega zmianie. Na końcu algorytmu rekordem jest wynik jego pracy.

Jeśli możliwe jest odrzucenie wszystkich elementów partycji, wówczas rekord jest optymalnym rozwiązaniem problemu. W przeciwnym razie spośród nieodrzuconych podzbiorów (na przykład z najniższą dolną wartością graniczną) wybierany jest najbardziej obiecujący i dzielony. Nowe podzbiory są ponownie sprawdzane itp.

Stosując metodę rozgałęzienia i wiązania do każdego konkretnego problemu, należy przede wszystkim określić jego dwie najważniejsze procedury: 1) rozgałęzienie zbioru możliwe rozwiązania; 2) obliczenie dolnych i górnych oszacowań funkcji celu.

2.1 Zasady rozgałęziania

W zależności od charakterystyki zadania do organizacji rozgałęzień zwykle stosuje się jedną z dwóch metod:

1. rozgałęzienie zbioru dopuszczalnych rozwiązań pierwotnego problemu D;

2. rozgałęzienie zbioru D" otrzymanego z D poprzez usunięcie warunku całkowitego na zmiennych.

Pierwsza metoda rozgałęziania jest zwykle stosowana w przypadku problemów z programowaniem liczb całkowitych i polega na identyfikacji poddomen możliwych rozwiązań poprzez ustalenie wartości Poszczególne komponenty całkowite zmienne optymalizacyjne (ryc. 1). Na ryc. 1-a podaje geometryczną interpretację obszaru dopuszczalnych rozwiązań problemu programowania liczb całkowitych, wyznaczonego przez dwa ograniczenia liniowe i warunki nieujemności zmiennych oraz podobszary utworzone przez rozgałęzienie, a na ryc. Rysunek 1-b przedstawia odpowiedni schemat rozgałęzień.

Druga metoda rozgałęziania jest bardziej uniwersalna niż pierwsza. Aby przeprowadzić rozgałęzienie pewnego obszaru D i „w ten sposób na D i”, zostało to rozwiązane problem optymalizacji z funkcją celu pierwotnego problemu i zmiennymi rzeczywistymi.

Rozgałęzienie przeprowadza się, jeśli w rozwiązaniu optymalnym wartość przynajmniej jednej zmiennej całkowitej zgodnie z pierwotnym sformułowaniem problemu nie jest liczbą całkowitą. Spośród tych zmiennych wybierana jest jedna, na przykład j - i. Oznaczmy jego wartość w znalezionym rozwiązaniu optymalnym x 0 [j]. Mówią, że rozgałęzianie realizuje zmienna x[j]. Region D i " dzieli się na dwa podregiony D i1 " i D i2 " w następujący sposób:

Gdzie ] - cała część wartości x 0 [j]

Na ryc. 2 konwencjonalnie podaje geometryczną interpretację takiego rozgałęzienia.

Ryż. 2. Geometryczna interpretacja rozgałęzień

Można zauważyć, że w tym przypadku część pomiędzy płaszczyznami nowo wprowadzonych ograniczeń jest usuwana z obszaru D i ". Ponieważ zmienna x[j] zgodnie z warunkami obszaru dopuszczalnych rozwiązań pierwotnego problemu wynosi liczba całkowita, to z poddziedziny dopuszczalnych rozwiązań pierwotnego problemu.D i (D i D i ") z takim wyjątkiem żadna decyzja nie jest wykluczona.

2.2 Tworzenie dolnych i górnych oszacowań funkcji celu

Zanim przystąpimy do dyskusji na ten temat, należy stwierdzić, że ogólnie przyjęte jest stosowanie metody rozgałęzionej i powiązanej w przypadku problemu, w którym kierunek optymalizacji sprowadza się do postaci minimalizacji. Aby uczynić dalszą notację i obliczenia bardziej zwięzłą, napiszemy problem programowania dyskretnego, dla którego użyjemy metody rozgałęzienia i wiązania, w następującej uogólnionej formie:

gdzie x jest wektorem zmiennych optymalizacyjnych, z których część jest rzeczywista, a część jest liczbą całkowitą; f(x) - w ogólnym przypadku nieliniowa funkcja celu; D to obszar możliwych rozwiązań ogólnego problemu programowania dyskretnego.

Dolne estymaty docelowej dykcji, w zależności od wybranej metody rozgałęzienia, można wyznaczyć albo dla podobszarów D i D, albo dla podobszarów D i „D” (D i „ i D” otrzymuje się z odpowiednich zbiorów D i oraz D poprzez usunięcie warunki całkowitości dla zmiennych dyskretnych).
Dolnym oszacowaniem funkcji celu f(x) na zbiorze D i (lub D i ") będzie wielkość:

Obliczenie dolnych granic w każdym konkretnym przypadku można przeprowadzić, biorąc pod uwagę charakterystykę rozwiązywanego problemu. Jednocześnie, aby szacunki jak najskuteczniej spełniały swoją funkcję, muszą być jak największe, tj. być jak najbliżej rzeczywistych wartości min f(x). Jest to konieczne przede wszystkim, aby dolne estymatory jak najdokładniej odzwierciedlały rzeczywistą relację min f(x) na podzbiorach powstałych podczas rozgałęziania i pozwalały na dokładniejsze określenie kierunku dalszych poszukiwań optymalnego rozwiązania oryginalny problem.

Na ryc. Rysunek 3 przedstawia taki idealny przypadek, gdy dolne szacunki (połączone przerywaną linią przerywaną) prawidłowo odzwierciedlają zależności pomiędzy wartością rzeczywistą wartości minimalne f(x) (połączone linią przerywaną) dla czterech podzbiorów rozwiązań dopuszczalnych D 1, D 2, D 3, D 4.

Jeden z metody uniwersalne Obliczenie dolnych granic polega na rozwiązaniu następującego problemu:

Tak zdefiniowane O i jest dolnym oszacowaniem f(x) na D i (lub D i "), ponieważ D i D i ".

Jeśli przy rozwiązywaniu problemu (4) zostanie to ustalone, to dla ogólności to przyjmiemy.

Należy zwrócić uwagę na jedną ważną właściwość dolnych estymatorów, a mianowicie to, że ich wartości dla podzbiorów powstałych podczas rozgałęziania nie mogą być mniejsze od dolnego oszacowania funkcji celu na zbiorze poddawanym rozgałęzieniu.

Wraz z dolną granicą metoda rozgałęzienia i wiązania wykorzystuje górne granice f(x). Z reguły obliczana jest tylko jedna wartość górnej granicy, którą definiuje się jako wartość funkcji celu dla najlepiej znalezionego wykonalnego rozwiązania pierwotnego problemu. To górne oszacowanie jest czasami nazywane rekordem. Jeżeli dla rozwiązywanego problemu możliwe jest w prosty i dokładny sposób wyznaczyć górne granice f(x) dla poszczególnych zbiorów powstałych podczas rozgałęziania, to należy je zastosować w metodzie, aby zmniejszyć złożoność obliczeniową procesu rozwiązania. W przypadku stosowania pojedynczej górnej granicy przyjmuje się zwykle, że jej wartość początkowa jest równa nieskończoności (), chyba że z rozważań apriorycznych nie jest znane żadne możliwe rozwiązanie pierwotnego problemu. Przy znalezieniu pierwszego możliwego rozwiązania:

Następnie przy ustalaniu lepszego wykonalnego rozwiązania koryguje się górną granicę:

Zatem wartość górnego oszacowania może się jedynie zmniejszać w procesie rozwiązywania problemu.

2.3 Algorytm rozgałęziający i związany

Podstawowe zasady algorytmu można sformułować następująco:

1. W pierwszej kolejności rozgałęzieniu podlega podzbiór o liczbie odpowiadającej najniższej wartości dolnego oszacowania funkcji celu (I jest zbiorem liczb wszystkich podzbiorów, (lub) znajdujących się na końcach rozgałęzień i którego rozgałęzianie nie zostało jeszcze zatrzymane). Jeżeli zostanie zastosowany powyższy sposób rozgałęziania zbiorów, wówczas może pojawić się niejasność co do wyboru elementu, wzdłuż którego należy przeprowadzić kolejny etap rozgałęzienia. Niestety, kwestia „najlepszego” z ogólnego punktu widzenia sposobu takiego wyboru nie została jeszcze rozstrzygnięta, dlatego w konkretnych problemach stosuje się pewne reguły heurystyczne.

2. Jeżeli dla jakiegoś i-tego podzbioru warunek jest spełniony, to należy przerwać jego rozgałęzianie, gdyż potencjalne możliwości znalezienia dobra decyzja w tym podzbiorze (charakteryzuje je) okazują się gorsze od wartości funkcji celu dla rzeczywistej znalezionej przez w tym momencie czasie dopuszczalne rozwiązanie pierwotnego problemu (charakteryzuje).

3. Rozgałęzianie podzbioru kończy się w przypadku znalezienia optymalnego rozwiązania znalezionego w zadaniu (4). Jest to uzasadnione faktem, że nie ma zatem lepszego wykonalnego rozwiązania niż w tym podzbiorze. W takim przypadku rozważana jest możliwość dostosowania.

4. Jeżeli, gdzie, to spełnione są warunki optymalności dla najlepszego możliwego rozwiązania znalezionego w tym momencie. Uzasadnienie jest takie samo jak w ust. 2 niniejszego regulaminu.

5. Po znalezieniu przynajmniej jednego wykonalnego rozwiązania pierwotnego problemu można rozważyć możliwość zatrzymania algorytmu, oceniając bliskość najlepszego z wynikowych rozwiązań dopuszczalnych do optymalnego (na podstawie wartości funkcji celu ):

2.4 Rozwiązanie problemu metodą rozgałęzienia i wiązania

Cały .

Początkowo znajdujemy metodę simpleksową lub metodę sztuczna podstawa optymalny plan problemu bez uwzględnienia całkowitej liczby zmiennych.

Jeśli wśród składników tego planu nie ma liczb ułamkowych, wówczas znaleziono pożądane rozwiązanie tego problemu.

Jeśli wśród elementów planu znajdują się liczby ułamkowe, konieczne jest przejście do nowych planów, dopóki nie zostanie znalezione rozwiązanie problemu.

Metoda rozgałęzień opiera się na założeniu, że nasz optymalny projekt niecałkowity daje wartość funkcji większą niż jakikolwiek kolejny projekt rozgałęzienia.

Niech zmienna w planie będzie liczbą ułamkową. Wtedy w optymalnym planie jego wartość będzie wg co najmniej albo mniejsza lub równa najbliższej mniejszej liczbie całkowitej, albo większa lub równa najbliższej większej liczbie całkowitej.

Wyznaczając te liczby, znajdujemy rozwiązanie dwóch problemów programowania liniowego metodą simpleksową

- cały .

Cały .

Istnieją cztery możliwe przypadki rozwiązania tej pary problemów:

1. Jeden z problemów jest nierozwiązywalny, a drugi ma optymalny plan całkowity. Następnie ten plan i wartość funkcji celu zapewniają rozwiązanie pierwotnego problemu.

2. Jeden z problemów jest nierozwiązywalny, a drugi ma niecałkowity plan optymalny. Następnie rozważamy drugi problem i w jego optymalnym planie wybieramy jeden ze składników, którego wartość jest równa liczbie ułamkowej i konstruujemy dwa problemy podobne do poprzednich.

3. Obydwa problemy można rozwiązać. Jeden z problemów ma optymalny plan całkowity, a optymalny plan drugiego problemu ma liczby ułamkowe. Następnie obliczamy wartości funkcji celu z planów i porównujemy je ze sobą. Jeżeli na planie całkowitym optymalnym wartość funkcji celu jest większa lub równa jej wartości na planie, którego składowymi są liczby ułamkowe, to ten plan całkowity jest optymalny dla pierwotnego problemu i daje pożądane rozwiązanie.

4. Obydwa problemy są rozwiązywalne, a optymalne plany dla obu problemów uwzględniają liczby ułamkowe. Następnie rozważamy problem, dla którego wartość funkcji celu jest największa. I konstruujemy dwa zadania.

Zatem rozwiązując problem, otrzymujemy następujący diagram:

1. Znaleźć rozwiązanie problemu programowania liniowego bez uwzględnienia liczby całkowitej.

2. Tworzy dodatkowe ograniczenia części ułamkowej planu.

3. Znajdź rozwiązanie dwóch problemów z ograniczeniami komponentu.

4. W razie potrzeby konstruujemy dodatkowe ograniczenia, według możliwych czterech przypadków uzyskujemy optymalny plan liczb całkowitych lub ustalamy nierozwiązywalność problemu.

Przykład

Znajdźmy rozwiązanie problemu

Cały .

Rozwiązanie. Rozwiązanie bez uwzględnienia wartości całkowitej problemu znajdujemy metodą sympleksową.

Rozważmy następna para zadania:

Zadanie nr 1

i zadanie nr 2

Pierwszy problem ma optymalny plan

drugie jest nierozwiązywalne.

Sprawdzamy plan pierwszego zadania pod kątem rzetelności. Warunek ten nie jest spełniony, dlatego konstruujemy następujące zadania:

Zadanie nr 1.1

i zadanie nr 1.2

Problem nr 1.2 jest nierozwiązalny, a problem nr 1.1 ma optymalny plan, na którym funkcjonuje wartość celu.

W rezultacie odkryliśmy, że pierwotny problem programowania liczb całkowitych ma optymalny plan i.

3. Rozwiązywanie problemu komiwojażera metodą rozgałęzień i wiązań

Rozważmy teraz klasę stosowanych problemów optymalizacyjnych. W wielu z nich stosowana jest metoda rozgałęzień i wiązań. Proponuje się rozważenie jednego z najpopularniejszych problemów - problemu komiwojażera. Oto jego treść. Istnieje kilka miast połączonych w jakiś sposób drogami o określonej długości; należy ustalić, czy istnieje ścieżka, którą można odwiedzić każde miasto tylko raz i jednocześnie wrócić do miasta, z którego dana trasa się rozpoczęła („objazd komiwojażera”), a jeżeli taka ścieżka istnieje, ustalić najkrótszą z takich ścieżek.

3.1 Opis problemu

Sformalizujmy warunek w kategoriach teorii grafów. Miasta będą wierzchołkami grafu, a drogi pomiędzy miastami będą zorientowanymi (skierowanymi) krawędziami grafu, na każdej z nich dana funkcja wagi: Ciężar krawędzi to długość odpowiedniej drogi. Ścieżka, którą należy znaleźć, to zorientowany cykl rozpinający prosty o minimalnej wadze w digrafie (przypomnijmy: cykl nazywa się rozpinającym, jeśli przechodzi przez wszystkie wierzchołki grafu; cykl nazywa się prostym, jeśli przechodzi przez każdy ze swoich wierzchołki tylko raz; cykl nazywamy zorientowanym, jeśli początek każdej kolejnej krawędzi pokrywa się z końcem poprzedniej; waga cyklu to suma wag jego krawędzi; wreszcie dwuznak nazywamy pełnym, jeśli zawiera wszystkie możliwe krawędzie); takie cykle nazywane są również hamiltonianami.

Oczywiście pełny digraf zawiera cykle typu wskazanego powyżej. Zauważmy, że wystarczy rozważyć kwestię obecności cyklu Hamiltona w dwugrafie jako szczególny przypadek Problemy komiwojażera dla pełnych dwuznaków. Rzeczywiście, jeśli dany digraf nie jest kompletny, to można go uzupełnić do kompletności o brakujące krawędzie i każdej z dodanych krawędzi można przypisać wagę `, biorąc pod uwagę, że `` jest „nieskończonością komputerową”, tj. maksimum ze wszystkich możliwych liczb. Jeśli teraz w nowo skonstruowanym pełnym digrafie znajdziemy najlżejszy cykl Hamiltona, to jeśli ma on krawędzie z wagą , możemy powiedzieć, że w tym oryginalnym grafie nie ma „cyklu komiwojażera”. Jeśli w pełnym dwugrafie najlżejszy cykl Hamiltona okaże się mieć skończoną wagę, wówczas będzie to pożądany cykl na pierwotnym wykresie.

Wynika z tego, że wystarczy rozwiązać problem komiwojażera dla pełnych dwuznaków z funkcją wagi. Sformułujmy to teraz w ostatecznej formie:

niech będzie pełny Kierowany wykres i - funkcja wagi; znajdź prosty cykl zorientowany na rozpiętość („cykl komiwojażera”) o minimalnej wadze.

Niech konkretny skład zbioru wierzchołków będzie macierzą wag danego digrafu, tj. i dla każdego.

Rozważanie metody oddziału i wiązania w celu rozwiązania problemu komiwojażera najwygodniej przeprowadza się na tle konkretny przykład. Korzystając z wprowadzonej tutaj notacji, dokonamy tego opisu w następnym wykładzie.

Wprowadźmy kilka terminów. Niech będzie jakaś macierz numeryczna. Redukcja wiersza tej macierzy oznacza wybranie najmniejszego elementu w wierszu (nazywa się to stałą redukcji) i odjęcie go od wszystkich elementów tego wiersza. Oczywiście w rezultacie w tej linii minimalny element będzie wynosić zero, a wszystkie pozostałe elementy będą nieujemne. Podobne znaczenie mają słowa „podaj kolumnę macierzy”.

Słowa „przynieś macierz wiersz po rzędzie” oznaczają, że podane są wszystkie wiersze macierzy. Podobne znaczenie mają słowa „zmniejsz macierz o kolumny”.

Wreszcie słowa „zmniejsz macierz” oznaczają, że macierz jest najpierw redukowana o wiersze, a następnie o kolumny.

Waga elementu macierzy jest sumą stałych redukcyjnych macierzy, którą otrzymujemy z danej macierzy poprzez zastąpienie danego elementu przez ``. Dlatego słowa najcięższe zero w macierzy oznaczają, że obliczana jest waga każdego zera w macierzy, a następnie ustalane jest zero o maksymalnej wadze.

Przejdźmy teraz do opisu metody rozgałęzionej i powiązanej rozwiązania problemu komiwojażera.

Pierwszy krok. Naprawiamy zbiór wszystkich przejść komiwojażera (tj. wszystkich prostych zorientowanych cykli rozpinających). Ponieważ wykres jest kompletny, zbiór ten z pewnością nie jest pusty. Skojarzmy z nim liczbę, która będzie pełnić rolę wartości na tym zbiorze funkcji oceny: liczba ta jest równa sumie stałych redukcyjnych danej macierzy wag krawędzi grafu. Jeśli zbiór wszystkich rund komiwojażera oznaczymy przez G, to suma stałych redukcji macierzy wag będzie oznaczona przez j(G). Należy pamiętać o podanej macierzy wag dla tego wykresu; oznaczmy to przez M 1; Zatem wynik pierwszego kroku:

zbiór G wszystkich rund komiwojażera powiązany jest z liczbą j(G) i macierzą M 1 .

Drugi krok. Wybierzmy najcięższe zero w macierzy M 1; niech stoi w klatce; ustalamy krawędź grafu i dzielimy zbiór G na dwie części: część składającą się z przejść przechodzących przez krawędź i część składającą się z przejść, które nie przechodzą przez krawędź.

Powiążmy ze zbiorem następującą macierz M 1,1: w macierzy M 1 liczbę w komórce zastępujemy przez `. Następnie w powstałej macierzy skreślamy numer wiersza i i numer kolumny j, a pozostałe wiersze i kolumny zachowujemy z ich pierwotnymi numerami. Na koniec zredukujmy tę ostatnią macierz i zapamiętajmy sumę stałych redukcji. Powstała zredukowana macierz będzie macierzą M 1,1; Sumę właśnie zapamiętanych stałych redukcji dodajemy do j(G) i wynik, oznaczony dalej przez j(), jest porównywalny ze zbiorem.

Teraz ze zbiorem kojarzymy także pewną macierz M 1,2. W tym celu w macierzy M 1 zastępujemy liczbę w komórce przez `` i prezentujemy otrzymaną macierz. Zapamiętajmy sumę stałych redukcji i otrzymaną macierz oznaczmy przez M 1,2. Dodajmy zapamiętaną sumę stałych redukcji do liczby j(G) i otrzymana liczba, oznaczona dalej przez j(), będzie porównywalna ze zbiorem.

Wybierzmy teraz spośród zbiorów ten, na którym funkcja j jest minimalna (czyli zbiór odpowiadający mniejszej z liczb j() i j()).

Zauważmy teraz, że w powyższym rozumowaniu jako wyjściowy wykorzystano tylko jeden obiekt rzeczywisty – zredukowaną macierz wag danego dwuznaku. Za jego pomocą zidentyfikowano pewną krawędź grafu i skonstruowano nowe macierze, do których oczywiście można zastosować to samo.

Przy każdym takim powtórzeniu aplikacji rejestrowana będzie kolejna krawędź wykresu. Umówmy się Następna akcja: przed usunięciem wiersza i kolumny następnej macierzy należy zastąpić przez ` liczby we wszystkich komórkach odpowiadające krawędziom, które w oczywisty sposób nie należą do tych cykli Hamiltona, które przechodzą przez wybrane wcześniej krawędzie.

To samo powtórzymy dla wybranego zbioru z macierzą i powiązaną z nim liczbą j itd., o ile będzie to możliwe.

Udowodniono, że wynikiem jest zbiór składający się z pojedynczej rundy komiwojażera, którego waga jest równa kolejnej wartości funkcji j; zatem wszystkie warunki omówione przy opisie metody rozgałęzionej i powiązanej są spełnione.

Następnie rekord jest poprawiany aż do uzyskania ostatecznej odpowiedzi.

3.2 Stan problemu

Student Iwanow otrzymał zadanie dostarczenia kilku ważnych dokumentów z 12. budynku. Ale los chciał, że ma na to bardzo mało czasu i wciąż musi wracać. Musimy znaleźć najkrótszą ścieżkę. Odległości pomiędzy obiektami podano w tabeli

3.3 Model matematyczny problemu

Aby rozwiązać problem, przypisujemy do każdego punktu trasy konkretny numer: Budynek 12 - 1, Biały Dom - 2, KRK "Premier" - 3, Administracja - budynek 4 i 5 - 5. Odpowiednio łączna liczba punktów. Następnie wprowadzamy zmienne alternatywne, które przyjmują wartość 0, jeżeli w trasie nie jest uwzględnione przejście z i-tego do j-tego, oraz 1 w przeciwnym wypadku. Warunki dotarcia do każdego punktu i wyjścia z każdego punktu wyrażone są tylko raz przez równości (8) i (9).

Dla zapewnienia ciągłości trasy dodatkowo N zmienne i dodatkowe ograniczenia (10).

Całkowita długość trasy F, który należy zminimalizować, zostanie zapisany w następującej postaci:

W naszym przypadku warunki te zostaną zapisane w następującej formie:

3.4 Rozwiązanie problemu metodą rozgałęzienia i wiązania

zadanie granica oddziału komiwojażera

1) Analiza zbioru D.

Znajdźmy niższą ocenę N. W tym celu definiujemy macierz minimalnych odległości w wierszach (1, gdy odległość w rzędzie jest minimalna).

Podobnie definiujemy macierz minimalnych odległości wzdłuż słupów.

Wybierzmy początkowy plan: . Wtedy górna granica wynosi:

Oczywiście gdzie oznacza przejście od pierwszego punktu do j-tego. Rozważmy te podzbiory w kolejności.

2) Analiza podzbioru D 12 .

3) Analiza podzbioru D 13 .

4) Analiza podzbioru D 14 .

5) Analiza podzbioru D 15 .

6) Odsiewanie mało obiecujących podzbiorów.

Podzbiory D 13 i D 15 nie są obiecujące. Ponieważ , ale potem będziemy dalej rozważać podzbiór D 14.

7) Analiza podzbioru D 142 .

8) Analiza podzbioru D 143 .

9) Analiza podzbioru D 145 .

10) Odsiewanie mało obiecujących podzbiorów

Podzbiór D 143 nie jest obiecujący. Ponieważ , ale potem będziemy dalej rozważać podzbiór D 145.

11) Analiza podzbioru D 1452 .

12) Analiza podzbioru D 1453 .

Optymalne rozwiązanie: .

I tak trasa studenta: budynek 12 - Administracja - budynek 5 - Biały Dom - KRK Premier - budynek 12.

Bibliografia

1. Abramov L.A., Kapustin V.F. Programowanie matematyczne. - L.: Wydawnictwo Leningradzkiego Uniwersytetu Państwowego, 1981. -328 s.

2. Aleksiejew O.G. Zintegrowane zastosowanie dyskretnych metod optymalizacji. - M.: Nauka, 1987. -294 s.

3. Korbut A.A., Finkelgein Yu.Yu. Programowanie dyskretne. M.: Nauka. 1969. -240 s

4. Kuzniecow Yu.N. itp. Programowanie matematyczne: Instruktaż. - wyd. 2, poprawione i uzupełnione. - M.: Szkoła wyższa, 1980. -300 s.

5. Papadimitriou H., Steiglitz K. Optymalizacja kombinatoryczna. Algorytmy i złożoność. - M.: Mir, 1985. -213 s.

Podobne dokumenty

    Metody rozwiązywania problemów matematyki wyższej z wykorzystaniem teorii grafów, jej istota i procedura rozwiązywania. Główną ideą metody rozgałęzionej i powiązanej jest praktyczne użycie do zadania. Podział zbioru tras na podzbiory i jego graficzna reprezentacja.

    zadanie, dodano 24.07.2009

    Istota i treść, podstawowe pojęcia i kryteria teorii grafów. Koncepcja i główny pomysł o problemie komiwojażera. Opis metody rozgałęzionej i związanej, zastosowanie praktyczne. Przykład użycia Ta metoda oddziałów, aby rozwiązać problem komiwojażera.

    test, dodano 07.06.2011

    Metody rozwiązywania problemu komiwojażera. Model matematyczny problemu komiwojażera. Algorytm Little'a do znajdowania minimalnego konturu Hamiltona dla grafu o n wierzchołkach. Rozwiązywanie problemu komiwojażera z wykorzystaniem algorytmu Kruskala i algorytmu „drewnianego”.

    praca na kursie, dodano 30.04.2011

    Istota problemu komiwojażera, jego zastosowanie. ogólna charakterystyka metody jego rozwiązania: metoda poszukiwań wyczerpujących, metody „zachłanne”, algorytmy genetyczne i ich uogólnienia. Cechy metody rozgałęzionej i związanej oraz określenie najbardziej optymalnego rozwiązania problemu.

    praca na kursie, dodano 18.06.2011

    Model matematyczny problemu. Rozwiązanie problemu transportu metodą potencjalną. Wartość funkcji celu. Układ składający się z 7 równań z 8 niewiadomymi. Rozwiązywanie problemów metoda graficzna. Wybór półpłaszczyzny odpowiadającej nierówności.

    test, dodano 12.06.2011

    Teoria programowania dynamicznego. Koncepcja optymalnej podkonstrukcji. Niezależny i całkowicie zależny zbiór wierzchołków. Problem znalezienia maksymalnego zbioru niezależnego w drzewie. Algorytm Brona-Kerboscha jako rozgałęziona metoda wyszukiwania klik.

    streszczenie, dodano 10.09.2012

    Rozwiązanie podwójny problem wykorzystując pierwsze podstawowe twierdzenie teorii dualności, metody graficzne i sympleksowe. Model matematyczny problemu transportowego, obliczenia planie referencyjnym transport metodami narożnika północno-zachodniego i elementu minimalnego.

    test, dodano 27.11.2011

    Sformułowanie problemu komiwojażera i podstawowe algorytmy jego rozwiązania. Trasy i ścieżki. Koncepcje sieci transportowych. Koncepcja rosnącego łuku, łańcucha, cięcia. Algorytm Floyda-Warshella. Rozwiązanie problemu Metoda analityczna. Tworzenie aplikacji rozwiązującej problem.

    praca na kursie, dodano 10.08.2015

    Rozwiązanie pierwszego problemu, równania Poissona, funkcja Greena. Zagadnienia brzegowe równania Laplace'a. Zestawienie problemów wartości brzegowych. Funkcje Greena dla problemu Dirichleta: przypadki trójwymiarowe i dwuwymiarowe. Rozwiązanie problemu Neumanna z wykorzystaniem funkcji Greena, implementacja na komputerze.

    praca na kursie, dodano 25.11.2011

    Kolejność rozwiązywania liniowego problemu wartości brzegowych. Cechy metody zamiatania. Algorytm metody różnic skończonych: zazębianie dany obszar, wymiana operatora różniczkowego. Rozwiązywanie SLAE metodą Gaussa, równania różnic skończonych.

Rozważmy następujący problem programowania liniowego na liczbach całkowitych. Maksymalizuj przy ograniczeniach

Na rys. 1 przestrzeń możliwych rozwiązań problemu programowania liniowego liczb całkowitych jest reprezentowana przez punkty. Odpowiedni początkowy problem programowania liniowego (oznaczamy go jako LP0) uzyskuje się poprzez odrzucenie warunku całkowitego. Jego optymalnym rozwiązaniem będzie =3,75, =1,25, z=23,75.

Ryc.1.

Ponieważ optymalne rozwiązanie problemu LP0 nie spełnia warunku całkowitego, metoda rozgałęzień i ograniczeń modyfikuje przestrzeń rozwiązań problemu programowania liniowego tak, aby ostatecznie otrzymać optymalne rozwiązanie problemu programowania liniowego całkowitego. W tym celu należy najpierw wybrać jedną ze zmiennych całkowitych, której wartość w optymalnym rozwiązaniu zadania LP0 nie jest liczbą całkowitą. Przykładowo wybierając (=3,75) zauważamy, że obszar 3? ?4 przestrzeni dopuszczalnych rozwiązań problemu LP0 nie zawiera całkowitych wartości zmiennej i dlatego można je wykluczyć z rozważań jako mało obiecujące. Jest to równoznaczne z zastąpieniem pierwotnego problemu LP0 dwoma nowymi problemami programowania liniowego LP1 i LP2, które są zdefiniowane w następujący sposób:

Przestrzeń rozwiązań dopuszczalnych LP1 = przestrzeń rozwiązań dopuszczalnych LP0 + (), przestrzeń rozwiązań dopuszczalnych LP2 = przestrzeń rozwiązań dopuszczalnych LP0 + ().

Rysunek 2 przedstawia przestrzenie dopuszczalnych rozwiązań problemów LP1 i LP2. Obie przestrzenie zawierają wszystkie możliwe rozwiązania pierwotnego problemu CLP. Oznacza to, że problemy LP1 i LP2 „nie stracą” rozwiązań zadanie początkowe LP0.

Ryc.2.

Jeśli w dalszym ciągu będziemy inteligentnie wykluczać z rozważań obszary, które nie zawierają rozwiązań całkowitych (takich jak) poprzez wprowadzenie odpowiednich ograniczeń, ostatecznie otrzymamy problem programowania liniowego, którego optymalne rozwiązanie spełnia wymagania liczb całkowitych. Innymi słowy, rozwiążemy problem CLP, rozwiązując sekwencję problemów ciągłego programowania liniowego.

Nowe ograniczenia wzajemnie się wykluczają, zatem problemy LP1 i LP2 należy traktować jako niezależne problemy programowania liniowego, jak pokazano na rys. 3. Dychotomizacja problemów LP jest podstawą koncepcji rozgałęzień w metodzie rozgałęzionej i powiązanej. W tym przypadku nazywa się to zmienną rozgałęzioną.

Ryc.3.

Optymalne rozwiązanie problemu CLP znajduje się w przestrzeni rozwiązań dopuszczalnych albo w LP1, albo w LP2. Dlatego oba podproblemy muszą zostać rozwiązane. Najpierw wybieramy problem LP1 (wybór jest dowolny), który ma dodatkowe ograniczenie?3.

Maksymalizuj przy ograniczeniach

Optymalnym rozwiązaniem problemu LP1 jest i. Optymalne rozwiązanie problemu LP1 spełnia warunek, aby zmienne i były liczbami całkowitymi. W tym przypadku mówią, że zadanie zostało zbadane. Oznacza to, że zadanie LP1 nie powinno być już sondowane, gdyż nie może zawierać najlepsze rozwiązanie Zadania TsLP.

W tej sytuacji nie możemy ocenić jakości rozwiązania całkowitego uzyskanego z rozważenia problemu LP1, ponieważ rozwiązanie problemu LP2 może prowadzić do lepszego rozwiązania całkowitego (przy ważna decyzja w funkcji celu z). Na razie możemy jedynie powiedzieć, że wartość ta jest dolną granicą optymalnej (maksymalnej) wartości funkcji celu pierwotnego problemu CLP. Oznacza to, że każdy nierozważony podproblem, który nie może prowadzić do rozwiązania całkowitego z dużą wartością funkcji celu, należy wykluczyć jako mało obiecujący. Jeśli nierozważony podproblem może prowadzić do lepszego rozwiązania w postaci liczb całkowitych, należy odpowiednio dostosować dolną granicę.

Przy wartości dolnej granicy badamy LP2. Ponieważ w problemach LP0 optymalna wartość funkcja celu jest równa 23,75, a wagi jej współczynników są liczbami całkowitymi, to nie da się otrzymać rozwiązania całkowitoliczbowego problemu LP2, które byłoby lepsze od istniejącego. W rezultacie odrzucamy podzadanie LP2 i uważamy je za sprawdzone.

Implementacja metody rozgałęzionej i powiązanej została zakończona, ponieważ zbadano oba podzadania LP1 i LP2. Dlatego dochodzimy do wniosku, że optymalnym rozwiązaniem problemu CLP jest rozwiązanie odpowiadające dolnej granicy, a mianowicie i.

Gdybyśmy jako zmienną rozgałęziającą wybrali zmienną, to rozgałęzienie i szybkość znalezienia rozwiązania optymalnego byłyby inne Rys. 4.

Ryc.4. Drzewo decyzyjne gałęzi