La programmazione lineare

001

Scopriamo il funzionamento di un semplice ed utile programma, finalizzato alla risoluzione dei problemi di ottimizzazione, connessi alla ricerca dell’ottimo, per minimizzare e massimizzare i risultati. Ne avevamo già parlato in un articolo tempo fa, ma ora affrontiamo il tema sotto un profilo più pratico.

La programmazione lineare è quella branca della programmazione matematica che ha come scopo quello della ricerca del minimo o del massimo di una funzione lineare. La funzione deve essere descritta mediante un sistema di equazioni o disequazioni lineari. Si parla in questo caso di ottimizzazione lineare vincolata.

Benchè molte applicazioni sono basate su modelli e basi teoriche, l’applicazione della programmazione lineare trova largo impiego pratico pressochè in ogni campo. Aziende, compagnie di voli, scuole, agenzie di trasporti e laboratori utilizzano in maniera intensiva la programmazione lineare, per sfruttare al meglio le proprie risorse al minor costo possibile.

Senza addentrarci troppo nella trattazione della programmazione lineare, solitamente lo scenario pratico del suo utilizzo potrebbe essere, ad esempio, il seguente:

Una azienda decide di avviare la produzione di due prodotti differenti. I due articoli da fabbricare devono essere realizzati utilizzando due macchinari diversi. Stabiliti i tempi di lavorazione, i costi e i prezzi di vendita, fornendo inoltre alcuni vincoli da rispettare (come ad esempio il numero massimo di ore lavorative), si vuol conoscere la quantità di pezzi da produrre per ottenere il massimo guadagno (problema di massimizzazione).

Ovviamente, se il problema è semplice, ed è caratterizzato da poche variabili ed altrettanti vincoli, si potrebbe risolvere con carta e penna. Ma quando l’obiettivo finale è estremamente complicato ed è caratterizzato da numerosi interrogativi, allora occorre percorrere una strada diversa. La matematica offre diversi spunti risolutivi, tra le quali spicca l’algoritmo del simplesso.

Per chi non mastica la matematica, esistono tuttavia molti software che si occupano proprio della ottimizzazione del problema, risolvendo problemi di programmazione lineare anche molto complessi.

Uno dei software più blasonati  e semplici, nonchè gratuito ed utilizzato nelle facoltà di matematica ed ingegneria di tutto il mondo, è il GLPK (GNU Linear Programming Kit). Si può liberamente scaricare dall’indirizzo http://www.gnu.org/software/glpk/.

Passiamo adesso direttamente ad un problema pratico, che ben si adatta alla realtà di ogni giorno. Un problema del genere potrebbe benissimo attuarsi nella vita pratica di tutti. Si abbiano le seguenti ipotesi:

Dobbiamo pagare al negoziante la somma di € 1498.66. Egli (per non riempire il suo registratore di cassa di monetine o banconote, vuole ricevere da noi il NUMERO PIU’ BASSO di pezzi (sia di carta che di metallo). Dal momento che possiamo usare eventualmente fino a 5 pezzi per ogni taglio, quanti pezzi per taglio dobbiamo consegnare, per pagare la somma? E’ concesso di evitare l’utilizzo di qualche taglio.

 

Per la risoluzione del problema, dunque, è necessario fornire al computer tutti i fatti in maniera completa ed esatta. Nella fattispecie, occorre dichiarare quanto segue:

  • Ogni taglio di valuta è rappresentato rispettivamente dalle variabili m1, m2, m3, m4, m5, m6, m7 e m8 per quanto riguarda le monete metalliche, e dalle variabili b1, b2, b3, b4, b5, b6 e b7 per quanto riguarda le banconote cartacee. Ovviamente si può usare qualsiasi altro nome di variabile. Tali entità conterranno il numero di pezzi per ogni taglio, quindi se una soluzione dovesse prevedere, per la variabile b2 il valore di 4, vorrà dire che occorreranno 4 pezzi da 10 euro (vedi tabella dei tagli);
  • Come detto prima, ogni taglio dovrà essere utilizzato al massimo per 5 volte. Non si potranno quindi dare al venditore, ad esempio, 8 monete da 50 cents;
  • Il numero di monete deve essere, ovviamente, intero;
  • La variabile S (somma) è calcolata in base alla quantità di ogni taglio moltiplicato per il suo valore intriseco;
  • Infine, la funzione da minimizzare è quella che calcola, semplicemente, il numero di tutti i tagli utilizzati.

Bene, stabiliti i vincoli e le connessioni, si può scrivere il listato LP da dare in pasto al programma GLPK. Esso deve essere contenuto in un semplice file di testo, editabile anche con il blocco note. Il nostro esempio prevede che il file di testo si chiami “euro.txt”.

 

var m1 >=0,<=5,integer; /* moneta da 1 cent */
var m2 >=0,<=5,integer; /* moneta da 2 cent */
var m3 >=0,<=5,integer; /* moneta da 5 cent */
var m4 >=0,<=5,integer; /* moneta da 10 cent */
var m5 >=0,<=5,integer; /* moneta da 20 cent */
var m6 >=0,<=5,integer; /* moneta da 50 cent */
var m7 >=0,<=5,integer; /* moneta da 1 euro */
var m8 >=0,<=5,integer; /* moneta da 2 euro */
var b1 >=0,<=5,integer; /* banconota da 5 cent */
var b2 >=0,<=5,integer; /* banconota da 10 cent */
var b3 >=0,<=5,integer; /* banconota da 20 cent */
var b4 >=0,<=5,integer; /* banconota da 50 cent */
var b5 >=0,<=5,integer; /* banconota da 100 cent */
var b6 >=0,<=5,integer; /* banconota da 200 cent */
var b7 >=0,<=5,integer; /* banconota da 500 cent */
minimize QTPezzi: m1+m2+m3+m4+m5+m6+m7+m8+b1+b2+b3+b4+b5+b6+b7;
S:(m1*0.01)+(m2*0.02)+(m3*0.05)+(m4*0.10)+(m5*0.20)+(m6*0.50)+(m7*1)+(m8*2)+(b1*5)+(b2*10)+(b3*20)+(b4*50)+(b5*100)+(b6*200)+(b7*500)=1498.66;
end;
Al prompt di sistema, una volta posizionati nella cartella del programma, si digiti il seguente comando:
C:\Programmi\GnuWin32\bin> glpsol.exe -m euro.txt -o CON

Dopo qualche istante l’output a Video (CON) sarà il seguente (tralasciando le parti non interessanti):

 

INTEGER OPTIMAL SOLUTION FOUND
Time used:        0.2 secs
Memory used:      0.2 Mb (190819 bytes)
lpx_print_mip:    writing MIP problem solution to `CON’…
Problem:          euro
Rows:             2
Columns:          15 (15 integer, 0 binary)
Non-zeros:        30
Status:           INTEGER OPTIMAL
Objective:        QTPezzi = 14 (MINimum)
No.      Row name      Activity   Lower bound  Upper bound
—— ———— ————- ———— ————
1      QTPezzi                14
2      S                 1498.66       1498.66           =
No.     Column name    Activity   Lower bound  Upper bound
—— ———— ————- ———— ———–
1           m1     *           1             0           5
2           m2     *           0             0           5
3           m3     *           1             0           5
4           m4     *           1             0           5
5           m5     *           0             0           5
6           m6     *           1             0           5
7           m7     *           1             0           5
8           m8     *           1             0           5
9           b1     *           1             0           5
10          b2     *           0             0           5
11          b3     *           2             0           5
12          b4     *           1             0           5
13          b5     *           0             0           5
14          b6     *           2             0           5
15          b7     *           2             0           5

 

Questa soluzione di MINIMIZZAZIONE ha pertanto decretato il numero “minimo” di pezzi che consentono di soddisfare la somma di € 1498.66, utilizzando solo 14 pezzi, cosi ripartiti:
  • 1 moneta    da   1 cent
  • 1 moneta    da   5 cent
  • 1 moneta    da  10 cent
  • 1 moneta    da  50 cent
  • 1 moneta    da   1 euro
  • 1 moneta    da   2 euro
  • 1 banconota da   5 euro
  • 2 banconote da  20 euro
  • 1 banconota da  50 euro
  • 2 banconote da 200 euro
  • 2 banconote da 500 euro
———————————————
     TOTALE:      € 1498.66
Meno di così non si può!
Come si vede, occorre pianificare bene il problema e formalizzarlo in una notazione matematico-logica.
Questo esempio è sufficiente per comprendere il funzionamento della programmazione logica con il programma GPLK. Da questo punto si può proseguire per la realizzazione di esempi ben più complessi. Buona programmazione.
GDM

 

 

Quello che hai appena letto è un Articolo Premium reso disponibile affinché potessi valutare la qualità dei nostri contenuti!

Gli Articoli Tecnici Premium sono infatti riservati agli abbonati e vengono raccolti mensilmente nella nostra rivista digitale EOS-Book in PDF, ePub e mobi.

volantino eos-book1

Vorresti accedere a tutti gli altri Articoli Premium e fare il download degli EOS-Book?
Allora valuta la possibilità di sottoscrivere un abbonamento a partire da € 2,95!

Scopri di più

4 Comments

  1. Luigi Francesco Cerfeda 30 aprile 2013
  2. Giovanni Di Maria gio22 30 aprile 2013
  3. Piero Boccadoro Piero Boccadoro 30 aprile 2013
  4. Piero Boccadoro Piero Boccadoro 30 aprile 2013

Leave a Reply