Ricerca operativa - Esercizi vari

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

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

Sessione estiva - Prova d'esame del 26.09.2002

Risolvere nell’ordine i seguenti esercizi.

Esercizio n. 1

Un’azienda di scatolame produce due prodotti, 1 e 2, i cui profitti unitari per quintale sono rispettivamente pari a 200 e 1000 euro. Ogni giorno devono essere prodotti in totale, tra 1 e 2, al massimo 9 quintali di prodotto. La produzione di 1 deve essere compresa tra 3 e 8 quintali al giorno. Si vuol conoscere quali sono le produzioni giornaliere, espresse in quintali, 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.

-1

(f) Si scrivano la matrice B e la matrice B 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) A quali punti del dominio di ammissibilità di un problema di programmazione lineare corrispondono le soluzioni basiche ammissibili?

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.

4 6 1 2 3 4 5 5 9 5 6 4 5 6 5

Esercizio