Metodi e modelli di ottimizzazione discreta 1

METODI E MODELLI DI OTTIMIZZAZIONE DISCRETA

L1 28/09/2002

• PROGRAMMAZIONE LINEARE A NUMERI INTERI

vincoli e funzione obiettivo sempre lineari

es. binaria:

x > 0

x ≤ 1

x è intero

• 0
• 1

PROBLEMA DELLO ZAINO (KNAPSACK BINARIO)

Abbiamo uno zaino di una certa capacità e una serie di oggetti ognuno caratterizzato da un'utilità e a tale peso lo zaino non riesce a contenerli tutti.

oggetti:

• 1
• 2
• 3

utilità:

• 8 kg
• 3
• 5
• 2
• 1

peso (kg):

• 1
• 3
• 5
• 7

Trovare quali oggetti portare in modo tale da via massima l'utilità complessiva e non hi ecceda la capacità dello zaino.

implicitamente determiniamo anche quali oggetti NON portare

insieme complementare:

S = {1,2,...,n}/S degli oggetti da non portare

insieme di n oggetti

A-S=S

sottinsieme S degli oggetti da portare

è una BIPARTIZIONE

Formulazione

Stati: n oggetti di peso p_i ≥ 0 i=1,...,n... di utilità u_i ≥ 0 i=1,...,n

Dato un intero B ≥ 0 (capacità dello zaino)trovare un sottoinsieme S ⊆ {1,...,n}

tale che:

• ∑ u_i: max (funzione obiettivo)
• ∑ p_i ≤ B (vincolo)

Una volta scritta la formulazione individuare ilPROBLEMA DI DECISIONE corrispondente... in questo caso, trovare un sottoinsieme ...

Come rappresentare S?

Attraverso variabili x_i:

• 1 se oggetto i ∈ S
• 0 se oggetto i ∉ S

Si possono rappresentare le variabili attraversoun grafo bipartito

x_i:

• 1 ... i ∈ S
• 0 ... i ∉ S

... deve essere un MATCHING PERFETTO

Valutiamo le possibili soluzioni sul piano delle soluzioni:

8x₁ + 4x₂ = 10

x₁ + 0 = 2x₁ = 10, x₂ = 2,5

x₂ = 0 => 2x₁ = 10, x₁ = 1,25

Per tutti il semipiano buchi univocamente il punto grafico e vedi se si verifica il vincolo

Analizziamo la f.o.:

3x₁ + 5x₂

• x₁ = 0 se a_i ∈ S
• x₁ = 1 o k a_i ∉ S => 3x₁ = 1 o k a_i ∉ S

Questo termine assume valore 0 o 3

Consideriamo ora variabili definite in modo complementare:

4_i = 0 se a_i ∈ S

4_i = 1 o k a_i ∉ S i = 1, 2

Come scriviamo una formulazione equivalente?

• x₁ + 4₂ = 1
• x₂ + 4₂ = 1
• {x, 4(sono variabili complementari)}

x₄ = 1 - 4₂ ↦ x₂ = 1 - 4₂

(inseriamo nella formulazione precedente)

Massimo Matching Pesato (Problema Generale)

dato: grafo G-(V, E), peso (p_i ≥ 0) i ∈ E

trovare sottoinsieme M di archi (M ⊆ E) t.c. su ogni nodo incide al più 1 arco di M

Il peso complessivo di M sia max

∑_i∈M p_i

max z = ∣E∣ ∑ e_i ∈ E p_ei

se anche ammettess. per negativi gli archi corrispondenti verrebbero esclusi in automatico

Hp per assurdo

β₃ = -5 < 0

M ⊇ β₃

Ŕ = M \ β₃

c(Ŕ) = c(M) - β₃ = c(M) + β₃

=> c(Ŕ) > c(M) → su matching senza 3 è sempre migliore

Ha senso il problema di minimizzazione?

Sì ma è banale, basta non prendere alcuni archi

Massima Clique (sottografo completo)

dato: grafo G = (V, E)

Trovare un sottoinsieme S ⊆ V di nodi t.c. |S| sia max

Ogni coppia di nodi di S sia collegata da un arco

In S non ci possono essere 2 nodi se tra loro non c'è l'arco

Es. S = {1, 1, 3} sì

S = {1, 2, 6} no

insieme universo V

x_i = ¹₀ x_i ∈ S

max z = Σx_i

Per esprimere il vincolo ricorriamo al contrario sulla condizione equivalente

x_i + x_j ≤ 1, j = 1,...,m : (i, j) ∉ E

es.

1. x₁ + x₂ ≤ 1
2. x₁ + x₃ ≤ 1
3. x₁ + x₄ ≤ 1
4. x₁ + x₆ ≤ 1
5. x₂ + x₃ ≤ 1
6. x₂ + x₄ ≤ 1
7. x₂ + x₅ ≤ 1
8. x₂ + x₆ ≤ 1
9. x₃ + x₄ ≤ 1
10. x₃ + x₅ ≤ 1
11. x₄ + x₅ ≤ 1
12. x₄ + x₆ ≤ 1
13. x₅ + x₆ ≤ 1

x_i ∈ {0, 1}

0 1 sì

1 0 sì

1 1 no

Funzione di variabili binarie

M = 2

x₁, x₂ ∈ {0,1}

A( , ) posso avere 2⁴ - 2 (2^{M^m}) funzioni

ogni configurazione ha un unico corrispondente (non univoco)

es.

f₃ → x₁ ≥ 1

f₁₃ → x₁ + x₂ ≤ 1

f₁₁ → x₁ ≥ x₂

x₁ - x₂ ≥ 0

∀

P(A) ⇒ ogni soluzione è ammissibile

min / max ∑ c_i x_i

i = 1

st. x_i ∈ {0,1}; i = 1, ..., m

soluz. ottima

x^* = (0, ..., 0)

z^* = z(x^*) = 0 (LB)

soluz. ottima

x^* = (1, ..., 1)

z^* = ∑ c_i (UB)

i = 1, ..., n

⇒ 0 ≤ z ≤ ∑ c_i

i = 1

∀

P(A) / {a₁, a₂, a₃}

m = 4

|a| = |P(A)| = 4 - 1 = 2⁴ - 1

Ipotesi caso dei vincoli

1. V₁ x₁ + x₂ + x₃ = 0
2. V₂ x₁ + x₂ + x₃ ≤ 2

sottainsieme di A che contengano va più di due elementu tra a₁, a₂, a₃ NO