Esercizi svolti di Analisi matematica 1 e geometria

PROVA N. 1

Trovare un albero ricoprente di peso minimo applicando l’algoritmo di Kruskal. Verificare l’ottimalità della soluzione ottenuta.

Ordine costi

• AC 5
• BE 5
• BC 7
• CD 9
• AD 10
• DE 40

• Iterazione 0 _S0 = {} _T0 = {} |T₀| < |N| – 1 4 → algoritmo prosegue
• Iterazione 1 _S1 = {AC} _T1 = {C, A} si considera l’arco di peso minimo
• Iterazione 2 _S2 = {AC, BE} _T2 = {B, E, C, A}
• Iterazione 3 _S3 = {AC, BE, BC} _T3 = {B, E, D, C, A}
• Iterazione 4 _S4 = {AC, BE, BC, CD} _T4 = {B, E, D, C, A}
• Iterazione 5 _S5 = {AC, BE, BC, AD} _T5 = {B, E, D, C, A}
• Aggiunta DE genera un ciclo già selezionati
• Iterazione 6 _S6 = {BE, DE, BC, AC} _T6 = {B, E, D, C, A} |T₆| = |N| – 1 = stop
• C(H(N,T)) = 25

Criterio di ottimalità su tagli

• Arco AC
  • C_AC ≤ C_AD = 11
  • C_AC ≤ C_AD = 10
• Arco BC
  • C_BC ≤ C_AB = 11
  • C_BC ≤ C_AB = 11
• Arco DE
  • C_DE ≤ C_AD = 40
  • C_DE ≤ C_CD = 9
• Arco BE
  • C_BE ≤ C_CE = 7
  • C_BE ≤ C_CD = 9
  • C_BE ≤ C_AD = 10

Componenti connesse devo vedere se l’albero, non sul grafo per ogni altro arco dell’albero lo rimuovo e vedo taglia delle 2 componenti connesse che si formano archi che hanno un estremo in una componente e l’altro estremo nell’altra

Prova M.S.

Scrivere la formulazione del problema del cammino s-t di peso minimo

min 2x_1s + x₃₄ + x₄₁ + x₁₂ + 2x₂₂ + 6x_ut + 3x_3t

• - x_1s = -1
• x₄₁ - x₁₂ = 0
• - x₃₄ + x₁₂ - x₂₃ = 0
• - x₂₂ + x_3t = 0
• x_ut = 1

x_1s ≥ 0

x₄₁ ≥ 0

x₂₃ ≥ 0

x₃₄ ≥ 0

x₁₂ ≥ 0

x_3t ≥ 0

x_ut ≥ 0

Trovare il massimo flusso s-t applicando l'algoritmo di Ford-Fulkerson

1° Iterazione:

f(u) = 0 + Δ = 6

P = {s, s₁, 4, u₄, t} Δ = 6

x_s4 = 6

x_4t = 6

2° Iterazione:

f(w) = 6 + Δ = 8

P = {s, s₁, 4, 1₂, 2, 2₃, 3_t, t} Δ = 2

x_s4 = 2

x₂₃ = 2

x_3t = 2

3° Iterazione:

Non è possibile individuare una rete incrementale s-t

• δ^*(x) = 8
• x₅₄^* = 2
• x₁₂^* = 2
• x_ut^* = 6
• x_su^* = 6
• x₁₃^* = 2
• x_4t^* = 0

Prova n. 3

max 4x_A - x_B 7x_A - 5x_B ≤ 14 x_A + x_B ≤ 3 x_A ≥ 0 x_B ∈ Z

a) Scrivere la formulazione del corrispondente rilassamento lineare

max 4x_A - x_B 7x_A - 5x_B ≤ 14 x_A + x_B ≤ 3 x_A ≥ 0 x_B ≥ 0

rilasso vincoli di interezza delle variabili

b) Stabilire se la formulazione di RLI data è ideale e in caso contrario trovare la sua formulazione ideale:

P = { x ∈ R² : Ax ≤ b, x ≥ 0 } A = [ 7 -5 ]         [ 1 -1 ] b = [ 14 ]       [ 3 ]

i vertici di P non sono interi: la formulazione non è ideale. Devo introdurre dei vincoli: x_A ≤ 2 x_A - x_B ≤ 1

Quesito 2

• archi (s,a) (s,b) (s,c) (a,d) (b,d) (b,c) (c,e) (e,b) (d,e) (a,t) (e,t)
• flusso 10 5 0 5 0 5 0 45 0 5 0
• capacità 10 5 5 5 5 6 15 15 6 15 10

a) Verificare se la soluzione di flusso data è ammissibile e, in tal caso, determinare il corrispondente valore del flusso s-t:

• vincoli di capacita' degli archi rispettati
• flusso ≥ 0 per ogni arco
• vincoli di bilanciamento dei flussi ai nodi:
  • 10 - 15 = -5 modo s
  • 5 - 5 = 0 modo a
  • 5 - 5 = 0 modo b
  • 0 - 5 = -5 modo c
  • 45 - 5 = 0 modo e
  • 5 - 5 = 0 modo d
  • 45 = flusso s-t

b) A partire dal flusso iniziale dato, determinare il massimo flusso in S-t utilizzando l'algoritmo di Ford-Fulkerson

rete incrementale f(x) = 15 ↑ Δ = 17