Ricerca Operativa II
prova scritta del 26 giugno 2001

Nuove professioni per la nuova economia
Mamma mi vuole medico, papà avvocato, ma io in un anno ─ con CEPPU ─ diventerò Traveling Salesman! Travel… che vorrà dire? Titolare di un’agenzia di viaggi?

………

Mi hanno dato un furgoncino e devo fare il giro di 8 città (A, B, C, …, H). Per trovare il giro più breve ho scaricato un software dalla rete. Dice che ogni coppia di città (i, j) ha associato un numero: se è 1, allora devo visitare j subito dopo i, se è 0 invece no. Solo che io ho trovato questi numeri: 

AC = ½		BC = ¼		FC = ¼		HE = ¼
AG = ½	BD = ¾		FD = ¼		HG = ¼
					FE = ¼
					FG = ¼

CA = ¼		DA = ¾	EB = 1/3	GB = 2/3
CH = ¾		DH = ¼	EF = 2/3 	GF = 2/3

Allora ho interpellato un mio amico laureato in informatica. Mi ha detto che la soluzione non è ammissibile, ma che si può provare a trovare una diseguaglianza che la tagli via. 
Ma come si fa? Lo dicevo io che l’università non serve a niente. 

Soluzione
Si tratta di trovare un (s, t)-taglio di capacità minima nel grafo riportato in figura. Può non essere facile (anche perché si tratta di applicare Ford-Fulkerson a tutte le coppie di nodi s, t), e magari il taglio minimo non corrisponde a una diseguaglianza violata. Non si pretende perciò di trovare la soluzione numerica del problema, basta solo formularlo correttamente. 

A

B

C

D

E

F

G

H

1/4

1/2

3/4

2/3

1/4

1/4

1/4

1/4

1/3

1/3

3/4

1/3

3/4

3/4

1/4

1/4

1/2

2/3