17 11 12

Page 1

Nome: Cognome: Matricola : 1. Si determini l’albero di copertura di costo minimo per il grafo in figura illustrando i passaggi intermedi del procedimento adottato. 1 3 2 4 5 67 1 6 7 4 3 29 8 10 2 8 Domanda aggiuntiva: Dopo aver determinato la soluzione, si consideri l’aggiunta di un nuovo arco (1,4) di costo 5. Questo arco ` e utile per migliorare il costo della soluzione? Perch´ e? Si consideri anche l’arco (1,7) di costo 5. Questo arco ` e utile per migliorare il costo della soluzione? Perch´ e? 2. Si determini il flusso massimo per il problema in figura a partire dal flusso dato. Si illustrino i passaggi intermedi. Indicare il taglio di capacit` a minima. 1 3 2 ts 4 5,53,8 4,4 4,7 0,3 2,3 5,10 2,2 i jxij,uij 3. Una azienda produce 2 tipi di robot. Il robot A richiede 1 scheda di tipo 1 e 4 schede di tipo 2, il robot B richiede 2 schede di tipo 1 e 3 di tipo 2. La capacit` a massima di produzione (p) di robot (tipo A pi` u tipo B) ` e di 50 al giorno. La richiesta di robot per i prossimi n giorni ` e data dadAt edBt rispettivamente per i robot A e B, per t = 1,...,n . Mentre la disponibilit` a di schede 1 e 2 nei vari giorni ` e data da b1t e b2t per t = 1,...,n . Si noti che le schede disponibili e non utilizzate nel giorno t non sono utilizzabili i giorni successivi. L’azienda dispone di un magazzino (inizialmente vuoto) di capacit` aK in cui pu` o immagazzinare i robot pronti per la vendita nei giorni successivi. L’azienda deve soddisfare esattamente la domanda e incorre in un costo di magazzino quantificabile in cA e cB per robot per giorno a seconda del tipo. Formulare il problema di minimizzare il costo di magazzino, rispettando i vincoli di disponibilit` a di risorse, di capacit` a di produzione e di magazzino e soddisfacendo esattamente la domanda. 4. Un…