Ricerca Operativa II
prova scritta del 4 giugno 1999
Domanda 1
Mostrare come il problema di programmazione lineare intera
min cx
Ax > b
x > 0 intero
dove c = (4, 2, 2, 3, 1, 5), b = (2, 3, 1, 4, 3) e A è data da
|
0 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
1 |
possa essere risolto mediante il metodo del simplesso su reti.
Domanda 2
Il grafo di figura riproduce fedelmente la celebre costellazione dello scarrafone, ben visibile nelle chiari notti estive dell’emisfero australe. Un astrofilo che non aveva altro da fare mi ha chiesto, tra l’ironico e l’ingenuo, se sapessi calcolare quale fosse il massimo numero di stelle che si potevano congiungere usando i tratti rettilinei. Ci ha messo un po’ per spiegarmi che se una stella era congiunta a un’altra, non poteva essere congiunta a una terza: insomma, voleva sapere quale fosse il massimo matching che si può estrarre dal grafo. Ora, a me pareva che ci fosse un certo algoritmo… insomma, ho preso tempo: speravo me lo diceste voi.