Cos’è la programmazione lineare

Modelli di programmazione lineare

I modelli di programmazione matematica sono modelli che descrivono le caratteristiche della soluzione ottima di un problema di ottimizzazione attraverso relazioni matematiche.
Un modello di programmazione matematica è composto dai seguenti elementi:
• Insiemi: raggruppano gli elementi del sistema;
• Parametri: sono i dati del problema e rappresentano delle quantità fissate che dipendono dai diversi elementi del sistema;
• Variabili decisionali o di controllo: sono le grandezze del sistema di cui non conosciamo il valore (assimilabili a delle incognite) e sulle quali possiamo agire per determinare diverse soluzioni alternative del problema;
• Vincoli: sono delle relazioni matematiche che descrivono le condizioni di ammissibilità delle soluzioni. Servono quindi per discriminare le combinazioni di valori delle variabili decisionali che rappresentano soluzioni accettabili del problema, da quelle che non lo sono;
• Funzione obiettivo: è la quantità da massimizzare o minimizzare, espressa come funzione delle variabili decisionali.

Un modello di programmazione matematica dichiara le caratteristiche della soluzione cercata (che cosa), piuttosto che definire la strategia per la ricerca della soluzione stessa (come). Un modello di programmazione matematica potrebbe essere paragonato ad un linguaggio dichiarativo, che indica cosa si vuole ottenere, piuttosto che a un linguaggio procedurale, che indica i passi per ottenere il risultato cercato.
La risoluzione di un problema di ottimizzazione formulato con un modello di programmazione matematica consiste nella determinazione dei valori delle variabili che soddisfano tutti i vincoli e massimizzano o minimizzano il valore della funzione obiettivo. Come nei linguaggi dichiarativi, una volta messo a punto il modello matematico, la ricerca della soluzione ottima può essere effettuata da appositi motori di ottimizzazione, pertanto un modello di programmazione matematica non ha solo valenza descrittiva, ma anche operativa.
I modelli di programmazione lineare sono una particolare classe di modelli di programmazione matematica in cui:
• la funzione obiettivo è un’espressione lineare delle variabili decisionali;
• i vincoli sono determinati da un sistema di equazioni e/o disequazioni lineari.

Formulazione di un modello di Programmazione Lineare

La formulazione generale di un modello di Programmazione Lineare è la seguente:

dove:
z è la funzione obiettivo da minimizzare (min) o massimizzare (max);
x_j ∀ j = 1, …, n, sono le variabili decisionali (incognite) che possono essere reali (eventualmente non negative), intere (eventualmente non negative) o binarie (x_j ∈ {0, 1});
c_j ∀ j = 1, …, n, sono i coefficienti di costo (min) o profitto (max) e sono costanti note del problema (parametri);
a_ij ∀ i = 1, …, m e ∀ j = 1, …, n, sono i coefficienti tecnologici (parametri);
b_i ∀ i = 1, …, m, sono i termini noti (parametri).

In base alla natura o dominio delle variabili decisionali, si parla di
• modelli di Programmazione Lineare (in senso stretto, PL) se tutte le variabili possono assumere valori reali;
• modelli di Programmazione Lineare Intera (PLI) se tutte le variabili possono assumere valori interi;
• modelli di Programmazione Lineare Intera Mista (PLIM) se alcune variabili possono assumere valori reali e altre valori interi.
L’importanza dei modelli di programmazione lineare risiede nella loro notevole valenza operativa (a scapito a volte della potenza descrittiva), grazie alla disponibilità di motori di ottimizzazione particolarmente efficienti.

UN ESEMPIO SEMPLICE

Una fabbrica produce due manufatti: A e B. Per il manufatto A, che poi rivende a € 1,5 al pezzo, spende € 0,3 al pezzo per l’acquisto delle materie prime e per la lavorazione del prodotto e deve affrontare una spesa fissa giornaliera di € 250. Per il manufatto B, che poi rivende a € 1,1 al pezzo, spende € 0,2 al pezzo per l’acquisto delle materie prime e per la lavorazione del prodotto e deve affrontare una spesa fissa giornaliera di € 140.
Per impegni assunti la fabbrica deve produrre giornalmente almeno 400 pezzi del manufatto B ma la produzione complessiva giornaliera dei due manufatti non può superare i 900 pezzi e il numero dei pezzi di A non può superare la metà di quello dei pezzi di B.

SOLUZIONE

Proviamo a tradurre questo problema in uno schema matematico.
Indichiamo con x ed y rispettivamente (x ≥ 0, y ≥ 0) il numero dei pezzi di A e quello dei pezzi di B che vengono prodotti giornalmente.
L’utile dell’azienda è evidentemente una funzione delle variabili x, y: indichiamo questa funzione con ω. Dunque si ha:

ω = [(1,5 – 0,3) x – 250] + [(1,1 – 0,2) y – 140]

cioè, dopo aver semplificato (sottintendendo che i vari termini sono espressi in euro):
ω = 1,2 x + 0,9 y – 390
Siccome nell’arco di una giornata lavorativa la fabbrica deve produrre almeno 400 pezzi del manufatto B, deve essere:

y ≥ 400 

d’altronde la produzione complessiva giornaliera non può superare i 900 pezzi; perciò:

x + y ≤ 900

inoltre, giacché il numero dei pezzi di A non può superare la metà dei pezzi di B, deve essere:

x ≤ y/2 , cioè: 2x − y ≤ 0

In definitiva il modello matematico che traduce il problema è il seguente:

• Rendere massima la funzione:
  ω = 1,2 x + 0,9 y – 390
• sotto le condizioni seguenti:
  y ≥ 400 , x + y ≤ 900 , 2 x – y ≤ 0 
• e naturalmente con x≥0, y≥0

Nel nostro caso:

La funzione da rendere massima (o eventualmente minima, in altre situazioni) si chiama funzione obiettivo. Essa dipende da una o più variabili – chiamate variabili attive (o variabili di azione o variabili decisionali), che devono soddisfare a determinate condizioni (equazioni e/o disequazioni), dette vincoli (o restrizioni).
Quindi:

– la funzione obiettivo è: ω = 1,2 x + 0,9 y – 390 ;
– le variabili di azione sono x, y;
– i vincoli sono le disequazioni: y≥ 400, x+y≤ 900, 2x–y≤ 0, oltre alle condizioni x≥ 0, y≥ 0, che a volte sono chiamate vincoli economici, mentre le disequazioni (e/o equazioni) sono dette vincoli tecnici.
Quando, come nel suddetto schema, la funzione obiettivo è un polinomio di 1° grado nelle sue variabili ed i vincoli sono equazioni e/o disequazioni di 1° grado in quelle variabili, il problema è chiamato problema di programmazione lineare (sinteticamente: PL).
Rientrano nella categoria più generale dei problemi di ottimizzazione.

Ritorniamo ora allo schema matematico che abbiamo lasciato poco sopra. Di esso possiamo dare facilmente un’interpretazione geometrica, dopo aver riferito il piano ad un sistema di assi cartesiani ortogonali (Oxy):

– La disequazione y≥ 400 è rappresentata dalle coppie ordinate (x,y) di numeri reali per cui risulta appunto y≥ 400, vale a dire dal semipiano chiuso (cioè contenente anche la retta origine dello stesso) posto al di sopra della retta di equazione y=400.
– La disequazione x+y≤ 900 è rappresentata dal semipiano chiuso avente come origine la retta di equazione x+y=900 e contenente il punto (0,0) le cui coordinate soddisfano alla disequazione medesima.
– La disequazione 2x–y≤ 0 è rappresentata dal semipiano chiuso avente come origine la retta di equazione 2x–y= 0 e contenente il punto (0,1) le cui coordinate soddisfano alla disequazione medesima.

In conclusione, i vincoli sono rappresentati graficamente dai punti della regione evidenziata  in giallo nella precedente figura, compreso il suo contorno. Questa regione si chiama regione delle soluzioni ammissibili (o semplicemente regione ammissibile o anche dominio dei vincoli).
Ora, però, non si tratta di prendere un qualunque punto di tale regione, ma di determinare il punto di essa che, con le sue coordinate, fa assumere il valore massimo alla funzione:
ω = 1,2 x + 0,9 y – 390 .
Per questo poniamo:
1,2 x + 0,9 y – 390 = k
ottenendo in questo modo un fascio di rette parallele, di coefficiente angolare –4/3, la generica delle quali indichiamo con t.
Per un certo valore di k, che chiamiamo max(k), si ottiene la retta t_max che passa per uno dei vertici del contorno della regione delle soluzioni ammissibili, mentre per k> max(k) la retta t non interseca quella regione. Il valore max(k) è il massimo valore della funzione ω che stiamo cercando.
Nel nostro caso il vertice in questione è il punto A le cui coordinate si ottengono risolvendo il sistema delle due equazioni: x+y=900, 2x–y=0.

Si trova: A(300, 600).

Dunque:

max (ω) = max (k) = 1,2×300 + 0,9×600 – 390 = 510

Pertanto, in conclusione: per ottenere il massimo ricavo giornaliero, che è di € 510, l’azienda deve produrre 300 pezzi del manufatto A e 600 del manufatto B.

Si capisce che se la regione ammissibile è l’insieme vuoto – il che accade quando i vincoli sono incompatibili – allora il problema è inconsistente, vale a dire che non ha soluzioni.

Leggi anche :

Shopping? questione di ottimizzazione!

(550)