Ricerca operativa - Esercizi

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

Corso di Ricerca Operativa, A.A. 2007/2008

Prof. Improta - Prova d'esame del 6 maggio 2008

Quesito 1

Dato il seguente problema di programmazione lineare:

max 3x₁ + x₂

s.t.

(1) x₁ + 2x₂ ≤ 24

(2) x₂ ≥ 4

(3) -2x₁ + x₂ ≤ 2

(4) 4x₁ - 3x₂ ≤ 8

x₁ ≥ 0, x₂ ≥ 0

1. Si disegni il dominio di ammissibilità;
2. Si disegni sul grafico la funzione obiettivo e la direzione del gradiente;
3. Si risolva graficamente il modello, individuando il vettore corrispondente alla soluzione ottima e i corrispondenti vincoli saturi;
4. Si individui che eventuali vertici corrispondenti a soluzioni degeneri, specificando anche se sono ammissibili o meno;
5. Si indichino tutte le soluzioni di base, ammissibili e non ammissibili, individuabili sul grafico e desumibili da esso, specificando la composizione della base;
6. Si calcoli analiticamente la soluzione ottima, utilizzando uno dei metodi di simplesso noti;
7. Si indichi sul grafico la successione dei vertici, non ammissibili ed ammissibili, toccati durante la ricerca della soluzione ottima.

Quesito 2

Con riferimento alla soluzione ottima determinata al quesito 1, si effettui l'analisi di stabilità in modo grafico ed analitico:

• Per il termine noto relativo al vincolo (4);
• Per il coefficiente di costo relativo alla variabile x₂.

Quesito 3

Con riferimento al modello di PL del quesito 1:

1. Si scriva il modello matematico del suo problema duale;
2. Si spieghino le operazioni effettuate per ottenerlo;
3. Si determinino i valori delle variabili del problema duale all'ottimo.

Quesito 4

Si consideri l'introduzione di una terza variabile x₃, con coefficiente di costo pari a 2 e vettore colonna dei tassi di assorbimento associato alla variabile pari a [-5,3,4,6]. Si determini la nuova soluzione ottima, a partire dalla soluzione ottima individuata al quesito 1.

Quesito 5

Si discuta sotto quali condizioni risulta conveniente l'utilizzo dell'algoritmo del simplesso revisionato rispetto al simplesso standard, con riferimento alla minimizzazione delle risorse computazionali.

Quesito 6

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

1. Si determini l'arborescenza dei minimi percorsi relativa al nodo origine, con etichetta 1, utilizzando l'algoritmo di Dijkstra;
2. Si illustrino i passi teorici 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.

Tempo massimo a disposizione 3 ore. Rispondere ai quesiti, ed ai sottquesiti, 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.