Problema di assegnamento

X

X X

X X

X

2 0 1

= + + =

x

d x

d x

d

ij ij ij

ij j i

j=1

i=1 i=1

j=1 j=1

i=1

n n n n n n

X X X X X X

2 0 1

= + +

x

d d x d x .

ij ij ij

ij j i

i=1 j=1 j=1 i=1 i=1 j=1 – p. 11/40

n

P = 1 per ogni e

Per ogni assegnamento si ha x j

ij

i=1

n

P = 1 per ogni , quindi il valore dell’assegnamento è

x i

ij

j=1

uguale a n n n n

X X X X

2 0 1

+ +

x

d d .

d

ij

ij j i

i=1 j=1 j=1 i=1

Ponendo n n

X X

0 1

= =

D D

d ,

d

0 1

j i

j=1 i=1

si ha infine n n n n

X X X X 2

= + +

d x x D D .

d 0 1

ij ij ij

ij

i=1 j=1 i=1 j=1 – p. 12/40

Continua

2 ≥ 0 per ogni , e poiché si

Poiché, come già osservato, i, j

d ij

≥ 0

ha anche che per ogni , si ha che

x i, j

ij n n

X X ≥ +

d x D D ,

0 1

ij ij

i=1 j=1

per ogni possibile assegnamento. – p. 13/40

Nell’esempio ...

= 8 = 0 + = 8

... abbiamo e . Quindi, fornisce

D D D D

0 1 0 1

un lower bound per il valore ottimo di questa istanza del

problema di assegnamento. – p. 14/40

Ma allora ... +

... se trovo un assegnamento con valore pari a ,

D D

0 1

questo è certamente anche una soluzione ottima.

Quindi la domanda che ci poniamo ora è la seguente:

+

esiste o meno un assegnamento con valore ?

D D

0 1

In caso di risposta positiva, abbiamo una soluzione ottima

del problema, in caso di risposta negativa ci dovremo poi

porre la questione di cosa fare se non esiste. – p. 15/40

Problema associato

∆

Determinare un sottinsieme di cardinalità massima degli

∆

0 della matrice tale che presi due elementi qualsiasi di

T 2

essi sono , ovvero appartengono a righe e

indipendenti

colonne diverse. – p. 16/40

Se ... ∆ | ∆ |=

... questo problema ammette una soluzione con ,

n

consideriamo allora: ( 1 (i, ∈ ∆

se j)

=

x ij 0 altrimenti

Per prima cosa dimostriamo che tale soluzione è un

assegnamento. Supponiamo per assurdo che non lo sia.

Per esempio supponiamo che per qualche si abbia

j

n

X 6 = 1.

x ij

i=1 – p. 17/40

Casi possibili

n

P = 0

: in tal caso non c’è nessun elemento

x

Caso I ij

i=1

∆

di nella colonna . Quindi ve ne dovranno essere

j n

− 1

nella restanti colonne. Ciò vuol dire che almeno

n ∆

una colonna contiene due elementi in , ma questo è

∆

assurdo in quanto gli elementi di devono essere tra

loro indipendenti e quindi non possono appartenere ad

una stessa colonna.

n

P ≥ 2

: in tal caso ci sono due elementi di

x

Caso II ij

i=1

∆ nella colonna e si ha una contraddizione identica a

j

quella vista per il Caso I. – p. 18/40

Continua

In modo del tutto analogo si vede che le condizioni

n

X = 1 ∀

x i,

ij

j=1

non possono essere violate. Quindi abbiamo un

assegnamento. – p. 19/40

Valore dell’assegnamento

Si nota che le sono uguali a 1 solo in corrispondenza di

x

ij 2 = 0

(i, . Quindi

coppie per cui si ha

j) d ij

n

n

n

n X

X

X

X 2

= + + = +

x x D D D D .

d

d 0 1 0 1

ij ij

ij ij

j=1

i=1

j=1

i=1 +

ovvero il valore di questo assegnamento è e per

D D

0 1

quanto già osservato la soluzione è ottima. – p. 20/40

∆?

Ma come si calcola

Si costruisca un grafo bipartito nel modo seguente:

i due insiemi di vertici sono rispettivamente rappresentati

*

dall’insieme e dall’insieme ;

A B

tra il vertice ed il vertice si traccia un arco (non

a b

* i j

2 = 0

.

orientato) se e solo se d ij

Un insieme indipendente di 0 equivale a un matching su

tale grafo bipartito. Infatti, cercare insiemi di 0 nella tabella

che non siano mai sulla stessa riga e colonna equivale a

cercare insiemi di archi nel grafo bipartito che non abbiano

nodi in comune, ovvero equivale a cercare dei matching.

Quindi, determinare il massimo insieme di 0 indipendenti

equivale a risolvere un problema di matching di cardinalità

massima sul grafo bipartito. – p. 21/40

Nell’esempio

Risolvendo con l’algoritmo visto per i problemi di matching

di cardinalità massima su grafi bipartiti, si ottiene la

seguente soluzione:

∆ = {(a ); (a ); (a )}

, b , b , b

1 1 2 3 3 2

| ∆ |< = 4

con .

n – p. 22/40

| |< n?

∆

Che fare se

L’obiettivo finale sarà quello di giungere ad un’ulteriore

trasformazione della matrice . Per arrivare a questa è

T 2

necessario un passaggio ulteriore in cui si sfrutta l’insieme

∆ trovato. Si tratterà di risolvere il seguente problema:

determinare un insieme minimo di righe e colonne tali che

ricoprendole si ricoprono tutti gli 0 della matrice T 2

Nel seguito si parlerà genericamente di linee, dove una

linea può essere indifferentemente una riga od una

colonna. – p. 23/40

Continua

Questo è strettamente legato a quello della determinazione

∆

dell’insieme .

Infatti, consideriamo le etichette ottenute all’ultima

iterazione dell’algoritmo per il massimo matching sul grafo

∆

bipartito costruito per determinare . Si può dimostrare la

seguente proprietà:

Un ricoprimento ottimo per il problema dato è formato da

| ∆ |

esattamente linee ed è costituito da:

(i) Le righe corrispondenti a nodi non etichettati.

a

i

(ii) le colonne corrispondenti a nodi etichettati.

b i – p. 24/40

Nell’esempio

Le righe corrispondenti a nodi non etichettati al termine

della risoluzione del problema di matching sono e ,

a a

2 3

mentre la sola colonna corrispondente a un nodo

etichettato è la .

b 1 – p. 25/40

T

Aggiornamento della matrice 2

Il ricoprimento con un numero minimo di linee ottenuto con

la procedura appena descritta ci serve per aggiornare la

matrice e trasformarla in una nuova matrice . La

T T

2 3

trasformazione avviene seguendo questi passi.

Determinare il valore minimo tra tutti gli elementi di

λ T

a) 2

ricoperti da alcuna linea. Si noti che essendo gli 0

non

di tutti ricoperti, gli elementi non ricoperti sono tutti

T 2

positivi e quindi stesso è positivo.

λ – p. 26/40

3 della nuova matrice sono definiti in

Gli elementi T

d

b) 3

ij

questo modo: 3

3

2

3 +

+

= ,

d

d

d

d j

i

ij

ij

dove ( 0 se la riga è nel ricoprimento

a

i

3 =

d i −λ altrimenti

e ( se la colonna è nel ricoprimento

λ b j

3 =

d j 0 altrimenti – p. 27/40

Più semplicemente ...

... quanto visto equivale alla seguente regola:

gli elementi ricoperti da due linee in devono essere

T 2

incrementati di ;

λ

gli elementi non ricoperti da alcuna linea vengono

decrementati di ;

λ

tutti gli altri (gli elementi ricoperti da una sola linea) non

cambiano – p. 28/40

Nell’esempio

= 1

Si ha e sarà la seguente tabella:

λ T 3 b b b b

1 2 3 4

0 0 1 2

a

1 5 0 0 0

a

2 6 0 1 1

a

3 0 0 1 2

a

4 – p. 29/40

Osservazione

Da questa regola si vede anche che i soli elementi a cui

viene sottratto qualcosa sono quelli non ricoperti e ad essi

viene sottratto il minimo di tutti gli elementi non ricoperti.

3 di saranno non

Ciò significa che tutti gli elementi T

d 3

ij

negativi come lo erano quelli di .

T 2 – p. 30/40

Un nuovo lower bound

Il valore di un assegnamento era stato riscritto in questo

modo: n n n n

X X X X 2

= + +

d x x D D .

d 0 1

ij ij ij

ij

i=1 j=1 i=1 j=1 3

3

3

2 −

−

= ed andando a

Osserviamo ora che d

d

d

d j

i

ij

ij

sostituire otteniamo:

X X X X

n n n n

2 3 3 3

+ + = (d )x + + =

d x D D d d D D

− −

0 1 0 1

ij ij

ij ij i j

i=1 j=1 i=1 j=1

X X X X X X

n n n n n n

3 3 3

= + + =

d x d x d x D D

− − 0 1

ij ij ij

ij j i

i=1 j=1 j=1 i=1 i=1 j=1

X X X

X X

X

n n n

n n

n

3 3 3

= + +

d x x

d x D D .

d

− − 0 1

ij ij ij

ij j i

i=1 j=1 i=1

j=1 j=1

i=1 – p. 31/40

Quindi ...

... per ogni assegnamento, si avrà

n

n n n n n

X X X X X X

3 3 3

= − − + +

d x x

d d D D .

d 0 1

ij ij ij

ij j i

i=1 j=1 i=1 j=1 j=1 i=1 – p. 32/40

Continua n

n 3

3 P

P .

e

Vediamo ora di calcolare d

d i

j i=1

j=1

Indichiamo con il numero di righe nel ricoprimento e con

h

1

il numero di colonne nel ricoprimento. Si noti che

h

2 + =| ∆ |

.

h h

1 2

Si ha:

X

n 3 = (numero = ),

righe che non sono nel ricoprimento)

d h

−λ × −λ(n − 1

i

i=1

e X

n 3 = (numero =

colonne che sono nel ricoprimento)

d λ λh .

× 2

j

j=1 – p. 33/40

Quindi...

n n n n

X X X X 3

= + − ) − + +

d x x λ(n h λh D D ,

d 1 2 0 1

ij ij ij

ij

i=1 j=1 i=1 j=1

da cui

n n n n

X X X X 3

= + | ∆ |) + +

d x x λ(n− D D .

d 0 1

ij ij ij

ij

i=1 j=1 i=1 j=1 – p. 34/40

Continua

3 ≥ 0 ≥ 0

e si ha che un limite

dal momento che x

d ij

ij

inferiore per il problema di assegnamento è

+ + | ∆ |) ;

D D λ(n−

0 1

se riesco a trovare un assegnamento che ha come

valore dell’obiettivo proprio tale limite inferiore ho

determinato una soluzione ottima;

la verifica se un tale assegnamento esista può essere

fatto cercando un sottinsieme indipendente di

cardinalità massima in , esattamente come si era fatto

T 3

in . Se esso ha cardinalità si ha un assegnamento

T n

2<