[ Italian version | English Version | Home ]
Valore | Peso
Miglior valore ottenuto finora: zcur = (nessuno)
Possibili branch: (nessuno)
Questa pagina web e gli script di accompagnamento permettono di risolvere il problema di Programmazione Lineare Intera noto come "problema dello zaino":
max v x
w x ≤ Wmax
dove x è il vettore incognito di variabili binarie.
Si tratta di scegliere quali oggetti trasportare in uno zaino (che sopporta un peso massimo Wmax). Per ogni oggetto i sono noti il peso wi e il valore vi. L'obbiettivo è massimizzare il valore trasportato.
Il vettore x rappresenta una possibile soluzione: le sue componenti xi valgono 1 oppure 0 a seconda che l'oggetto venga incluso o no nello zaino.
Il problema rilassato (in cui cioè le xi possono essere frazionarie) si risolve facilmente riempiendo lo zaino in ordine di densità (di = vi / wi)
Viene adottata la tecnica branch-and-bound. La scelta dei vincoli su cui realizzare il branch viene lasciata all'utente, l'applicazione si occupa automaticamente di calcolare il rilassamento e tenere traccia del valore ottimo man mano raggiunto.
L'utente ha in ogni momento a disposizione l'albero risolutore.
Per quanto possibile, si è mantenuto isolato il codice relativo all'interfaccia (interface.js), quello relativo all'algoritmo risolutore (bb.js) e quello specifico del particolare problema risolto (knapsack.js).
In questo modo è possibile adattare con poche modifiche l'applicazione a risolvere problemi dello stesso tipo, o creare un'interfaccia diversa.
La pagina è strutturata in modo da essere funzionale anche su schermi piccoli e interfacce che non supportano CSS. Per questa ragione, la pagina ha un layout strettamente verticale. Inoltre, si costruisce l'albero in senso orizzontale, che risulta più facilmente leggibile su uno schermo di piccole dimensioni. Solo su schermo, si mantengono sempre visibili i principali parametri della risoluzione.
L'inserimento dei dati avviene tramite caselle di testo e pulsanti.