Ricerca operativa - esercizi

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

Corso di Ricerca Operativa

Prof. IMPROT A - Prova d'esame del 17 2009

lO

Quesito 1

Si consideri il problema PL: >

<

+

:::; 30

z= 40/3

40

4x] 10x2

Max!

(*) +

x] X2 2: 20

+

s. a Xl Xj,X22:0

XI 4X2 XJ

(1)

(2)

(3)

(4)

(*) Nel seguito i vincoli e le slack ad essi associate dovranno essere richiamati riferendosi alla

numerazione dei vincoli proposta.

a. Assumendo orizzontale l'asse delle se ne disegni il dominio di ammissibilità, ]a direzione del

XI

gradiente e quella della funzione obiettivo;

b. si dica se esistono o meno vincoli ridondanti e, qualora esistano, a meno che non tocchino la

frontiera del dominio, li si escluda da tutte le considerazioni successive.

c. si risolva graficamente il modello, individuando il vertice ottimo (o i vertici ottimi), i corrispondenti

vincoli saturi e calcolando il valore che tutte le variabili del problema (variabili di decisione e slack)

e la funzione obiettivo assumono in esso;

d. si indichino, motivandone la scelta, gli eventuali vertici, o intersezioni di vincoli, corrispondenti a

soluzioni di base degeneri presenti nel grafico;

e. si calcoli il numero delle soluzioni di base, quello delle soluzioni di base ammissibili e quello delle

soluzioni di base non ammissibili e le si indichino o, se necessario, le si descrivano con chiarezza

facendo riferimento alla rappresentazione grafica del problema; si fornisca la composizione della

base solo per una soluzione di base ammissibile ed una di base non ammissibile, chiarendo, per

quest'ultima, quale o quali variabili sono negative;

f. utilizzando uno degli algoritmi di simplesso noti (giustificandone eventualmente la scelta) si ricavi

la soluzione del problema: valori delle variabili decisionali, delle slack e della funzione obiettivo;

a si indichi la successione di tutte le soluzioni di base (non ammissibili ed ammissibili) incontrate

o· dall 'algoritmo per giungere alla soluzione ottima, chiarendo per ciascuna di esse (soluzione b.a. o

soluzione b.n.a.) a quale veliice (ammissibile o non ammissibiJe) corrisponda;

relative alla soluzione ottima; e si indichino i valori delle variabiJi

h. si scrivano le matrici B e B-1

duali chiarendo come i tre elementi siano stati individuati;

l. si calcoli, motivando la metodologia, l'intervallo di stabilità per variazioni del coefficiente di costo

e si indichino graficamente, qualora esistano, le posizioni estreme del gradiente;

della X2 +

si individui graficamente l'intervallo di stabilità per variazioni del termine noto del vincolo

J. XI

indicando, qualora esistano, le posizioni estreme del vincolo;

4X2 :::; 40

k. una volta eliminati eventuali vincoli ridondanti, si mostri analiticamente se l'introduzione del

vincolo ulteriore 2.5 altera la base ottima trovata. e, qualora la alteri, si individui la nuova

X2 :::;

base ottima;

Quesito 2

(a) Si dia la definizione, in PL, di coefficiente di costo modificato di una variabile e si spieghi quale

C'j Xj

è il suo significato geometrico;

(b) si spieghi quale criterio si segue nel determinare la variabile entrante nell'algoritmo del Simplesso

(c) e con quale criterio si individua la variabile uscente nell'algoritmo del SimpJesso?

(d) si spieghi perché per individuare la riga pivot, e, dunque la variabile uscente, si sceglie la riga in

corrispondenza della quale si verifica il minimo dei rappolii b/ais?