Programmazione lineare

Esiste una categoria di problemi di matematica che rientrano nella Linear Programming (LP) o anche programmi interi misti (MIPS). In questi problemi l'obiettivo è di massimizzare o minimizzare una risorsa (funzione obiettivo), che è soggetta a dei vincoli.

Con queste tecniche si possono risolvere problemi come quello del commesso viaggiatore, il SUDOKU, tecniche bancarie etc.

Molti di questi problemi possono risolversi sia graficamente che con strumenti di calcolo usando, nel caso LP, il metodo del simplex (vedi Wikipedia), del punto intermedio (primal-dual interior point); mentre nel caso MIPS tecniche come "Branch and bound".

Spesso un problema di massimizzazione è anche affrontabile come una minimizzazione al contrario.

La tecnica grafica, che deve essere altrettanto dominata, va bene se il problema ha poche dimensioni in gioco; appena il numero di dimensioni diventano moltissime, serve uno strumento automatico che risolvi il problema.

Molti di questi problemi sono isomorfi, nel senso che capito come si risolve uno di essi, tutti gli altri problemi, anche se con descrizione diversa, possono essere ricondotti ad una tale tecnica.

Un sito proposto per gli approfondimenti è http://www.sce.carleton.ca/faculty/chinneck/StudentOR.html


Esempio
Supponiamo che la Fargo è una società che produce barattoli di pittura bianca, gialla, nera e rossa. Per
fare queste pitture la Fargo usa tre materiali grezzi: 40 litri di olio, 25 litri di solvente e 20 litri di pigmenti.

Per fare il bianco si spendono 12 euro, con 0.8 litri di pigmento, 0.4 di solvente e 0.5 di olio.
Per fare il giallo si spendono 8 euro, con 0.5 litri di pigmento, 0.2 di solvente e 0.7 di olio.
Per fare il nero si spendono 9 euro, con 0.2 litri di pigmento, 0.5 litri di solvente, 0.6 di olio.
Per fare il rosso si spendono 11 euro, con 0.3 litri di pigmento, 0.6 litri di solvente e 0.4 litri di olio.

L'obiettivo è di massimizzare il profitto della Fargo.

Si possono usare molti strumenti: alcuni professionali (LINDO etc) ed altri open source (GNUWin32 con GLPSOL). Noi useremo GNUWin32 nel seguito per l'esempio didattico (http://www.gnu.org/software/glpk).

Installiamo GNUWin32 e inseriamo nel PATH di windows il percorso fino alla directory bin.

Il primo passo è formalizzare il problema. Esistono molti formati per farlo (GMPL, LP etc).

Nel seguito useremo il formato più intuitivo LP per la formalizzazione algebrica, poi successivamente quello GMPL.

Scriviamo con Notepad un file Fargo.txt del tipo:

\\ Problem Fargo.txt - LP format

Maximize
    obj: 12 x1 + 8 x2 + 9 x3 + 11 x4
   
Subject to
    c1:    .8 x1 + .5 x2 + .2 x3 + .3 x4 <= 20
    c2:    .4 x1 + .2 x2 + .5 x3 + .6 x4 <= 25
    c3:    .5 x1 + .7 x2 + .6 x3 + .4 x4 <= 40
End   
   
Da DOS sotto Windows (comando cmd) ci posizioniamo nella directory del file Fargo.txt.

Proviamo prima l'help per vedere se l'installazione funziona:  glpsol --help

Adesso dobbiamo istruire GLPSOL che abbiamo un file in formato LP:
glpsol --cpxlp fargo.txt --output fargo.out

e otterrete la soluzione a video e sul file di output fargo.out. Se c'è la scritta OPTIMAL SOLUTIONS FOUND, significa che ha trovato anche la soluzione ottimale.

L'output si presenta come segue
Problem:   
Rows:       3
Columns:    4
Non-zeros:  12
Status:     OPTIMAL
Objective:  obj = 553.7037037 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 c1           NU            20                          20       9.25926
     2 c2           NU            25                          25        12.963
     3 c3           NU            40                          40       1.11111

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                    -1.14815
     2 x2           B        23.4568             0              
     3 x3           B        37.6543             0              
     4 x4           B        2.46914             0              

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 1.48e-015 on row 2
        max.rel.err. = 5.68e-017 on row 2
        High quality

KKT.PB: max.abs.err. = 0.00e+000 on row 0
        max.rel.err. = 0.00e+000 on row 0
        High quality

KKT.DE: max.abs.err. = 8.68e-016 on column 4
        max.rel.err. = 7.24e-017 on column 4
        High quality

KKT.DB: max.abs.err. = 0.00e+000 on row 0
        max.rel.err. = 0.00e+000 on row 0
        High quality

End of output


Potreste usare anche le opzioni:
glpsol --cpxlp fargo.txt --output fargo.out --bound fargo.bnd

In questo modo otterrete anche un file di spiegazione. Il vantaggio di GLPK è che è open source e fornisce non solo il tool GLPSOL per la risoluzione interattiva di problemi, ma anche API per linguaggio C/C++.

In formato GMPL occorre scrivere prima il file modello fargo.gmpl:

# FARGO’S PRODUCTION PLANNING MODEL
# MODEL file
set R; /* resources */
set P; /* paint products */
param b{r in R}; /* on-hand levels of paint resources (in liters) */
param c{p in P}; /* profit contribution (per liter of paint) */
param a{p in P, r in R}; /* amount of resource consumed from producing paint */
var x{p in P} >= 0; /* amount of paint p to be produced */
s.t. rc{r in R}: sum{p in P} a[p,r] * x[p] <= b[r];
/* resource capacity */
maximize profit: sum{p in P} c[p] * x[p];
/* total profit (dollars) */
end;

poi va scritto il file dati fargo.data:

data;
set R := Pigment Solvent Oil;
set P := PaintA PaintB PaintC PaintD;
param : b :=
Pigment 20 /* liters */
Solvent 25 /* liters */
Oil 40 /* liters */ ;
param : c :=
PaintA 12 /* euros */
PaintB 8 /* euros */
PaintC 9 /* euros */
PaintD 11 /* euros */ ;
param a : PaintA PaintB PaintC PaintD :=
Pigment 0.8 0.5 0.2 0.3
Solvent 0.4 0.2 0.5 0.6
Oil 0.5 0.7 0.6 0.4 ;
end;

I comandi dovranno usare questa volta le opzioni --model e --data

Per una introduzione teorica dei problemi LP vi segnalo il pdf "Linear Programming
A Concise Introduction - Thomas S. Ferguson" che potrete scaricare da internet.

Alla prox