prova scritta del 21 luglio 1998

I prodotti elaborati da una certa società sono costituiti da componenti di 2 tipi diversi. Non tutti i componenti del primo tipo sono tuttavia compatibili con quelli del secondo tipo; inoltre, l’assiematura di una coppia compatibile (u, v) di componenti ha un certo costo c_uv.

Orbene, la società desidera minimizzare il costo richiesto dall’assiematura di tutti i componenti disponibili in magazzino. Formulare il problema descritto. Determinare poi tramite il metodo primale-duale il valore di una soluzione ottima nel caso in cui la matrice di compatibilità dei prodotti sia quella sotto riportata.

P.S. La matrice di compatibilità va letta come segue: i componenti di tipo 1 (di tipo 2) sono riportati per righe (per colonne); se 2 componenti non sono compatibili – se cioè non è possibile montarli insieme – allora il corrispondente elemento della tabella è un trattino, altrimenti risulta pari al costo di assiematura dei componenti.