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:
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:
Krok 1.
Sprawdzić, czy b ≥ 0. Jeśli tak, to optymalnym rozwiązaniem jest x = 0. W przeciwnym razie podstawić
Krok 2.
Obliczyć:
Krok 3.
Utworzyć następujący podzbiór T zmiennych swobodnych xj:
Krok 4.
TEST NIEDPOPUSZCZALNOŚCI. Sprawdzić, czy istnieje taki wskaźnik i, że:
Krok 5.
TEST ROZGAŁĘZIEŃ BALASA. Dla każdej zmiennej swobodnej x utworzyć zbiór:
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Ę:
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
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 iteracyjneKrok 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Ę:
- 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.
- 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
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Robert Dudek | C/C++ | MS Visual Studio | .cpp | .cpp | ***** / 1 |
| Michał Kot | C/C++ | .cpp | .cpp | ***** / 3 |
Poprawiony: 29 września 2012 16:31