Ricerca operativa - Esercitazione

Università degli Studi di Napoli "Federico II" - Facoltà di Ingegneria

Corso di Ricerca Operativa, A.A. 2001 / 2002 (Nuovo Ordinamento)

Prova d'esame del 14.01.2003

Risolvere nell’ordine i seguenti esercizi.

Esercizio n. 1

Un’azienda manifatturiera produce due prodotti, 1 e 2, i cui profitti unitari sono rispettivamente pari a 80 e 20 euro. Ogni giorno devono essere prodotti in totale, tra 1 e 2, al massimo 150 unità di prodotto. La produzione di 2 deve essere compresa tra 20 e 100 unità al giorno. Si vuol conoscere quali sono le produzioni giornaliere di 1 e 2 che rendano massimo il profitto.

Con riferimento al problema descritto:

• (a) Si formuli il modello in programmazione lineare, illustrando le diverse componenti ed elencando i vincoli nell’ordine in cui sono stati presentati;
• (b) Si disegni il dominio di ammissibilità e la direzione della funzione obiettivo;
• (c) Si risolva graficamente il modello, individuando il vertice corrispondente alla soluzione ottima;
• (d) Si indichino le soluzioni basiche ammissibili del problema e la relativa composizione;
• (e) Si risolva il modello analiticamente con il metodo del Big M;
• (f) Si scrivano la matrice B e la matrice B^-1 relative alla soluzione ottima del problema.

Esercizio n. 2

• (a) Si effettui l’analisi di stabilità della soluzione ottima del modello dell’esercizio n. 1 al variare (in incremento e decremento) del termine noto del vincolo relativo alla produzione totale.
• (b) Si indichino graficamente le posizioni limite del vincolo.
• (c) Si indichi inoltre la successione delle soluzioni ottime all’aumentare del coefficiente di profitto del prodotto 2.

Esercizio n. 3

Si trasformi il modello primale dell’esercizio 1 in forma standard e si scriva il corrispondente modello duale.

Esercizio n. 4

Si risponda alle seguenti domande:

• (a) Che cosa è un insieme convesso?
• (b) Perché la soluzione ottima di un problema di programmazione lineare si trova in un vertice del dominio di ammissibilità?
• (c) Che cosa è una soluzione basica ammissibile di un sistema di equazioni lineari con n variabili ed m equazioni?
• (d) In quali circostanze in un problema di programmazione lineare si hanno infinite soluzioni ottime?

Esercizio n. 5

• (a) Si scriva il modello del minimo percorso per una coppia origine/destinazione.
• (b) Con riferimento alla rete in figura si determini l’arborescenza dei minimi percorsi dal vertice 1 a tutti gli altri, utilizzando l’algoritmo di Dijkstra o l’algoritmo di Dantzig.

931 2 384 2 1810 64 5 53

Tempo massimo a disposizione: 2 ore e 30 minuti.