Metodi e modelli di ottimizzazione discreta 1

Name: Metodi e modelli di ottimizzazione discreta 1
Rating: 4.0 (2 reviews)
Author: sofia.carrino

Revisionato il 27/07/2026

di sofia.carrino

Publisher

Vota 4,0/5 (2)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Appunti completi del corso comprensivi di spiegazioni ed esercitazioni commentate.Argomenti: formulazioni, poliedri e formulazioni, combinazioni convesse, bound, algoritmi esatti, algoritmi …

Esame Metodi e modelli di ottimizzazione discreta 1

Facoltà Ingegneria

Dal corso del Prof. Nicoloso Sara

Università Università degli Studi di Roma Tor Vergata

A.A. 2022-2023

165 pagine

5 download

Appunti esame

Scarica

Estratto del documento

Metodi e modelli di ottimizzazione discreta

PLI programmazione lineare a numeri interi

Vincoli e funzione obiettivo sempre lineari.

Esempio binario:

x ≥ 0

x ≤ 1 e intero

Problema dello zaino (Knapsack binario)

Abbiamo uno zaino di una certa capacità e una serie di oggetti ognuno caratterizzato da un'utilità e da un peso. Lo zaino non riesce a contenerli tutti.

Oggetti 3

Utilità: 3
Peso (kg): 15
Utilità: 5
Peso (kg): 32
Utilità: 2
Peso (kg): 5

Trovare quali oggetti portare in modo tale che sia massima l'utilità complessiva e non si ecceda la capacità dello zaino.

Implicitamente determiniamo anche quali oggetti non portare.

Metodi e modelli di ottimizzazione discreta

Programmazione lineare a numeri interi

Esempio binario:

x ≥ 0

x ≤ 1 e intero

Vincoli e funzione obiettivo sempre lineare.

Problema dello zaino (Knapsack binario)

Abbiamo uno zaino di una certa capacità e una serie di oggetti, ognuno caratterizzato da un'utilità e dal peso. Lo zaino non riesce a contenerli tutti.

Oggetti:

Utilità: 3, 5, 2, 1
Peso (kg): 1, 3, 5, 7

Trovare quali oggetti portare in modo tale da sia massima l'utilità complessiva e non si ecceda la capacità dello zaino.

Implicitamente determiniamo anche quali oggetti non portare.

È una bipartizione.

Formulazione

Dati: n oggetti, di peso p_i > 0 i = 1, ..., n

Di utilità: u_i > 0 i = 1, ..., n

Un intero B ≥ 0, capacità dello zaino.

Trovare un sottoinsieme S ⊆ {1, ..., n}

Tale che:

Σ_{i ∈ S} u_i ma max, funzione obiettivo
Σ_{i ∈ S} p_i ≤ B, vincolo

Una volta scritta la formulazione individuare il problema di decisione corrispondente.

In questo caso, trovare un sottoinsieme.

Rappresentazione del sottoinsieme S

Come rappresentare S?

Attraverso variabili x_i:

1 se oggetto i ∈ S
0 se oggetto i ∉ S

Ogni oggetto può essere scelto o non scelto.

Si possono rappresentare le variabili attraverso un grafo bipartito.

x_i: 1

Anteprima

Vedrai una selezione di 10 pagine su 165