Riassunto programma di metodi e modelli per le decisioni

ESPLORAZIONE NODI GRAFO

• VENTAGLIO (BFS) LARGHEZZA → TUTTI I NODI, VICINI A S₀ HANNO LIVELLO LA - DIST. DA S
• SCANDAGLIO (DFS) PROFONDITÀ → S = 1 POI 2, 3,... → X VICINANZA

CAMMINI MINIMI

NO CIRCUITI <0 → ESISTE CAMMINO MIN

NO CIRCUITI ≤0 → LUNGHEZZE MIN = UNICHE SOL. EQ. BELLMAN

• BELLMAN
  1. A)_S = 0 (NO CIRCUITI NEGATIVI)
  2. (i,j) ∈ A → M_j ≤ M_i + l_ij
  3. ∀ 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. 4) DA 2) E 3) → M_j = min{M_i + l_ij | (i,j) ∈ A }, ∀ j ≠ s
• DIJKSTRA
  • SOLO SE TUTTI GLI ARCHI l_ij > 0!
  • INIZIO: λ = 0, ρ, ∞,...
  • P = 0, 0, 0, 0,...
• 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 NICOPPONENTE 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) LUNGHEZZA → TUTTI I NODI, VICINI A S(₀) HANNO LIVELLO L_A - DIST. DA S
• SCANDAGLIO (DFS) PROFONDITÀ → S=1 POI 2, 3,...X VICINANZA

CAMMINI MINIMI

• NO CIRCUITI _∞ → ESISTE CAMMINO MIN
• NO CIRCUITI _≥0 → LUNGHEZZE MIN = UNICHE SOL. EQ. BELLMAN

• BELLMAN
1. M_s=0 (NO CIRCUITI NEGATIVI)
2. (i,j)∈A → M_j ≤ M_i + l_ij
3. ∀j≠S ⇒ UNGO CAMMINO MIN DA S A J; ESISTE NODO K PREDECESSORE DI 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

SOLO SE TUTTI GLI ARCHI l_ij ≥ 0!

• INIZIO: λ = 0, p = 0, ∞...
• P = 0, 0, 0, 0, ...

• 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 MINUSCENTE 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 BUDGETx_j ∈ {0, 1}, j = 1,..., m → VARIABILI BINARIE

|U| = insieme ambiente = 2^mse 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 PERSONAX_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. iX_j ∈ {0, 1}, j = 1,..., m → VARIABILI BINARIE

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