Problemi di massimo

(1)

Ricerca Operativa 2

Ricerca Operativa 2 – p. 1/65

(2)

Introduzione

In questo corso ci occuperemo di problemi di ottimizzazione.

(3)

Introduzione

In questo corso ci occuperemo di problemi di ottimizzazione.

Tali problemi sono tipicamente raggruppati in classi ognuna delle quali è formata da più istanze.

(4)

Classi di problemi

Una classe di problemi di ottimizzazione è formata da un insieme I di istanze. Ogni istanza I ∈ I è rappresentata da una coppia (f_I, S_I) dove

f_I : S_I → R

è detta funzione obiettivo e S_I è detta regione ammissibile.

(5)

Problemi di massimo

Se il problema è di massimo, allora una sua istanza I si rappresenta nel modo seguente

maxx∈S^I f_I(x)

e risolvere l’istanza vuol dire trovare un x^∗ ∈ S_I tale che f_I(x^∗) ≥ f_I(x) ∀ x ∈ S_I.

(6)

Problemi di minimo

Se il problema è di minimo, allora una sua istanza I si rappresenta nel modo seguente

x∈Smin^I f_I(x)

e risolvere l’istanza vuol dire trovare un x^∗ ∈ S_I tale che f_I(x^∗) ≤ f_I(x) ∀ x ∈ S_I.

(7)

Ottimo e valore ottimo

In entrambi i casi il punto x^∗ viene chiamato ottimo (globale) dell’istanza I del problema, mentre f_I(x^∗) viene detto valore ottimo dell’istanza.

(8)

Classi già note

Problemi di Programmazione Lineare (PL):

ogni istanza I è definita dal vettore ^c_I dei coefficienti delle variabili nell’obiettivo, dal vettore ^b_I dei termini noti e dalla matrice dei vincoli ^A_I:

max c_Ix A_Ix ≤ b_I

x ≥ 0

(9)

Classi già note

Problemi di Programmazione Lineare (PL):

ogni istanza I è definita dal vettore ^c_I dei coefficienti delle variabili nell’obiettivo, dal vettore ^b_I dei termini noti e dalla matrice dei vincoli ^A_I:

x ≥ 0 In tal caso:

f_I(x) = c_Ix, S_I = {x ∈ Rⁿ : A_Ix ≤ b_I, x ≥ 0}.

(10)

Esempio

max 2x₁ + 3x₂ + 4x₃ x₁ − x₂ + x₃ ≤ 5

−x₁ + 2x₂ + 3x₃ ≤ 2 x₁, x₂, x₃ ≥ 0

(11)

Esempio

max 2x₁ + 3x₂ + 4x₃ x₁ − x₂ + x₃ ≤ 5

−x₁ + 2x₂ + 3x₃ ≤ 2 x₁, x₂, x₃ ≥ 0

c_I = (2 3 4)

(12)

Esempio

max 2x₁ + 3x₂ + 4x₃ x₁ − x₂ + x₃ ≤ 5

−x₁ + 2x₂ + 3x₃ ≤ 2 x₁, x₂, x₃ ≥ 0

c_I = (2 3 4)

b_I = (5 2)

(13)

Esempio

max 2x₁ + 3x₂ + 4x₃ x₁ − x₂ + x₃ ≤ 5

−x₁ + 2x₂ + 3x₃ ≤ 2 x₁, x₂, x₃ ≥ 0

c_I = (2 3 4)

b_I = (5 2)

A_I =

"

1 −1 1

−1 2 3

#

(14)

Classi già note: continua

Problemi di Programmazione Lineare Intera (PLI):

x ≥ 0 x ∈ Zⁿ

(15)

Classi già note: continua

Problemi di Programmazione Lineare Intera (PLI):

x ≥ 0 x ∈ Zⁿ In tal caso:

f_I(x) = c_Ix, S_I = {x ∈ Zⁿ : A_Ix ≤ b_I, x ≥ 0}.

(16)

Classificazione

All’interno delle classi dei problemi di ottimizzazione possiamo riconoscere due grandi categorie.

Ottimizzazione Combinatoria: in ogni istanza I la regione ammissibile S_I contiene un numero finito o un’infinità numerabile di punti.

(17)

Classificazione

All’interno delle classi dei problemi di ottimizzazione possiamo riconoscere due grandi categorie.

Ottimizzazione Combinatoria: in ogni istanza I la regione ammissibile S_I contiene un numero finito o un’infinità numerabile di punti.

Ottimizzazione Continua: la regione ammissibile S_I può contenere un’infinità non numerabile di punti.

(18)

Esempi

Alla categoria dei problemi di ottimizzazione

combinatoria appartiene la classe dei problemi di PLI;

(19)

Esempi

alla categoria dei problemi di ottimizzazione continua appartiene la classe dei problemi di PL.

(20)

Esempi

alla categoria dei problemi di ottimizzazione continua appartiene la classe dei problemi di PL.

In questo corso ci occuperemo prevalentemente di problemi di ottimizzazione combinatoria (con regione ammissibile di solito costituita da un numero finito di elementi) ma

dedicheremo una parte anche all’ottimizzazione continua.

(21)

Cenni di complessità

Come primo passo vogliamo associare ad ogni problema di ottimizzazione un grado di difficoltà.

(22)

Cenni di complessità

Ci renderemo conto che esistono delle notevoli differenze nella difficoltà di risoluzione dei diversi problemi di

ottimizzazione.

(23)

Cenni di complessità

ottimizzazione.

Tali differenze vengono formalizzate nella teoria della complessità.

(24)

Cenni di complessità

ottimizzazione.

Tali differenze vengono formalizzate nella teoria della complessità.

Per cominciare introdurremo come esempi di diversi gradi di difficoltà tre problemi di ottimizzazione.

(25)

Alberi

Definizione Sia dato un grafo G = (V, A) con | V |= n dove

| V | denota la cardinalità (il numero di elementi)

dell’insieme V . Si dice che G è un albero se soddisfa le seguenti condizioni (equivalenti tra loro)

1. G è privo di cicli e connesso (ovvero esiste un cammino tra ogni coppia di nodi);

2. G è privo di cicli e | A |= n − 1; 3. G è connesso e | A |= n − 1;

4. esiste un unico cammino che congiunge ogni coppia di nodi.

(26)

Alberi di supporto

Definizione Sia dato un grafo generico G = (V, A). Si

definisce albero di supporto di G un sottografo T = (V, A_T) di G (quindi con A_T ⊆ A) che è un albero.

Si noti che un albero di supporto di G deve contenere tutti i nodi di G e che in virtù del punto 2. (o del punto 3.) della definizione di albero, si dovrà avere | A_T |=| V | −1.

(27)

Alberi di supporto

Definizione Sia dato un grafo generico G = (V, A). Si

definisce albero di supporto di G un sottografo T = (V, A_T) di G (quindi con A_T ⊆ A) che è un albero.

Si noti che un albero di supporto di G deve contenere tutti i nodi di G e che in virtù del punto 2. (o del punto 3.) della definizione di albero, si dovrà avere | A_T |=| V | −1.

Ad ogni arco e ∈ A del grafo associamo un peso w(e): w : A → R

(28)

Esempio

G = (V, A) V = {a, b, c, d}

A = {(a, b); (a, c); (a, d); (b, c); (b, d); (c, d)}

e w(e)

(a, b) 3 (a, c) 6 (a, d) 2 (b, c) 5 (b, d) 4 (c, d) 8

(29)

Albero di supporto a peso minimo

Regione ammissibile S: è composta da tutti i possibili alberi di supporto del grafo G, che sono in numero finito.

(30)

Albero di supporto a peso minimo

Funzione obiettivo f: per ogni albero di supporto

T = (V, A_T) ∈ S è definita come somma dei pesi degli archi dell’albero, cioè

f(T ) = X

e∈A^T

w(e).

(31)

Albero di supporto a peso minimo

Funzione obiettivo f: per ogni albero di supporto

T = (V, A_T) ∈ S è definita come somma dei pesi degli archi dell’albero, cioè

f(T ) = X

e∈A^T

w(e).

Il problema dell’albero di supporto a peso minimo o

Minimum Spanning Tree (abbreviato nel seguito con M ST) consiste nel determinare un albero di supporto

T ^∗ = (V, A_T^∗) tale che

f(T^∗) ≤ f (T ) ∀ T ∈ S

(32)

Esempio

T₁ = (V, A_T₁) A_T₁ = {(a, b); (a, d); (c, d)}

f(T₁) = 3 + 2 + 8 = 13

(33)

Esempio

T₁ = (V, A_T₁) A_T₁ = {(a, b); (a, d); (c, d)}

f(T₁) = 3 + 2 + 8 = 13

T₂ = (V, A_T₂) A_T₂ = {(a, c); (b, d); (c, d)}

f(T₂) = 6 + 4 + 8 = 18

(34)

Il problema dello zaino

Sia dato un insieme {1, . . . , n} di oggetti. Ad ogni oggetto i è associato:

un peso p_i > 0; un valore v_i > 0.

Si ha inoltre a disposizione uno zaino con capacità (peso massimo trasportabile) pari a b > 0.

(35)

Regione ammissibile

È formata da tutti i sottinsiemi di oggetti il cui peso

complessivo non supera la capacità dello zaino e quindi S = {N ⊆ {1, . . . , n} : X

i∈N

p_i ≤ b}.

(36)

Regione ammissibile

i∈N

p_i ≤ b}.

Si noti che S è un insieme finito.

(37)

Regione ammissibile

i∈N

p_i ≤ b}.

Si noti che S è un insieme finito. Infatti

| S |≤ 2ⁿ.

(38)

Funzione obiettivo f

La funzione obiettivo è definita dalla somma dei valori degli oggetti nel sottinsieme, ovvero

f(N ) = X

i∈N

v_i.

(39)

Funzione obiettivo f

La funzione obiettivo è definita dalla somma dei valori degli oggetti nel sottinsieme, ovvero

f(N ) = X

i∈N

v_i.

Il problema dello zaino, indicato nel seguito come problema KNAPSACK, è un problema di massimo e consiste nel

determinare un sottinsieme N^∗ ∈ S tale che f(N^∗) ≥ f (N ) ∀ N ∈ S.

(40)