Ricerca operativa - Esercizi

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

Corso di Ricerca Operativa

Prof. Improta - Prova d'esame del 27 03 2010

Quesito 1

Si consideri il problema PL:

z = -2x₁ + x₂ Max!

s. a.

-3x₁ + 2x₂ ≤ 60

x₁ + x₂ ≥ 5

x₁ + x₂ ≥ 10

x₁ ≥ 0

x₂ ≥ 0

x₁ ≤ 0; x₂ ≤ 0

(*) I vincoli e le slack ad essi associate dovranno essere richiamati nel compito riferendosi alla numerazione dei vincoli proposta.

1. Assumendo orizzontale l'asse delle x₁ si disegni (su di un foglio quadrettato separato) il dominio di ammissibilità del problema, così come viene presentato, la direzione del gradiente e quella della funzione obiettivo;
2. Si dica se e 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 ottimo (o i vertici ottimi), i corrispondenti vincoli saturi e calcolando, 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, corrispondenti a soluzioni di base degeneri presenti nel grafico; si indichi il numero delle soluzioni di base degeneri 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 elenchi, se necessario, le si descriva con chiarezza facendo riferimento alla rappresentazione grafica del problema; si fornisca la composizione della base solo per due soluzioni di base non ammissibili, dichiarando quale e quali variabili sono negative;
6. Utilizzando l'algoritmo del simplesso in due fasi si ricavi la soluzione ottima del problema: valori delle variabili decisionali, delle slack e della funzione obiettivo; (Si suggerisce di riportare innanzi i calcoli utilizzando, nel caso, vari frazionari – Qualora vi siano più variabili candidate ad essere entrante in base deve essere quella che presenta il coefficiente di costo modificato più favorevole. Non deve essere utilizzata la regola di Bland);
7. Si indichi, sinteticamente, la successione di tutte le soluzioni di base (non necessariamente 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 scrivino le matrici B e B* relativa alla soluzione ottima; chiarendo come sono state individuate;
9. Si indichino i valori delle variabili duali chiarendo come sono stati individuati;
10. Si trasformi il vincolo (4) in -x₁ + x₂ ≥ 8 e si individui, con un metodo a piacere, la successione di vertici ottimi che si verifica al variare di a ∈ [10
11. Si individui numericamente l'intervallo di stabilità della soluzione ottima per variazioni del coefficiente di costo della variabile x₁;
12. Si mostri analiticamente se l'introduzione del nuovo vincolo x₂ ≤ 8 altererebbe la base ottima trovata e, nel caso, si individui la nuova base ottima.

Quesito 2

Si consideri il problema PL:

z = x₁ + x₂ Max!

s. a.

x₁ + 3x₂ ≤ 20

x₁ - x₂ ≤ 0

x₁ - x₃ ≤ 15

x₁; x₂ ≥ 0

1. Se ne scriva il problema duale;
2. Lo si risolva graficamente o analiticamente;
3. Utilizzando il teorema dello scarto complementare si ricavi la soluzione ottima del problema duale.

Quesito 3

Gigione Sposito, piccolo artigiano e venditore ambulante, ha la possibilità di lavorare, con l'aiuto del cognato e delle loro numerose famiglie, 5 varietà di frutta secca (che vengono vendute per le strade di Napoli con appositi carrettini): (1) noccioline americane, (2) nocciole tostate e sgusciate, (3) carubbe, (4) ceci e (5) semi di zucca.

Per incrementare l'attività, Gigione ha deciso di attrezzarsi con due tipi di macchine presi in leasing. La Shell-Dry Machine, per l'essiccamento e lo sguasciatura, e la Shell-Roast Machine, per la tostatura e la sgucciolatura (in grado di lavorare lotti di frutta secca di 1 kg per volta), e ne ha acquistato 2 del primo tipo e 1 del secondo, da un'industria vestegealizzata nel settore, con un prestito delle sorelle.

Ha poi sfruttato, con pagamento differito di un anno, l'uso di parte di un secondo, di proprietà di una famiglia cinese, in cui le macchine potrebbero essere tenute in