Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Segherie - 11.01.00 ::
Testo del problema
I tronchi tagliati nei boschi di una regione quadrata vengono portati in punti di raccolta da cui poi devono essere trasferiti nelle segherie. L'azienda che gestisce le segherie deve decidere dove aprire le segherie e in quale di esse far trasportare i tronchi da ogni punto di raccolta. Le località in cui è possibile aprire le segherie sono state individuate; le posizioni dei punti di raccolta sono date. In ciascuna delle località che potrebbero ospitare una segheria ci sono delle limitazioni di spazio e altri fattori che ne limiterebbero la capacità e ne influenzerebbero i costi di funzionamento e manutenzione.
Inoltre, poiché la stessa azienda deve anche eseguire il trasporto dei tronchi dai punti di raccolta alle segherie, occorre minimizzare i relativi costi di trasporto, che sono proporzionali alle quantità trasportate e alle distanze percorse (in linea d'aria, poiché la zona è estremamente impervia ed il trasporto avviene tramite elicotteri).
Formulare e classificare il problema e risolverlo con i dati del file SEGHERIE.TXT.
Dati
Le coordinate dei 15 punti di raccolta del legname sono le seguenti,
espresse come frazione del lato del quadrato che delimita la regione
(lato di 100 km).
Ogni punto di raccolta ha associata una quantità di legname fornito.
posizione quantita'
(quintali
giornalieri)
0.40 0.66 58
0.76 0.17 35
0.11 0.47 27
0.65 0.58 42
0.18 0.88 60
0.19 0.02 31
0.62 0.62 18
0.90 0.17 24
0.66 0.95 36
0.42 1.00 37
0.95 0.12 48
0.16 0.26 39
0.07 0.71 53
0.75 0.43 61
0.30 0.76 29
I costi di trasporto giornalieri sono pari a 10000 Lire per ogni km
e per ogni quintale.
Le possibili localizzazioni delle segherie sono 5:
Posizione Costi di manutenzione Capacita'
e funzionamento giornalieri (quintali
(in migliaia di lire) al giorno)
0.25 0.20 3000 190
0.55 0.25 4500 240
0.90 0.15 3000 200
0.15 0.45 4400 220
0.85 0.55 4600 190
Formulazione del problema
Dati
- pr = 15 (numero dei punti di raccolta del legname)
- assexPi (coordinata x del punto di raccolta i=1..15)
- asseyPi (coordinata y del punto di raccolta i=1..15)
- lato = 100 (lunghezza del lato della regione) [km]
- qli (quantità di legname raccolto nel punto di raccolta i=1..15) [quintali/giorno]
- costi = 10000 (costi di trasporto giornalieri per ogni km e per ogni quintale) [€]
- ps = 5 (numero di possibili segherie)
- assexSj (coordinata x della possibile segheria j=1..5)
- asseySj (coordinata y della possibile segheria j=1..5)
- manFunj (costi di manutenzione e funzionamento della possibile segheria j=1..5) [€/giorno]
- '''capaj (capacità della possibile segheria j=1..5) [quintali/giorno]
Variabili
- xj (indica se la segheria j=1..5 esiste o no) (binaria)
- yij (quantità di legname trasportato dal punto di raccolta i=1..15 alla segheria j=1..5) [quintali/giorno]
- zij (distanza tra il punto di raccolta i=1..15 e la segheria j=1..5) [km]
Notare che questa variabile si può calcolare dai dati come:
zij = radiceQuadrata ((assexPi – assexSi)2 + (asseyPi - asseySi)2)
Funzione obiettivo
min (yij * costi * zij * qli) + (xj * manFunj)
Vincoli
- vincolo sulla quantità di legname che non deve superare il limite di capacità:
((somma)i yij) <= capaj (per ogni j)
- vincolo che imponga che ogni punto di raccolta sia servito:
((somma)j yij) > 0 (per ogni i)
Lindizzazione del problema
! esercizio - Segherie
! variabili: x(i) = indica se la segheria esiste o no (binaria)
! y(i,j) = quantità di legname trasportato da i a j
! la variabile y è continua e non negativa
! funzione obiettivo
min + 3000 x1 + 4500 x2 + 3000 x3 + 4400 x4 + 4600 x5
+ 28062.65 y11 + 25321.50 y12 + 41424.35 y13 + 18936.80 y14
+ 26868.46 y15 + 17880.86 y21 + 7865.27 y22 + 4949.75 y23
+ 23491.75 y24 + 13667.94 y25 + 8211.73 y31 + 13282.24 y32
+ 23013.44 y33 + 1207.48 y34 + 20096.42 y35 + 23172.43 y41
+ 14482.39 y42 + 20890.51 y43 + 21698.19 y44 + 8493.97 y45
+ 41015.61 y51 + 43836.97 y52 + 61519.75 y53 + 25862.71 y54
+ 44811.61 y55 + 5881.84 y61 + 13243.21 y62 + 22375.90 y63
+ 13387.55 y64 + 26240.36 y65 + 10075.18 y71 + 6778.14 y72
+ 9847.50 y73 + 8996.40 y74 + 4327.49 y75 + 15616.61 y81
+ 8616.64 y82 + 480.00 y83 + 19213.50 y84 + 9198.61 y85
+ 30771.05 y91 + 25509.25 y92 + 30068.08 y93 + 25711.66 y94
+ 15941.94 y95 + 30260.93 y101 + 28163.78 y102 + 36118.14 y103
+ 22669.86 y104 + 23029.34 y105 + 33818.72 y111 + 20188.55 y112
+ 2798.86 y113 + 41538.72 y114 + 21190.79 y115 + 4218.49 y121
+ 15215.00 y122 + 29177.11 y123 + 7420.26 y124 + 29190.14 y125
+ 28664.13 y131 + 35236.03 y132 + 53066.21 y133 + 14417.56 y134
+ 42200.78 y135 + 33572.17 y141 + 16413.42 y142 + 19376.50 y143
+ 36620.33 y144 + 9528.50 y145 + 16304.60 y151 + 16471.39 y152
+ 24813.22 y153 + 9987.12 y154 + 17073.10 y155
st
! vincoli sulla quantità di legname
quant1) 58 y11 + 35 y21 + 27 y31 + 42 y41 + 60 y51 + 31 y61
+ 18 y71 + 24 y81 + 36 y91 + 37 y101 + 48 y111
+ 39 y121 + 53 y131 + 61 y141 + 29 y151 - 190 x1 <= 0
quant2) 58 y12 + 35 y22 + 27 y32 + 42 y42 + 60 y52 + 31 y62
+ 18 y72 + 24 y82 + 36 y92 + 37 y102 + 48 y112
+ 39 y122 + 53 y132 + 61 y142 + 29 y152 - 240 x2 <= 0
quant3) 58 y13 + 35 y23 + 27 y33 + 42 y43 + 60 y53 + 31 y63
+ 18 y73 + 24 y83 + 36 y93 + 37 y103 + 48 y113
+ 39 y123 + 53 y133 + 61 y143 + 29 y153 - 200 x3 <= 0
quant4) 58 y14 + 35 y24 + 27 y34 + 42 y44 + 60 y54 + 31 y64
+ 18 y74 + 24 y84 + 36 y94 + 37 y104 + 48 y114
+ 39 y124 + 53 y134 + 61 y144 + 29 y154 - 220 x4 <= 0
quant5) 58 y15 + 35 y25 + 27 y35 + 42 y45 + 60 y55 + 31 y65
+ 18 y75 + 24 y85 + 36 y95 + 37 y105 + 48 y115
+ 39 y125 + 53 y135 + 61 y145 + 29 y155 - 190 x5 <= 0
! vincoli sui punti di raccolta
racSe1) y11 + y12 + y13 + y14 + y15 = 1
racSe2) y21 + y22 + y23 + y24 + y25 = 1
racSe3) y31 + y32 + y33 + y34 + y35 = 1
racSe4) y41 + y42 + y43 + y44 + y45 = 1
racSe5) y51 + y52 + y53 + y54 + y55 = 1
racSe6) y61 + y62 + y63 + y64 + y65 = 1
racSe7) y71 + y72 + y73 + y74 + y75 = 1
racSe8) y81 + y82 + y83 + y84 + y85 = 1
racSe9) y91 + y92 + y93 + y94 + y95 = 1
racSe10) y101 + y102 + y103 + y104 + y105 = 1
racSe11) y111 + y112 + y113 + y114 + y115 = 1
racSe12) y121 + y122 + y123 + y124 + y125 = 1
racSe13) y131 + y132 + y133 + y134 + y135 = 1
racSe14) y141 + y142 + y143 + y144 + y145 = 1
racSe15) y151 + y152 + y153 + y154 + y155 = 1
end
! definiamo binarie le variabili x(i)
int x1
int x2
int x3
int x4
int x5
Torna alla pagina di Ricerca Operativa
