vuoi
o PayPal
tutte le volte che vuoi
ESPLORAZIONE NODI GRAFO
- VENTAGLIO (BFS) LARGHEZZA → TUTTI I NODI VICINI A S (la) HANNO LIVELLO LA - DIST. DA S
- SCANDAGLIO (DFS) PROFONDITÀ → S = 1 POI 2, 3, ... X VICINANZA
CAMMINI MINIMI
- NO CIRCUITI □ → ESISTE CAMMINO MIN
- NO CIRCUITI ■ → LUNGHEZZE MIN = UNICHE SOL. EQ. BELLMAN
- BELLMAN
- Ms = 0 (NO CIRCUITI NEGATIVI)
- (i, j) ∈ A → Mj ≤ Mi + lij
- ∀ j ≠ s → LUNGO CAMMINO MIN DA S A j; ESISTE NODO k PREDECESSORE DI j, CIOÈ (k, j) ∈ A. X OTTIMALITÀ: Mj = Mk + lkj
- Da 2) e 3) → Mj = min {Mi + lij | (i, j) ∈ A}, ∀j ≠ s
- DIJKSTRA
- SOLO SE TUTTI GLI ARCHI lij > 0!
- INIZIO: λ = 0, p0, p∞...
- P = 0, 0, 0, 0...
- FLOYD - WARSHALL
- CAMMINI MIN TRA TUTTE LE COPPIE DI NODI!
- MATRICI D e P → [NO ARCO: ∞
- i ≠ j : 0
- AGGIORNAMENTI: lij → □ SUDIAGONALE: CIRCUITI NEGATIVI
ALBERO INCOGNENTE 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 E 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=1m Cj Xj → guadagno atteso
Σj=1m aj Xj ≤ b → non posso superare budget
Xj ∈ {0,1} ; j=1,...m → variabili binarie
|U| = insieme ambiente = 2m
se b - Σj=1m aj Xj/2 → almeno metà dei sottoinsiemi di N sono ammissibili cioè X ha almeno 2m-1 elementi.
PBM ASSEGNAZIONE
min z(x) = Σi=1m Σj=1m Cij Xij → costo assegnazione
Σj=1m Xij = 1 (i=1,...,m) → ogni Persona (i) → 1 uomo
Σi=1m Xij = 1 (j=1,...,m) → ogni Lavoro (j) → 1 persona
Xij ∈ {0,1}; j=1,...,m → variabili binarie
X = insieme ammissibile = permutazioni su {1,...,n} → |X| = m!
PBM COPERTURA
min z(x) = Σj=1m Cj Xj → costo salari pagati a medi.
Σj=1m aijXj≥1 (∀i ∈ M) → almeno 1 medico fa interv. i
Xj ∈ {0,1}; j=1,...,m → variabili binarie
N = {1,...,m,n} insieme finito medici (j)
M = {1,...,m,n} insieme finito interventi (i) → Mj ⊂ M ∀j ∈ N
Copertura di M tramite N → ⊂N t.c.
∪ Mj = M
PBM IMPACCAMENTO
Σj=1m aijXj≤1 (∀i ∈ M) → al più 1 medico fa interv. i
Impaccamento di M tramite N → ⊂N t.c.
Mj ∩ Mk = ∅ ∀j,k ∈ T j≠k
PBM PARTIZIONE
(max o min)
Σj=1m aijXj=1 (∀i ∈ M) → esattamente 1 medico fa int. j
Partizione di M tramite N → ⊂N t.c.
∪ Mj = M e Mj ∩ Mk = ∅
(PL) AMMETTE SBA OTTIME INTERNE?
SE det B = ±1 ➔ SBA {X:B^-1b,O} E A COMPONENTI INTERNE.
INFATTI BcB SEMPRE A COMPONENTI INTERNE.
B^-1 = A/det((I-A)T)s det Bi,j , MATRICE B SENZA j-ESIMA RIGA e i-ESIMA COLONNA
SE X SBA OTTIMA DI (PL) ➔
PROPRIETÀ 3 INVALIDAMENTI
X s.o. DI (PI)MATRICI TOTALMENTE UNIMODULARI (TU)
COEFFICIENTI INTERI e det = ±1, 0, 1 PER OGNI SOTTOMATRICE QUADRATA,
SE A ∈ TU ➔ (PL) AMMETTE SBA OTTIMA INTERNA INTERNO B
PER IL QUALE AMMETTE UNA SOLUZIONE OTTIMA.
- CONDIZ. NECESSARIA E SUFFICIENTI:
- A, AT, -A , [A,A], [A,I], [A,-A], [AI], [-AI] ... SONO TU
- CONDIZ. SUFFICIENTI: ➔ MATRICE TU PUÒ (NON) SODDISFARE
- 1) COEFFICIENTI = 0, -1, 1
- 2) OGNI COLONNA MA 2 COEFF. ≠0
- 3) RIGHE RIPARTITE IN 2 SOTTOINSIEMI T.C.
• COLONNA HA 2 COEFF. = ±1 ⇔ G-A ➔ SOTTOINSIEMI DI RIGHE ≠
• COLONNA HA UN COEFF. = 1 e UNO = -1 ➔ STESSO SOTTOINSIEME
MATRICE INCIDENZA NODI-ARCHI
- • GRAFO ORIENTATO ➔ TU ➔ MA=M e M2=∅
- • GRAFO NON ORIENTATO ➔ IN GENERALE NO TU
- • GRAFO NON ORIENTATO BIPARTITO ➔ TU ➔ MA=V1 e M2=V2
TEOREMA DI INTEREZZA
{ x ∈ ℝm: Ax=b, x⪰0 }
- • FORMA STANDARD
- 1)SE A ∈ TU ➔ VERTICI DI P(A,b) SONO INTERI ∀ b∈ℤm PER CUI
- 2)SE A ∈ TU ➔ (PL) max ℕ{x: Ax=b, x⪰0} AMMETTE SBA OTTIMA
- 3)SE A ∈ TU ➔ (PL) minbℕ {y: AT y⪯c, y∈ℝm} AMMETTE SBA OTTIMA
- 1 Z+PL = W+DL CONV(X ∩ {x ∈ ℝm+: Dx ≤ d }) = CONV(X) ∩ {x ∈ ℝm+: Dx ≤ d }
- 2 W+DL = ZPL CONV(X) = { x ∈ ℝm+: Ax ≤ b }
- M > 0
- 0 = 1
- 0 -1
P(A,b) ≠∅
INTERNA ∀ b (VETTORI INTERNI) PER CUI IL PBL AMMETTE S.O.
INTERNA ∀ c (VETTORE INTERNO) PER CUI IL PBL AMMETTE S.O.
N.B. A É TU ➔ P(A,b) HA VERTICI INTERNI
DUALE LAGRANGIANO VS RILASSAMENTO LINEARE
v.o. (DL) = W+DL = max {cTx: Dx ≤ d, x ∈ CONV(X)} ⊂ ℝm Program. Lineare
NB:
CONV(x) = CONV{x ∈ ℤm+: Ax ≤ b } ⊃ {x ∈ ℤm+: Ax ≤ b } ⊂ ℝm+
(PL) Z+PL = max{zPL = cTx: Dx ≤ d, Ax ≤ b, x ∈ ℝm+^}R.A. DI (P*) CONV(X) ∩ {x ∈ ℝm+: 0x ≤ d }R.A. DI (PL) = {x ∈ ℝm+: Ax ≤ b } ∩ { x ∈ ℝm+: Dx ≤ d }
SICCOME L.A. DI (P*) ⊂ R.A. DI (PL) Z+PL ≤ W+DL ≤ ZPL
DUALE LAGRANGIANO DA STIME MIGLIORI DI RILASSAM. LINEARE
CASI PARTICOLARI:
Pbm Zaino (0-1 6 INTERO): W+DL = 2PL (stima duale Lagr. = rilassam. lineare)
Valore/Ingombr e ordine da Maggiore a MinoreLM = Zpi + M(b - ax) → raccolgo le x
Vincolo budget
*
4-2M
4-3M
wDL(m) := L* {12-3m 0 ≤ m ≤ 1/211-m 1/2 ≤ m ≤ 1
trovo min → S.O. = M* = 1 (M che da min)V.O. = M sostituito nella sua eq.
SO (PL) → A per valore/ingombro ↑ poi frazioni (vincolo budget)VO (PL) → metto le x nella funz. obiettivo
INTERNI:
A Uguale
wDL(m): = L* {+∞, 0 ≤ m < 2 → Dove ho almeno un{+m, M > 2
trovo min → M* ≥ 2 → S.O.7 - 2 = 14 = V.O.
SO (PL) → valore max dove valore/ingombro ↑ (vincolo budget)VO (PL) → metto le x nella funz. obiettivo