Riassunto programma di metodi e modelli per le decisioni

Esplorazione nodi grafo

Ventaglio (BFS)

Ventaglio (BFS) larghezza → tutti i nodi, vicini a S₀ hanno livello La - dist. da S.

Scandaglio (DFS)

Scandaglio (DFS) profondità → S = 1 poi 2, 3,... → x vicinanza.

Cammini minimi

Cammini minimi no circuiti <0 → esiste cammino min no circuiti ≤0 → lunghezze min = uniche sol. eq. Bellman.

Bellman

• A)_S = 0 (no circuiti negativi).
• (i,j) ∈ A → M_j ≤ M_i + l_ij.
• ∀ s → U.lngo cammino min da S a j; esiste nodo K predecessore D_j, cioè (k,j) ∈ A x ottimalità: M_j = M_k + l_kj.
• 4) Da 2) e 3) → M_j = min{M_i + l_ij | (i,j) ∈ A }, ∀ j ≠ s.

Dijkstra

Dijkstra solo se tutti gli archi l_ij > 0!

Inizio: λ = 0, ρ, ∞,...

P = 0, 0, 0, 0,...

Floyd-Warshall

Floyd-Warshall cammini min tra tutte le coppie di nodi!

Matrici D e P → quadrante [no arco: ∞ i ≠ j: 0 altrimenti: l_ij → 0 suddiagonaLe: circuiti negativi.

Albero ricoprente min (MST)

• 1) G connesso e |A| = |V| - 1.
• 2) G privo di cicli e |A| = |V| - 1.
• 3) Ogni coppia di nodi connessa da unico cammino.
• 4) G privo di cicli e unendo 2 nodi non adiacenti si ha ciclo considero solo certi archi del grafo → arco di min uscente da un nodo qualsiasi è un arco del MST (archi da nodi collegati a nodi non collegati).

Esplorazione nodi grafo

Ventaglio (BFS)

Ventaglio (BFS) lunghezza → tutti i nodi, vicini a S(₀) hanno livello L_A - dist. da S.

Scandaglio (DFS)

Scandaglio (DFS) profondità → S=1 poi 2, 3,...x vicinanza.

Cammini minimi

Cammini minimi no circuiti _∞ → esiste cammino min.

No circuiti _≥0 → lunghezze min = uniche sol. eq. Bellman.

Bellman

• M_s=0 (no circuiti negativi).
• (i,j)∈A → M_j ≤ M_i + l_ij.
• ∀j≠S ⇒ lungo cammino min da S a J; esiste nodo K predecessore di J, cioè (k,j)∈A x ottimalità: M_j = M_k + l_kj.
• Da 2) e 3) → M_j = min{M_i + l_ij | (i,j)∈A} ∀j ≠S.

Dijkstra

Dijkstra solo se tutti gli archi l_ij ≥ 0!

Inizio: λ = 0, p = 0, ∞...

P = 0, 0, 0, 0, ...

Floyd-Warshall

Floyd-Warshall cammini min tra tutte le coppie di nodi!

Matrici D e P.

Quadrante → |no arco: ∞ i = j: 0 [alimenti: l_ij → 0 sudiagonale: circuiti negativi].

Albero ricoprente min (MST)

• G connesso e |A| = |V|-1.
• G privo di cicli e |A| = |V|-1.
• Ogni coppia di nodi connessa da unico cammino.
• G privo di cicli e unendo 2 nodi non adiacenti si ha ciclo considero solo certi archi del grafo → arco di min uscente da un nodo qualsiasi è un arco del MST (archi da nodi collegati a nodi non collegati).

PBM zaino 0-1

max z(x) = ∑_j=1^m C_j x_j → guadagno atteso.

∑_j=1^m a_j x_j ≤ b → non posso superare budget.

x_j ∈ {0, 1}, j = 1,..., m → variabili binarie.

|U| = insieme ambiente = 2^m.

Se b = (∑_j=1^m a_j)/2 → almeno metà dei sottoinsiemi di N sono ammissibili, cioè X ha almeno 2^m-1 elementi.

PBM assegnazione

min z(x) = ∑_i=1ⁿ ∑_j=1^m C_ij X_ij → costo assegnazione.

∑_j=1^m X_ij = 1 (i = 1, ..., m) → ogni persona(i) → 1 lavoro.

∑_i=1ⁿ X_ij = 1 (j = 1, ..., m) → ogni lavoro(j) → 1 persona.

X_ij ∈ {0, 1}, i, j = 1,..., m → variabili binarie.

X = insieme ammissibile = permutazioni su {1,..., m} → |X| = m!

PBM copertura

min z(x) = ∑_j=1^m C_j X_j → costo salari pagati a med. j.

∑_j=1^m a_ij X_j = 1 (∀ i ∈ M) → almeno 1 medico fa interv. i.

X_j ∈ {0, 1}, j = 1,..., m → variabili binarie.

N = {1, ..., n} ins