Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Immagini - 3.11.03 ::
Testo del problema
Un satellite può eseguire osservazioni di porzioni della superficie terrestre, immagazzinando le immagini sotto forma di files in una memoria di bordo e ritrasmettendole a terra successivamente.
Le immagini vengono acquisite a pagamento per conto di utenti che avanzano le proprie richieste in anticipo. In seguito avviene una fase di pianificazione delle attività del satellite, durante la quale alcune di queste richieste vengono inserite nel piano e altre no. Non è detto infatti che sia possibile soddisfare tutte le richieste poiché alcune di esse possono sovrapporsi. In particolare di ogni richiesta sono noti gli istante iniziale e finale per l’acquisizione dell’immagine corrispondente. Inoltre il tempo disponibile per la trasmissione a terra delle immagini è limitato e quindi il piano non deve prevedere l’acquisizione di più immagini di quante se ne possono poi trasmettere a terra. Il tempo che sarebbe necessario per trasmettere a terra ogni immagine è dato.
Ciascuna richiesta ha associato un valore economico e l’obiettivo è quello di massimizzare il ricavo complessivo che si ottiene dalle immagini acquisite.
I dati del problema sono nel file IMMAGINI.TXT, dove le richieste sono ordinate per istante iniziale crescente e, a parità di esso, per istante finale crescente.
Formulare il problema, classificarlo e risolverlo con i dati del file IMMAGINI.TXT.
Dati
Gli obiettivi sono 40.
Istante iniziale dell'acquisizione (sec):
0 4 8 12 16 20 20 22 24 28 32 36 40 40 40 42 44 45 46 47
48 50 54 58 60 61 62 63 64 65 66 66 66 68 70 72 74 75 75 78
Istante finale dell'acquisizione (sec):
6 8 10 14 18 21 22 24 28 30 35 40 42 44 48 50 48 48 52 50
56 54 56 70 62 66 64 64 68 70 68 70 72 72 72 78 76 80 84 82
Tempo richiesto per la trasmissione a terra (sec):
10 12 18 17 15 21 10 28 24 15 16 18 24 17 25 12 11 16 16 17
15 12 15 11 15 19 18 20 12 28 13 16 17 13 14 14 19 10 10 11
Valore dell'immagine (Euro):
400 280 186 325 315 290 281 256 289 333 401 286 245 197 245
233 168 312 176 348 194 396 296 267 339 229 201 300 360 411
284 293 330 209 248 190 184 294 299 310
Tempo disponibile per la trasmissione (sec):
300
Immagini forzate: 2, 3, 6, 13, 16, 24, 37.
Formulazione del problema
Dati
- obiettivi = 40 (numero di obiettivi da fotografare)
- acqInizi (istante di inizio acquisizione dell'obiettivo i=1..40) [secondi]
- acqFinei (istante di fine acquisizione dell'obiettivo i=1..40) [secondi]
- tTrasmi (tempo richiesto per trasmissione a terra dell'obiettivo i=1..40) [secondi]
- valImmi (valore della foto dell'obiettivo i=1..40) [€]
- tDisp = 300 (tempo disponibile per la trasmissione) [secondi]
Variabili
- xi (variabile binaria che indica se l'obiettivo i=1..40 è stato fotografato o meno)
Funzione obiettivo
max (somma)i xi * valImmi [€]
Vincoli
- vincolo sul tempo disponibile per la trasmissione:
(somma)i xi * tTrasmi <= tDisp
- vincolo per evitare la sovrapposizione tra due acquisizioni. Quello che dobbiamo dire è che per ogni obiettivo i e j, con i diverso da j: se "i finisce dopo l'inizio di j" e se "i inizia prima della fine di j", allora posso scattare la foto o solo a i o solo a j, o a nessuno dei due. In altre parole, se ho due acquisizioni che si sovrappongono, devo sceglierne o una o nessuna delle due. Il nostro vincolo sarà quindi:
xi + xj <= 1
(per ogni obiettivo i e per ogni obiettivo j,
con i diverso da j,
con acqFinei > acqInizj,
con acqInizi < acqFinej)
Linghizzazione del problema
! Esercizio "Immagini", TeRO_26, 3 Novembre 2003;
model:
sets:
obiettivo /1..40/: acqIniz, acqFine, tTrasm, valImm,
x; ! variabile binaria;
endsets
data:
acqIniz = 0 4 8 12 16 20 20 22 24 28
32 36 40 40 40 42 44 45 46 47
48 50 54 58 60 61 62 63 64 65
66 66 66 68 70 72 74 75 75 78;
acqFine = 6 8 10 14 18 21 22 24 28 30
35 40 42 44 48 50 48 48 52 50
56 54 56 70 62 66 64 64 68 70
68 70 72 72 72 78 76 80 84 82;
tTrasm = 10 12 18 17 15 21 10 28 24 15
16 18 24 17 25 12 11 16 16 17
15 12 15 11 15 19 18 20 12 28
13 16 17 13 14 14 19 10 10 11;
valImm = 400 280 186 325 315 290 281 256 289 333
401 286 245 197 245 233 168 312 176 348
194 396 296 267 339 229 201 300 360 411
284 293 330 209 248 190 184 294 299 310;
tDisp = 300;
enddata
! funzione obiettivo;
max = @sum(obiettivo(i): x(i) * valImm(i));
! vincolo sul tempo disponibile per la trasmissione;
@sum(obiettivo(i): x(i) * tTrasm(i)) <= tDisp;
! vincolo per evitare sovrapposizioni nelle acquisizioni;
@for(obiettivo(i):
@for(obiettivo(j) |
(i #ne# j) #and#
(acqFine(i) #gt# acqIniz(j)) #and#
(acqIniz(i) #lt# acqFine(j)) :
x(i) + x(j) <= 1
)
);
! definisco le variabili binarie;
@for (obiettivo(i): @bin(x(i)));
end
Altre domande
Nota bene: purtroppo la mia versione di Lingo ha un limite di variabili intere utilizzabili pari a 30, quindi non riesco a far risolvere questo problema (che ne ha 40). Per questo motivo userò come riferimento l'output messo a disposizione dal professore.
Se il tempo disponibile per la trasmissione a terra delle immagini potesse essere allungato, ritenete che sarebbe conveniente farlo? In che misura e con quale miglioramento rispetto al caso precedente?
Per rispondere basta eliminare il vincolo sul tempo disponibile di trasmissione. Risolvendo ci accorgiamo che la soluzione ottima aumenta da 5870.000 a 6164.000, ed il tempo di trasmissione totale stimato è pari a:
Variable Value Reduced Cost
Q 352.0000 0.0000000
Supponendo che alcune richieste non in conflitto tra loro, indicate nel file IMMAGINI.TXT, debbano essere soddisfatte per forza per motivi di emergenza o di sicurezza nazionale, di quanto peggiorerebbe il valore ottimo del ricavo?
Per forzare il satellite ad acquisire quella data sequenza, bisognerà aggiungere nel codice il seguente vincolo:
x(2) + x(3) + x(6) + x(13) + x(16) + x(24) + x(37) = 7;
Risolvendo il problema osserviamo che la soluzione peggiora moltissimo, arrivando a un valore di 4892.000.
Torna alla pagina di Ricerca Operativa
