Domande di teoria ed esercizi di esami di OC2

Name: Domande di teoria ed esercizi di esami di OC2
Rating: 4.0 (2 reviews)
Author: pael

Revisionato il 04/09/2026

di pael

Publisher

Vota 4,0/5 (2)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Domande teoriche ed esercizi verificati di prove d'esame raccolti nel corso degli anni Domande teoriche ed esercizi verificati di prove d'esame raccolti nel corso degli anni basate su appunti …

Esame Ottimizzazione combinatoria

Facoltà Ingegneria dell'informazione

Dal corso del Prof. Sassano Antonio

Università Università degli Studi di Roma La Sapienza

A.A. 2017-2018

52 pagine

4 download

Appunto

Scarica

Estratto del documento

Esercizio 1

Applicare l'algoritmo primale-duale relativo al node-cover per trovare la soluzione 2-approssimata del problema. Individuare pertanto la sequenza di voli che garantisca il minimo costo.

Sono dati i seguenti pairings ammissibili:

Berlino-Amsterdam-Atene {1,2,3}
Roma-Budapest {4,5}
Roma-Amsterdam-Helsinki {4,2,6}
Helsinki-Londra {6,7}
Berlino-Londra {1,7}
Atene-Budapest {3,5}

Abbiamo I = {F₁, F₂, ..., F₇} V servizio h = 1,...,7. F_n ⊆ J sono insiemi che contengono lo stesso servizio h. J = {1,...,6} pairings ammissibili.

Svolgimento

Determino gli F_n:

F₁ = {1,5}

F₂ = {1,3}

F₃ = {1,6}

F₄ = {2,3}

F₅ = {2,6}

F₆ = {3,4}

F₇ = {4,5}

T ⊆ J è un cover ⟺ |F_i ∩ T| ≥ 1 ∀ F_i ∈ I.

Nodi := pairings ammissibili.

Archi := F_i.

Vediamo che ogni arco sia coperto.

Esercizio 1

Applicare l'algoritmo primale-duale relativo al Node-Cover per trovare la soluzione 2-approssimata del problema. Individuare pertanto la sequenza di voli che garantisca il minimo costo.

Sono dati i seguenti pairings ammissibili:

Berlino - Amsterdam - Atene {1, 2, 3}
Roma - Budapest {4, 5}
Roma - Amsterdam - Helsinki {4, 2, 6}
Helsinki - Londra {6, 7}
Berlino - Londra {1, 7}
Atene - Budapest {3, 5}

Abbiamo I = {F₁, F₂, ..., F₇} ∀ servizio ń = 1, ..., 7. F_n ⊆ J sono insiemi che contengono lo stesso servizio ń J = {1, ..., 6} pairings ammissibili.

Svolgimento

Determino gli F_n:

F₁ = {1, 5}

F₂ = {1, 3}

F₃ = {1, 6}

F₄ = {2, 3}

F₅ = {2, 6}

F₆ = {3, 4}

F₇ = {4, 5}

T ⊆ J è un cover <=> |F_i ∩ T| ≥ 1 ∀ F_i ∈ I.

Nodi := pairings ammissibili.

Archi := F_i.

Vogliamo che ogni arco sia coperto.

Vogliamo trovare il cammino a costo minimo.

Definiamo primale e duale

Primale

min c^Tu

Σ_eεF u_e ≥ 1 FεI

u_e ≥ 0 eεJ

Duale

max 1^Ty

Σ_FεI y_F ≤ c_e eεJ

y_F ≥ 0 FεI

F₁ u₁ + u₅ ≥ 1

F₂ u₁ + u₃ ≥ 1

F₃ u₁ + u₆ ≥ 1

F₄ u₂ + u₃ ≥ 1

F₅ u₂ + u₆ ≥ 1

F₆ u₃ + u₄ ≥ 1

F₇ u₄ + u₅ ≥ 1

u₁, ..., u₆ ≥ 0

Passo Φ

Scelgo una soluzione iniziale.

Passo 1

Scelgo una &overline;F=> Aggiungo J^¯: J^¯ = J^¯ ∪ {1,3} = {1,3}=> Aggiungo Y^¯_F2 = 1=> Aggiungo T - J^¯ = {1,3}

Passo 2

Scelgo una F^¯ che non interseca J^¯: F^¯ = F₅ = {2,6} ^ {1,3} = ∅.

Infatti in J^¯ = {1,3} non ci sono {2,6}=> non avrei potuto inserire F₁, F₃, F₄, F₆.

=> Aggiungo Y_F = Y^¯_F5 = Y^¯_F5 + min_{2,6} (c_e - ΣY^¯_F)= 0 + min{(1 - Y^¯_F4 - Y_F5), (1 - Y^¯_F3 - Y_F5)}_{2,6}= 0 + min{(1,1)}_{2,6} = 1=> Aggiungo J^¯: J^¯ = J^¯ ∪ {2,6} = {1,3,2,6}=> Aggiungo Y^¯ = Y^¯_F5 = 1=> Aggiungo T - J^¯ = {1,3,2,6}

Passo 3

Scelgo una F^¯ che non interseca J^¯:=> F^¯ = F₇ = {4,5}

Aggiungo Y_{F_¯} = Y^¯_F7 = Y^¯_F7 + min_{c∈F_¯} (c_e - ΣY^¯

Anteprima

Vedrai una selezione di 10 pagine su 52