home	accès étudiants

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

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

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.

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 :

• Quel est l'affectation du fret entre les entrepôts et les magasins de sorte que le coût de transport soit minimal ?
• Quel est le coût de transport minimum ?
• Faire un plan montrant l'intensité du trafic entre les entrepôts et les magasins.
• Si le coût de transport devrait se lever à 1,25 € par tonne-km, quel en serait l'impact sur l'affectation du trafic ?

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

où

• m est le nombre d'entrepôts ;
• n est le nombre de magasins ;
• a_i est l'offre de l'entrepôt i ;
• b_j est la demande du magasin j ;
• c_ij est le coût du transport par tonne de l'entrepôt i au magasin j ;
• z est le coût optimal de transport ;
• x_ij est le quantité transportée entre l'entrepôt i et le magasin j.

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.