RICERCA OPERATIVA GRUPPO A prova scritta del 15 febbraio 2007
Rispondere alla seguente domanda marcando a penna la lettera corrispondente alla risposta ritenuta corretta (una sola tra quelle riportate). La risposta esatta vale 3 punti, quella sbagliata vale –1 punto.
1. Un grafo non orientato G = (V, E) si dice hamitoniano se contiene un ciclo H = (V, F), F ⊆ E, che tocca tutti i vertici (ciclo hamiltoniano): in altri termini, G è costituito da un ciclo hamiltoniano al quale sono aggiunti archi trasversali, detti corde (vedi figura).
D’altra parte un grafo G si dice planare se è possibile disegnarlo nel piano euclideo in modo che nessuna coppia di archi si intersechi in un punto: in tal caso si dice che G ammette un disegno planare. Dato ora un qualsiasi disegno di G con le corde interne al circuito hamiltoniano (tale disegno, come quello di figura, non è quindi necessariamente planare) si consideri il grafo G’ = (E – F, A), dove ab ∈ A se e solo se gli archi a e b si intersecano in un punto. Allora G è planare se e solo se G’
(A) è hamiltoniano (B) è planare
(C) non contiene cicli dispari
G’ non contiene cicli dispari se e solo se è bipartito, ed è bipartito se e solo E – F può essere partizionato in due insiemi stabili S, T. Se ciò accade, le corde in S (le corde in T) non si intersecano tra di loro, e quindi possono essere disposte all’esterno (all’interno) del circuito hamiltoniano, ottenendo così un disegno planare. Viceversa supponiamo che G ammetta un disegno planare, e siano rispettivamente S e T gli insiemi di corde che in tale disegno giacciono all’esterno e all’interno del circuito hamiltoniano. Siccome il disegno è planare, le corde di S non si intersecano tra di loro, e tale proprietà evidentemente si conserva anche se si dispongono le corde di S tutte all’interno del circuito. D’altra parte, neppure le corde di T si intersecano tra di loro: dunque il grafo G’ = (S∪T, A) è bipartito.
(D) è privo di cicli
Rispondere alle seguenti domande marcando a penna la lettera corrispondente alla risposta ritenuta corretta (una sola tra quelle riportate). Una risposta esatta vale 3 punti, una sbagliata vale –1 punto.
2. I vettori di IR3 (2, 0, 1/3), (2, 2, 1) e (0, 3, 1)
(A) sono linearmente ma non affinemente indipendenti
(B) sono affinemente ma non linearmente indipendenti. Infatti combinandoli con coefficienti 1, –1, 2/3
si ottiene il vettore nullo: la somma dei coefficienti tuttavia è diversa da 0.
(C) non sono né affinemente né linearmente indipendenti
3. I vettori b1 = (3, 1, 4), b2 = (0, 2, 0), b3 = (1, 3, –1) formano una base per IR3. Sostituendo x = (2, –2, 5) a (A) b1 oppure b2
(B) b2 oppure b3
(C) b1 oppure b3
si ottiene ancora una base per IR3.
Infatti x si esprime come combinazione lineare di b1, b2, b3, ma il coefficiente di b2 è 0. Quindi per il teorema di sostituzione x non può sostituire b2 in una base di IR3.
PDF created with pdfFactory Pro trial version www.pdffactory.com
1
2 3
4
5 6
7
Risolvere il seguente esercizio. La soluzione viene valutata fino a 6 punti.
4. La COOP sei tu
Una grande società di distribuzione di generi alimentari vuole inaugurare m supermercati in altrettante città di una determinata regione, e deve predisporne il supporto logistico aprendo contemporaneamente p magazzini intermedi di smistamento. Dopo un’accurata analisi sono state selezionate n > p località candidate per l’apertura di questi magazzini. Sia di j la distanza della località i dalla città j sede di un supermercato. Evidentemente, il generico supermercato si rifornirà dal magazzino più vicino tra tutti quelli aperti. Si vuole allora scegliere le p località dove aprire i magazzini in modo da minimizzare la distanza che separa la coppia supermercato-magazzino più lontana. Formulare il problema come programmazione lineare 0-1 (suggerimento: si usino variabili di scelta della località e di assegnamento del supermercato alla località).
Il problema, noto come p-centro, può essere formulato associando
• a ciascuna località i una variabile xi ∈ {0, 1}, che assume valore 1 se e solo se la località viene scelta come sede di un magazzino intermedio
• a ciascuna coppia (i, j) di località-supermercato una variabile xij ∈ {0, 1}, che assume valore 1 se e solo se xi = 1 e il magazzino posto in i serve il supermercato posto in j.
Per come sono definite le xij, deve ovviamente valere il vincolo xij < xi per ogni località i e supermercato j
Poiché ciascun supermercato si rifornisce da un solo magazzino, deve poi aversi
Σ
i xi j = 1 per ogni supermercato jLa distanza del supermercato j dal magazzino prescelto per il rifornimento è data da dj =
Σ
i dijxij per ogni supermercato je la distanza massima dei supermercati dai magazzini prescelti verifica d > dj per ogni supermercato j
Il problema si scrive quindi min d
d >
Σ
i dijxij ∀jΣ
i xij = 1 ∀jxij < xi ∀i, j xi, xi j ∈ {0, 1} ∀i, j
Risolvere il seguente esercizio. La soluzione viene valutata fino a 5 punti.
5. La coperta di Linus
Formulare il problema di coprire i vertici del grafo di figura con un insieme di archi che abbia peso minimo, dove il peso dell’arco ij è fornito dalla seguente tabella. Quale soluzione ottima si otterrebbe con questa formulazione se invece di minimizzare si massimizzasse? Quali vincoli occorre aggiungere per garantire che la soluzione ottima sia minimale?
1 2 3 4 5 6 7
1 - 2 4
2 2 - 6 3
3 6 - 6
4 6 - 2
5 4 3 - 1
6 1 - 5
7 2 5 -
PDF created with pdfFactory Pro trial version www.pdffactory.com
Detta xij una variabile binaria pari a 1 se e solo se l’arco ij appartiene all’insieme prescelto, il problema si formula
min 2x12 + 4x15 + 6x23 + 3x25 + 6x34 + 2x47 + x56 + 5x67 x12 + x15 > 1
x12 + x23 + x25 > 1 x23 + x34 > 1 x34 + x47 > 1 x15 + x25 + x56 > 1 x56 + x67 > 1 x47 + x67 > 1 xij ∈ {0, 1} per ogni ij∈E
Se invece di minimizzare si volesse massimizzare si otterrebbe banalmente una soluzione identicamente pari a 1, corrispondente all’intero insieme E. Per garantire che la soluzione ottima del problema sia minimale non occorre aggiungere vincoli. Infatti i pesi degli archi sono positivi: se perciò la soluzione ottima fosse non minimale sarebbe possibile ridurne il peso eliminando uno dei suoi archi.
