Ricerca operativa - Esercizi

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

Corso di Ricerca Operativa

Prof. Improta - Prova d'esame del 20 07 2011

(Tempo a disposizione: 9 CFU: 3 ore 45' - 6 CFU: 3 ore 15')

Quesito 1

Si consideri il problema PL:

(*) z = 4x₁ + 3x₂ - 140 Max!

s. a

(1) 4x₁ + 5x₂ >= 80

(2) x₂ <= 20

(3) x₁ <= 20

(4) 4x₁ - 3x₂ >= 0

x₁, x₂ >= 0

(*) I vincoli e le slack ad essi associate dovranno essere richiamati nel grafico e nel compito utilizzando esclusivamente la numerazione dei vincoli proposta in tabella. I vertici del dominio dovranno essere indicati con le lettere dell'alfabeto maiuscole (A, B, C, ...) a partire dal vertice più vicino all'origine degli assi. Ai vertici seguiranno le intersezioni dei vincoli non corrispondenti a vertici.

Richieste

• Assumendo orizzontale l'asse delle x₁ si disegni (su di un foglio quadrettato a parte sul quale deve essere riportato solo il grafico) il dominio di ammissibilità del problema, la direzione del gradiente e quella della funzione obiettivo;
• Si dica e si motivi se esistono vincoli ridondanti (che non siano quelli di ammissibilità) e, qualora esistano, a meno che non tocchino la frontiera del dominio, li si escluda da tutte le considerazioni successive.
• Si risolva graficamente il modello, individuando il vertice o i vertici cui corrisponde il massimo di z; si indichino i vincoli saturi e si calcoli, a partire dai risultati dell'analisi grafica, il valore che tutte le variabili del problema (variabili di decisione e slack) e la funzione obiettivo assumono in esso;
• Si indichino, motivandone la scelta, gli eventuali vertici, o intersezioni di vincoli presenti nel grafico, ai quali corrispondano soluzioni di base degeneri; si indichi il numero delle soluzioni di base degeneri complessivamente presenti;
• Si calcoli il numero massimo delle soluzioni di base, si dica quante di esse sono ammissibili e quante non ammissibili e le si indichi o, solo se necessario, le si descriva con chiarezza facendo riferimento alla rappresentazione grafica del problema; si fornisca la composizione della base solo per una soluzione di base non ammissibile, chiarendo quale o quali variabili sono non ammissibili ed il valore che assumono;
• Utilizzando l'algoritmo del simplesso standard in due fasi si ricavi la soluzione "massima" del problema: valori delle variabili decisionali, delle slack e della funzione obiettivo; (Portare innanzi i calcoli utilizzando, nel caso, valori frazionari - Attenzione - Se più variabili sono candidate ad entrare in base deve essere scelta quella che presenta il coefficiente di costo modificato più favorevole. Non deve essere utilizzata la regola di Bland; se, in una iterazione il rapporto b/ais risulta minimo in più di una riga, si deve scegliere come riga pivot la prima di esse)
• Si elenchi, sinteticamente, la successione di tutte le soluzioni di base (non ammissibili ed ammissibili) incontrate dall'algoritmo per giungere alla soluzione ottima, chiarendo per ciascuna di esse (soluzione b.a. o soluzione b.n.a.), utilizzando la lettera con la quale è stato contrassegnato, a quale vertice (ammissibile o non ammissibile) corrisponda;
• Si scrivano le matrici B e B^-1 relative alla soluzione ottima; motivando metodologicamente come sono state individuate;
• Si indichino i valori delle variabili duali chiarendo metodologicamente come sono stati individuati e spiegando il motivo del segno che esse assumono;
• Si imposti l'analisi parametrica dei termini noti, avendo assunto come vettore dei tassi di variazione il vettore v = [0, 0, -1, 2] e si calcoli il valore del parametro t che determina il primo cambiamento della base ottima;
• Si trasformi la funzione obiettivo in x₁ + a x₂ Max!, e si individui, con un metodo a piacere, la successione di vertici ottimi che si verifica al variare di a (0 <= a < +oo), indicando in quale modo siano stati ottenuti i valori di a che determinano la transizione da ogni base alla successiva e quale variabile esce e quale entra nella nuova base; [solo 9 crediti]
• Si scrivano le espressioni che si utilizzano, nell'analisi di stabilità dei termini noti, per calcolare Delta b_i⁺ e Delta b_i^- e si chiarisca come si ricavano; per il problema PL risolto, si individui numericamente e graficamente l'intervallo di stabilità della soluzione ottima per variazioni del termine noto del vincolo 4 e si indichi l'effetto che la traslazione del vincolo produce sul valore della funzione obiettivo;