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

Teoria MMOD 1 parte I: formulazioni matematiche

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

max/min Cx

Cx = sum c_ix_i = (c₁ ... c_n) (x₁ / ... / x_n) quindi C in R^1xn, x in R^{n x 1}

s.t. Ax <= b

x >= 0 e intere

A = (a₁₁ ... a_1n / a₂₁ ... a_2n / ... / a_m1 ... a_mn) quindi A in R^mxn e Ax = sum a_ijx_i <= b_j con j = 1,...,m - pertanto sono presenti m vincoli in n variabili.

Condizione di positività e interezza della variabili: x = (x₁ / ... / x_n) >= (0 / ... / 0)

Soluzione del problema: un vettore colonna xbar 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 PLI

Formulazioni PLI: formulazioni di problemi relativi a programmazione lineare a numeri interi

• Vincoli e funzioni obiettivo sono funzioni lineari
• Condizione sulle variabili

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

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

Problema 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: n oggetti, ciascuno con peso p_i i=1,...,n, utilità u_i i=1,...,n e capacità B >= 0

Trovare: un sottoinsieme di oggetti (tutti o solo alcuni)

Tale che:

• Il peso totale degli oggetti scelti non superi la capacità dello zaino
• L'utilità complessiva sia massima

Formulazione PLI (PLB) associata al problema: per ogni oggetto bisogna determinare se bisogna sceglierlo o meno - trattandosi di una scelta a due vie per gli n oggetti è più semplice associare una variabile binaria x_i:

• 1 se si sceglie
• 0 se non si sceglie

con i = 1,...,n

La soluzione finale è quindi un vettore di numeri interi binaria con n componenti: la componente i-esima (x_i i=1,...,n) stabilisce la decisione presa sull'i-esimo oggetto. La soluzione quindi determina un sottoinsieme di oggetti scelti, diverse soluzioni equivalgono a diversi vettori e quindi diversi sottoinsiemi.

Complessivamente lo spazio di tutte le possibili soluzioni è costituito dall'unione di tutti i possibili sottoinsiemi degli n elementi.

I possibili sottoinsiemi di un insieme universale di n elementi sono: 2ⁿ.

Ad esempio consideriamo tutte le possibili configurazioni di un vettore binario a 4 componenti: 2⁴ = 16! Per ogni elemento (n = 4) hai a disposizione 2 scelte!

Possibili scelte per ogni variabile 0 <= xi <= 1 e intero:

Caso generale: # sottoinsiemi = PI (2 elevato a vi) (# valori possibili variabile)

1) ... 2) ...

tra il vettore soluzione scelto in termini binari e il sottoinsieme identificato sussiste una relazione biunivoca

Teoria MMOD 1 parte I: formulazioni matematiche

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

max/min Cx

Cx = sum c_ix_i = (c₁ ... c_n) (x₁x₂...x_n) quindi C in R^1xn, x in R^{n x 1}

s.t. Ax ≤ b

x ≥ 0 e intere

A = (a₁₁ ... a_1na₂₁ ... a_2n...a_m1 ... a_mn) quindi A in R^mxn e Ax = sum a_jix_i ≤ b_j con j = 1,...,m - pertanto sono presenti m vincoli in n variabili.

Condizione di positività e interezza della variabili: x = (x₁x₂...x_n) ≥ (00...0)

Soluzione del problema: un vettore colonna x che rispetta 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 PLI

Formulazioni PLI: formulazioni di problemi relativi a programmazione lineare a numeri interi

• Vincoli e funzioni obiettivo sono funzioni lineari
• Condizione sulle variabili

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

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

Problema di knapsack

Problema 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: n oggetti, ciascuno con peso p_i i = 1,...,n, utilità u_i i = 1,...,n e capacità B ≥ 0

Trovare: un sottoinsieme di oggetti (tutti o solo alcuni) (soluzione da determinare)

Tale che: