GLPK

Présentation

Il existe plusieurs logiciels de résolution de problèmes de programmation linéaire et de programmation en nombres entiers. Parmi les produits commerciaux on peut citer notamment CPLEX. Dans le monde des logiciels libres, GLPK est un des outils les plus performants.

GLPK (GNU Linear Programming Kit) est distribué sous GNU GPL. C'est un ensemble de routines écrites en C et organisées sous forme d'une bibliothèque. Il comprend également un optimiseur autonome, glpsol. La documentation du GLPK (format ps) se trouve ici.

Installation locale

répertoirefichier
~balev/binglpsol
~balev/liblibglpk.a
~balev/includeglpk.h

glpsol

Pour lancer glpsol, soit spécifiez son chemin absolu ~balev/bin/glpsol, soit ajoutez ~balev/bin dans votre PATH. Commencez par glpsol --help.

glpsol supporte plusieurs formats de fichiers. Le plus simple est le format LP. Voici le problème du chocolatier en format LP.

\ le problème du chocolatier en format LP

Maximize
     profit: 20 Extra + 30 Sublime
Subject To
      cacao:    Extra + 3 Sublime <= 18
  noisettes:    Extra +   Sublime <=  8
       lait:  2 Extra +   Sublime <= 14
Bounds
\ cette section est facultative, les variables sont non-négatives par défaut
  Extra   >= 0
  Sublime >= 0
End

Pour plus d'informations sur glpsol et les formats des fichiers, consultez la doc.

Exercice

Résoudre le problème du chocolatier en utilisant glpsol. Récupérer les résultats et les comparer avec les résultats de la résolution graphique. Idem pour le problème de 4 variables vu en cours.

La bibliothèque glpk

Le programme choco.c est un exemple d'utilisation de la bibliothèque sur le problème du chocolatier. Pour compiler ce programme, il faut spécifier les chemins correspondants de la bibliothèque et des fichiers entête. Ce Makefile devrait marcher pour l'installation locale.

Exercice

Compiler et exécuter le programme. Lire et comprendre le code á l'aide de la doc.

Une application

Le problème

Une compagnie possède plusieurs magasins et entrepôts dans une région métropolitaine. Elle souhaite réduire ses frais d'opération en optimisant son système de distribution de fret entre ses entrepôts où sont stockés ses produits et ses magasins où ils sont vendus au consommateur. Les deux tableaux suivants présentent l'offre et la demande (tonnes de fret par mois) des entrepôts et magasins respectivement.

MagasinDemande
A340
B550
C110
D400
E200
EntrepôtOffre
X1030
Y320
Z250

Le total de l'offre et de la demande est de 1600 tonnes de fret par mois. Le plan suivant montre la localisation des magasins et des entrepôts ainsi que les distances les séparant (en km). Le coût de transport est de 1 € par tonne-km.

Exercice 1

Modéliser le problème ci-dessus sous forme d'un problème de programmation linéaire. Résoudre le problème à l'aide de glpsol. Répondre aux questions suivantes :

Exercice 2

En utilisant la bibliothèque glpk, résoudre le problème dans le cas général. Ecrire un programme qui prend en entrée un fichier en format

m n

a1 ... am 
b1 ... bn 

c11 ... c1n
... ... ...
cm1 ... cmn

et qui fournit en sortie un fichier en format

z

x11 ... x1n
... ... ...
xm1 ... xmn

Le fichier transport.c contient une fonction permettant de lire le fichier de données et de construire le modèle.

Le fichier n3700.dat contient un exemple plus « serieux » à tester (50 entrepôts et 100 magasins). Le coût minimal est 156733.