Ricerca Operativa - Esercizi vari

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

Corso di Ricerca Operativa

Prof. Improta - Prova d'esame del 31 03 12

(Tempo a disposizione: 9 CFU: 3 ore 45’ – 6 CFU: 2 ore 45’ - Integrazione 3 CFU 1 ora)

Le risposte ai quesiti (ed ai sottoquesiti) devono apparire necessariamente nel medesimo ordine in cui sono posti nel compito. Utilizzare fogli a quadretti, numerare i fogli e segnare cognome nome e matricola. Non scrivere a matita. Compiti scritti con calligrafie illeggibili non saranno corretti.

Quesito 1

Si consideri il problema PL:

(*)

(1)

(2)

(3)

(*)

a. 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;

b. 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 tutte le considerazioni successive.

c. Si risolva graficamente il modello, individuando il vertice o i vertici cui corrisponde il massimo di z; si indichino i vincoli saturi e si specifichino, a partire dai risultati dell’analisi grafica, i valori delle variabili del problema (anche non di slack) e la funzione obiettivo assumono essi;

d. Si indichino, motivandone la scelta, gli eventuali vertici, o intersezioni di vincoli presenti nel grafico, ai quali corrispondono soluzioni di base degeneri; si indichi il numero delle soluzioni di base degeneri complessivamente presenti;

e. Si calcoli il numero massimo delle soluzioni di base chiarendo il modo con cui esso viene calcolato. Si dica quante di esse sono ammissibili, quante non ammissibili e quali corrispondono a punti all’infinito e le si indichi o, solo se necessario, le si descriva con chiarezza facendo riferimento alla rappresentazione grafica del problema;

f. Utilizzando l’algoritmo del semplice standard in due fasi si ricavi la soluzione ottima del problema: valori delle variabili decisionali, delle slack e della funzione obiettivo; (Portare innanzi al calcolo 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/a è degenerato per più di una riga, si deve scegliere come già previsto la prima di esse)

g. Si elenchi, sinteticamente, la successione di tutte le soluzioni di base (non ammissibili ed ammissibili) incontrate dall'applicazione della prima tabella della prima fase a giungere alla soluzione "massima", chiedendo per ciascuna di esse (soluzione b.a. o soluzione b.n.a.), utilizzando la lettera con la quale è stata contrassegnata nel grafico, a quale vertice (ammissibile o non ammissibile) corrisponda;

h. Si scrivano le matrici B e B^-1 relative alla soluzione "massima", motivando metodologicamente come sono state individuate;

i. Si indichino i valori, in corrispondenza del “massimo” delle variabili duali chiarendo metodologicamente come sono stati individuati e spiegando il motivo del

Quesito 2

Si consideri il problema di programmazione lineare:

z = 3x₁ - 9x₂ + 7x₃ Min!

(1) -2x₂ + 2x₃

(2) x₁ - 3x₂ + x₃ ≥ 0.5

x₁, x₂, x₃ ≥ 0

a. Utilizzando il teorema dello scarto complementare, se ne ricavi la soluzione ottima e se ne discutano le soluzioni ottime del diretto e del duale.