Recherche opérationnelle - Programmation linéaire - Résolution de problèmes par la méthode du simplex

Jean Baptiste FAVRE

février 2010

Introduction

La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes de management du système d'information utilisables pour élaborer de meilleures décisions. Elle propose des modèles conceptuels pour analyser des situations complexes et permet aux décideurs de faire les choix les plus efficaces. (Source: Wikipedia)

Parmis ces problèmes, on trouve les problèmes dits combinatoires, en ce qu'ils comprennent un grand nombre de solutions admissibles parmi lesquelles on cherche une solution optimale ou proche de l'optimum. Exemple typique : déterminer où installer 5 centres de distribution parmi 30 sites d'implantation possibles, de sorte que les coûts de transport entre ces centres et les clients soient minimum (Source: Wikipedia)

Pour résoudre ces problèmes combinatoires, on utilise la programmation linéaire. Sous linux, ceci peut être fait à l'aide de GLPK.

Installation de GLPK sous Debian / Ubuntu 
aptitude install glpk

Exemple de problème

Ce problème est extrait du cours RCP-101: Recherche opérationnelle et techniques d'aide à la décision du CNAM

Un appareil peut être fabriqué à l'aide de 3 processus techniques de production: T1, T2 et T3.
Ces processus consomment chacun 4 ressources: E (énergie), MP (matière première), L (main-d'œuvre) et K (machine).
Les consommations par processus, les ressources disponibles et le prix de revient des pièces sont donnés dans le tableau suivant
Tableau récapitulatif des données
 EMPLKPrix de revient
T13235170
T22364160
T34145190
Capacité8664156138 
 
L'appareil sera vendu 280€.
Objectif : Trouver la quantité d'appareils à produire afin de maximiser le profit.

Définition des variables et contraintes

Variables réelles
  • x1: nombre d'appareils produits par le processus technique T1 ; x1 >= 0
  • x2: nombre d'appareils produits par le processus technique T2 ; x2 >= 0
  • x3: nombre d'appareils produits par le processus technique T3 ; x3 >= 0
Contraintes
  • Contrainte d'énergie: 3x1 + 2x2 + 4x3 <= 86
  • Contrainte de matière première: 2x1 + 3x2 + x3 <= 64
  • Contrainte de main d'œuvre: 3x1 + 6x2 + 4x3 <= 156
  • Contraintes de machines: 5x1 + 4x2 + 5x3 <= 138
Profit par processus de fabrication
  • Le processus T1 dégage : 280 - 170 = 110€
  • Le processus T2 dégage : 280 - 160 = 120€
  • Le processus T3 dégage : 280 - 190 = 90€
Fonction objectif
Π = max (110x1 + 120x2 + 90x3)

Résolution à l'aide de GLPK

Il faut tout d'abord formater les variables, contraintes et fonction objectifs afin que GLPK puisse le comprendre.

#
# Optimisation de production d'appareils à l'aide des processus T1, T2 et T3
#

/* Variables réelles */
var x1 >=0; /* nbre d'appareil à produire avec le processus T1 */
var x2 >=0; /* nbre d'appareil à produire avec le processus T2 */
var x3 >=0; /* nbre d'appareil à produire avec le processus T3 */

/* Fonction objectif */
maximize z: 110*x1 + 120*x2 + 90*x3;

/* Contraintes */
s.t. Energy : 3x1 + 2x2 + 4x3 <= 86;
s.t. RawMaterial : 2x1 + 3x2 + x3 <= 64;
s.t. Employees : 3x1 + 6x2 + 4x3 <= 156;
s.t. Machines : 5x1 + 4x2 + 5x3 <= 138;

end;
$ glpsol -m  ~/maths/glpk.mod -o  ~/maths/glpk.sol
GLPSOL: GLPK LP/MIP Solver 4.38
Reading model section from test1.mod...
19 lines were read
Generating z...
Generating Energy...
Generating RawMaterial...
Generating Employees...
Generating Machines...
Model has been successfully generated
glp_simplex: original LP has 5 rows, 3 columns, 15 non-zeros
glp_simplex: presolved LP has 4 rows, 3 columns, 12 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  6.000e+00  ratio =  6.000e+00
Problem data seem to be well scaled
Size of triangular part = 4
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     3: obj =   3.260000000e+03  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (120578 bytes)
Writing basic solution to `test1.sol'...
$ cat ~/maths/glpk.sol
Problem:    test1
Rows:       5
Columns:    3
Non-zeros:  15
Status:     OPTIMAL
Objective:  z = 3260 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B           3260                             
     2 Energy       NU            86                          86             4 
     3 RawMaterial  NU            64                          64            24 
     4 Employees    B            134                         156 
     5 Machines     NU           138                         138            10 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           B             10             0               
     2 x2           B             12             0               
     3 x3           B              8             0               

Karush-Kuhn-Tucker optimality conditions:

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

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

KKT.DE: max.abs.err = 1.42e-14 on column 1
        max.rel.err = 6.43e-17 on column 1
        High quality

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

End of output

La première ligne en gras vous indique que la solution optimale a été trouvée.

La seconde vous donne le résultat de la fonction objectif.

Enfin, le dernier bloc vous donne les valeurs de x1, x2 et x3.

Format

Ce document est disponible aux formats suivants:

À propos de Jean Baptiste FAVRE

Je suis responsable d'exploitation dans le domaine de l'hébergement. Je travaille, entre autres, sur la virtualisation et l'amélioration des performances web. De temps en temps, j'arrive à décrocher de mon clavier pour lire un bon bouquin en écoutant de la musique.

License

Creative Commons License Cette publication est publiée sous contrat Creative Common by-nc-sa

Valid XHTML 1.0 Strict |  Valid CSS |  contrat Creative Common by-nc-sa

Table des matières

  1. Introduction
  2. Exemple de problème
  3. Définition des variables et contraintes
  4. Résolution à l'aide de GLPK
  5. Format
  6. À propos ...
  7. License