Ricerca Operativa - Esercitazione

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

Corso di Ricerca Operativa

Prof. IMPROTA - Prova d'esame del 2002 12

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

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:

(*) z = 4x₁ + 2x₂, Max!

4x₁ + x₃ ≤ 2

2x₁ + x₂ ≤ 6

3x₁ + x₃ ≤ 18

6x₁ + x₂ ≤ 30

x₁, x₂ ≥ 0

(*) I vincoli e le slack ad essi associate dovranno (*) 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.

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 e slack) e la funzione obiettivo assumono in esso;

Si indichino, motivandone la scelta, gli eventuali vertici, o intersezioni di vincoli dei 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 chiedendo il modo con cui esso viene calcolato, sì che quante di esse sono ammissibili, quante non ammissibili e quali corrispondano a punti all'infinito e le si indichi o, solo se necessario, le si descriva con chiarezza facendo riferimento alla rappresentazione grafica del problema;

Utilizzando l'algoritmo del simplesso standard in due fasi di ricavo e, se necessario, si discutano le soluzioni "minima" e "massima" del problema: valori delle variabili decisionali, delle slack e della funzione obiettivo: (Portare innanzi a 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 un'iterazione il rapporto b/a_ik 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 dalla prima tabella della prima fase sino a giungere alla soluzione "massima", chiarendo per ciascuna di esse (soluzione b.a. o soluzione b.a.n.u.), utilizzando la lettera o le lettere a) e b) stata contrassegnata nel grafico, a quale vertice (ammissibile o non ammissibile) corrisponda;

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

Si indichino i valori, in corrispondenza del "massimo" delle variabili duali chiarendo metodologicamente come sono stati scelti e precisando il motivo del segno che esse assumono;

Si scrivano le espressioni di se utilizzano, nell'analisi di stabilità dei termini noti, per calcolare Ab^* e Ab^*; e si chiarisca il principio a partire dal quale esse si ricavano; nel ripertema PL risolto, si individuino numericamente e graficamente le frontiere di stabilità della soluzione ottima per variazioni del termine noto del vincolo 5 e si indichi l'effetto che la nuova soluzione lineare subisce sul valore della funzione obiettivo.

Quesito 2

Si consideri il problema di programmazione lineare:

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

4x₃ + x₁ - 2x₃ ≤ 7

4x₃ + x₁ - 2x₃ ≥ 12

3x₂ - x₂ ≤ 6

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