Esercitazione n
o13 per il corso di Ricerca Operativa
Modello di assegnamento Il problema `e stato tratto dal libro
Kenneth R. Baker. ”Optimization Modeling with Spreadsheet”, 2nd Edition, 2011, ISBN: 978-0-470- 92863-9, pag. 77.
Un’azienda produce sei tipi di veicoli in sei diversi impianti di produzione. L’azienda ha stabilito che ogni veicolo deve essere prodotto in un solo impianto e conosce i costi annuali di produzione di ogni veicolo in ogni impianto. Tali costi osno riportati nella seguente tabella
prodotto
1 2 3 4 5 6
impianto Compact Coupe Sedan SUV Truck Van
Akron 80 56 43 62 46 58
Buffalo 94 50 88 64 63 52
Columbus 94 46 50 40 55 73
Detroit 98 79 71 65 91 59
Evansville 61 59 89 98 45 52
Flint 77 49 65 95 72 91
Si vuole decidere come assegnare gli oeratori ad ogni turno in modo che la richiesta di personale sia soddisfatta e il numero totale di persone necessarie a coprire le necessit´a sia minimizzato.
1
Analisi sintetica del problema.
* ogni prodotto deve essere assegnato ad un solo impianto
* ogni impianto realizza un solo prodotto.
Formulazione.
– Variabili di decisione. xij, i, j = 1, . . . , 6: vale 1 se il prodotto i ´e realizzato nell’impianto j;
zero altrimenti.
– Funzione obiettivo. Si vuole minimizzare il costo annuale X6
i=1
X6 j=1
cijxij.
– Vincoli.
Vincoli di assegnazione di prodotto a impianto viceversa
impianto j : X6 i=1
xij = 1 ∀ j
prodotto i : X6 j=1
xij = 1 ∀ i
Infine si devono considerare i vincoli di non negativit`a xij≥ 0, i, j = 1, . . . , 6.
Si osservi che si possono eliminare i vincoli xij ∈ {0, 1}, in quanto la matrice dei vincoli risulta essere totalmente unimodulare.
2
