Ricerca operativa - Esercizi

Università degli Studi di Napoli "Federico II" - Facoltà di IngegneriaCorso di Ricerca Operativa

Prof. IMPROTA - Prova d'esame del 08 07 2011(Tempo a disposizione: 9 CFU: 3 ore 45’ – 6 CFU: 3. ore 15’ )

Quesito 1 [per tutti] **Si consideri il problema PL:

(*)   z = x₁ + 2x₂ Max!   s. a     (1)   -4x₁ + 3x₂ ≥ 0     (2)   -8x₁ + 3x₂ ≤ 0     (3)   -x₁ + 2x₂ ≥ 5     (4)   x₂ ≤ 8         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.

1. 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;
2. 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.
3. 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;
4. 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;
5. 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, se necessario, le si descriva con chiarezza facendole 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;
6. 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 il rapporto b/a_is risulta minimo in più di una riga, si deve scegliere come riga pivot la prima di esse)
7. 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) a quale vertice (ammissibile o non ammissibile) corrisponda;
8. si scrivano le matrici B e B¹ relative alla soluzione ottima; motivando metodologicamente come sono state individuate;
9. si indichino i valori delle variabili duali chiarendo metodologicamente come sono stati individuati;
10. si effettui l’analisi parametrica dei termini noti, determinando soltanto il valore del parametro r che determina un primo cambiamento di base, avendo assunto come vettore dei tassi di variazione il vettore v = [0, 0, 1, -2]^T;
11. si trasformi la funzione obiettivo in x₁ + a z₂ Max! e, si individui, con un metodo a piacere, la successione di vertici ottimi che si verifica al variare di a (-∞