Un esercizio svolto di programmazione lineare

Cos’è la programmazione lineare

ESERCIZIO 

Un’impresa produce un certo articolo in due diversi centri di produzione: P₁ e P₂. Settimanalmente sono prodotti 2800 pezzi nel centro P₁ e 3500 pezzi nel centro P₂. Tutti i pezzi prodotti devono essere convogliati in tre centri di smistamento – S₁, S₂, S₃ – in modo che ogni settimana in S₁ giunga il 50 % dei pezzi prodotti, in S₂ ne giunga il 22 % ed in S₃ la quantità rimanente. La seguente tabella indica il costo unitario di trasporto (in euro) dai centri di produzione a quelli di smistamento:

Trovare quale piano di trasporto ottimizza i costi.

SOLUZIONE

Osserviamo anzitutto che i pezzi prodotti sono in numero di:

2800 + 3500 = 6300 .

Di essi:

– in S₁ ne deve essere convogliato il 50 % , vale a dire: 0,50×6300 = 3150 ;
– in S₂ ne deve essere convogliato il 22 % , vale a dire: 0,22×6300 = 1386 ;
– in S₃ deve giungere la parte rimanente, vale a dire: 6300 – (3150+1386) = 1764 .

Indichiamo ora con x, y, z i numeri dei pezzi che devono essere trasportati da P₁ rispettivamente ad S₁, S₂, S₃; per cui:

x + y + z = 2800 

con x≥ 0, y≥ 0, z≥ 0

Allora i numeri dei pezzi che da P₂ devono essere convogliati in S₁, S₂, S₃ sono nell’ordine:

3150 – x , 1386 – y , 1764 – z

con 3150–x ≥ 0, 1386–y ≥ 0, 1764–z ≥ 0.

Il costo per il trasporto (espresso in euro) è chiaramente una funzione delle variabili x, y, z; se lo indichiamo con ω, risulta:

ω = (0,07 x + 0,09 y + 0,08 z) + [0,08 (3150–x) + 0,06 (1386–y) + 0,07 (1764–z)];

ossia, dopo aver semplificato:

ω = 458,64 – 0,01 x + 0,03 y + 0,01 z .

Si tratta di rendere minima questa funzione, con i seguenti vincoli:

x + y + z = 2800,
x ≤ 3150,
y ≤ 1386,
z ≤ 1764

e naturalmente con x≥ 0, y≥ 0, z≥ 0.

Ora, dall’equazione x+y+z=2800 si ricava z=2800–x–y. Per cui la funzione ω in effetti diventa una funzione delle due variabili x, y; vale a dire:

ω = 458,64 – 0,01 x + 0,03 y + 0,01 (2800 – x – y) ,

ossia, dopo aver semplificato:

ω = 486,64 – 0,02 x + 0,02 y .

Riguardo ai vincoli bisogna tener presente che la disequazione z ≤ 1764 diventa 2800–x–y≤1764, ossia x+y ≤ 1036; e la condizione z ≥ 0 diventa 2800–x–y ≥ 0, ossia x+y ≥ 2800.

In definitiva il modello matematico in cui si traduce il problema è il seguente:

Rendere minima la funzione:

ω = 486,64 – 0,02 x + 0,02 y ,

sotto le condizioni seguenti:

0≤ x ≤ 3150 , 0 ≤ y ≤ 1386 , 1036 ≤ x+y ≤ 2800 .

Troviamo anzitutto la regione delle soluzioni ammissibili, la quale è costituita dalla superficie evidenziata nella figura sotto, incluso il contorno.

Si fa notare che il vincolo x≤3150 è superfluo (o, come anche si dice, ridondante). Di fatto è implicito nel vincolo x+y ≤ 2800 (se x+y≤2800 allora sicuramente x< 3150).

Siccome si tratta di rendere minima la funzione:

ω = 486,64 – 0,02 x + 0,02 y (€) ,

poniamo:

486,64 – 0,02 x + 0,02 y = k ,

ottenendo così un fascio di rette parallele, di coefficiente angolare 1, la generica delle quali diciamo t.
Per un certo valore di k, che chiamiamo min(k), si ottiene la retta t_min che passa per uno dei vertici del contorno della regione delle soluzioni ammissibili, mentre per k<min(k) la retta t è esterna a quella regione. Il valore min(k) è il minimo valore della funzione ω che stiamo cercando.

Nel nostro caso il vertice in questione è il punto A in cui la retta x+y=2800 seca l’asse x,
ovvero il punto di coordinate (2800, 0).

Dunque:

min(ω)=min(k)=486,64–0,02×2800=430,64 (€).

 

(599)

PubblicitàPubblicità