Ricerca operativa, metodi risolutivi

(PL) con SIMPLESSO ALGEBRICAMENTE

1) SIMPLESSO PRIMALE

1. B = { }

2. • A_B
   • 1. X = A_B^-1 b_B
     2. Y_B = c_BA_B^-1
     3. Y_N = 0
   • x >> 0 V ∈ B   OTTIMA (MI FERMO)
   • Σ o vincoli non in base
   •  valori devi uncoli in base
   • B(h): quello tra i 1 e 2° numero della base = h
   • h = min {j ∈ B; Y_j < 0}
   • Ù_B(R) = {J}^T j < 0   dove ho messo h
   • ξ = A_N Ù_B(R)

   • A_N ∈∀   x_N ∈ ∀

   • SUP LHULU
   • D) VUOTO (MI FERMO)
   • - J ∈ ∀ A_jξj ≥ 0
   • d_i = b_i - A_i x   (lo calcola per tutti vincoli u∈j)
   • Τ = min {d_i; i ∈ Σ}
   • K = min {j ∈ Σ: d_j = Τ}
   • Sostituisco h con K → Trovo una nuova base
   • DOMANDA EXTRA

   • Se avessimo c=1   dato ξ sarebbe ancora di

   • uscita?

   • Verifico che:   ^{< 0 uscita} _{= 0 non di uscita}   < 0 decrescita

(PL) CON SIMPLESSO ALGEBRICAMENTE

1) SIMPLESSO PRIMALE

• 1) B = { }
• _AB
• A_N
• X = _AB b_B
• Y_B = c_AB
• Y_N = 0
• X => 0 V _{i ∈} B OTTIMO (MI FERMO)
• ∃ vincoli non in base
• h = min{j ∈ B : Ỹ_j < 0^j} B(h) = quello tra l'1° e 2° numero della base è h
• v_AB(h) = [J] < 0 dove ho messo h
• ∑ = _AB v_AB(h) REGOLA ANT-BLAND
• A_N ∑ INT^A A_j
• -∑ i∈N : A ∑ ₀=> 0
• d_i = b_i−A_i x (lo calcolo per tutti i vincoli u ∉ j)
• −T = min {x_i : i ∈ ∑ }
• −K = min{∑ i ∈ ∑ : d_i = T}
• Sostituoco h con K -> Trovo una nuova base

DOMANDA EXTRA

Se avessimo c = t ∑ dato ∑ sarebbe ancora di uscita?

Verifico che: c_jj

• >0 uscita
• =0 non di uscita
• b

NOCONTINUOFINITE

1. Θ = min {
   • i ∈ B ηi > 0
   • Θ = v_b / η_b
2. h = min {
   • z ∈ B: η > 0, Θ = vj / ηj

Se chiede di trovare la direz di receta illimitata

PROBLEMI

(METODI RISOLUTIVI)

1. INDIVIDUA ALBERO DEI CAMMINI MINIMI

1. ∃ cicli. ∃ archi di costo negativo → SPT-L QUEUE

   Prosegui normalmente da 1 in poi, ma quando aggiungi l'etichetta di un nodo RIDUCENDOLA rimuovilail nodo u in testa (in modo da far ripulire l'etichetta).

2. ∃ cicli, ∄ archi di costo negativo → SPT-S
   • Estr/ il nodo con etichetta minoreO(m²)Se Q implementato come lista non ordinata
   • O(mφ(m))Se Q implementato come heap binario bilanciato
3. ∄ cicli (∴ ∄ archi di costo negativo) → SPT-ACYCLIC

   o(m)Rinumero nodi partendo dalla radice in ordine crescente, posizionandoè nel modo il cui costo dell'etichetta per arrivarci è sempre minore.(Stra possibile)

   Seguo l'ordine crescente dei nodida 1 a n (non c'è Q)

2) Problema del flusso max con algoritmo Edmonds e Karp

Faccio il grafo residuo e lo visito, individuo un cammino aumentante e aumento il flusso lungo quel cammino (tutti i flacelli nella sella). Continuo fin quando la visita (fila) non trova più un cammino aumentante ma un taglio. Allora il flusso trovato è il max e il taglio è quello di capacità minima : u(Ns, Nt)

• e la somma delle distanze tra gli archi s(Ns è uguale a Nf

3) Problema di flusso di costo minimo con l'algoritmo di cancellazione dei cicli

• Faccio il grafo residuo e vedo se ci sono cicli aumentanti di costo negativo, in caso affermativo, inoltro il flusso lungo quel ciclo e mi accolto il nuovo cx.
• Quando non più ciclo di costo negativo, visito il grafo residuo finale e se mi trova un albero dei cammini minimi allora la soluzione trovata è ottima. (Per trovare cicli di costo negativo faccio la vista del prof. reso in spe. la queue.)

v⁺=3

È AMMISSIBILE

È la mia soluzione ottima?

Per calcolare una miglior devo ribaltare il grafo mamantenere quello originale per quello nuovo, ma il nuovo grafocomincia come quello di prima tranne negli archi incui è successo qualcosa.

(1, 2) = ritorno = c'è la sorella ma non più il fratello.

(2, 5) = prima c'era il fratello ora solo la sorella.

(5, 7) = c'è sia il fratello che la sorella.

(piano non è miovuoto me

ritorno)

Quindi il nuovo grafo residuo è

Continuo: È il flusso massimo? Prendo il grafo residuoe lo inverto per vedere se c'è n'è unoimpegno:

Vinto: Da 1 non vedo più 2, vedo 4³, da 3 vedo 2,5,6, da 4 vedo5 ma già l'ho visto, non vedo 7 vedo 5 e da 5 vedo 7 e hotrovato un cammino che mi permette di migliorare ilflusso.

Che ho dimenticato?

Da (1, 2) potrebbero andare 5 anche da (3, 5) ma da (5, 7)è penso andare solo 8 almeno 3.

Posso quindi ¹ Il flusso di quegli archi di 3.

costruisco allora un nuovo flusso aumentabile:

ν=6

Ho trovato quindi un flusso migliore

costruisco un grafo residuo nuovo: uguale a quello di prima tranne dove è successo qualcosa

• (1,3) prima era vuoto ora c'è ma fratello di sorella
• (3,5)
• (5,7) è morto il fratello (perché è saturo) 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 2 ma non mi importa, 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 è:

Quanto flusso posso mandare in questo cammino?

Altri 2 perché (1,3) ha capacità max 5 e me ne ha già 3

Aumento allora di 2 il flusso del cammino:

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

ν=8

Cerco un cammino che va dalla sorgente alla destinazione e che mi permette di portare più flusso alla destinazione → VISITA

Per prima cosa allora prendo il grafo e lo visito per scoprire se c'è un cammino (1,7) con la visita.

Da 1 vedo 2, 3, 4, prendo 2 e da lì esce 5, 6 che non avevo mai visto, esce 3, da 3 vedo 2, 5, 6 ma li ho già visti (non ricalca mentre) poi vedo 4. Da 4 vedo 5 ma è già stato preso e vedo 7. Finisco la visita avendo trovato un cammino da 1 a 7.

In questo cammino ci devo mandare flusso, quanto?

Allora

• 1 - 4 - 7 posso mandare 1 unità di flusso (da questo 1 esce 1)

Ora non posso rivisitare il grafo perchè se lo rivisito mi ritorna la stessa cosa!

Allora devo visitare qualcosa che non è il vero grafo di partenza: il GRAFO RESIDUO (è meglio) rispetto la x.

Visito il grafo residuo produce una copia di archi se il flusso < capacità; mentre produce una copia invertita dell'arco (sorella) se flusso > 0. Questa è un'operazione che dato un grafo in flusso ti dà un altro grafo.

Aumentando il flusso il tutto è il mio grafo il grafo residuo.

• Quindi nasce la scelta a (1->4), poichè _FLUSSO (3) | < | \ v \ | | (2) | V < (5) (7) | / | ^ \ V | ^ V / | (4) ------> (6)

• Da 1 vedo ₂₃₄, da 2 vedo 5,6 , da 3 vedo 2,5,6 quindi già li ho visti e non faccio niente, da 4 vedo 1, ma l'ho già visto quindi non succede in niute, vedo 5 ma già l'ho visto, non vedo 7 ma questo perchè (4->7) è diventato (7->4). Da 5 vedo 7 e la visita è finita

(**) (1) ----->[3] | | v | (2) ------->(6) | | | | v/ v / (4)------>(5)---(7)

• Quanto flusso posso mandare in questo cammino? Devo vedere le capacità degli archi: (1->2) c= 2, (2->5) c=2, (5->7) c=5
• Sul primo arco posso mandare altre 2 case, anche nel 2° ma 5 posso mandarne 5 ma più di 2 ma ne rimano. Quindi posso migliorare il mio flusso mandando ancora un altro po' in quel cammino, (2 è più al massimo). Il mio nuovo flusso sara

PROGRAMMAZIONE LINEARE

(PL) max {cᵀx: Ax ≤ b}

• matrici reali m x n
• b ∈ ℝᵐ , 1 ∈ ℝᵐ
• x ∈ ℝⁿ

min {cᵀx: Ax = b, x ≥ 0}

EQUIVALENTE

• max ∑ cⱼxⱼ = min ∑ (-cⱼ)xⱼ
• min ∑ cⱼxⱼ = max ∑ (-cⱼ)xⱼ
• ∑ aᵢⱼxⱼ = bᵢ =
  • ∑ aᵢⱼxⱼ ≤ bᵢ
  • ∑ aᵢⱼxⱼ ≥ bᵢ
• ∑ aᵢⱼxⱼ > bᵢ = ∑ (-aᵢⱼ)xⱼ ≤ -bᵢ
• ∑ aᵢⱼxⱼ > bᵢ = ∑ aᵢⱼxⱼ - sᵢ = bᵢ , sᵢ ≥ 0
• ∑ aᵢⱼxⱼ < bᵢ = ∑ aᵢⱼxⱼ + sᵢ = bᵢ , sᵢ ≥ 0

Costruisco il nuovo grafo residuo:

(3,1) ammazza il fratello

Se facciamo la visita ora senza le stelle, da 1 arrivoma a 4, da 4 a 5 e a 5 ci fermeremmo.Faccio quindi di nuovo la visita

• Ho trovato un nuovocammino utilizzandole stelle

Questo vuol dire che riesco a mandare altro flusso perché quando sto usando la stella, il flusso nell'arco corrispondentealla stella invece di aumentare diminuisce.(quindi perché tutti i flussi che faccio passano per gli archifratelli e non negli archi stella)Quanto flusso ci posso mandare quindi ?sull'arco fratello (1,4) potrei mandarne altre 3(1,5) ne posso mandare oltre 4(5,2) il terzo stella in quest'arco il flusso non deve aumentare maè al massimo di questo più diminuire di 2(fa il collo di bottiglia)Il massimo flusso che posso mandare in quest'arco orachiamato CAMMINO AUMENTANTE è 2, l’arco collo di bottiglianon è un arco che diminuisce ma che si svuota.Per fare un flusso migliore usando questo cammino aumentante:aumenta (1,4) a 3, diminuisce (1,5) a 2, diminuisce (5,2) a 0, aumenta 0 2 (2,6) / aumenta (6,7)

Ho così ottenuto un flusso aumentabile di valore 10

Un cammino aumentante, se γ può essere determinato,

mediante una visita del GRAFO RESIDUO G_f a partire

da s.

Se la visita raggiunge t allora se è determinato

un cammino aumentante ed il flusso X non è

ottimo perchè il cammino aumentante permette di

ottenere un nuovo flusso X' di valore strettamente

maggiore.

Aggiungere di quanto?

di una quantità θ:

θ(P, x) = min{ min{ u_ij - x_ij (i,j) ∈ P}; min{ x_ji (i,j) ∈ P}} > 0

(capacità flusso

dell'arco)

Ogni arco consente aumentare di questa quantità θ,

ogni arco discordo diminuisce

Il valore del flusso aumenterà di θ

Se invece al termine della visita non è visitato

t, allora X è un flusso massimo.

La fine della visita restituisce un taglio di capacità minima.

→ Problema flusso costo max

max ∑_(i,j)∈BS X_ji ∑_(i,j)∈FS X_ij = 0 i∈N\{s,t}

• = V i = s
• = -V i = t

→ Problema flusso costo minimo

min ∑_(i,j)∈A c_ijX_ij

∑_(i,j)∈BS X_ji ∑_(i,j)∈FS X_ij = 0 i |

• -1 i = s
• 1 i = t
• 0 altrimenti

→ Th. debole della dualità:

∀ x ammiss. per (P), ∀ y ammiss. per (D)

Cx ≤ yb

Se x̄ amm. Ax̄ ≤ b

∀ y ammiss. cx̄ ≤ yb → Cx̄ ≤ yb

→ Th. forte dualità:

se ∃ x ammiss. per (P) e ∃ y ammiss. per (D) allora

-∞ < z(P) = z(D) < +∞

Poiché x* ottima allora :

(Sp) { Ax ≤ c ξ > 0 c ≥ 0

(Sd) { yA = c y ≥ c

(Sp) non può avere soluzione. Per il lemma di Farkas (Sd) avrà necessariamente una soluzione

∀ t.c. ȳ * | ∀_k,o_j ammiss. per (D).

Ora per dimostrare che x̄, ȳ ottime utilizzo il

t.s.c. : ∀ x, y ammiss. x̄, ȳ ottime ↔ ȳ(b-Ax̄) = 0.

ovvero:

_yb = ^{y_BA-1_BX essendo c-ᴻB = y-ᴻA_B-1}

_yb = c^xx_̅x

- SIMPESSO PRIMALE ALGEBRA

A_{B b X} = A_B^xb₀ Y_B = c_bY_N Y = [_TY_B, Y_N;]

k = min { Y_i ∊ ℓ_T i_B, B {B (n) ȲB