Problema dell'assegnamento - Ricerca operativa

Si ricorda che: ∗ ∗

= min { , ∈ , ∉ }

Quindi, in realtà, bisogna prendere i cos di una so omatrice della matrice che è la

,

so omatrice evidenziata in giallo, perché le righe della so omatrice corrispondono ai nodi

di e le colonne non hanno nodi che appartengono a . Quindi:

∗ ∗

=3

1 2 3 4 5

1 3 3 3 7 8

2 5 7 8 5 11

3 7 8 11 3 10 −

4 7 10 11 4 4 −

5 6 6 10 8 1 −

+ +

Si o ene: 1 2 3 4 5

1 0 0 0 7 8

2 0 2 3 3 9

3 1 2 5 0 7

4 0 3 4 0 0

5 2 2 6 7 0

No amo che è apparso un nuovo e quindi la rete si arricchisce di un nuovo arco. Partendo

0

dalla nuova matrice si verifica se è possibile avere un assegnamento ammissibile: se ciò

accade sarà anche o mo.

Per verificare ciò si risolve il problema del massimo flusso e se il massimo flusso inviabile da

è pari a (in questo caso allora si ha un assegnamento o male.

5)

Risolvendo il problema del massimo flusso sul nuovo digrafo si o ene che:

∗ ∗

{2,3,4,5}

= = {1,4,5}

Non è possibile un assegnamento ammissibile e quindi modifichiamo ulteriormente la

matrice dei cos , seguendo i passaggi già vis precedentemente:

1 2 3 4 5

1 0 0 0 7 8

2 0 2 3 3 9

3 1 2 5 0 7

4 0 3 4 0 0

5 2 2 6 7 0

=2

1 2 3 4 5

1 3 3 3 7 8

2 5 7 8 5 11 −

3 7 8 11 3 10 −

4 7 10 11 4 4 −

5 6 6 10 8 1 −

+ + +

1 2 3 4 5

1 2 0 0 9 10

2 0 0 1 3 9

3 1 0 3 0 7

4 0 1 2 0 0

5 2 0 4 7 0

Risolvendo il problema del massimo flusso con questa istanza si o ene che:

∗ ∗

∗ ∗ ∗

∗

= 5 = 1 = 1 = 1 = 1 = 1

La soluzione ammissibile ricavata è anche o ma e si può verificare che:

∗ )

( = 21

ESERCIZIO

Partendo dalla tabella dei cos si applicherà il metodo ungherese.

=4

1 2 3 4

1 3 1 2 3

2 2 4 1 1

3 4 2 5 3

4 2 3 4 2

Ora, so raiamo per ogni riga il valore minimo della riga stessa:

1 2 3 4

1 3 1 2 3 → −1

2 2 4 1 1 → −1

3 4 2 5 3 → −2

4 2 3 4 2 → −2

Quindi: 1 2 3 4

1 2 0 1 2

2 1 3 0 0

3 2 0 3 1

4 0 1 2 0

So raiamo anche il minimo costo per ogni colonna, ma no amo che per ogni colonna il

minimo è 0 e quindi la matrice dei cos resta invariata.

Nella matrice sono apparsi diversi 0, e ques corrispondono agli archi di minimo costo.

Dove è presente lo 0 vuol dire che quella cella, e quindi quell’arco, sono papabili archi per

entrare in soluzione.

Supponiamo di scegliere alcune celle tra quelle con valore nullo, in modo da assegnare a

queste celle, e quindi alle variabili il valore 1 (e quindi fare un assegnamento).

Evidenziamo lo 0 per cui si impone e in questo caso si è fa o un

= 1, = 1:

assegnamento dall’elemento 4 di all’elemento 1 di

Supponiamo di scegliere anche gli altri 0 evidenzia :

1 2 3 4

1 2 0 1 2

2 1 3 0 0

3 2 0 3 1

4 0 1 2 0

Non si può imporre perché immaginiamo che nella tabella al posto dei cos ci

= 1

fossero i valori delle variabili: non sarebbe soddisfa o il vincolo del problema perché già

e quindi la sommatoria delle fissato non darebbe come risultato 1 ma 2.

= 1 = 2

Vale lo stesso discorso per in relazione alla riga 2 e per in relazione alla riga 4.

Disegniamo la rete istanza del problema del massimo flusso: =1 =0

Bisogna poi scegliere un qualsiasi algoritmo per risolvere il problema del massimo flusso

(Cammini Aumentan o Ford & Fulkerson).

Bisogna prima verificare se esistono cammini aumentan : se esistono si evidenziano nel

grafo e si inserisce il flusso.

La capacità è 1 su tu gli archi, quindi su ogni arco può transitare al più una unità di flusso.

Per verificare graficamente se esistono cammini aumentan , si parte da si va a 2, poi 3 e

,

poi non è necessario capire qual è il flusso che bisogna inserire (e quindi le delle

;

e che e).

Si è individuato: = {, 1,2 , }

Si evidenzia il flusso sul grafo perché ci si rende conto che su quegli archi c’è flusso e quegli

archi sono saturi, per cui non possono essere più presi per generare un cammino

aumentante:

Ora controlliamo se ci sono altri cammini aumentan ; l’arco è saturo quindi si procede

− 1

con e seguendo questa logica si trova:

− 2 = {, 2,3 , }

Procedendo secondo questo ragionamento si o ene l’ul mo cammino aumentante della

rete; ulteriori non ce ne saranno: = {, 4,1 , }

In questo caso: =3≠4

Allora, considerando le celle di non esiste un assegnamento ammissibile.

,

Bisogna modificare la matrice dei cos e quindi dobbiamo iden ficare e tali che

∗ ∗

dove è l’insieme dei nodi e che a all’ul ma iterazione del metodo di Ford

∗ ∗

∪ = ,

& Fulkerson. Quest’ul ma iterazione è quella per cui non si riesce a determinare un

cammino aumentante perché non si riesce ad e che are il nodo

Dato che non esiste un quarto cammino aumentante, bisogna individuare i nodi e che a

(non ci interessa sapere cosa contengono le e che e ma solamente quali sono i nodi

e che a e non).

Si parte con l’e che are il nodo lo si seleziona: il simbolo indica il nodo e che ato

, [•]

estra o da

Adesso, dal nodo bisogna andare o in avan o indietro e che ando i nodi successivi.

,

Provando ad andare in avan (per ora è possibile andare solo avan ), si può andare al nodo

3 perché l’arco non è saturo e quindi si e che a 3. Non possiamo e che are 1,2,4 perché

gli archi che partono da sono saturi.

Si seleziona quindi il nodo 3 (si aggiunge a

• [ ]):

Con la stessa logica si può e che are il nodo e selezionarlo. Non ci sono più archi uscen .

2

Ora si passa alla seconda parte del passo 2 dell’algoritmo di Ford & Fulkerson, nella quale

bisogna e che are i nodi degli archi entran nel nodo .

2

Gli archi entran nel nodo 2 sono e : l’arco non lo si considera perché 3 è

3−2 1 − 2 3 − 2

già stato e che ato. L’arco lo si può considerare perché 1 non è stato e che ato, e

1 − 2

quindi si può e che are il nodo 1 se (perché si sta andando indietro e se quell’arco

> 0

facesse parte del cammino aumentante, va a ridurre il flusso).

Si seleziona e si può estrarre il nodo 1:

Dal nodo 1 si può andare a finire solamente al nodo , che però è già stato e che ato e

2

quindi ci si ferma.

Allora: = {1,3,2 }

∗ ∗

{1,3}

= = {2 }

Grazie alle informazioni ricavate è possibile andare a modificare la matrice dei cos , e

quindi andare a sommare un valore:

∗ ∗ }

= min ∈ , ∉ = min{ , , , , = min{2,1,2,2,3,1} = 1

1 2 3 4

1 2 0 1 2 → −1

2 1 3 0 0

3 2 0 3 1 → −1

4 0 1 2 0

+1

1 2 3 4

1 1 0 0 1

2 1 4 0 0

3 1 0 2 0

4 0 2 2 0

Andiamo quindi a verificare se è possibile un assegnamento ammissibile.

I cammini aumentan saranno: = {, 1,2 , }

= {, 2,3 , }

= {, 4,1 , }

= {, 3,4 , }

Non esistono altri cammini aumentan ed è stata determinata la distribuzione di flusso

o ma per il problema del massimo flusso, con:

∗

= 4 ≡ = 4

Sulla matrice dei cos è possibile effe uare un assegnamento ammissibile.

Quest’assegnamento ammissibile non lo si fa a tenta vi ma l’assegnamento ammissibile è

associare la variabile pari ad 1 del problema dell’assegnamento in corrispondenza della

variabile per cui c’è flusso sul problema del massimo flusso appena risolto.

Naturalmente non ci interessano gli archi fi zi ma solo quelli che collegano i nodi di ai

nodi di .

Sull’arco ci sta flusso e quindi analogamente

1 − 2 = 1; = 1, = 1, = 1

1 2 3 4

1 1 0 0 1

2 1 4 0 0

3 1 0 2 0

4 0 2 2 0

E’ un assegnamento ammissibile perché per ogni riga si ha una variabile così come

= 1,

per ogni colonna. ∗ ∗ ∗ ∗

= 1 = 1 = 1 = 1

∗ )

( = + + + =1+1+3+2=7

No amo una cosa: all’iterazione 0 si è so ra o in totale (sommando per le righe) una

quan tà di 6, mentre sulle colonne non si è so ra o nulla:

1 2 3 4

1 3 1 2 3 → −1

2 2 4 1 1 → −1

3 4 2 5 3 → −2

4 2 3 4 2 → −2

Abbiamo modificato una sola volta la matrice dei cos , con un valore di = 1

Quindi: 6+1 =7

Questa è una sorta di verifica: si considera la somma di tu e le variazioni di costo che si

sono eseguite e si deve o enere il valore di funzione obie vo.

ESERCIZIO

Partendo dalla tabella dei cos si applicherà il metodo ungherese.

=4

1 2 3 4

1 14 5 8 7

2 2 12 6 5

3 7 8 3 9

4 2 4 6 10

Ora, so raiamo per ogni riga il valore minimo della riga stessa:

1 2 3 4

1 14 5 8 7 → −5

2 2 12 6 5 → −2

3 7 8 3 9 → −3

4 2 4 6 10 → −2

Quindi: 1 2 3 4

1 9 0 3 2

2 0 10 4 3

3 4 5 0 6

4 0 2 4 8

So raiamo anche il minimo costo per ogni colonna:

1 2 3 4

1 9 0 3 2

2 0 10 4 3

3 4 5 0 6

4 0 2 4 8

−0 −0 −0 −2

Quindi: 1 2 3 4

1 9 0 3 0

2 0 10 4 1

3 4 5 0 4

4 0 2 4 6

Si risolve il problema del massimo flusso (a pagina seguente)

I cammini aumentan saranno: = {, 1,2 , }

= {, 2,4,1 , }

= {, 3,3 , }

E che ando in modo adeguato i nodi:

Allora: = {2,4,1 }

∗ ∗

{2,4}

= = {1}

Segue che: ∗ ∗ }

= min ∈ , ¬i