Metody i algorytmy podejmowania decyzji

1. Wieloetapowe PD — Programowanie dynamiczne

Sformułowanie problemu

Zasada optymalności Bellmana

Jeśli optymalny proces decyzyjny przerwiemy w chwili n w stanie x_n, a następnie ponownie go podejmiemy przyjmując x_n za stan początkowy, to dalszy ciąg procesu będzie taki sam, jaki byłby gdyby nie przerywać procesu z x₀. Stan x_n w pełni determinuje dalszy proces — zawiera pełną informację o poprzednich decyzjach.

Algorytm — przebieg wstecz

\[ Q_N(\overline{u}_N) = \sum_{n=0}^{N-1} g(x_n, u_n), \qquad V_N(x_0) = \min_{\overline{u}_N} Q_N(\overline{u}_N) \]

n = N−1:

\[ V_1(x_{N-1}) = \min_{u_{N-1}} g(x_{N-1}, u_{N-1}) \longrightarrow u^*_{N-1} = \Psi_{N-1}(x_{N-1}) \]

n = N−2:

\[ V_2(x_{N-2}) = \min_{u_{N-2}}\left[g(x_{N-2}, u_{N-2}) + V_1\!\left(x_{N-1} = f(x_{N-2}, u_{N-2})\right)\right] \longrightarrow u^*_{N-2} = \Psi_{N-2}(x_{N-2}) \]

n = 0:

\[ V_N(x_0) = \min_{u_0}\left[g(x_0, u_0) + V_{N-1}(x_1 = f(x_0, u_0))\right] \longrightarrow u^*_0 = \Psi_0(x_0) \]

Przebieg w przód (odtworzenie rozwiązania)

2. Wielokryterialne PD (MCDM)

\( \mathbf{y} = [y^{(1)},\ldots,y^{(k)}]^T \) — wektor k kryteriów, \( y^{(i)} = f^{(i)}(u) \), \( F: U \rightarrow Y \)

Front Pareto

Ocena y dominuje ŷ jeśli:

\[ \begin{cases} \forall i \in \overline{1,k}: y^{(i)} \leq \hat{y}^{(i)} \\ \exists i \in \overline{1,k}: y^{(i)} < \hat{y}^{(i)} \end{cases} \]

Front Pareto = zbiór wszystkich ocen niezdominowanych przez żadną inną z Y. Decyzje odpowiadające zbiorowi Pareto są Pareto optymalne.

Skalaryzacja — metody sprowadzania do problemów jednokryterialnych

(a) Ważona suma kryteriów jednorodnych:

\[ G(u) = \sum_{i=1}^{k} w_i f^{(i)}(u), \quad w_i \geq 0,\; \sum_{i=1}^k w_i = 1 \]

(b) Ważona suma kryteriów niejednorodnych:

\[ G(u) = \sum_{i=1}^{k} w_i \frac{f^{(i)}(u)}{f^{(i)*}}, \quad f^{(i)*} = \min_{u \in U} f^{(i)}(u) \]

(c) Optymalizacja celu głównego: i-te kryterium jako cel główny, pozostałe jako ograniczenia:

\[ \min_{u \in U} f^{(i)}(u) \quad \text{s.t.} \quad \forall l \neq i: f^{(l)}(u) \leq b_l \]

(d) Minimalizacja odległości od punktu referencyjnego:

\[ \min_{u \in U} \|y - \bar{y}\|, \qquad \bar{y} = [f^{(1)*}(u) \;\; f^{(2)*}(u) \;\; \ldots \;\; f^{(k)*}(u)]^T \]

Metoda AHP (Analytic Hierarchy Process)

Rozważamy n wariantów decyzyjnych u ∈ U ≜ {u₁,…,uₙ}. Wartości kryteriów f⁽ⁱ⁾(u) nie muszą być liczbowe.

Skala Saatiego do porównań parami:

Macierz porównań kryteriów M⁽⁰⁾ = [m⁽⁰⁾_hl]: m_hh=1, m_hl=1/m_lh, m_hl=m_hp·m_pl (spójność)

Macierz porównań wariantów M⁽ⁱ⁾ = [m⁽ⁱ⁾_jl] dla każdego kryterium i: analogiczna struktura.

1. Normalizacja: \( \overline{m}^{(0)}_{hl} = \frac{m^{(0)}_{hl}}{c^{(0)}_l} \), gdzie \( c^{(0)}_l = \sum_h m^{(0)}_{hl} \)
2. Średnie wierszowe: \( s^{(0)}_h = \frac{1}{k}\sum_{l=1}^k \overline{m}^{(0)}_{hl} \) — waga kryterium h; \( s^{(i)}_j = \frac{1}{n}\sum_{l=1}^n \overline{m}^{(i)}_{jl} \) — pozycja wariantu j
3. Ranking końcowy: \( r_j = \sum_{h=1}^k s^{(0)}_h \cdot s^{(h)}_j \) — globalna ocena wariantu j

Sprawdzanie spójności: \( CR = \frac{CI}{RI} \leq 0{,}1 \), gdzie \( CI = \frac{\sum_l c^{(0)}_l \cdot s^{(0)}_l - k}{k-1} \)

Metoda ELECTRE I

1. Ustal wagi kryteriów w_i: \( \sum_{i=1}^k w_i = 1 \)
2. Oblicz relację: \( \varphi_i(u_j, u_l) = \begin{cases}1 & f^{(i)}(u_j) \geq f^{(i)}(u_l) \\ 0 & \text{wpp}\end{cases} \)
3. Oblicz współczynnik zgodności: \( c(u_j, u_l) = \sum_{i=1}^k w_i \varphi_i(u_j, u_l) \)
4. Wyznacz zbiór zgodności: \( C_s = \{(u_j, u_l): c(u_j, u_l) \geq s\} \), gdzie próg s ∈ [½, 1]
5. Wyznacz zbiór niezgodności: \( D_v = \{(u_j, u_l) \in C_s: \exists f^{(i)}: f^{(i)}(u_l) > f^{(i)}(u_j) + v_i\} \), gdzie v_i — próg weta
6. Relacja przewyższania: S(s,v) = C_s − D_v
7. Utwórz ranking — N podzbiorów wariantów, elementy pary z relacji S w sąsiednich podzbiorach

3. Algorytm rozdziału zasobów — operacje niezależne

Algorytm oparty na dwóch przesłankach: (1) najkrótszy czas T* gdy wszystkie operacje trwają tyle samo, (2) należy wykorzystać wszystkie zasoby U.

\[ \begin{cases} \forall i \in \{1,\ldots,n\}: \gamma_i(u^*_i; a_i) = T^* \\ \sum_{i=1}^n u^*_i = U \end{cases} \]

Algorytm (3 kroki):

1. Wyznacz u*_i za pomocą funkcji odwrotnych: \( \forall i: u^*_i = \gamma^{-1}_i(T^*; a_i) \)
2. Rozwiąż równanie \( \sum_{i=1}^n \gamma^{-1}_i(T^*; a_i) = U \) i wyznacz \( T^* = G(U, a_1, \ldots, a_n) \)
3. Oblicz: \( u^*_i = \gamma^{-1}_i(G(U, a_1, \ldots, a_n); a_i) \triangleq \eta_i(U, a_1, \ldots, a_n) \)

Warunek stosowania: istnienie γ⁻¹_i oraz G.
Przykład: rozdział pamięci RAM między procesory — U = całkowita RAM, v_i = wielkość zadania dla procesora i. Im więcej RAM, tym krótszy czas wykonania.

4. Algorytm rozdziału zasobów — operacje o dowolnej strukturze

Algorytm 3-krokowy: dekompozycja → alokacja lokalna → koordynacja.

Krok 1: Dekompozycja struktury na przedziały

Przedziały wyznaczane są przez zdarzenia (węzły) grafu kompleksu operacji:

Krok 2: Alokacja w j-tym przedziale (jak dla niezależnych)

Dodatkowe oznaczenia:

• U_j = {u_ij: i ∈ S_j} — zasoby w przedziale j
• x_ij — rozmiar operacji i w przedziale j; X_j = {x_ij: i ∈ S_j}
• T_ij = γ_i(u_ij, x_ij) — czas wykonania części operacji i w przedziale j

\[ T^j = F_j(U_j, X_j) = \max_{i \in S_j}[\gamma_i(u_{ij}, x_{ij})] \]

Rozwiązanie dla j-tego przedziału \( \forall i \in S_j: u^*_{ij}(X_j) = \eta_j(X_j; U) \) z układu równań:

\[ \begin{cases} \sum_{i \in S_j} u^*_{ij} = U \\ \gamma_i(u^*_{ij}; x_{ij}) = T^{j*} \quad i \in S_j \end{cases} \]

Krok 3: Koordynacja — wyznaczenie X*

\[ T(X^*_1,\ldots,X^*_{l-1}) = \min_{X_1,\ldots,X_{l-1}} \sum_{j=1}^{l-1} G_j(X_j; U) \]

Ograniczenia: x_ij ≥ 0; \( \sum_{j \in Q_i} x_{ij} = v_i \) (suma rozmiarów operacji i po wszystkich przedziałach = v_i)

5. Algorytm Ibarry dla R||C_max

Algorytm przybliżony dla szeregowania zadań niezależnych na maszynach dowolnych. Złożoność O(n), aproksymowalność: \( C^{\text{Ibarra}}_{\max} \leq m \cdot C^*_{\max} \)

6. Algorytm Johnsona dla F2||C_max

Problem przepływowy dla 2 maszyn dedykowanych. Algorytm optymalny. Złożoność O(n log n).

7. Algorytm NEH dla F||C_max (m > 2)

Dla maszyn dedykowanych, m > 2. Algorytm przybliżony, jakość typowo <2% od optimum. Złożoność O(mn²).

8. Algorytm najtańszego włączania dla TSP

Cheapest Insertion Algorithm — algorytm przybliżony. Złożoność O(n²log n), aproksymowalność ε = 2 (Q^INS ≤ 2·Q*).

9. Algorytm 2-optymalny dla TSP

Algorytm r-optymalny — startuje z rozwiązania dopuszczalnego (np. z najtańszego włączania), następnie poprawia przez wymianę krawędzi. Złożoność O(n²log n), aproksymowalność ε = 2.

10. Algorytm zachłanny dla 0-1 KP

Algorytm przybliżony. Złożoność O(n log n), aproksymowalność ε = 2.

Przykład (V=10):

V=10, załadowanie: i∈{1,5} (v=4), i=4 nie wchodzi (6+4>10) → Q = 5+3+4 = 12, zajętość = 1+3+6 = 10 ≤ V

11. Algorytm konstrukcyjny dla UFLP

Algorytm zachłanny dla Uncapacitated Facility Location Problem.

Zbiory pomocnicze: L' = {i ∈ L: x_i=1} — uruchomione lokalizacje; C' = {j ∈ C: nie przypisany do żadnej lokalizacji}.

Złożoność obliczeniowa i aproksymowalność — nieokreślone analitycznie dla ogólnego przypadku.

Zestawienie algorytmów