Metodi e modelli di ottimizzazione discreta

Name: Metodi e modelli di ottimizzazione discreta
Rating: 3.5 (2 reviews)
Author: edoardo.musche

Revisionato il 27/07/2026

di edoardo.musche

Publisher

Vota 3,5/5 (2)

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

Appunti molto dettagliati di tutte le lezioni del corso di MMOD1.Gli appunti coprono tutti gli argomenti del corso che si dividono principalmente in formulazioni, Bound per funzione obiettivo, …

Esame Metodi e Modelli di ottimizzazione discreta

Facoltà Ingegneria

Dal corso del Prof. Nicoloso Sara

Università Università degli Studi di Roma Tor Vergata

A.A. 2022-2023

106 pagine

1 download

Appunti esame

Scarica

Estratto del documento

Indice appunti

Knapsack binario P.3
Max matching P.6
Min node cover P.8
Max independent set P.9
Max clique P.10
Assegnamento P.11
Vincoli e Exor P.13
Set covering P.21
Set partitioning P.22
Set packing P.23
Regione non convessa P.25
Scheduling P.27
Attivazione y nella f.o. P.33
Bin packing P.34
Diversi tipi di vincoli P.37
Knapsack intero P.41
Poliedri e formulazioni P.42
Combinazione convessa P.45
Bound per la f.o. P.47
Rilassamento lineare P.51
Bound tramite dualità P.52
Dualità MM e MNC P.53
TSP e rilassamento combinatorio P.58

Indice appunti

Knapsack binario P.3
Max matching P.6
Min node cover P.8
Max independent set P.9
Max clique P.10
Assegnamento P.11
Vincoli e Exor P.13
Set covering P.21
Set partitioning P.22
Set packing P.23
Regione non convessa P.25
Scheduling P.27
Attivazione y nella f.o. P.33
Bin packing P.34
Diversi tipi di vincoli P.37
Knapsack intero P.41
Poliedri e formulazioni P.42
Combinazione convessa P.45
Bound per la f.o. P.47
Rilassamento lineare P.51
Bound tramite dualità P.52
Dualità MM e MNC P.53
TSP e rilassamento combinatorio P.58
Rilassamento lagrangiano P.61

Algoritmi

Totale unimodularità P.65
Branch & bound P.70
Programmazione dinamica P.73
PD per knapsack P.74
PD per TSP P.78

Algoritmi approssimati

TSP 2-Approx P.83
TSP 3/2-Approx (Christofides) P.85

Algoritmi euristici

Greedy knapsack binario P.88
Greedy set covering P.89
Ricerca locale P.93
Ricerca locale TSP P.94
Ricerca locale TSP simmetrico P.96
Ricerca locale knapsack P.97
Ricerca tabù P.100

Complessità computazionale

Problemi in forma di decisione P.103
Ricerca binaria P.106

Argomenti corso: programmazione a numeri interi

Formulazioni (LU, probl. max/min)
Bound - trattare problemi di difficile risoluzione

Soluzione che rispetta il bound.

Ottimo z1 z2.

Algoritmi esatti - possono trovare la soluzione ottima.

Algoritmo approssimativo.

Complessità computazionale → N° di operazioni eseguite in base al calcolatore

Problema di knapsack binario

Abbinato uno zaino con capacità B e diversi oggetti caratterizzati da utilità U da un peso.

Utilità: 3 5 2.

Pesi (w): 1 3 5.

Trovare quali oggetti porre in posto tale che sia massimizzata l’utilità corrispondente a non si ecceda la capacità dello zaino.

OAT: N oggetti di peso Pi ≥ 0, i = 1,..., n.

Di utilità Ui ≥ 0, i = 1,..., n.

Con un limite Di ≥ 0 (carattere intero).

Trovare un sottoinsieme tali che: ∑ I ∈ S Pi ≤ B - vincolo.

Bisogna definire come rappresentare il sottoinsieme S in modo matematico, ovvero quali variabili utilizzare.

Ogni oggetto viene eletto o meno per l’unione -> variabili.

Stati delle variabili che devo verificare le 2 situazioni:

1 -> S sottoinsiemi.

Formulazione

PLI - Programmazione lineare a numeri interi.

Sottomisure vincoli f.o. lin. di 1° grado.

Selezionare solo 0 e 1.

(z^*∈) max Z = Σ ( ) Selezioniamo gli elementi.

Vettore soluz. ( x₁, x₂, ..., x_n ), seleziono solo r o z.

Vettore indicherà gli interi.

In generale grazie alla variabile binaria posso trovare tutti i sottoinsiemi.

s.t (such that) per tutte le variabili bi >₌ b.

Classificazione delle variabili

Oppure: x > 0.

Oppure: x ≤ 2 e intero sulla singola variabile.

Oppure: x₁ ∈ { 0, 2, 3 } i=1, 2, ..., m.

Oppure: x ∈ { 0, 1 } no di variabili.

Insieme delle parti

Insieme delle parti P - Famiglia di tutti i sottoinsiemi di un insieme dato A= { a₁, a₂, a₃, a₄ } 1 - cardinalità zero (151=0) -> Ø.

(151=1) -> { { } { a_i } { a_i } }.

(151=2) -> { { } { a_2,3 } { Ø₁ { a₃ } } } { Ø₁ { a_2,3 } { Ø₁ { Ø₃ } } }.

(151=3) -> { { } { Ø_2,3 ¹ { Ø_1,3 ^x{ Ø₂ } }151|Z| = 2⁴ = 2^|A|> [ entero che deriva dalla sommatoria delle combinazioni > Σ₀ ( x₁ x₂ x₃ x₄.

Combinazioni

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1

Anteprima

Vedrai una selezione di 23 pagine su 106