Ricerca operativa - Esercizi

Question 1

La NewSerene SpA gestisce gli impianti sciistici di una nota località montana dell'Appennino Abruzzese. Il Sig. Rossi, responsabile dei sistemi di innevamento, preoccupato per la scarsezza delle precipitazioni nevose verificatasi durante la fine dell'autunno e la prima parte della stagione invernale e per le non confortanti previsioni meteorologiche relative ai mesi di febbraio e di marzo, in vista dell'inizio del periodo delle settimane bianche, ha deciso di cambiare i vecchi cannoni spara-neve, utilizzati nell'impianto di innevamento artificiale esistente, sostituendoli con altri, di più moderna concezione, di maggiore capacità e di maggiore efficienza.

Dopo un'attenta analisi di mercato, la sua attenzione si è concentrata sui prodotti offerti dalla SnowGun srl. Tra i cannoni presenti in listino gli sono apparsi di interesse per le esigenze della NewSerene due modelli che, per le loro prestazioni, sembrano essere coerenti con le caratteristiche delle piste da innevare e dell'impianto esistente: il MediumGun (capacità di innevamento 8 m³/h di acqua/ora; costo di listino 20.000 Euro/cannone) ed il SuperGun (capacità di innevamento 15 m³/h di acqua/ora; costo di listino 30.000 Euro/cannone), indicati per l'innevamento delle piste verdi ed azzurre, e di quelle rosse e nere, rispettivamente.

Tenendo conto dell'attuale dotazione di cannoni, dei possibili punti di attacco alla rete idrica, delle caratteristiche delle piste e di una certa incertezza esistente nei listini dei due modelli, il Sig. Rossi ha stimato che di cannoni del modello MediumGun ne se dovrebbero acquistare almeno 5 e di SuperGun ne se dovrebbero acquistare almeno 10 e che, complessivamente, da due modelli non se ne dovrebbero acquistare più di 25, ed ha fornito tali elementi, insieme alle caratteristiche dei cannoni, alla RO Consultant la quale, utilizzando un modello di PL, ha calcolato, con valore primo richiesti, il numero di cannoni dei due tipi da acquistare in grado di massimizzare la capacità complessiva di innevamento artificiale dell'impianto. Sulla base di quest'ultimo studio, il Sig. Rossi ha invitato un ordine da inviare urgente alla SnowGun srl.

1. Si formuli il modello in programmazione lineare utilizzato dalla RO Consultant, sulla base delle prime indicazioni del Sig. Rossi, illustrando le diverse componenti ed elencando i vincoli nell'ordine in cui sono stati presentati;
2. Si disegni il dominio di ammissibilità;
3. Si disegni su grafico le direzioni dei gradienti delle funzioni obiettivo per la massimizzazione della capacità di innevamento e per la minimizzazione del costo complessivo di acquisto;
4. Si risolva graficamente il modello, individuando i vertici corrispondenti alle soluzioni di minimo costo e di massimo innevamento ed i corrispondenti vincoli saturi;
5. Utilizzando uno degli algoritmi risolviati si rinviano la soluzione di minimo costo e quella di massimo innevamento;
6. Si indichi sul grafico la successione dei vertici (non ammissibili ed ammissibili) toccati durante la ricerca della soluzione ottima.

Question 2

1. Si effettui l'analisi di stabilità della soluzione a massima capacità di innevamento al variare del termine noto relativo al massimo numero di cannoni;
2. Si indichi di quanto potrebbe aumentare la capacità di innevamento se il numero massimo di cannoni dei due tipi da acquistare passasse da 25 a 26.

Question 3

Con riferimento al problema PL formulato dalla RO Consultant e risolto in quel no quesito 1:

1. Si scriva il modello matematico del suo problema duale;
2. Si scrivano il relativo significato delle variabili duali;
3. Si risolva con l'algoritmo del simplesso il problema duale formulato;

Question 4

Il Sig. Verdi, responsabile commerciale della SnowGun, esamina l'ordine, sulla base delle disponibilità esistenti a magazzino e dei lotti producibili a breve, ha rinviato alla NewSerene una accettazione preliminare della richiesta della NewSerene, allegando, però, ad essa, una controproposta così formulata: qualora venissero acquistati almeno 10 cannoni del modello MediumGun, ed i cannoni SuperGun e MediumGun fossero nel rapporto 3 a 2, potrebbe essere praticato uno sconto del 10% sui prezzi di listino per entrambi i tipi di cannoni ed, inoltre, al totale verrebbe detratto un bonus di 50.000 Euro. Esaminata tale controproposta il Sig. Rossi ha inoltrata alla RO Consultant per le opportune controduzioni.

1. Si modifichi il primo modello in programmazione lineare utilizzato dalla RO Consultant, introducendo gli elementi contenuti nella controposta del Sig. Verdi illustrando ed elencando i vincoli nell'ordine in cui sono stati presentati;
2. Si disegni il nuovo dominio di ammissibilità;
3. Si indichino tutte le soluzioni di base (ammissibili e non ammissibili) individuabili sul nuovo grafico, specificando la composizione della base per due soluzioni di base ammissibili e due non ammissibili scelte a piacere;
4. Si indichino gli eventuali vertici corrispondenti a soluzioni degeneri presenti nel dominio;
5. Partendo dalla soluzione ottima del primo quesito, si introducano i vincoli contenuti nella controposta del Sig. Verdi e si calcolino le variazioni che essi determinano sullo soluzione a massimo innevamento;
6. Si formulino le controduzioni della RO Consultant, indicando se la controposta del Sig. Verdi è conveniente.

Question 5

Con riferimento al grafo riportato in figura con i relativi pesi sugli archi.

1. Si determini l'arborizzazione dei minimi percorsi relativo al nodo origine utilizzando l'algoritmo di Dijkstra;
2. Si illustrino i passi della procedura utilizzata;
3. Ipotizzando che il grafo considerato rappresenti il reticolo delle attività di un progetto e che i costi sugli archi siano le durate delle attività, si determini la durata del progetto, il percorso critico e si costruisca il relativo diagramma di Gantt;
4. Supponendo il grafo non orientato, se ne determini, utilizzando uno degli algoritmi noti (Kruskal, Sollin o Prim) un albero minimo.

Tempo massimo a disposizione 3 ore. Rispondere ai quesiti (ed ai sottoquesiti) nel medesimo ordine in cui sono posti. Scrivendo in modo chiaro. Utilizzare fogli a quadretti, numerando i fogli e segnando cognome, nome e matricola in alto a destra.