CHAPITRE II
programme linéaire :
méthodologie
Méthodologie de la RO
(programmation mathématique)
Identifier le problème et
Valider le modèle
collecter les données
Préparer un cahier de charge pour le
Formuler le modèle
développement d’un système d’aide à la
mathématique
décision
Implémentation du système
Résoudre le modèle
d’aide à la décision
2
Identification du problème et
collecte des données
Les problèmes réels sont flous, non clairs
L’équipe de RO est appelée à bien identifier le problème :
L’objectif, les contraintes, le temps limité pour la prise
de décision, etc.
La définition du problème est une étape cruciale
puisqu’elle affecte les décisions à prendre : on ne peut
pas avoir des « bonnes » réponses suite à un problème
« mal défini »
3
Identification du problème et
collecte des données
Objectif : il faut bien choisir l’objectif approprié
Données : la collecte des données est une phase à
ne pas négliger
Elle prend beaucoup de temps (pas de données
disponibles ou les données disponibles ne sont pas
fiables).
4
Étape 2 : formulation
mathématique du problème
Après avoir bien défini le problème, il
faut le formuler sous une forme facilitant
l’étape de l’analyse.
Ainsi, l’équipe de RO est appelée à le
formuler en modèle mathématique.
5
Étape 2 : formulation
mathématique du problème
Les modèles mathématiques jouent un rôle
important dans un système d’aide à la
décision :
Il s’agit d’un système d’équations et des
expressions mathématiques reliant les
différentes variables et les différents
paramètres permettant de décrire le
problème.
6
Étape 2 : formulation
mathématique du problème
Soient n décisions liées et quantifiables à prendre ; elles sont présentées
par (x1, x2, . . . , xn) : nommées les variables de décisions dont les valeurs
sont à déterminer.
La mesure de la performance appropriée (exemple profit) est exprimée
par une fonction mathématique en fonction de ces variables de
décisions (exemple, P= 3x1 + 2x2 + …+ 5xn) : cette fonction est appelée
fonction objectif (fonction économique).
Des restrictions sur les valeurs des variables de décisions sont exprimés
mathématiquement, particulièrement par des inégalités (exemple,
x1+3x1x2+ 2x2≤10) : appelées des contraintes.
Les constantes (coefficients et les valeurs du côté droite: RHS (Right
Hand Side) dans les contraintes et la fonction objectif sont appelés des
paramètres.
7
Étape 2 : formulation
mathématique du problème
Le modèle mathématique correspondant à un
problème de décision, consiste à déterminer les
variables de décisions qui maximisent une fonction
objectif tout en respectant des contraintes : ce
sont les modèles utilisées en Recherche
Opérationnelle.
8
Étape 2 : formulation
mathématique du problème
La détermination des paramètres n’est pas si
évidente !
Ces paramètres seront estimés lors de la phase
de collecte des données
Ainsi, c’est important d’étudier le comportement
du système si les paramètres varient : on parle
d’analyse de sensibilité.
9
Étape 2 : formulation
mathématique du problème
Une des formulations mathématiques :
programmation linéaire
Toutes les équations sont linéaires
Avantages :
Possibilité de l’obtention de la solution optimale.
Possibilité d’étudier la relation cause / effet :
comment un changement de paramètre peut-il
influer sur la solution optimale ?
10
Programmation Linéaire : Exemple*
Une entreprise fabrique deux types de jouets en bois : des
soldats et des trains
Un soldat est vendu pour 27 D et utilise l’équivalent de 10 D de
matière première. Chaque soldat fabriqué coûte 14 D (main
d’œuvre et les frais généraux).
Un train peut être vendu pour 21 D et utilise 9 D de matière
première. Chaque train coûte 10 D ( MO et les frais généraux).
Chaque semaine l’entreprise peut obtenir toute la matière
première nécessaire, cependant, seulement 80 heures de
menuiserie et 100 heures de finition peuvent être disponibles.
La demande pour les trains est illimitée, mais au plus 40 soldats
sont vendus.
*Giapetto’s Woodcarving (Operations Research Applications and Algorithms) 11
Programmation Linéaire : Exemple
La fabrication de ces deux jouets nécessite deux types
d’opération spécialisées : menuiserie et finition
Prix de vente Matière première Coût Menuiserie Finition
Soldat 27 D 10 D 14 D 1h 2h
Train 21 D 9D 10 D 1h 1h
12
Programmation Linéaire : Exemple
La compagnie désire maximiser son profit (revenus-
coûts) hebdomadaire
On veut formuler un modèle mathématique de la
situation de la compagnie, qui peut être utilisé pour
maximiser le profit hebdomadaire
En développant le modèle, on va explorer les
caractéristiques communes à tous les programmes
linéaires (PL)
13
Forme du Programme Linéaire
(PL) est un problème mathématique de la forme :
Max ct x
s.c Ax≤b
x≥0
″Max″ signifie maximiser, c ∊ ℜn, b ∊ ℜm
A est une matrice réelle (m, n).
La fonction à maximiser (ct x) : fonction objectif ou fonction
économique.
Les inégalités définies par le système linéaire (A x ≤ b) : les
contraintes du problèmes.
Les n composantes du vecteur x : les variables de décision.
Une solution réalisable x* est optimale si la valeur de ct x* est la
meilleure des valeurs de ct x pour tous les vecteurs réalisables. 14
Variables de décisions
Dans un PL, les variables de décisions doivent
complètement décrire les décisions à prendre
La compagnie doit déterminer le nombre de
soldats et de trains à fabriquer par semaine
On définit alors :
X1 = nombre de soldats fabriqués par semaine,
X2 = ˶ trains ˶ ˶
15
Fonction objectif
Dans n’importe quel programme linéaire :
Le responsable de décision veut :
maximiser (en général, le revenue ou profit) ou
minimiser (en général le coût)
Une fonction des variables de décisions
Cette fonction est appelée « fonction objectif »
« fonction économique»
16
Fonction objectif
Profit hebdomadaire
= contribution des soldats au profit hebd. +
contribution des trains au profit hebd.
= (contr. Au profit/soldat) x1 + contr. au profit/train) x2
Contribution au profit/soldat = 27-10-14 = 3 D
Contribution au profit/train = 21-9-10 = 2 D
17
Fonction objectif
Profit hebdomadaire
Z(x)= 3x1 + 2x2
où x = (x1, x2)
L’objectif de la compagnie consiste à choisir
les quantités x1 et x2 qui maximisent la
fonction 3x1 + 2x2
Max Z(x) = 3x1 + 2x2 (1)
18
Contraintes
Si la compagnie est libre de choisir n’importe
quelles valeurs pour x1 et x2, elle peut avoir un
très large profit en choisissant des grandes
valeurs de x1 et x2. Malheureusement, ces
valeurs sont limitées par certaines contraintes.
19
Contraintes
Chaque semaine, pas plus que 80 heures
de menuiserie peuvent être effectuées :
Contraintes de ressources
x1 + x2 ≤ 80 (2)
20
Contraintes
Chaque semaine, pas plus que 100
heures de finition peuvent être effectuées :
2x1 + x2 ≤ 100 (3)
2, 1: coefficients technologiques (LHS : Left-Hand Side)
100: second membre (RHS : Right-Hand Side)
21
Contraintes
Contrainte dû à la limitation de la demande, au
plus 40 soldats doivent être produits par
semaine :
Contraintes d’environnement
x1 ≤ 40 (4)
22
Contraintes
Contraintes de signes
Pour compléter la formulation d’un PL, on doit
répondre à la question suivante :
Est-ce que les variables de décision peuvent
prendre seulement des valeurs non-négatives (≥ 0),
ou
Est-ce qu’elles n’ont pas de restriction de signe ?
Exemple: il est clair que x1 et x2 ≥ 0
23
Le Programme Linéaire
En combinant:
La fonction objectif avec
Les contraintes (2), (3) et (4) et les restrictions de signe
On obtient le modèle d’optimisation ou le programme
linéaire suivant :
Max z 3 x1 2 x2
s.c. x1 x2 80
2 x1 x2 100
(PL)
x1 40
x1 0 , x 2 0
“ S.c. ” veut dire que x1 et x2 doivent répondre à toutes les contraintes
24
Étape 3 : résolution du
problème
Après avoir développé un modèle
mathématique décrivant le problème, l’équipe
de RO est appelée à développer une procédure
pour trouver des solutions de ce modèle.
Il semble que c’est la phase la plus importante,
or ce n’est pas le cas !
25
Étape 3 : résolution du
problème
Il s’agit d’une étape simple, dans laquelle on
applique des algorithmes standards (des
logiciels et des outils existants déjà (CPLEX,
LINGO, LINDO, Solveur d’Excel etc.)).
26
Étape 3 : résolution du
problème
La recherche d’une solution optimale peut être
dans certains cas coûteuse en termes de temps
(donc argent)
Il suffit de trouver une solution satisfaisante
On recourt à des heuristiques ou des
métaheuristiques
Le travail le plus important ce sont les étapes
suivantes plus particulièrement la post-
optimalité.
27
Étape 3 : résolution du
problème
La post-optimalité : analyse faite après
avoir trouvé la solution optimale
La solution optimale peut ne pas être la
meilleure solution dans la réalité puisque le
modèle ne reflète pas vraiment la réalité
Donc, il faut se poser la question : quand un
paramètre change, quel serait son effet sur
la solution optimale ?
28
Étape 3 : résolution du
problème
L’analyse post-optimalité comprend
l’analyse de sensibilité : il s’agit de
déterminer quels sont les paramètres
critiques (paramètres sensibles) ?
Dans un modèle mathématique, un
paramètre est sensible, si une modification
de sa valeur est accompagnée par un
changement de la solution optimale.
29
Étape 3 : résolution du
problème
L’identification des paramètres sensibles est importante : ceci
permet d’identifier les paramètres auxquels une attention
particulière est accordée afin d’éviter l’obtention des solutions
erronées.
La valeur d’un paramètre est dans la plupart du temps estimée
(ex. profit/unité). Les paramètres sensibles seront identifiés
qu’après avoir développé le modèle mathématique et l’avoir
résolu.
Ainsi, une fois identifié, on tente d’estimer plus efficacement ces
paramètres ou déterminer dans quel intervalle de valeur, il se
situe.
On cherche donc les solutions correspondantes à toute
combinaison des paramètres sensibles. 30
Étape 4 : validation du modèle
Développer un modèle mathématique est analogue au
développement d’un programme informatique.
La première version d’un programme informatique contient
souvent des erreurs (bugs). Ainsi, ce programme doit subir
beaucoup de corrections et des modifications, des
améliorations afin qu’il fournisse à la fin des résultats
logiques
C’est la même chose pour une première version d’un modèle
mathématique. Elle contient des erreurs. Certaines
modifications seront incorporées (ajout d’une équation
exprimant une relation entre variables de décisions oubliées,
paramètres mal estimés…) 31
Étape 4 : validation du modèle
Ainsi, avant d’utiliser le modèle, on le teste afin de
corriger, améliorer jusqu’à ce qu’on obtienne des
résultats logiques.
Le processus de test et d’amélioration du modèle afin
qu’on obtienne des résultats logiques : validation du
modèle.
32
Étape 5 : préparer l’application
L’étape suivante consiste à préparer la
documentation : modèle, procédure pour
l’obtention de la solution, l’analyse post-
optimale, la procédure d’implémentation
Ainsi, si le personnel change, le système peut être
utilisé régulièrement
La documentation prépare à l’implémentation
d’un outil informatique d’aide à la décision.
33
Étape 6 : implémentation
Il s’agit de concevoir un outil informatique
d’aide à la décision
Former le personnel à l’exploitation de cet
outil
Suivre la performance de l’outil (en cas de
nécessité, intégrer des modifications).
34
Conclusion
Nous avons présenté une démarche pour la
résolution d’un problème de décision en
utilisant un outil de la RO : la
programmation linéaire
Ce cours s’intéresse particulièrement à
l’étape 3:
Procédure pour la résolution du problème
Analyse post-optimalité
35
