RICERCA OPERATIVA GRUPPO A

prova scritta intermedia del 12 febbraio 2002

Rispondere alle seguenti domande. Nelle domande a risposta multipla marcare a penna la lettera corrispondente alla risposta ritenuta corretta (una sola tra quelle riportate). Ogni risposta esatta vale 2 punti.

1. L’involucro convesso di un insieme S Í IRⁿ è

A) un qualsiasi poliedro contenente S

B) un cono poliedrale avente i punti di S come direttrici

C) il più piccolo poliedro contenente S

2. Un matching di un grafo G

A) non contiene nessuna clique di G

B) è un grafo bipartito

C) contiene solo cicli pari

3. Un grafo privo di cicli pari

A) è sempre bipartito

B) non può essere un albero

C) non ha clique con più di tre elementi

4. Un grafo in cui la più grande clique contiene 2 elementi

A) è sicuramente bipartito

B) non è un albero

C) può contenere un ciclo dispari

5. Nella famiglia dei sottoinsiemi di U che hanno cardinalità dispari

A) vale in generale la proprietà di scambio

B) vale la subclusione

C) i massimali hanno tutti la stessa cardinalità

6. In un matroide grafico l’insieme universale U

A) contiene tutti gli archi di un grafo dato

B) contiene tutti gli archi di un grafo dato che non formano cicli

C) contiene tutti i nodi di un grafo dato

RICERCA OPERATIVA GRUPPO A

Risolvere i seguenti problemi. Ogni problema viene valutato da 0 a 6 punti.

7. Sia P = (V, E) un percorso con n nodi e n – 1 archi. Ciascun nodo u Î V (ciascun arco uv Î E) è associato a un peso positivo a_u (b_uv). Rimuovendo un certo insieme di archi si vuole partizionare P in un certo numero di sottografi in modo che

• la somma dei pesi dei nodi di ciascun sottografo non superi un prefissato valore a
• il peso degli archi rimossi sia minimo.

Si definisca un opportuno sistema di indipendenza (U, Á) in modo che i massimali (o i minimali) di Á corrispondano a soluzioni ammissibili del problema. Si costruisca inoltre una funzione peso la cui ottimizzazione corrisponda a una soluzione ottima del problema. Si illustri infine un esempio di percorso pesato in corrispondenza al quale l’algoritmo greedy – applicato al sistema (U, Á) – fallisca nella costruzione di una soluzione ottima.

l’insieme U è formato da	tutti gli archi di P
XÎÁ se e solo se	rimuovendo E – X si ottengono componenti connesse di peso < a
"xÎU, c(x) vale	Il peso bx dell’arco x
Esempio	a = 2 a1, a2, … = 1, 1, 1, 1 b12, b23, … = 2, 3, 2

8. Due operai devono eseguire un certo numero di lavori, ciascuno della durata di un’ora. Per poter essere eseguito, ciascun lavoro richiede la disponibilità di un insieme di attrezzi. Poiché gli attrezzi sono presenti ciascuno in una sola copia e sono condivisi dai due operai, costoro devono mettersi d’accordo sull’ordine in cui eseguire i lavori in modo che i lavori che richiedono un medesimo utensile siano (per quanto possibile) eseguiti in tempi diversi. Formulare in termini di ottimizzazione combinatoria il problema di completare i lavori nel minimo tempo possibile servendosi di un opportuno grafo G. Indicare nella tabella seguente: l’insieme V dei vertici del grafo, l’insieme E dei suoi archi, l’insieme universale U, la regione ammissibile Á e la funzione peso c.

ogni vÎV corrisponde a	un lavoro
uvÎE se e solo se	i due lavori u e v non richiedono un medesimo insieme di attrezzi
l’insieme U è formato da	archi di E
XÎÁ se e solo se	X è un matching
"xÎU, c(x) vale	1

9. Dire se il seguente sistema di disequazioni lineari

2x₁ + 2x₂ – x₄ < 6

x₁ + x₂ – x₃ < 2

x₁ – 4x₂ > –6

x₁ – x₂ + x₄ = 2

ammette o no soluzioni in IR⁴, esibendo in caso affermativo una soluzione.

il sistema	non ammette soluzione |__|
	ammette la seguente soluzione x1 = 2, x2 = 0, x3 = 0, x4 = 0