Swappa : Uni / Ricerca Operativa - PLI - Hong Kong

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PLI - Hong Kong - 17.02.05 ::

Testo del problema

Un importante businessman di Hong Kong ha un’agenda fittissima di appuntamenti per la giornata di oggi. Ad ogni appuntamento egli può concludere un lucroso affare, di cui si conosce il guadagno. Gli appuntamenti sono stati fissati in modo che sia possibile teoricamente presenziare a tutti, in un dato ordine cronologico. Tuttavia per concludere questi affari il businessman deve spostarsi per la città e – per una scommessa con altri suoi amici - a questo scopo deve per forza servirsi di un mezzo di trasporto pubblico e usare un solo biglietto.
Ad Hong Kong i biglietti per il trasporto pubblico sono tessere magnetiche con punti a scalare. Al termine di ogni viaggio la tessera viene inserita in una macchinetta che toglie i punti consumati durante il viaggio. Se restano punti sulla tessera, questa viene restituita e può essere riutilizzata. Di conseguenza con l’ultimo viaggio l’utente può sforare dal totale di punti disponibili, senza pagare alcun addebito.
Per massimizzare i suoi guadagni il businessman si rivolge quindi ad un ricercatore operativo. Formulare il problema, classificarlo e risolverlo con i dati del file HONGKONG.TXT. Discutere l’ottimalità e l’unicità della soluzione ottenuta.

Dati

Gli appuntamenti sono 20.

Appuntamento          1   2   3   4   5   6   7   8   9  10 11 12 13 14 15 16 17 18 19 20
Punti consumati     200 180 165 141 138 130 122 115 109 104 90 79 61 50 42 34 27 20 12  9
Valore dell'affare  112 105 104  99  97  90  81  78  66  58 55 52 50 43 41 37 35 33 30 25

Il biglietto vale 850 punti.

Formulazione del problema

Dati

app = 20 (numero di appuntamenti)
pti_i (punti consumati per andare all'appuntamento i)
valAff_i (valore dell'affare dell'appuntamento i)
totPti = 850 (totale punti disponibili)

Variabili

x_i (variabile binaria che indica se sono andato o no all'appuntamento i)

Dato che con l'ultimo appuntamento posso sforare sulla quantità di punti rimanenti sul biglietto, introduco un'altra variabile binaria che vale 1 se quell'appuntamento è l'ultimo:

y_i

Perché è necessaria un'altra variabile? Perché in questo modo posso scrivere un vincolo sui punti residui che tenga conto solo delle x, mentre l'ultimo appuntamento (che avrà x = 0 e y = 1) darà il suo contributo solo sulla funzione obiettivo e non avrà peso sul vincolo.

Funzione obiettivo

max (somma)_i valAff_i * (x_i + y_i)

Il motivo per cui x e y vanno sommati è che se y_i vale 1, allora sicuramente la x_i corrispondente vale 0. Stiamo realizzando quanto detto prima: con le y tengo traccia solo dell'ultimo appuntamento, che non è conteggiato nelle x; sommandoli riusciamo a includere tutti gli appuntamenti a cui siamo andati, ultimo compreso.

Vincoli

vincolo sulla disponibilità di punti sul biglietto. Nel testo ci viene detto che "con l’ultimo viaggio l’utente può sforare dal totale di punti disponibili", quindi sarebbe il massimo se riusciamo ad arrivare all'ultimo viaggio con un solo punto sulla carta: tutto il resto è praticamente regalato. Il nostro vincolo avrà questa forma:
(somma)_i pti_i * x_i <= totPti - 1
Il motivo per cui togliamo un'unità a totPti è per permettere che avvenga un altro spostamento, quindi un altro appuntamento (quello che sarà individuato dalla variabile y): 1 punto residuo sulla carta è il minimo indispensabile per spostarsi, quindi dobbiamo garantire che ce ne sia almeno 1.
vincolo che imponga che ci sia un'unico "ultimo appuntamento":
(somma)_i y_i = 1
abbiamo bisogno infine di un vincolo che leghi la variabile x alla variabile y. Possiamo sfruttare il fatto che esiste un ordinamento negli appuntamenti, e che cioè l'appuntamento "i" viene sempre prima dell'appuntamento "i+1" e sempre dopo l'"i-1". Il nostro vincolo potrà quindi legare le due variabili dicendo che l'appuntamento rappresentato dalla y deve sempre venire dopo qualsiasi altro segnalato dalle x, dato che deve essere lultimo.
y_i <= 1 - x_j (per ogni appuntamento i e j, dove i<=j)

Linghizzazione del problema

! esercizio: Hong Kong;
model:

sets:
appuntamento /1..20/: pti, valAff, 
		      x, ! var binaria che indica se sono andato all'appuntamento;
		      y; ! var binaria che indica se l'appuntamento è l'ultimo;
endsets

data:
pti = 200 180 165 141 138 130 122 115 109 104 90 79 61 50 42 34 27 20 12  9;
valAff = 112 105 104  99  97  90  81  78  66  58 55 52 50 43 41 37 35 33 30 25;
totPti = 850;
enddata

! funzione obiettivo;
max = @sum(appuntamento(i): valAff(i) * (x(i) + y(i)));

! vincolo disponibilità punti residui sul biglietto;
@sum(appuntamento(i): pti(i) * x(i)) <= totPti-1;

! vincolo di unicità dell'ultimo appuntamento;
@sum(appuntamento(i): y(i)) = 1;

! vincolo sull'ordinamento;
@for(appuntamento(i):
   @for(appuntamento(j)| j #GE# i:
      y(i) <= 1 - x(j)  
   )
);

! definisco le variabili come binarie;
@for(appuntamento(i): @bin(x(i)));
@for(appuntamento(i): @bin(y(i)));

end

Torna alla pagina di Ricerca Operativa