algorytm.org

Algorytm Balas'a

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Balas'a
Ocena użytkowników:***** / 7
SłabyŚwietny 
Wpisany przez Robert Dudek, 27 grudnia 2005 22:22

Zero-jedynkowy addytywny algorytm Balasa pozwala na rozwiązanie następującego binarnego programu liniowego:

Znaleźć minimum:
z = c_1x_1 + c_2x_2 + ... + c_nx_n
Przy ograniczeniach:
a_{i1}x_1 + a_{i2}x_2 + ... + a_{in}x_n \leq b_i
gdzie:
i = 1, 2, ..., m
xj = 0 lub 1
j = 1, 2, ..., n.


Zasada działania algorytmu.
Do śledzenia postępu przeglądu używa się dwu wektorów: uT = (u1, u2, ..., un) oraz xT = (x1, x2, ..., xn). Jeśli w skład rozwiązania częściowego wchodzą zmienne xj1, xj2, ..., xjs, wybrane w takim właśnie porządku, to składowe wektora x odpowiadające tym zmiennym mają wartości albo 0 albo 1. Pozostałe składowe wektora x, odpowiadające zmiennym swobodnym, mają wartości -1. Składowe wektora u są postaci:
u= \begin{cases} jk & \text{ jeżeli } x_{jk} = 1 \text{ i jego dopełnienie nie było rozważane }\\ -jk & \text{ jeżeli } x_{jk} = 0 \text{ lub 1 i jego dopełnienie było rozważane }\\ 0 & \text{ jeżeli } k>s \end{cases}
Krok początkowy.
Krok 1.
Sprawdzić, czy b ≥ 0. Jeśli tak, to optymalnym rozwiązaniem jest x = 0. W przeciwnym razie podstawić
u^T = (0, 0, ..., 0)\\ x^T = (-1, -1, ..., -1)\\ z' = \infty \text{ (dostatecznie duża liczba) }
Kroki iteracyjne
Krok 2.
Obliczyć:
y_i = b_i - \sum_{j \in J}{a_{ij}x_j}\\ y' = \min y_i \text{, dla } i = 1, 2, ..., m\\ z = \sum_{j \in J}{c_jx_j}
gdzie J jest zbiorem wskaźników zmiennych o ustalonych wartościach (rozwiązanie częściowe). Jeśli y'≥0 oraz z<z', to przyjąć z = z' oraz x' = x. Wektor x' jest nowym potencjalnym rozwiązaniem. Przejść do kroku 6 (cofanie się). W przeciwnym razie iść dalej.

Krok 3.
Utworzyć następujący podzbiór T zmiennych swobodnych xj:
T = \left{j: z + c_j < z', a_{ij} < 0 \text{ dla } i \text{ takich, że } y_i < 0\right}
Jeśli T = {} (zbiór pusty), to przejść do kroku 6. W przeciwnym razie iść dalej.

Krok 4.
TEST NIEDPOPUSZCZALNOŚCI. Sprawdzić, czy istnieje taki wskaźnik i, że:
y_i < 0 \text{ oraz }\\ y_i - \sum_{j \in T}{\min(0, a_{ij})} < 0
Jeśli tak, to przejść do kroku 6. W przeciwnym razie iść dalej.

Krok 5.
TEST ROZGAŁĘZIEŃ BALASA. Dla każdej zmiennej swobodnej x utworzyć zbiór:
M_j = \left{i: y_i - a_{ij} < 0\right}
Jeśli wszystkie zbiory Mj są puste, przejść do kroku 6. W przeciwnym razie obliczyć:
v_j = \sum_{i \in M_j}{(y_i - a_{ij})}
dla każdej zmiennej swobodnej xj, gdzie vj = 0, gdy M,j = {} (zbiór pusty).
Powiększyć bieżące rozwiązanie częściowe o tę zmienną xj, dla której vj osiąga wartość największą. Wróć do kroku 2.

Krok 6.
COFANIE SIĘ:
  1. Zmienić w wektorze u znak najbardziej w prawo położonej składowej dodatniej. Nadać wszystkim składowym leżącym na prawo od niej wartość 0. Jest to nowe rozwiązanie częściowe. Wrócić do kroku 2.
  2. Jeśli wektor u nie ma dodatniej składowej, to przegląd pośredni został zakończony. Optymalnym rozwiązaniem jest x', a odpowiadającą mu wartością funkcji celu jest z'. Jeśli z' = ∞, to nie ma rozwiązania dopuszczalnego.

Przykład:

Aby zilustrować omówiony algorytm, rozważmy obecnie następujące zagadnienie:

Znaleźć minimum:
z = 5x1 + 7x2 + 10x3 + 3x4 + x5
przy warunkach:
-x1 + 3x2 - 5x3 - x4 + 4x5 ≤ -2
2x1 - 6x2 + 3x3 + 2x4 - 2x5 ≤ 0
x2 - 2x3 + x4 + x5 ≤ -1

Iteracja 1
Podzbiór T jest równy {1,3,4}. Test niedopuszczalności zawodzi. Zbiory Mj oraz wartości vj dla j=1, 2, ... 5 są odpowiednio równe:
M1 = {1, 2}, M2 = {1, 3}, M3 = {2}, M4 = {1, 2, 3}, M5 = {1, 3},
v1 = -4, v2 = -7, v3 = -3, v4 = -5, v5 =-8,
max = {vj 1 ≤ j ≤ 5} = v3 = -3

Do rozwiązania częściowego dodajemy zmienną x3 = 1. Pozostałe zmienne są swobodne i mają wartość 0.

Iteracja 2
T = {2, 5}. Test niedopuszczalności zawodzi. Otrzymujemy:
M1 = {2}, M2 = {}, M4 = {2}, M5 = {1, 2},
v1 = -5, v2 = 0, v4 = -5, v5 = -2,

Następną zmienną dodaną do rozwiązania częściowego jest x2 = 1, ze względu na to, że:
max = {vj j = 1, 2, 4, 5} = v2 = 0

Iteracja 3
Wektor xT = (0, 1, 1, 0, 0) jest dopuszczalny i staje się potencjalnym rozwiązaniem x', a z' = 17. Wykonuje się krok 6 (cofanie się). Mamy teraz x3 = 1, x2 = 0, a pozostałe zmienne są swobodne.

Iteracja 4
T = {5}. Test niedopuszczalności jest spełniony dla i = 2 (drugie ograniczenie) i przechodzimy do cofania się. Teraz x2 i x3 są ustalone jako 0, a pozostałe zmienne są swobodne.

Iteracja 5
T = {1, 4}. Test niedopuszczalności jest spełniony dla i = 3 i przechodzimy do cofania się. Przegląd jest zakończony, bo nie można się już cofnąć.

Optymalnym rozwiązaniem jest zatem:
x'1 = 0, x'2 = 1, x'3 = 1, x'4 = 0, x'5 = 0 oraz z' = 17

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Robert DudekC/C++MS Visual Studio
.cpp
.cpp
***** / 1
Michał KotC/C++
.cpp
.cpp
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 września 2012 16:31
Dodaj komentarz