Problemy optymalizacyjnego podejmowania decyzji
1. Alokacja zasobów w kompleksie operacji niezależnych i zależnych
Problem łatwy obliczeniowo dla dowolnej struktury oraz dowolnych modeli operacji. Szukamy rozdziału zasobu U między n operacjami minimalizując czas wykonania całego kompleksu.
\[ u^* = \arg\min_{u \in D_u} T \]
- N = {1,…,n} — zbiór operacji w kompleksie
- n — liczba operacji, i — indeks operacji
- Ti — czas wykonania i-tej operacji
- Model struktury: ρ ⊂ N×N — niezależnych lub zależnych
- ai — parametr(y) charakteryzujące i-tą operację
- Ti = γi(ui, ai) — model operacji, γ jest: ciągłe, ściśle malejące w ui, nieujemne; limu→0γ = +∞, limu→∞γ = 0
- U — globalna ilość zasobów
- ∀i ∈ {1,…,n}: ui ≥ 0
- \( \sum_{i=1}^n u_i \leq U \)
- \( u = [u_1 \; u_2 \; \ldots \; u_n]^T \)
\[ T = \max_i \bar{t}_i - \min_i \underline{t}_i = \Phi(T_1, T_2, \ldots, T_n) \]
Dla operacji niezależnych (struktura równoległa): \( \Phi = \max(\cdot),\; T = \max_i T_i \)
Przykład struktury ρ ⊂ N×N — graf z macierzą incydencji:
⎡0 0 1 1 0 0 0⎤
⎢0 0 0 0 1 1 0⎥
⎢0 0 0 0 1 1 0⎥
⎢0 0 0 0 0 0 1⎥
⎢0 0 0 0 0 0 1⎥
⎢0 0 0 0 0 0 0⎥
⎣0 0 0 0 0 0 0⎦
Łatwy obliczeniowo — algorytm rozdziału zasobów dla operacji niezależnych opisany w sekcji Metody i algorytmy.
2. Szeregowanie zadań niezależnych — R||Cmax
Celem jest wyznaczenie dla każdego zadania maszyny wykonującej oraz czasu rozpoczęcia, aby zminimalizować długość uszeregowania (termin zakończenia ostatniego zadania).
Wyróżniamy 2 rodzaje maszyn: równoległe (uniwersalne) i dedykowane (specjalizowane).
\[ u^* = \arg\min_{u} C_{\max}(u) \]
- M = {M₁,…,Mₘ} — zbiór maszyn dowolnych
- J = {J₁,…,Jₙ} — zbiór zadań
- pj = [p₁j…pij…pmj]T, gdzie pij — czas wykonania j-tego zadania przez i-tą maszynę
- ∀j ∈ {1,…,n}: \( \sum_{i=1}^m u_{ij} = 1 \) — każde zadanie wykonywane dokładnie raz
- uij ∈ {0, 1}
- \( u_{ij} = \begin{cases}1 & \text{zadanie } j \text{ na maszynie } i \\ 0 & \text{wpp}\end{cases} \)
- \( u = [u_{ij}]_{i \in \{1,\ldots,m\}} \)
\[ C_{\max}(u) = \max_i \sum_{j=1}^n p_{ij}u_{ij} \]
NP-trudny Algorytm przybliżony Ibarry: O(n), aproksymowalność CIbarramax ≤ m·C*max
3. Problem przepływowy — F||Cmax
Szeregowanie zadań na maszynach dedykowanych z ustaloną kolejnością operacji M₁→M₂→…→Mₘ. Każde zadanie składa się z dokładnie m operacji. Szukamy permutacji zadań minimalizującej czas wykonania.
\[ \pi^* = \arg\min_{\pi \in \Pi} C_{\max}(\pi) \]
- M = {M₁,…,Mₘ} — zbiór maszyn
- J = {J₁,…,Jₙ} — zbiór zadań
- Jj = (O₁, O₂,…, Omj) — ciąg operacji j-tego zadania
- pij — czas wykonania i-tej operacji zadania j
- Brak ograniczeń kolejnościowych między operacjami różnych zadań
- Każda maszyna jednocześnie przetwarza tylko jedno zadanie
- Rozpatrujemy problem permutacyjny bez buforów
- π = (π(1), π(2), …, π(n)) — permutacja zadań
- |Π| = n! — liczba możliwych permutacji
Terminy zakończenia operacji pierwszego zadania:
\[ C_{i,\pi(1)} = \sum_{l=1}^i p_{l,\pi(1)} \]
Pozostałe (i = 2,…,m; k = 2,…,n):
\[ C_{i,\pi(k)} = \max\left[C_{i-1,\pi(k)},\, C_{i,\pi(k-1)}\right] + p_{i,\pi(k)} \]
\[ C_{\max}(\pi) = C_{m,\pi(n)} \]
Silnie NP-trudny (m≥3) Dla m=2: optymalny algorytm Johnsona O(n log n). Dla m≥3: algorytm NEH (aproksymacyjny <2% od optimum).
4. Problem komiwojażera (TSP)
Travelling Salesman Problem — zadanie optymalizacji dyskretnej, problem silnie NP-trudny. Szukamy trasy w postaci cyklu Hamiltona (wspólny początek i koniec, każde miasto odwiedzane dokładnie raz) minimalizującej łączny koszt.
\[ u^* = \arg\min_u Q(u) \]
- N = {1,…,n} — zbiór miast o liczebności n
- i, j ∈ {1,…,n} — indeksy miast
- cij — koszt podróży między miastami i oraz j
- C = [cij] — macierz kosztów
- ∀j: \( \sum_{i=1}^n u_{ij} = 1 \) — dotarcie do każdego miasta
- ∀i: \( \sum_{j=1}^n u_{ij} = 1 \) — opuszczenie każdego miasta
- ∀S ⊂ N: \( \sum_{i \in S}\sum_{j \in N-S} u_{ij} \geq 1 \) — brak podcykli
- \( u_{ij} = \begin{cases}1 & \text{przejazd } i \to j \\ 0 & \text{wpp}\end{cases} \)
- \( u = [u_{ij}]_{i,j \in \{1,\ldots,n\}} \)
Suma kosztów przejazdów:
\[ Q(u) = \sum_{i=1}^n \sum_{j=1}^n c_{ij} u_{ij} \]
Silnie NP-trudny Algorytm Held-Karp (dokładny): O(n²·2ⁿ). Najtańsze włączanie: O(n²log n), aproksymowalność ρ=2.
5. Problem plecakowy 0-1 (KP)
0-1 Knapsack Problem — problem NP-trudny. Maksymalizacja wartości elementów przy nieprzekroczeniu pojemności plecaka.
\[ u^* = \arg\max_u Q(u) \]
- V — rozmiar (pojemność) plecaka
- n — liczba elementów, i — indeks elementu
- vi — rozmiar i-tego elementu
- wi — waga (wartość) i-tego elementu
- ∀i ∈ {1,…,n}: ui ∈ {0,1}
- \( \sum_{i=1}^n v_i u_i \leq V \) — nieprzekraczanie pojemności
- \( u_i = \begin{cases}1 & \text{element } i \text{ w plecaku} \\ 0 & \text{wpp}\end{cases} \)
- \( u = [u_i]_{i \in \{1,\ldots,n\}}^T \)
Wartość elementów w plecaku:
\[ Q(u) = \sum_{i=1}^n w_i u_i \]
NP-trudny Algorytm DP pseudowielomianowy O(nV). Algorytm zachłanny: O(n log n), aproksymowalność ρ=2.
6. Lokalizacja obiektów — CFLP, UFLP, P-Median
Dla danego zbioru klientów, z danego zbioru lokalizacji należy wybrać podzbiór lokalizacji minimalizujących łączny koszt otwarcia i transportu.
6.1 CFLP — Capacitated Facility Location Problem
Lokalizacje mają skończoną pojemność vi. Minimalizujemy koszt uruchomienia i transportu:
\[ u^* = \arg\min_u Q(u) \]
- L = {1,…,n} — zbiór n lokalizacji
- C = {1,…,m} — zbiór m klientów
- fi — koszt uruchomienia lokalizacji i
- cij — koszt transportu z i do klienta j
- dj — popyt klienta j
- vi — pojemność lokalizacji i
- \( x_i = \begin{cases}1 & \text{i-ta lokalizacja uruchomiona} \\ 0 & \text{wpp}\end{cases} \)
- yij — część popytu j zaspokojona z i
- ∀j: \( \sum_i y_{ij} = 1 \) — każdy klient obsłużony
- ∀i: \( \sum_j d_j y_{ij} \leq v_i x_i \) — nie można zaspokoić popytu z nieuruchomionej lokalizacji
- xi ∈ {0,1}; 0 ≤ yij ≤ 1
\[ Q(u) = \min_{u \equiv (x,y)} \sum_{i=1}^n \sum_{j=1}^m c_{ij}y_{ij} + \sum_{i=1}^n f_i x_i \]
6.2 UFLP — Uncapacitated Facility Location Problem
Jak CFLP, ale pojemność vi = ∞. Każda lokalizacja zaspokaja całkowity popyt klientów (klient przypisany do jednej lokalizacji).
Zmienne decyzyjne
- xi ∈ {0,1} — uruchomienie lokalizacji
- \( z_{ij} = \begin{cases}1 & \text{klient } j \text{ obsługiwany z i} \\ 0 & \text{wpp}\end{cases} \)
- ∀j: \( \sum_i z_{ij} = 1 \)
- ∀i,j: zij ≤ xi — brak obsługi z nieuruchomionej lokalizacji
- xi, zij ∈ {0,1}
\[ Q(u) = \min_{u \equiv (x,z)} \sum_{i=1}^n \sum_{j=1}^m c_{ij}z_{ij} + \sum_{i=1}^n f_i x_i \]
6.3 P-Median
Problem NP-trudny (nie jest silnie NP-trudny). Różni się od UFLP: brak kosztów inwestycyjnych, wymagana dokładnie p uruchomionych lokalizacji. Modeluje minimalno-kosztową klasteryzację.
- L = {1,…,n} — lokalizacje
- p ≤ n — liczba lokalizacji do uruchomienia
- S ⊆ L — p-elementowy podzbiór L
- C = {1,…,m} — klienci
- cij — koszt transportu z i do j; vi = ∞
- ∀j: \( \sum_i z_{ij} = 1 \)
- ∀i,j: zij ≤ xi
- \( \sum_i x_i = p \) — wybieramy dokładnie p
- xi, zij ∈ {0,1}
\[ Q(u) = \min_{u \equiv S \subseteq L} \sum_C \min_{i \in S} c_{ij} \]
| Wariant | Pojemność vi | Koszty fi | Liczba lokalizacji | Zmienne |
|---|---|---|---|---|
| CFLP | skończona | tak | optymalna | xi, yij |
| UFLP | ∞ | tak | optymalna | xi, zij |
| P-Median | ∞ | nie | dokładnie p | xi, zij |
NP-trudny Algorytm konstrukcyjny zachłanny dla UFLP opisany w sekcji Metody i algorytmy.
*Na podstawie wykładów prof. J. Józefczyka, PWr.