Appunti di Metodi e modelli di ottimizzazione discreta 1 - parte 1

Teoria Mmod 1

Parte 1: Formulazioni Matematiche

Consideriamo un semplice problema di massimizzazione/minimizzazione di una funzione obiettivo in presenza di vincoli:

max/min c^T x s.t. Ax ≤ b x ≥ 0 e intere

Condizione di positività e interezza delle variabili: x_j ∈ ℕ

Soluzione del problema: un vettore colonna x che rispetti le condizioni di non negatività e interezza per tutte le n variabili Soluzione ammissibile: deve essere soluzione del problema e soddisfare gli m vincoli Soluzione ammissibile e ottima: soluzione ammissibile per il problema e massimizza/minimizza la funzione obiettivo.

Formulazioni PU : formulazioni di problemi relativi a programmazione lineare a numeri interi In particolare possiamo considerare PLB : formulazioni relative a programmazione lineare.

Problemi di Knapsack

categoria di problemi con vincoli di capacità e condizioni sui pesi e le utilità. Struttura tipica del problema: occorre riempire uno zaino rispettando i vincoli di capacità e massimizzando l’utilità. Dati : oggetti, ciascuno con peso p_i e utilità u_i, e capacità B ≥ 0 Nome : numero totale degli oggetti scelti per fini giornalieri.

Formulazione PU (PLB)

associato al problema: per ogni oggetto bisogna determinare se bisogna sceglierlo o meno ↔ trasformando una scelta a due vie per gli n oggetti è più semplice associare una variabile binaria x_i = {1 se si sceglie, 0 altrimenti} con i = 1,…,n.

Ad esempio consideriamo tutte le possibili configurazioni di un vettore binario x di componenti n: 2ⁿ. Per ogni elemento (n = 4) ha a disposizione 2 scelte.

Una volta scelto il vettore soluzione in termini binari il sottoinsieme identificato soddisfa una relazione binaria.

TEORIA MMOD 1

PARTE 1: FORMULAZIONI MATEMATICHE

Consideriamo un semplice problema di massimizzazione/minimizzazione di una funzione obiettivo in presenza di vincoli:

max/min     Cx    S.T.

x ≥ 0 e intere    Ax ≤ b

Quindi c ∈ Rⁿ, x ∈ R^{n x 1}

Quindi A ∈ R^{m x n} e Ax = Σ x_ij b_j con j=1,...,m     →  pertanto sono presenti m vincoli n variabili.

Condizione di positività e interezza delle variabili:

x =  ⎛ x₁

⎜ x₂

⎜ x₃

⎜ ...

⎝ x_n

Soluzione del problema: un vettore colonna X che rispetti le condizioni di non negatività e interezza per tutte le n variabili.

Soluzione ammissibile deve essere soluzione del problema e soddisfare gli m vincoli.

Soluzione ammissibile e ottima: soluzione ammissibile per il problema e massimizza/minimizza la funzione obiettivo.

Formulazioni PU : formulazioni dei problemi relativi a programmazione lineare a numeri interi vincoli e f.ini obiettivo sono f.ini lineari condizioni sulle variabili:

In particolare possiamo considerare PLB : formulazioni relative a programmazione lineare (f.o.e vincoli) biniaria (condizione aggiuntiva di binarietà delle variabili).

Esiste anche PLI: programmazione lineare mista con variabili reali e intere insieme.

PROBLEMA DEL KNAPSACK:

Categoria dei problemi con vincoli di capacità e condizioni sui pesi e le utilità.

Struttura tipica del problema: occorre riempire uno zaino rispettando vincoli di capacità e massimizzando l’utilità.

1. Dati: n oggetti, ciascuno con peso p_i e utilità u_i, capacità massima B=Σ

Numero di soluzioni:        Possiamo avere 2ⁿ soluzioni da determinare.

→ Tra le soluzioni tutte devono sempre rispettare unità di grandezza in gioco (vincoli).

1. Esiste la soluzione ottima e f.m.o.

Formulazione PLI (PLB) associato al problema: per ogni oggetto bisogna determinare se bisogna sceglierlo o meno + tradurlo ad una scelta a due vie per gli n oggetti è più semplice associare una variabile binaria x_i =      1: se si sceglie       i

0: se non si sceglie con    i = 1,...,n

La soluzione finale è quindi un vettore di numeri interi binaria con n componenti i-th (i=1,...,n) stabilisce la decisione presa sull’ennesimo oggetto. Alla soluzione ottima determinarono autonomia con oggetti scelti, diverse soluzioni equivalgono a diversi ordini di questi stessi:

Complessivamente lo spazio di tutte le possibili soluzioni è costituito dall’insieme di tutti i possibili soluzioni esistenti degli n elementi:

Possibili soluzioni simili ad un insieme di cardinalità (numero degli elemeni → e.pi).

Ad esempio consideriamo tutte le possibili con