Prova del 12/01/2016

RICERCA OPERATIVA II a.a. 2015/16
Laurea Magistrale Ingegneria Gestionale
12 gennaio 2016 - 1◦ appello
Nome:
Cognome:
Matricola:
Esercizio 1.
Si vuole ottimizzare la composizione ed il carico di un treno merci. Sono disponibili m vagoni. Per
ogni vagone i ∈ {1, . . . , m} è nota la capacità in peso bi , la lunghezza li ed il costo variabile di utilizzo cvi
per ogni unità di merce caricata in esso. Sono date n unità di merce da caricare. Per ogni unità di merce
j ∈ {1, . . . , n} è noto il peso wj ed il sottoinsieme di vagoni Ij ⊆ {1, . . . , m} in cui può essere caricata.
Si desidera caricare tutta la merce in modo da minimizzare il costo di utilizzo dei vagoni e garantendo
che la lunghezza complessiva del treno non superi L.
1. Determinare un modello ILP di tipo “descrittivo” con variabili binarie che dicano se una certa unità
merce è assegnata ad un certo vagone;
2. Dimostrare la complessità del problema della determinazione di una soluzione ammissibile;
3. Determinare un algoritmo euristico guidato dal rilassamento continuo del modello definito al punto
1;
4. Determinare un modello ILP di tipo “pattern” con variabili binarie associate ad ogni possibile
assegnamento di merci ad un vagone;
5. Per il modello del punto 4, si definisca un modello ILP per il problema della generazione di colonne;
6. Determinare un modello ILP per la variante del modello al punto 1 in cui si vuole rispettare la
seguente condizione logica: se il peso del carico del vagone 1 è maggiore di w̄ allora (=⇒) il vagone 2
deve far parte della composizione del treno e (∧) la lunghezza massima del treno è L + K (K > 0).
Esercizio 2.
Definire il concetto di disuguaglianza valida per un poliedro.