Metodi e modelli di ottimizzazione discreta

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

Revisionato il 11/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 Indipendent 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 Indipendent 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

OTTIIMO

Z1 Z2

ALGORITMI ESATTI - POSSONO TROVARE LA SOLUZIONE OTTIMA

ALGORITMO APPROSCIMATIVO

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À CORRISPONDETE 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 indichera 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 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₄

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