Appello Straordinario – 12/04/2017 1

RICERCA OPERATIVA (a.a. 2016/17)

1 2 3 49 4

3

1

5

4

71

35 6 7 8

5 54 6

24 2

1) Si determini un albero (foresta) dei cammini minimi con insieme diradici R = {3, 8} per il grafo in figura, utilizzando l’algoritmo piu effi-ciente dal punto di vista della complessita computazionale e motivando lascelta effettuata. Per ciascuna iterazione si forniscano il nodo i selezion-ato, l’insieme Q (se utilizzato), i vettori delle etichette e dei predecessori.Al termine si disegni e si discuta la soluzione individuata, discutendonel’unicita. Infine, si discuta ottimalita e unicita della soluzione ottenuta nelcaso in cui il costo dell’arco (4, 3) fosse c43 = −7. Giustificare le risposte.

2) Si enunci e dimostri formalmente la complessita dell’algoritmo SPT.L.Queue.

3) Si consideri il problema di PL dato, parametrico in ε, e la soluzione x =[1, 2, 1]: utilizzando il il teorema degli scarti complementari si determini perquali valori di ε la soluzione x e ottima, discutendone l’unicita al variaredi ε. Giustificare le risposte.

max 3x1 + 6x2 + εx3

x1 + x2 + 2x3 ≤ 7x1 + 2x2 ≤ 5

−x1 + 3x2 − x3 ≤ 5x2 − 3x3 ≤ 0

A2

A1

c

A3

A4 A5

A6

4) Si risolva geometricamente, per mezzo dell’algoritmo del SimplessoDuale, il problema di PL in figura a partire dalla base B = {2, 3}. Si notiche c e collineare ad A1 e A5, e perpendicolare ad A2 ed A6, che sonocollineari; inoltre, anche A3 ed A4 sono collineari. Per ogni iterazione siindichino: la base, la soluzione primale di base (in figura), l’indice en-trante k, i segni delle componenti dei vettori yB e ηB e l’indice uscente h,giustificando le risposte. Al termine si discuta quali vincoli del problemapotrebbero essere eliminati senza modificare la conclusione ottenuta, gius-tificando la risposta fornita mediante i risultati ottenuti dell’algoritmo.

5) Una fonderia deve produrre 1000 lingotti del peso ciascuno di un chilogrammo. Per questo puo comprare il ferroda tre diversi fornitori, ciascuno dei quali propone condizioni di vendita differenti:

A fino a 350kg il ferro costa 0.03 e/kg, oltre 350kg e fino a 750kg costa 0.05 e/kg, oltre 750kg costa 0.08 e/kg;

B fino a 600kg il ferro costa 0.04 e/kg, oltre 600kg costa 0.02 e/kg, ma ordini maggiori di 450kg e minori di 600kgnon possono essere accettati;

C pagando 10e si puo ordinare qualsiasi quantita di ferro compresa tra 100kg e 400kg; oltre i 400kg, il ferro costa0.06 e/kg, mentre non si possono ordinare quantita inferiori ai 100kg.

Inoltre, per precedenti accordi commerciali, se si ordinano almeno 100kg dal fornitore C allora se ne devono ordinarealmeno 200kg dal fornitore A. Si scriva in forma di PLI il problema di determinare il piano di acquisto dai tre diversifornitori che minimizza il costo del ferro.

6) Si applichi alla seguente istanza del problema dello zaino

max 6x1 + 9x2 + 7x3 + 5x4 + 4x5 + 1x6

3x1 + 5x2 + 4x3 + 3x4 + 3x5 + 2x6 ≤ 14x1 , x2 , x3 , x4 , x5 , x6 ∈ {0, 1}

l’algoritmo Branch&Bound che utilizza il rilassamento continuo per determinare la valutazione superiore, l’euristicaGreedy CUD per determinare la valutazione inferiore, esegue il branching sulla variabile frazionaria, visita l’albero dienumerazione in modo depth-first e, tra i figli di uno stesso nodo, visita per primo quello in cui la variabile frazionariae fissata a 0. Si esegua l’algoritmo fino al momento in cui si possa certificare di avere ottenuto una soluzione con unerrore assoluto pari al massimo a ε = 1.5, sfruttando questa condizione per velocizzare l’algoritmo. Per ogni nododell’albero si riportino le soluzioni ottenute dal rilassamento e dall’euristica (se vengono eseguiti) con le corrispondentivalutazioni superiore ed inferiore; si indichi inoltre se viene effettuato il branching, e come, o se il nodo viene chiusoe perche. Al termine si giustifichi formalmente il fatto che la soluzione ottenuta rispetta la condizione richiesta, ossiaha un valore della funzione obiettivo distante dal valore ottimo non piu di ε.