Esercizi - 2.6
Esercizio n. 2.6.1
Determinare un accoppiamento di massima cardinalita' nel grafo
bipartito in figura, utilizzando l' algoritmo basato sui cammini
alternanti aumentanti. Si risolva successivamente il problema
trasformandolo in un problema di flusso massimo, determinando inoltre
un taglio di capacita' minima. Si risolva infine lo stesso problema per
il grafo ottenuto aggiungendo l' arco (5,10) a quello in figura.
Esercizio n. 2.6.2
Un' azienda metalmeccanica deve assegnare quattro lavori a quattro operai.
La tabella indica il grado di efficienza con cui gli operai possono
eseguire i lavori. Un "/" nella posizione (i,j) indica che l' operaio i
non e' in grado di svolgere il lavoro j.
1) Assegnare i lavori agli operai massimizzando la somma dei gradi di
efficienza con cui vengono svolti i lavori.
2) Assegnare i lavori agli operai in modo che sia massimo il minimo grado
di efficienza con cui vengono svolti i lavori.
Esercizio n. 2.6.3
Il Magnifico Rettore dell' Universita' deve assegnare la presidenza di
n commissioni ad altrettanti preselezionati professori. Ogni docente
propone (in ordine decrescente di preferenza) una lista di tre commissioni,
che e' disposto a presiedere. Supponendo che sia possibile assegnare
le presidenze in modo che ciascun professore presieda una commissione tra
quelle da lui indicate, bisogna determinare un assegnamento che renda
massimo il numero di docenti che presiedono la commissione da loro
preferita ed inoltre, tra tutti questi assegnamenti, quello che rende
massimo il numero di docenti che presiedono la seconda commissione da loro
indicata. Mostrare come risolvere questo problema come un unico
problema di assegnamento.