Esercitazione n
o3 per il corso di Ricerca Operativa
Ultimo aggiornamento October 17, 2011
Fornitura acqua
Una citt`a deve essere rifornita, ogni giorno, con 500 000 litri di acqua. Si richiede che l’acqua non contenga sostanze inquinanti in quantit`a superiore a 100 parti per milione.
L’acqua pu`o essere ottenuta da un fiume o da un pozzo. La quantit`a di acqua che pu`o essere fornita dal fiume `e illimitata, e un impianto di depurazione pu`o depurarla in modo che il livello di inquinamento sia inferiore a 150 parti per milione ad un costo di e10 ogni 5 000 litri di acqua trattata o a 75 parti per milione ad un costo di e30 per 5 000 litri di acqua trattata. Il pozzo, invece, pu`o fornire al pi`u 200 000 litri di acqua al giorno con un livello di inquinamento pari a 50 parti per milione. L’acqua fornita dal pozzo pu`o, volendo, essere purificata mediante un processo sperimentale che riduce le impurit`a a 10 parti per milione. Il pompaggio dell’acqua del pozzo costa e40 ogni 5 000 litri e la stessa quantit`a di acqua pu`o essere purificata mediante il processo sperimentale al costo di e15.
Scrivere il problema di PL che permette di determinare il modo di soddisfare le esigenze idriche della citt`a al costo minimo.
Analisi sintetica del problema.
citt´a fiume pozzo
proced. 1 proced. 2 estrazione depurazione 500 000 richiesta/fornitura in lt. illimitato 200 000
al pi`u 100 ppm livello inquinante 150 ppm 75 ppm 50 ppm 10 ppm costo e10/5 000lt. e30/5 000lt. e40/5 000lt. e(40+15)/5 000lt.
variabili di decisione
x1F x2F x1P x2P
Formulazione.
– Variabili di decisione. Scegliamo come variabili di decisione le quantit`a di acqua (in litri) x1F ottenuta dal fiume con procedimento di depurazione 1, x2F ottenuta dal fiume con procedimento di depurazione 2, x1P ottenuta dal pozzo senza depurazione, x2P ottenuta dal pozzo con procedimento di depurazione.
– Vincoli. Si devono imporre i seguenti vincoli:
• Vincoli di domanda: la citt`a deve essere rifornita con 500000 lt.di acqua:
x1F + x2F + x1P + x2P = 500 000
• Vincoli di capacit`a: il pozzo pu`o fornire al pi`u 200000 lt. di acqua:
x1P + x2P ≤ 200 000.
• Vincoli di qualit`a: la qualit`a della miscela `e misurata in parti di sostanze inquinanti per milione, e deve risultare
150x1F + 75x2F + 50x1P + 10x2P
x1F + x2F + x1P + x2P ≤ 100 che fornisce il vincolo lineare
150x1F + 75x2F + 50x1P + 10x2P ≤ 100(x1F + x2F + x1P + x2P).
N.B. Nel caso specifico la quantit`a x1F + x2F + x1P + x2P = 500 000, dunque il vincolo `e equivalente a 150x1F + 75x2F + 50x1P + 10x2P ≤ 100 · 500 000.
• Vincoli di non negativit`a. si tratta di quantit`a acqua, quindi xiF ≥ 0 xiP ≥ 0 i = 1, 2.
– Funzione obiettivo. `E il costo da minimizzare. Il costo `e diverso a seconda della sorgente e del trattamento effettuato e supponiamo che valga l’ipotesi di proporzion- alit`a. Poich´e 5000 lt. di acqua del tipo 1F costano 10000, il costo di x1F lt. di acqua `e (x1F/5000)10000 = 2x1F, analogamente il costo di x2F lt. di acqua prodotti con modalit`a x2F `e (x2F/5000)30000 = 6x2F. Per quanto riguarda l’acqua ottenuta dal pozzo, abbiamo che per la quantit`a x1P dobbiamo pagare solo il pompaggio dato da:
Complessivamente possiamo scrivere il problema di PL min 2x1F + 6x2F + 8x1P + 11x2P
x1F + x2F + x1P + x2P = 500000 x1P + x2P ≤ 200000
50x1F − 25x2F − 50x1P − 90x2P ≤ 0 xiF ≥ 0, xiP ≥ 0 i = 1, 2.
N.B. Si `e scelta la formulazione del vincolo 150x1F + 75x2F + 50x1P + 10x2P − 100(x1F + x2F + x1P + x2P) ≤ 0. Soluzione con uso di Foglio elettronico
Il foglio Microsoft Excel che corrisponde alla rappresentazione dei dati modello `e in figura .La tabella Microsoft Excel che corrisponde alla rappresentazione del modello `e in figura . Risulta x∗1F = 166666.¯6, x∗2F = 333333.¯3, x∗1P = 0, x∗2P = 0
Figure 1: Foglio Excel relativo ai dati del problema
La tabella corrispondente al report di Sensibilit`a `e in figura. Il files corrispondenti sono disponibili in rete.
Figure 2: Foglio Excel relativo al modello del problema
Analizziamo i fogli di report generati da Excel e la soluzione ottima fornita. A questo scopo poniamo il modello in forma standard di PL, aggiungendo le variabili di slack. Al fine di ottenere una completa corrispondenza con il file di Report generato da Excel, `e stata inserita anche la variabile s1 nel primo vincolo di uguaglianza. In una qualunque soluzione ammissibile il valore di s1 `e identicamente nulla. In particolare si ottiene
min 2x1F + 6x2F + 8x1P + 11x2P
x1F + x2F + x1P + x2P + s1 = 500000 x1P + x2P + s2 = 200000
50x1F − 25x2F − 50x1P − 90x2P + s3 = 0 xiF ≥ 0, xiP ≥ 0 i = 1, 2,
si ≥ 0, i = 1, 2, 3.
. I valori delle variabili di slack sono sul Rapporto Valori (”Tolleranza”)e si ha s∗1 = 0, s∗2 = 200000, s∗3 = 0.
Le variabili positive sono tre x∗1F, x∗2F, s∗2 e corrispondono alle tre variabili in base. La matrice di base B∗ `e dunque costituita dalle tre colonne della matrice A corrispondenti,
Figure 3: Foglio Excel del Report di Sensibilit`a del problema La soluzione ammissibile di base corrispondente a B∗ `e ovviamente
x∗1F x∗2F s∗2
=
1 1 0
0 0 1
50 −25 0
−1
500000 200000
0
=
166666.¯6 333333.¯3 200000
,
x∗1P x∗2P s∗1 s∗3
= 0.
Si pu`o risolvere il sistema dei vincoli rispetto ad xB∗ =
x1F x2F
s2
, ovvero scrivere xB∗ =
Figure 4: Report Valori
B∗−1b − B∗−1N∗xN∗ e si ottiene il problema ridotto nelle sole variabili xN∗ =
x1P x2P s1 s3
:
min (2 6 0)
166666.¯6 333333.¯3 200000
+ γNT∗
x1P x2P
s1 s3
166666.¯6 333333.¯3 200000
−
1 1 0
0 0 1
50 −25 0
−1
1 1 1 0
1 1 0 0
−50 −90 0 1
x1P x2P
s1 s3
≥ 0
xiP ≥ 0 i = 1, 2, si ≥ 0, i = 1, 3.
dove
1 1 0−1 1 1 1 0
0.6667 1.5333
