a) Programmazione lineare

Le variabili del problema sono costituite dal numero di calcolatori che la OSS acquista da ogni concessionario nei diversi mesi: si indichi pertanto con x_ij il numero di calcolatori acquistato dal concessionario i nel mese j.

La funzione obiettivo C (da minimizzare) è il costo totale dell’operazione per l’OSS. Se si indica con c_ij il costo di un calcolatore acquistato presso il concessionario i nel mese j, si ha:

C = 7.6x₁₁ + 7.8x₁₂ + 7.8x₁₃ + 8.1x₁₄ + 8.2x₂₁ + 8.3x₂₂ + 8.4x₂₃ + 8.5x₂₄ + 7.4x₃₁ + 7.4x₃₂  + 7.5x₃₃ + 7.6x₃₄

I vincoli sono di due tipi. Il primo riguarda il soddisfacimento della domanda, mese per mese:

x₁₁ + x₂₁ + x₃₁ =  8                 (gennaio)

x₁₂ + x₂₂ + x₃₂ =  6                 (febbraio)

x₁₃ + x₂₃ + x₃₃ = 10                (marzo)

x₁₄ + x₂₄ + x₃₄ =  6                 (aprile)

Il secondo tipo di vincoli è relativo alla disponibilità di macchine presso i singoli concessionari:

x₁₁ + x₁₂ + x₁₃ + x₁₄ £ 12       (concessionario IBM)

x₂₁ + x₂₂ + x₂₃ + x₂₄ £ 13       (concessionario Olivetti)

x₃₁ + x₃₂ + x₃₃ + x₃₄ £ 11       (concessionario HP)

La formulazione del problema di programmazione lineare è quindi la seguente:

C_min = min S_i S_j c_ij x_ij

S_i x_ij = d_j                                     (j = 1,….,4)

S_j x_ij £ o_i                                     (i = 1,….,3)

x_ij ³ 0

Inoltre le variabili x_ij devono essere intere.

Ai fini della risoluzione del problema, è necessario introdurre tre ulteriori variabili, dette variabili di slack, per trasformare i tre vincoli di disuguaglianza in altrettanti vincoli di uguaglianza. In totale si hanno perciò 15 variabili e 7 vincoli.

b) Trasporto

Il problema può essere riformulato come un problema di trasporto, facendo corrispondere il vettore delle quantità disponibili presso i singoli concessionari (offerta) al vettore delle origini o_i e il vettore delle quantità richieste nei singoli mesi (domanda) al vettore delle destinazioni d_j. La matrice dei costi c_ij, orlata dai due vettori rappresentanti la domanda e l’offerta, è mostrata in figura.

Si noti l’introduzione, nel vettore della domanda, di un elemento (scarto) che rappresenta la differenza tra la quantità totale offerta (36 macchine) e la domanda reale (30 macchine); a tale elemento è associata nella matrice dei costi una colonna di zeri, in quanto le 6 macchine non vengono acquistate, ma restano a magazzino presso i concessionari.

Il problema così formulato presenta 15 variabili e 8 vincoli, questi ultimi in corrispondenza ai tre termini del vettore offerta e ai cinque del vettore domanda. Uno dei vincoli, tuttavia, è ottenibile come combinazione lineare degli altri: i vincoli linearmente indipendenti sono pertanto solo 7.