Outil pour la programmation linéaire

Je vous présente l'outil GLPK qui permet de résoudre des instances de la programmation linéaire. L'algorithme du simplexe est implémenté (avec des optimisations...). Sous Linux, il est sans doute installé ou alors vous pouvez l'installer en 2 clics sur la plupart des distributions. Sous Windows, l'installation est manuelle : http://winglpk.sourceforge.net/.

Définition d'un programme linéaire

Vous créez un fichier qui décrit votre programme. Par exemple vous créez le fichier chocolatier.pl :


\Problem name: chocolatier.lp
Maximize
     obj: x + 6 y + 13 z
Subject To
  c1: x <= 200
  c2: y <= 300
  c3: x + y + z <= 400
  c4: y + 3 z <= 600
Bounds
   0 <= x <= +Inf
   0 <= y <= +Inf
   0 <= z <= +Inf
End

Résolution

Vous lancez le programme dans une console avec glpsol --cpxlp chocolatier.lp. On obtient :


GLPSOL: GLPK LP/MIP Solver, v4.48
Parameter(s) specified in the command line:
 --cpxlp chocolatier.lp
Reading problem data from `chocolatier.lp'...
4 rows, 3 columns, 7 non-zeros
13 lines were read
GLPK Simplex Optimizer, v4.48
4 rows, 3 columns, 7 non-zeros
Preprocessing...
2 rows, 3 columns, 5 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  3.000e+00  ratio =  3.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 2
      0: obj =   4.000000000e+02  infeas =  2.000e+02 (0)
*     1: obj =   2.000000000e+02  infeas =  0.000e+00 (0)
*     4: obj =   3.100000000e+03  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (53084 bytes)

Le profit maximum du chocolatier est de 3100 (4: obj = 3.100000000e+03).