Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PL - Condotte - 09.06 ::
Testo del problema
Si vuole dimensionare una rete di condotte per trasportare sostanze gassose da un insieme di origini ad un insieme di destinazioni. Ogni origine può essere collegata ad ogni destinazione ad un dato costo unitario di trasporto. Sono date le quantità prodotte ad ogni luogo di origine e le quantità che devono essere ricevute ad ogni luogo di destinazione. Per motivi tecnologici tutte le condotte devono avere la stessa capacità massima, anche se alcune di esse potrebbero risultare sotto-utilizzate.
Formulare il problema, classificarlo e risolverlo con i dati del file CONDOTTE.TXT. Discutere l’ottimalità della soluzione trovata.
Dati
I luoghi di origine sono 5 e i luoghi di destinazione sono 5.
Tabella 1: Costi di trasporto [Euro/quintale]
Riga = origine; colonna = destinazione.
15 18 23 31 16
27 19 14 28 31
20 15 12 25 15
17 18 24 23 25
26 17 17 17 28
Tabella 2: Offerta [Quintali/giorno]
Origine Quantità
1 340
2 290
3 310
4 325
5 360
Tabella 3: Domanda [Quintali/giorno]
Destinaz. Quantità
1 410
2 200
3 400
4 315
5 300
Formulazione del problema
Dati
- o = 5 (numero luoghi di origine)
- d = 5 (numero luoghi di destinazione)
- costoij (costo di trasporto dall'origine i=1..5 alla destinazione j=1..5) [€/quintale]
- prodi (quantità prodotta nell'origine i=1..5) [quintali/giorno]
- ricej (quantità che devono essere ricevute nella destinazione j=1..5) [quintali/giorno]
Variabili
- xij (quantità di sostanza trasportata dall'origine i=1..5 alla destinazione j=1..5) [quintali/giorno]
La variabile è continua e non negativa.
Funzione obiettivo
- Si deve minimizzare il costo complessivo
min (somma)j costoij * xij (per ogni i = 1..5)
Vincoli
- vincoli sulle quantità prodotte all'origine
(somma)j xij = prodi (per ogni i = 1..5)
- vincoli sulle quantità ricevute a destinazione
(somma)i xij = ricej (per ogni j = 1..5)
Lindizzazione del problema
! esercizio - Condotte
! variabili: x(i,j) = quantità di sostanza trasportata dall'origine i
! alla destinazione j [quintali/giorno]
! la variabile è continua e non negativa
! funzione obiettivo
min 15 x11 + 18 x12 + 23 x13 + 31 x14 + 16 x15
+ 27 x21 + 19 x22 + 14 x23 + 28 x24 + 31 x25
+ 20 x31 + 15 x32 + 12 x33 + 25 x34 + 15 x35
+ 17 x41 + 18 x42 + 24 x43 + 23 x44 + 25 x45
+ 26 x51 + 17 x52 + 17 x53 + 17 x54 + 28 x55
st
! vincoli sulle quantità prodotte all'origine
origin1) x11 + x12 + x13 + x14 + x15 = 340
origin2) x21 + x22 + x23 + x24 + x25 = 290
origin3) x31 + x32 + x33 + x34 + x35 = 310
origin4) x41 + x42 + x43 + x44 + x45 = 325
origin5) x51 + x52 + x53 + x54 + x55 = 360
! vincoli sulle quantità ricevute a destinazione
destin1) x11 + x21 + x31 + x41 + x51 = 410
destin2) x12 + x22 + x32 + x42 + x52 = 200
destin3) x13 + x23 + x33 + x43 + x53 = 400
destin4) x14 + x24 + x34 + x44 + x54 = 315
destin5) x15 + x25 + x35 + x45 + x55 = 300
end
Altre domande
Studiare la dipendenza dei costi di trasporto dalla capacità:
(1) qual è il minimo valore di capacità per cui il problema ammette soluzione?
(2) qual è il massimo valore di capacità che ha senso installare?
(3) se ogni unità di capacità delle condotte costa 50 Euro/giorno, qual è la capacità ottima e qual è il costo corrispondente?
Come prima cosa bisogna inserire nel modello il vincolo che tutte le variabili devono essere limitate superiormente da un valore di capacità. Quindi dovremo aggiungere la seguente nuova serie di vincoli al nostro programma in Lindo:
lim11) x11 - cap <= 0
lim12) x12 - cap <= 0
lim13) x13 - cap <= 0
lim14) x14 - cap <= 0
lim15) x15 - cap <= 0
lim21) x21 - cap <= 0
lim22) x22 - cap <= 0
lim23) x23 - cap <= 0
lim24) x24 - cap <= 0
lim25) x25 - cap <= 0
lim31) x31 - cap <= 0
lim32) x32 - cap <= 0
lim33) x33 - cap <= 0
lim34) x34 - cap <= 0
lim35) x35 - cap <= 0
lim41) x41 - cap <= 0
lim42) x42 - cap <= 0
lim43) x43 - cap <= 0
lim44) x44 - cap <= 0
lim45) x45 - cap <= 0
lim51) x51 - cap <= 0
lim52) x52 - cap <= 0
lim53) x53 - cap <= 0
lim54) x54 - cap <= 0
lim55) x55 - cap <= 0
capac) cap = 1000
Ora possiamo rispondere alle domande:
(1)
facciamo l'analisi parametrica del problema, fissando il valore del vincolo capac a 0 e osservando cosa succede:
RIGHTHANDSIDE PARAMETRICS REPORT FOR ROW: CAPAC
VAR VAR PIVOT RHS DUAL PRICE OBJ
OUT IN ROW VAL BEFORE PIVOT VAL
1000.00 0.000000E+00 25380.0
SLK 27 X42 27 325.000 0.000000E+00 25380.0
SLK 35 X44 35 315.000 0.000000E+00 25380.0
SLK 19 X22 19 290.000 5.00000 25505.0
X32 X53 10 230.000 7.00000 25925.0
SLK 12 X21 12 205.000 13.0000 26250.0
SLK 24 X31 24 175.000 25.0000 27000.0
SLK 16 X12 16 170.000 25.0000 27125.0
SLK 30 X24 30 157.500 35.0000 27562.5
SLK 26 X45 26 150.000 43.0000 27885.0
SLK 34 X13 34 133.333 51.0000 28735.0
X22 X51 19 125.000 66.0000 29285.0
SLK 33 X22 33 117.500 67.0000 29787.5
SLK 20 X14 20 105.000 69.0000 30650.0
SLK 22 X34 22 103.333 81.0000 30785.0
SLK 14 X43 14 100.000 81.0000 31055.0
SLK 31 X55 31 100.000 85.0000 31055.0
SLK 17 SLK 33 17 87.5000 94.0000 32230.0
SLK 13 X32 13 83.7500 98.0000 32597.5
SLK 32 ART 32 82.0000 110.000 32790.0
0.000000E+00 +INFINITY INFEASIBLE
Il minimo valore di capacità per cui il problema ammette soluzione è 82.
(2)
Osservando l'analisi parametrica verrebbe da dire che il massimo valore di capacità che ha senso installare è 325. In realtà la risposta corretta è 315 perché rispetto al precedente non ci sono differenze di costi (entrambe fisse a 25380), quindi ha più senso impostare lui come limite massimo.
(3)
Dobbiamo cercare nella colonna dei prezzi duali tra quali righe si trova il valore 50, e scopriamo che si trova in corrispondenza del valore 150 dei termini noti (colonna RHS VAL): il suo coefficiente angolare corrispondente varia infatti tra 51 e 43. Qui la funzione obiettivo vale 27885, che sono i costi di trasporto, mentre i costi per la capacità andranno calcolati come 50 x 150 = 7500 euro al giorno.
Torna alla pagina di Ricerca Operativa
