OTTIMIZZAZIONE COMBINATORIA II Cognome _________________
Parziale del 18-05-2007 Nome _________________
Matricola _________________
Esercizio 1
Si consideri la formulazione P di un dato problema di PL0-1:
2 1
1
1 1 1
7 6 5 4 3 2
5 1
5 4
7 3 6 2
7 4 3
6 2 1
≤ + + + + +
≤ +
≤ +
≤ + + +
≤ + +
≤ + +
x x x x x x
x x
x x
x x x x
x x x
x x x
Date le disuguaglianze I:x1+x2+x3 +x4 +x5 ≤2 e J:x1+x2+x3+x4 +x5+x6+x7 ≤2 dimostrare o confutare le seguenti affermazioni:
1. I e J sono valide per conv(S) (dove S =P {0,1}7). In caso affermativo si calcoli il relativo rango di Chvátal rispetto alla formulazione P.
2. I e J sono facce massimali di conv(S).
Trovare altre disuguaglianze valide per conv(S) e dire se sono facce massimali.
Esercizio 2
Dato l’insieme S={x∈R×Z+:x1−x2 ≤2,x1+2x2 ≥1,2x1+2x2 ≥1}, disegnare e descrivere conv(S) attraverso le sue facce massimali.
Esercizio 3
Risolvere il seguente problema di PLI con l’algoritmo dei piani di taglio di Gomory:
∈ +
= + +
= + +
+ + +
Z x
x x x
x x x
x x x x
i
2 2
1 2
4 3 2 min
4 2 1
3 2 1
4 3 2 1
Esercizio 4
Dato il grafo in figura, sia S la collezione degli insiemi di archi che contengono un cammino da s a t. Si determini se il punto x =(0.3,...,,0.3) appartiene a conv(S) e, in caso contrario, si individui una disuguaglianza lineare che separa x da conv(S).
s t
1 4
2
5 3
