Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PL - Trasmissioni da Marte - 10.10.06 ::
I rover esploratori di Marte immagazzinano dati scientifici tramite i numerosi strumenti di cui sono dotati. Ogni strumento genera dati per un diverso banco di memoria. In dati intervalli di tempo è possibile trasmettere questi dati a Terra. Durante ognuno di questi intervalli le memorie possono essere lette – e quindi parzialmente svuotate – una sola per volta e con un bit-rate noto, che può essere diverso da intervallo ad intervallo. Il tempo disponibile per la trasmissione in ogni intervallo può essere distribuito a piacimento ai diversi banchi di memoria. Ogni banco di memoria, collegato ad un diverso dispositivo scientifico, ha capacità finita ed è gestito come un buffer first-in-first-out. Nel caso in cui la quantità di dati generati dallo strumento ad esso collegato ecceda la capacità del banco di memoria, i dati più antichi vengono sovrascritti da quelli più recenti ed ovviamente si vuole evitare – o per lo meno minimizzare la probabilità - che questo accada. Perciò l’obiettivo del pianificatore delle trasmissioni è di mantenere il più basso possibile in ogni banco di memoria il rapporto tra il livello di occupazione e la capacità. Questo serve a garantire la massima robustezza rispetto a possibili variazioni delle quantità di dati scientifici generati.
Formulare il problema, classificarlo e risolverlo con i dati del file MARTE.TXT. Discutere l’ottimalità della soluzione trovata.
Si consideri il problema con 6 banchi di memoria e 9 intervalli temporali.
Tab.1: Produzione dati (Mbit)
Strumento
Intervallo 1 2 3 4 5 6
1 4 11 31 3 18 27
2 6 8 34 4 19 23
3 7 23 38 5 21 19
4 3 31 35 6 15 18
5 3 14 37 7 14 23
6 8 8 35 6 14 24
7 1 10 31 5 14 25
8 3 20 40 4 18 20
9 4 13 28 5 19 13
Tab. 2: Capacità memoria (Mbit)
Strumento Capacità
1 32
2 60
3 100
4 30
5 50
6 80
Tab. 3: Livello iniziale di occupazione della memoria (Mbit)
Strumento Occupazione
1 8
2 15
3 25
4 5
5 16
6 23
Tab. 4: Tempo disponibile per la trasmissione (secondi)
Intervallo Durata Bit-rate
(Kbit/sec)
1 490 195
2 420 160
3 460 180
4 485 195
5 400 160
6 455 180
7 480 195
8 380 160
9 450 180
Le variabili sono continue e non negative.
Vogliamo minimizzare il massimo livello di riempimento del banco di memoria dello strumento i. Dobbiamo quindi introdurre una variabile ausiliaria z, che definiremo poi nei vincoli.
min z
Nota prima di iniziare: poiché la soluzione sarà scritto in Lingo, non mi dovrò preoccupare di mettere variabili a sinistra e termini noti a destra o di linearizzare le espressioni.
Come prima cosa bisogna bilanciare i dati in ingresso con quelli in uscita. Definisco quindi due vincoli:
Notare che il primo vincolo è praticamente identico al secondo, con la differenza che nel secondo caso la yik è nota: è il dato occInii
Altri vincoli:
! esercizio - Trasmissioni da Marte;
model:
sets:
strumento /1..6/: capMem, occIni;
intervallo /1..9/: brInt, durInt;
coppia (strumento,intervallo): x, y,
prDati;
endsets
data:
prDati = 4 11 31 3 18 27
6 8 34 4 19 23
7 23 38 5 21 19
3 31 35 6 15 18
3 14 37 7 14 23
8 8 35 6 14 24
1 10 31 5 14 25
3 20 40 4 18 20
4 13 28 5 19 13;
capMem = 32 60 100 30 50 80;
occIni = 8 15 25 5 16 23;
durInt = 490 420 460 485 400 455 480 380 450;
brInt = 195 160 180 195 160 180 195 160 180;
enddata
! funzione obiettivo;
min = z;
! vincoli per il bilanciamento dei dati in ingresso con quelli in uscita;
! ...nel primo intervallo, con j = 1...;
@for(strumento(i): occIni(i) + prDati(i,1) = x(i,1) + y(i,1));
! ...e in tutti gli altri, con j != 1;
@for(strumento(i):
@for(intervallo(j) | j #GT# 1:
y(i,j-1) + prDati(i,j) = x(i,j) + y(i,j);
)
);
! vincoli di capacità sulla quantità di dati trasmessa;
@for(intervallo(j): @sum(strumento(i): x(i,j)) * 1000 <= brInt(j) * durInt(j));
! vincolo per definire la variabile ausiliaria z;
@for(strumento(i): @for(intervallo(j): z >= y(i,j) / capMem(i) ));
end