Ricerca operativa, metodi risolutivi

(PL)

1) SEMPLICE PRIMARE

• x_j ≥ 0
• v. b. i ottima
• v. b. i inf.

(o vincoli non in base)

valori dei vincoli in base

B(h): quello tra i ≤ è numero della base di h

REGOLA ANTI BLAND

supUJ(j): dove ho preso h

(D) VUOTO (INF.)

• st: viene A₃ = b_i - A_iX

lo calcolo per tutti vincoli in j

• λ_T = min λ, i: ɛ J
• K - minima i: ɛ j

Sostituisco h con K – Trovo una nuova base

DOMANDA EXTRA

Se avessi c = l J , dato J, sarebbe ancora di realtà?

x_j > 0 - riuscita

x_j = 0 - non di riuscita

x_j < 0 - decresciuta

1) SEMPLICE DUALE

1) B = { }

• Δ_B
• Δ_A
• X = A_B b_B

A N X = b_ NO A N X ≤ b_ NO

k: min { i ∈ N A x > 0 }

γ_a = A_B → η_B ≤ 0 ∀ α ∈ B

θ = min { x_i ≠ 0, θ ≥ 0 }

Se chiede di trovare la direz di retta illimitata di [ ] → vincolo in base vincolo entrante

Costruisco allora un nuovo flusso aumentabile

v = 6

Ho trovato quindi un flusso migliore

Costruisco un grafo residuo nuovo, uguale a quello di prima tranne dove è successo qualcosa

• (3,3) prima era vuoto ora c’è ma fratello ma sorella
• (3,5)
• (3,7) è morto il fratello (perché è positivo) ed è nata la sorella

Posso ancora chiedermi se questo grafo può farmi trovare ancora un cammino da 1 a 7. Perché se lo trovo posso ↑ il flusso.

Vinta

Da 1 vedo 3↑, da 3 vedo 4 ma man mano porta, 2, 5, 6, da 4 vedo 5 ma già l'ho visto, da 5 vedo 2 ma già l'ho visto, anche 3 già l'ho visto, da 6 vedo 7. Ho trovato il nuovo cammino

Questo flusso posso mandare su questo cammino no? Infatti 2 perché (3,3) ha capienza max 5 ⁰ ma ha già 3

Aumento allora di 2 il flusso del cammino

• (1,3)
• (3,6)
• (6,7)

v = 8

Costruisco il nuovo grafo residuo.

(3,1) ammazza il fratello

Se faccio la visita in ampiezza le scelte vanno da 1 arriviamo a 4, da 4 a 5 e a 5 a finalmente faccio quindi di nuovo la visita.

Ho trovato un nuovo cammino utilizzando le scelte

Questo vuol dire che riesco a mandare altro flusso finché quando sto scendendo la scelta, il flusso nell'arco corrispondente alla scelta invece di ↑ diminuisce.

(Quindi perché tutto il flusso che faccio passa per degli archi fratelli, nei grafi delle scelte)

Quanto flusso ci posso mandare quindi?

Sull'arco fratello (1,4) potrei mandare altre 3.

(4,5) ne posso mandare altre 4

(5,2) e l'arco scelta in quest'arco il flusso non deve ↑ ma ↓ al massimo di quanto può diminuire feb 2

(fai il ciclo di bottiglia)

Il massimo flusso che posso mandare in quell'arco, sul cammino aumentante, feb 2 l'arco della bottiglia non è un arco di 3 eurine, ma che è svuotato.

Per fare un flusso migliore usando questo cammino scriviamo:

(4,1) 3

(4,5) 3

(5,2) 0

(2,6) ma 6!

(5,7)

Ho così ottenuto un flusso aumentabile di valore 10.

Modellazione

x_A = x_A

x_A + x_B ≤ 1

x_A ∩ x_C ∩ x_B ∩ x: x_C + x_A + x_B

x_C ≤ x_A + x_B

> x_A + x_B ≤ 1

x_C > x_A - x_B - 1

x_C ≤ x_A + x_B

x_B > x_A

SPT

1. F. adj → f archi più comp
2. SPT.1 QUEUE
3. O(m, n)
4. b) F. adj →
5. SPT.5
6. O(m²)
7. c) F. adj → SPT. ACYCLIC O(m)