04 07 12

Page 1

Nome: Cognome: Matricola : 1. Un falegname deve tagliare dei listelli di varie lunghezze da dei bastoni di identica sezione. I listelli di cui ha bisogno il falegname sono di n tipi. Per ogni tipo di listello i la lunghezza ` eli e la quantit` a richiesta ` eri. I bastoni in commercio sono di m tipi. Ogni tipo di bastone j ha lunghezza Lj e costo cj. Il falegname deve decidere quanti bastoni acquistare per ogni tipo e come ricavare i listelli con l’obiettivo di minimizzare i costi. Fornire un modello lineare del problema specificando il significato delle variabili, i vincoli e la funzione obiettivo. V ariante: come si modifica il modello se si considera che la lama utilizzata per il taglio ha una ampiezza di α, quindi il taglio di ogni listello spreca α unit` a di lunghezza. 2. Si consideri il seguente grafo. Si calcoli l’albero dei cammini minimi di radice 1. Nel caso del grafo in esame, quale algoritmo ` e pi` u efficiente? Riportare i passaggi intermedi del calcolo. 3. In una fabbrica sono presenti q macchine identiche. In una giornata di lavoro sono da processare n lavori. I lavori sono tutti disponibili subito. Ogni lavoro ha tempo di esecuzione unitario e pu` o essere eseguito in ogni istante. Una volta iniziato, un lavoro non pu` o essere interrotto. La titolare della fabbrica ha un contratto con i committenti che le fanno pagare una penalit` a dicj(t) se il lavoroj viene terminato al tempot,j = 1,...,n , dovecj(t) ` e una funzione crescente del tempo t. Formulare il problema di assegnare i lavori alle macchine minimizzando il costo complessivo in termini di flusso di costo minimo. Specificare i nodi e gli archi del grafo, i bilanci, i costi e le capacit` a. Esame 4/7/2012 1 Fond. Ricerca Operativa, MAT Nome: Cognome: Matricola : Seconda Parte 4. Si consideri il…