:: Zaino trekking ::
Testo
Il ricercatore operativo va in montagna per un lungo trekking e prepara lo zaino. Egli ha bisogno di confezioni di cibo di dieci tipi diversi, numerati da 1 a 10. Ciascun tipo di confezione occupa un certo volume nello zaino e dą un certo apporto nutritivo. Il ricercatore operativo vuole ovviamente massimizzare il potere nutritivo del cibo che porta con sč, senza eccedere la capacitą di 100 litri del suo zaino.
Formulare il problema come PLI (Knapsack) e risolverlo sia a mano che con LINDO * nel caso in cui ogni tipo di confezione alimentare sia frazionabile a piacere
- nel caso in cui ogni tipo di cibo sia disponibile in numero illimitato di confezioni non frazionabili
- nel caso in cui per ogni tipo di cibo sia disponibile una sola confezione non frazionabile.
Alimenti Potere nutritivo Volume occupato (litri)
di ogni confezione da ogni confezione
1 4 8
2 6 9
3 40 13
4 15 24
5 20 28
6 20 36
7 21 41
8 38 57
9 46 68
10 56 70
Soluzione
Come si puņ vedere, il problema e triplice:
- se posso portare una qualunque frazione delle scatole, allora abbiamo variabili continue
- se posso portare un infinito numero di scatole intere, siamo nel campo delle variabili intere
- se posso portare al max una scatola per tipo, siamo nel campo delle variabili binarie.
Per dire a Lindo che le variabili sono intere, si usa la seguente sintassi:
gin x1, x2, x3
dove gin sta per General INteger. Questo vuol dire, piuttosto controintuitivamente, che x1, x2 e x3 sono variabili intere.
Ma c'č una scorciatoia: scrivendo
gin 10
Lindo automaticamente vede le prime 10 variabili del modello (qualsiasi esse siano) come gin.
Per avere invece variabili binarie, usiamo int allo stesso modo di gin.
! Zaino trekking
! Variabili
! Ci sono 3 casi:
! 1) posso frazionare ogni scatola a piacere -> Var continue non negative
! 2) posso portare un numero illimitato di scatole non frazionabili -> Var intere
! 3) posso portare 1 sola scatola non frazionabile per tipo di alimento -> Var binarie
! Obiettivo: il max potere nutritivo
max 4 x1 + 6 x2 + 40 x3 + 15 x4 + 20 x5 + 20 x6 + 21 x7 + 38 x8 + 46 x9 + 56 x10
st
! L'unico vincolo č che non posso eccedere la capacitą dello zaino, in litri
8 x1 + 9 x2 + 13 x3 + 24 x4 + 28 x5 + 36 x6 + 41 x7 + 57 x8 + 68 x9 + 70 x10 <= 100
end
! Per ottenere il caso numero 2, metto le variabili in modo intero generale
! (ocio: int = binarie, gin = intere)
!gin 10
! Per ottenere il caso numero 3, metto le variabili binarie
int 10
