Appunti di Metodi e modelli di ottimizzazione discreta 1 - parte 3 algoritmi

Parte III: Algoritmi

Esistono diverse categorie di algoritmi:

• Esatti: identificano la soluzione ottima - possono richiedere tempi troppo lunghi.
• Approssimati: la soluzione è garantita entro una certa percentuale dell’ottimo.
• Euristica: identificano soluzioni ammissibili.

Algoritmi esatti

Tipologie di algoritmi con complessità temporale limitata e quindi applicabili.

Ricerca esaustiva

• Algoritmo che esamina ogni soluzione e ne verifica l’ammissibilità.
• Se una soluzione è ammissibile, calcola il valore della f_o e deve verificare tutti i vincoli (tot. m * coeffic. di x).
• Cerca il valore migliore della f_o e individua la soluzione ottima.

L’operazione di verifica per ogni vincolo serve a individuare una soluzione ammissibile, ma è una sequenza molto lunga. Di base l’algoritmo funziona, ma è impraticabile nella realtà, la complessità cresce troppo rapidamente con il numero di variabili.

Matrice totalmente unimodulare

Per problemi RL nel caso di matrice TUM possiamo risolvere con l’algoritmo del simplesso.

Consideriamo: A_{(m x n)}, max {c : Ax ≤ b, x ∈ Zⁿ} con A^m ∈ Z^m- r.m._x (X): {x,b,c} ∈ Rmax {c^tx : Ax ≤ b, x ∈ Rⁿ}

Sol di base ammissibile

Una soluzione di base ammissibile è definita come x = (x_B, x_N) = (B^-1b, 0), dove B_" è l'inversa di una sottomatrice quadrata B di A [a_ij] ∈ Z_{m x n}.

Se g (elementi di B_") sono al numeratore, prodotti di termini interi di (AIE) e al denominatore i det B, che sarà anche esso prodotto di numeri interi. I termini di B_" sono interi sicuramente se det B = ±1, di conseguenza x_B=B^-1b è intera avendo B_" intera avendo B pure.

Def

Una matrice A ∈ R_{m x n} e ogni sua sottomatrice quadrata ha det ∈ {0, -1, +1} corrisponde ad essere colonne in base.

Prop. 2

Se TUM il problema RL ha soluzione ottimale intera finita vb intero.

Consideriamo A = {a_ij} = e valutiamo quali sono le sottomatrici quadrate.

Nei casi peggiori B = D quindi sono n! sottomatrici quadrate se le righe sono tutte L.I. ⇔ esiste un numero di sottomatrici quadrate è pari al numero di coppie di righe che possiamo estrarre da m (combinazioni m righe). ∗ Il numero di coppie tra le n colonne: ⌈m / (n-m)x (n * (n-1)) ⌉.

Algoritmi

Esistono diverse categorie di algoritmi:

• Esatti: identificano la soluzione ottima - possono richiedere tempi troppo lunghi.
• Approssimati: la soluzione è garantita entro una certa percentuale dell'ottimo.
• Euristica: identificano soluzioni ammissibili.

Algoritmi esatti

Tipologie di algoritmi con complessità temporale limitata e quindi applicabili.

Ricerca esaustiva

L'algoritmo esamina ogni soluzione, ne verifica l'ammissibilità.

Se una soluzione è ammissibile, calcola il valore della f_o; deve verificare tutti i vincoli.

Cerca il valore migliore della f_o e individua la soluzione ottima.

L'operazione di verifica per ogni vincolo serve a individuare una soluzione ammissibile, ma è una sequenza molto lunga. Di base l'algoritmo funziona, ma è impraticabile nella realtà, la complessità cresce troppo rapidamente con il numero di variabili.

Matrice totalmente unimodulare

Per problemi di RL nel caso di matrice TUM possiamo risolvere con l'algoritmo del simplesso.

Consideriamo: A = max {cx : Ax ≤ b, x ∈ Zⁿ} con A ∈ Z^nxm e b ∈ Z^m.

Sol di base ammissibile

Una soluzione di base ammissibile è definita come x = (x_B, x_N) = (B^-1b, 0), dove B^-1 è l’inversa di una sottomatrice quadrata B di A | E | ≥ e₂ x e_n, |f(m+n)| ≤ 2^m+n.

Una matrice A è TUM e ogni sua sottomatrice quadrata ha det ∈ {0, -1, +1} corrispondente alle colonne in base.

Se B - {3 × 3}: il numero delle sottomatrici quadrate è pari alle combinazioni delle possibili triple da m righe × il numero di combinazioni delle possibili triple tra n colonne = m·(m-1)·(m-2)/3! × n·(n-1)·(n-2)/3!

Se B - {4 × 4}: il numero delle sottomatrici quadrate è pari alle combinazioni delle possibili quadruple da m righe × il numero di combinazioni delle possibili quadruple tra n colonne = m·(m-1)·(m-2)·(m-3)/4! × n·(n-1)·(n-2)·(n-3)/4!

Per la nostra matrice A si avrebbero 125 sottomatrici quadrate: troppe, sarebbe difficile calcolare il determinante di tutte TEORE