Modelli e algoritmi per l'ottimizzazione di layout fieristici

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

1.2 Cutting and Pa king problems 7 Per generalizzare il problema hiamiamo gli oggetti items, on una quantità pari ad n; il valore e la dimensione dell'oggetto j − esimo sono hiamati rispettivamente protto e peso e indi ati on pj e vj (j = (1, ..., n)). Na- turalmente il dis orso appena fatto riguarda un aso knapsa k generi o, il ui s opo onsiste nel determinare uno o più sottoinsiemi per ui la somma dei pesi non superi (o eguagli) una erta quantità limite (detta bound) e la somma dei valori sia massimizzata. Questa tipologia di problema, ri ondu i- bile all'algoritmo Knapsa k, ha ris ontrato enorme interesse da entrambi i punti di vista teori o e prati o, adattandosi a varie forme di progettazione he ri hiedono l'ottimizzazione. Di seguito si analizzeranno più in dettaglio le varie tipologie di Cutting and Pa king problems in base alle denizioni pre edentemente fornite per problemi a una e due dimensioni. KNAPSACK 0-1 (BINARY) IlKnapsa k problem 0-1 è il più importante dei problemi di ottimizzazione ombinatoria. Esiste un esempio di problema asso iato allo knapsa k he ne espli a in maniera piuttosto esauriente la funzione. Tale problema, detto ``dello zaino''5 è posto nel modo seguente: sia dato uno zaino he possa supportare un determinato peso e siano dati inoltre N oggetti, ognuno dei quali aratterizzato da un peso e un'utilità (ovvero un guadagno). Il problema si propone di s egliere quali di questi oggetti mettere nello zaino per ottenere la maggiore utilità senza e edere nel peso sostenibile dallo zaino stesso, il quale non è altro he un problema analogo al aso visto in pre edenza. Detto iò si può proseguire elen ando tre motivi fondamentali per ui l'algo- ritmo ha assunto tale importanza: • può essere trattato ome un sempli e problema di Programmazione Intera Lineare (ILP) 5 in inglese knapsa k indi a proprio la parola zaino

Anteprima della Tesi di Erick Baldi

Anteprima della tesi: Modelli e algoritmi per l'ottimizzazione di layout fieristici, Pagina 9

Laurea liv.I

Facoltà: Ingegneria

Autore: Erick Baldi Contatta »

Composta da 119 pagine.

 

Questa tesi ha raggiunto 1019 click dal 26/09/2008.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.