Christelle CAILLOUET
([email protected])
Aide à la décision
Utilisation d'information :
On a beaucoup de données et une puissance de calcul énorme.
Comment les utiliser pour obtenir l'aide à la décision voulue?
1. Réfléchir rigoureusement aux problèmes d’optimisation :
Qu'est-ce qu'on veut faire? Qu'est-ce qui nous empêche de le faire?
Quelles réalités influencent ou limitent nos actions?
Autrement, il s'agit de la bonne modélisation.
2. Utiliser le logiciel disponible :
modélisation efficace
utilisation intelligente du logiciel
Ces deux aspects sont inséparables.
2
Aide à la décision
Dans les entreprises où on hésite à utiliser les
méthodes ou outils d'optimisation, c'est souvent à
cause de :
un manque de temps (pour formuler un modèle, pour
attendre qu'un logiciel résolve le modèle, pour modifier,
affiner, et résoudre le modèle, etc.)
un manque d'argent (pour la main d’œuvre nécessaire
à ce qui est dit au point précédent, pour payer un
logiciel, pour payer des consultants, etc.)
C'est pour les situations dans lesquelles on prend les
décisions stratégiques (à long terme) où ces raisons
sont moins compréhensibles.
3
Outils et logiciels pour
l’optimisation
Utiliser l’outil informatique pour prendre les
meilleures décisions.
Un logiciel d’optimisation est composé de :
un solveur : le moteur qui fait l'optimisation
une langue de modélisation : l'interface qui nous
permet de communiquer le modèle au solveur
un environnement de développement : des éditeurs
et autres logiciels qui nous permettent de créer le
modèle que le solveur va lire.
4
Langage de modélisation
La langue est composée du vocabulaire, de la syntaxe,
etc., qui définissent un modèle pour le solveur, et qui
donnent au solveur les commandes de résoudre le
modèle et de sortir des données.
Important: Il s'agit toujours d'une langue formelle. Le
solveur comprend exactement ce que vous lui
communiquez et non pas ce que vous voulez
communiquer!
5
Environnement de développement
Aide l'utilisateur aux activités suivantes :
écrire un modèle correctement dans la langue associée
utiliser la bonne syntaxe
trouver et corriger des erreurs
lancer le solveur
sortir et analyser les résultats, etc.
6
Solveur
C'est le module qui fait le calcul mathématique.
Nous allons étudier certaines méthodes qu'emploient
les solveurs :
Programmation linéaire,
Optimisation de flots des réseaux,
Algorithmes de plus courts chemins,
Problème du voyageur de commerce,
etc.
7
Outils et logiciels pour
l’optimisation
Logiciels commerciaux :
Spécifiques à un secteur d’activité (transport - TMS, livraison
– tournées, planning, emploi du temps, etc.)
Le solveur est lui-même commercial ou l’algorithme
implémenté est opaque.
La langue de modélisation est spécifique au logiciel.
L’environnement de développement est ergonomique pour
une utilisation la plus large possible.
Les logiciels ont souvent des coûts de licence exorbitants et
pour rentabiliser leur exploitation, il faut avoir un nombre
important de données à gérer.
8
Outils et logiciels pour
l’optimisation
Dans cette ressource :
Environnement de développement : Eclipse ou IntelliJ
Langage de modélisation : Java
Solveur : IBM CPLEX
https://www.ibm.com/fr-fr/products/ilog-cplex-
optimization-studio
disponible gratuitement pour les académiques
9
C. Caillouet M213 - POO 10
Eléments d'un modèle
La modélisation par la programmation mathématique
exige de bien préciser :
les décisions qu'on peut prendre;
les limites sur ces décisions, et les relations entre ces décisions
et leurs limites;
notre objectif;
les données qu'il nous faut avoir pour pouvoir prendre les
meilleures décisions possibles.
La connaissance de ces éléments est indispensable pour la
gestion efficace d'une entreprise. En effet, posséder des
données ne nous aidera pas si on ignore quelles données
sont importantes et comment les utiliser !
11
1er travail :
avoir une modélisation efficace
Formulations correctes et précises :
Il faut que la formulation intègre toutes les facettes
importantes du problème, sans contenir trop de détails.
Formulations raisonnables :
Il faut que la formulation comprenne toutes les facettes
importantes du problème, sans contenir trop de détails.
Formulations alternatives :
Il faut que la formulation aide les solveurs à résoudre le
problème aussi bien que possible.
12
Questions utiles pour définir un
modèle pertinent et correct
Quel est notre objectif à atteindre ?
Quelles sont les décisions que l'on peut prendre ?
Qu'est-ce qu'on peut/doit modifier ou changer ?
Quelles sont les données nécessaires pour prendre et
évaluer nos décisions?
Quelles sont les contraintes imposant des limites sur
les décisions possibles?
13
Eléments nécessaires à un
programme mathématique
Données
Variables
Objectif
Contraintes
14
C. Caillouet M213 - POO 15
La Programmation Linéaire
§ Problème d’optimisation consistant à :
n maximiser (ou minimiser) une fonction objectif
linéaire
n de n variables de décision
n soumises à un ensemble de contraintes exprimées
sous forme d’équations ou d’inéquations linéaires
§ La terminologie est due à George B. Dantzig,
inventeur de l’algorithme du simplexe (1947)
16
Mise en forme Mathématique
n Définir les variables de décision
n ensemble des variables qui régissent la situation à modéliser
n variables réelles, entières, binaires
n Préciser la fonction objectif
n fonction mathématique composée des variables de décision qui
représente le modèle physique modélisé
n fonction linéaire
n Préciser les contraintes du problème
n ensemble des paramètres qui limitent le modèle réalisable
n équations ou inéquations composées des variables de décision
n Préciser les paramètres du modèle
n constantes associées aux contraintes et à la fonction objective
17
Attention à :
• Donner une définition précise des variables en vérifiant
qu’elles sont positives (unités des variables, période
d’observation,…)
• Vérifier l’homogénéité des contraintes linéaires (paramètre
de même unité)
• Préciser le type d ’optimisation recherchée
18
Formulation mathématique
n Fonction Objectif
n Maximiser ou minimiser z = c1x1 + c2x2 + c3x3 + … + cnxn
n Contraintes
n a11x1 + a12x2 + a13x3 + … + a1nxn (£, =, ³) b1
n a21x1 + a22x2 + a23x3 + … + a2nxn (£, =, ³) b2
n am1x1 + am2x2 + am3x3 + … + amnxn (£, =, ³) bm
n Contraintes de non-négativité
n xj ³ 0 ; j = 1, 2, 3, … n
n avec
n xj variables de décision (inconnues)
n aij, bi, cj paramètres du programme linéaire
19
Classification des contraintes
Contraintes de capacités
Contraintes de temps
Contraintes d’approvisionnement
Contraintes de stockage
Contraintes de marché
Contraintes de sous-traitance
20
Terminologie de la solution
n Solution réalisable
n Solution où toutes les contraintes du modèle sont
satisfaites
n Zone de solution
n Ensemble de toutes les solutions réalisables
n Solution optimale
n Solution réalisable où la fonction objectif atteint la
meilleure valeur, maximum ou minimum
n Plusieurs solutions optimales possibles
21
Terminologie du problème
n Problème irréalisable
n s'il n'admet pas de solutions réalisables
n Problème non borné
n si aucune des solutions réalisables n'est optimale
nProblème sous forme standard (ou canonique)
Max (c1x1 + c2x2 + c3x3 + … + cnxn)
ai1x1 + ai2x2 + ai3x3 + … + ainxn £ bi; i = 1, 2, 3, … m
xj ³ 0 ; j = 1, 2, 3, … n
Par quelques transformations simples tout programme
linéaire peut se ramener à un programme sous forme
canonique.
22
Transformation d ’un problème
Cas d ’une variable négative x : on pose y=-x
Cas d ’une variable de signe quelconque x : on introduit
deux variables positives x1 et x2 en posant x=x1-x2
Cas d ’une recherche de minimum : On remarque que
Min(Z)= -Max(-Z)
Cas d ’une contrainte de type ³ on prend l ’opposé de
l ’inégalité et on obtient une contrainte linéaire de type £
23
Exemple
MAX: 350X1 + 300X2
T.Q.: 1X1 + 1X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0
X2 >= 0
24
Solution Réalisable
Posons X2 = 0
1ère contrainte : 1X1 <= 200
2è contrainte : 9X1 <=1566 ou X1 <=174
3è contrainte : 12X1 <= 2880 ou X1 <= 240
Si X2=0, la valeur maximale de X1 est 174 et la
valeur de l'objective est:
(350 * 174) + (300 * 0) = 60 900
C’est une solution possible mais est-elle optimale?
Non!
25
Résolution problème PL: approche graphique
n Les contraintes d'un programme linéaire définissent une
zone de solution.
n Le meilleur point dans la zone de solution correspond à la
solution optimale.
n Pour des problèmes à 2 variables, il est facile de tracer la
zone de solution et de trouver la solution optimale
graphiquement.
26
Contraintes linéaires à deux
variables
Une contrainte linéaire à deux variables est de l ’une de ces
cinq formes :
a1x1+a2x2=b Dans ce cas, les solutions sont les points d ’une
droite du plan
a1x1+a2x2£b ou ³b Dans ce cas, les solutions sont les points
d ’un demi plan limité par la droite (droite comprise)
a1x1+a2x2>b ou <b Dans ce cas, les solutions sont les points
d ’un demi plan limité par la droite (droite exclue)
27
La fonction objectif
La fonction économique a pour forme Z= c1x1+c2x2
Il faut la rendre maximum.
Les droites Dk d ’équation c1x1+c2x2=k s ’appellent droites
d ’iso-profit. Elles sont parallèles entre-elles.
28
Principe de la résolution graphique
Etape 1 : On représente graphiquement toutes les contraintes.
Etape 2 : La zone du plan qui respecte les contraintes
correspond à un polygone fermé appelé polygone des solutions
réalisables (ou zone de solution). Si ce domaine est vide le
problème est impossible.
Etape 3 : Parmi toutes les droites d ’iso-profit, on recherche
celle qui donne le profit maximum (celle qui est la plus à droite
en restant dans le polygone des solutions réalisables).
29
Exemple
MAX: 350X1 + 300X2
T.Q.: 1X1 + 1X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0
X2 >= 0
30
X2 Tracé de la première contrainte
250
(0, 200)
200
X1 + X2 = 200
150
100
50
(200, 0)
0
0 50 100 150 200 250 X1
31
X2 Tracé de la deuxième contrainte
(0, 261)
250
200 9X1 + 6X2 = 1566
150
100
50
(174, 0)
0
0 50 100 150 200 250 X1
32
X2 Tracé de la troisième contrainte
250
(0, 180)
200
150
12X1 + 16X2 = 2880
100
Zone de solution
50
(240, 0)
0
0 50 100 150 200 250 X1
33
Tracé d’une droite de la fonction objectif
X2
250
200
(0, 116.67) Fonction objectif
150
350X1 + 300X2 = 35000
100
50 (100, 0)
0
0 50 100 150 200 250 X1
34
Un deuxième tracé de la fonction objectif
X2
250
(0, 175) Fonction objectif
200
350X1 + 300X2 = 35000
Fonction objectif
150
350X1 + 300X2 = 52500
100
(150, 0)
50
0
0 50 100 150 200 250 X1
35
X2 Tracé de la solution optimale
250
Fonction objectif
200
350X1 + 300X2 = 35000
150
Solution optimale
100
Fonction objectif
350X1 + 300X2 = 52500
50
0
0 50 100 150 200 250 X1
36
Calcul de la solution optimale
La solution optimale se trouve à l’intersection des
contraintes :
X1 + X2 = 200 (1)
9X1 + 6X2 = 1566 (2)
De (1) nous avons:
X2 = 200 -X1 (3)
En substituant (3) pour X2 dans (2) nous avons:
9X1 + 6 (200 -X1) = 1566
ce qui fait X1 = 122
37
Calcul de la solution optimale
La solution optimale est :
X1 = 122
X2 = 200-X1=78
Objective = (350*122) + (300*78) = 66 100
38
Solutions obtenues
Dans le cas où une solution existe deux possibilités peuvent se
présenter :
On a une solution unique. Il s ’agit d ’un sommet du polygone
des solutions réalisables.
On a une infinité de solutions. Il s ’agit de tout un coté du
polygone des solutions réalisables. Ce coté est parallèle aux
droites d ’iso-profit.
39
C. Caillouet M213 - POO 40
IBM ILOG CPLEX Optimization
Studio 20.1
Moyen le plus rapide de créer des modèles d'optimisation
efficaces et des applications de pointe permettant de traiter
les multiples problèmes de planification et
d'ordonnancement.
Contient :
environnement de développement intégré,
langage de modélisation descriptive,
outils et solveurs avancés, traitant les problèmes de
programmation mathématique et les problèmes de
programmation par contraintes.
Il prend en charge le processus complet de développement
et de résolution des modèles.
C. Caillouet M213 - POO 41
Algorithmes
Programmation linéaire
Simplexe primal
Simplexe dual
Simplexe pour les problèmes de flot
Point intérieur
Programmation quadratique
Simplexe primal
Simplexe dual
Point intérieur
Programmation à contraintes quadratiques
Point intérieur
C. Caillouet M213 - POO 42
Composantes de Cplex
S’utilise sous différentes manières :
Mode intéractif
Cplex Callable library (bilbiothèque en langage C) :
utilise les matrices pour représenter un problème
Ilog Concert Technology : utilise les objets et les
méthodes pour représenter un problème avec les
langages de programmation Python, C++, Java…
Avec un langage propre de modélisation tel que OPL,
MPL, AMPL…
C. Caillouet M213 - POO 43
IBM ILOG CPLEX Optimization
Studio 20.1
Disponible pour toutes les plateformes : Windows,
MacOS, Linux
A l’IUT : exécutable Windows disponible dans
SupportCours/BUT3
Pour vos machines personnelles : lien vers les
exécutables depuis le cours Moodle
C. Caillouet M213 - POO 44
Utilisation de l’API Java
Installation dans
C:\Program Files\IBM\ILOG\CPLEX_Studio201
Répertoire lib : cplex.jar
Contient l’ensemble des classes nécessaires à la
construction d’un programme linéaire
Répertoire bin : solveur cplex.exe
Solveur qui est appelé pour la résolution
C. Caillouet M213 - POO 45
Dans Eclipse
Créer un Java Project contenant vos classes
Mettre à jour le build path : inclure la librairie pour
utiliser les
classes
C. Caillouet M213 - POO 46
Dans la classe
Pour utiliser les interfaces Java Ilog Cplex, vous devez
importer les 2 packages :
import ilog.concert.*;
import ilog.cplex.*;
https://www.ibm.com/docs/en/icos/22.1.1?to
pic=optimizers-cplex-java-reference-manual
Création d’une instance d’un objet Cplex :
IloCplex model = new IloCplex();
Type IloCplex qui implémente l’interface
IloMPModeler et donc IloModeler.
C. Caillouet M213 - POO 47
Les variables
Elles sont de type :
IloNumVar : variables continues
IloIntVar : variables entières (qui hérite de IloNumVar)
Chacun de ces objets doit ensuite être intégré au modèle
avec ces informations : (borne inf, borne sup, nom)
Continue
Entière
Booléenne
C. Caillouet M213 - POO 48
Les expressions
C’est une combinaison de variables : somme,
différence, multiplication par des constantes, …
Une expression est un objet de type IloNumExpr, ou
IloLinearNumExpr
Pour chaque opération (+, -, *, /, …), il existe une
fonction ui s’applique sur l’objet IloCplex.
C. Caillouet M213 - POO 49
Les expressions
Exemple
pour écrire 𝑥 + 2𝑦
Pour exprimer une
expression
linéaire, on peut
utiliser le produit
scalaire
C. Caillouet M213 - POO 50
Les contraintes
Ce sont des objets de type IloRange
Une contrainte se définit à partir :
D’une expression
D’une borne inférieure et/ou supérieure ou une égalité
Pour ajouter une contrainte, on applique les fonctions au
modèle :
C. Caillouet M213 - POO 51
La résolution
La fonction objectif :
C’est une expression
On spécifie dans le modèle si on la maximise ou
minimise :
model.addMaximize(xp);
model.addMinimize(xp);
L’appel au solver :
model.solve();
C. Caillouet M213 - POO 52
A l’exécution
Ouvrir les configurations
Ajouter le chemin
jusqu’à cplex.exe du
répertoire bin de Cplex
dans les propriétés de la
VM avec l’option
-Djava.library.path
C. Caillouet M213 - POO 53
Le résultat
Récupérer la valeur de l’objectif :
model.getObjValue();
Récupérer les valeurs des variables :
model.getValue(v1);
model.getValues(var);
Obtenir le statut : model.getStatus();
Fermer le solveur : model.end();
C. Caillouet M213 - POO 54
