Ottimizzazione Combinatoria 2006/2007 Homework 1
Cognome __________________
Nome __________________
Matricola __________________
Domanda 1
Disegnare un grafo G = (V, E), connesso, tale che 1. α(G) + τ(G) = 10.
2. μ(G) = τ(G) = 4 Domanda 2
Dato il grafo G di figura:
1. Formulare come problema di PL-{0, 1} il problema del massimo insieme stabile su G.
2. Sia D il duale del rilassamento lineare del problema precedente. Scrivere esplicitamente D e calcolarne la soluzione ottima.
3. Calcolare il massimo matching e il minimo vertex cover di G
Ottimizzazione Combinatoria 2006/2007 Homework 1
Cognome __________________
Nome __________________
Matricola __________________
Esercizio 1
La seguente matrice è una matrice delle distanze di un’istanza del problema del Commesso Viaggiatore.
1 2 3 4 5 6 7
1 - 12 42 7 10 11 21
2 12 - 31 4 8 27 7
3 42 31 - 27 6 5 15
4 7 4 27 - 14 33 23
5 10 8 6 14 - 12 32
6 11 27 5 33 12 - 14
7 21 7 15 23 32 14 -
Calcolare
1. Il valore del rilassamento che si ottiene determinando l’1-albero di costo minimo 2. Una soluzione euristica S ottenuta tramite l’algoritmo di Christofides.
3. Una soluzione euristica S ottenuta tramite l’algoritmo Double Tree.
4. Una soluzione euristica S ottenuta tramite l’algoritmo Farthest Insertion 5. Una soluzione euristica S ottenuta tramite l’algoritmo Nearest Neighbor.
Esercizio 2
Un’azienda di autotrasporti effettua un giro di consegne nelle seguenti città europee:
Roma Atene Madrid Bruxelles Belgrado Parigi Berlino
- 1460 2040 1580 1410 1500 1400 Roma
- 3470 3010 1280 2729 2580 Atene
- 1550 1730 1260 2340 Madrid
- 1730 590 810 Bruxelles
- 1040 1310 Belgrado - 1080 Parigi
- Berlino Sapendo che:
1. Ogni elemento (i, j) della matrice rappresenta la distanza in km tra le città i e j;
2. L’azienda effettua il giro con un automezzo condotto da un unico autista che può guidare consecutivamente per un massimo di 1200 km;
3. Il giro di consegna parte da Roma e termina a Roma.
Provate a minimizzare il numero di soste spiegando le scelte algoritmiche effettuate.
