COURS D’INITIATION A LA
RECHERCHE OPERATIONNELLE
2ème Année Licence – Département de Génie Industriel –
UNIVERSITE BATNA2
I- Introduction
1. Présentation
La recherche opérationnelle est un outil d’aide à la décision et c’est une
branche qui étudie le traitement mathématique d'un procédé, d'un
problème pour en déterminer le but et pour atteindre l'efficacité
maximale (Problème de maximisation ou de Minimisation d’une
fonction).
2. Objectif du cours
L’objectif de ce cours de Recherche opérationnelle est d’être initié aux
problèmes d’optimisation linéaire telle que l’évaluation d’une fonction
permettant de maximiser des profits ou de minimiser des dépenses,
d’une entreprise, sous des contraintes exprimées par des inéquations.
Ce cours se focalisera essentiellement sur la méthode de résolution dite
Algorithme du Simplexe et ses différentes variantes.
Nous aborderons aussi, dans ce cours, des exemples de tournées de
véhicules connues sous l’appellation du problème de voyageur de
commerce et nous expliquerons, à la fin du cours, le problème du sac-à-
dos.
3. La Modélisation
La modélisation en recherche opérationnelle sert à transformer un
énoncé d’un problème en un modèle mathématique c.a.d réécrire le
problème sous forme d’un système d’équation et d’une fonction objectif.
Le but primordial est de maximiser un profit ou de minimiser un cout. Ce
qui revient à écrire : - Min f(x, y)
- Max f(x, y)
Exemple :
Un restaurateur propose deux types de menus
Assiette 1 contient : 5 sardines, 2 merlans et 1 rouget et coute
800DA
Assiette 2 contient : 3 sardines, 3 merlans et 3 rougets et coute
1200DA
Sachant que le restaurateur dispose des quantités suivantes 30
sardines, 24 Merlans et 18 Rougets.
Donnez le modèle mathématique qui permet de maximiser le profit du
restaurateur ?
Solution :
Tout d’abord on va résumer cet énoncé dans un tableau puis on passera
à la modélisation.
1
Assiette1 Assiette 2 Contraintes
Sardine 5 3 30
Merlan 2 3 24
Rouget 1 3 18
Cout 800 DA 1200 DA
Modélisation
On pose X1 : Nombre d’assiette 1 , X2 : Nombre d’assiette 2
Notre Fonction « Objectif » devient :
Max Z = 800 X1 + 1200 X2
Sous les contraintes :
{
5 x1 + 3x2 ≤ 30
2 x1 + 3 x2 ≤ 24
x1 + 3 x2 ≤ 18
On sait résoudre ce genre de problème en utilisant la Méthode du
simplexe
Donc en résumé :
Dans la modélisation d’un problème linéaire, on doit définir :
Les variables de décision X1 , X2 …..
La fonction « objectif »
Les contraintes du problème
Exercice
Une entreprise prépare trois types de boites de fruits :
1. Une boite1 qui contient 0.45 kg de dattes, 0.67 kg d’abricots et
0.34 kg de pêches.
2. Une boite2 qui contient 0.56 kg de dattes, 0.34 kg d’abricots et
0.084 kg de pêches.
3. Une boite3 qui contient 0.45 kg de dattes, 0.22 kg d’abricots.
L’entreprise dispose de 33.6 kg de dattes, 25.2 kg d’abricots et de 10.08
kg de pêches. Elle gagne respectivement pour chaque boite 3 DA, 2 DA
et 1.5 DA.
- Donnez le modèle mathématique qui permet de maximiser le profit de
cette entreprise ?
2
II- La méthode du simplexe
1. Méthode de résolution du simplexe
Après modélisation du problème précédent, nous obtenons le système
suivant :
Fonction « Objectif » Max Z = 800x1 + 1200x2
{
𝟓𝑿𝟏 + 𝟑𝑿𝟐 ≤ 𝟑𝟎
𝟐𝑿𝟏 + 𝟑𝑿𝟐 ≤ 𝟐𝟒
Sous les contraintes 𝑿𝟏 + 𝟑𝑿𝟐 ≤ 𝟏𝟖
𝑿 𝟏, 𝑿 𝟐 ≥ 𝟎
On commence tout d’abord par transformer les inéquations en
équations en ajoutant les variables d’écart ei
𝟓𝑿𝟏 + 𝟑𝑿𝟐 ≤ 𝟑𝟎 𝒅𝒆𝒗𝒊𝒆𝒏𝒕 𝟓𝑿𝟏 + 𝟑𝑿𝟐 + 𝒆𝟏 = 𝟑𝟎
Si l’inéquation est du type ≥ 0 alors la transformation s’écrit :
𝟓𝑿𝟏 + 𝟑𝑿𝟐 ≥ 𝟑𝟎 𝒅𝒆𝒗𝒊𝒆𝒏𝒕 𝟓𝑿𝟏 + 𝟑𝑿𝟐 ― 𝒆𝟏 = 𝟑𝟎
Donc en ajoutant les variables d’écart ei notre système devient :
Max Z = 800x1 + 1200x2
{
𝟓𝑿𝟏 + 𝟑𝑿𝟐 + 𝒆𝟏 = 𝟑𝟎
𝟐𝑿𝟏 + 𝟑𝑿𝟐 + 𝒆𝟐 = 𝟐𝟒
𝑿𝟏 + 𝟑𝑿𝟐 + 𝒆𝟑 = 𝟏𝟖
𝑿𝟏, 𝑿𝟐, 𝒆𝟏, 𝒆𝟐,𝒆𝟑 ≥ 𝟎
Nous pouvons maintenant établir le tableau initial
𝑿𝟏 𝑿𝟐 𝒆𝟏 𝒆𝟐 𝒆𝟑 R R/Xi
𝒆𝟏 5 3 1 0 0 30 10
𝒆𝟐 2 3 0 1 0 24 8
𝒆𝟑 1 3 0 0 1 18 6
Z 800 1200 0 0 0 0 Variable Sortante
Variable Entrante
Pour le choix de la variable rentrante on prend :
- Le Maximum des Zi pour des problèmes de Max
- Le Minimum des Zi pour des problèmes de Min
3
La variable sortante sera déterminée par le Min(R/Xi : Var Ent).
Dans notre cas on prend le Min(10, 8, 6) qui est 6.
Donc e3 est la variable qui sort de la Base.
Détermination du pivot
𝑿𝟏 𝑿𝟐 𝒆𝟏 𝒆𝟐 𝒆𝟑 R R/Xi
𝒆𝟏 5 3 1 0 0 30 10
𝒆𝟐 2 3 0 1 0 24 8
𝒆𝟑 1 3 0 0 1 18 6 Variable Sortante
Z 800 1200 0 0 0 0
Variable Entrante
La cellule grise désigne le Pivot qui est dans notre cas égal à 3.
Second Tableau
𝑿𝟏 𝑿𝟐 𝒆𝟏 𝒆𝟐 𝒆𝟑 R R/Xi
𝒆𝟏 4 0 1 0 -1 12
𝒆𝟐 1 0 0 1 -1 6
𝑿′𝟏 1/3 1 0 0 1/3 6
Z 400 0 0 0 - 400 -7200
La ligne du pivot est divisée par la valeur du pivot
La colonne du pivot est mise à Zéro sauf le pivot qu’on laisse à 1
Les autres valeurs du tableau sont obtenues en calculant, dans le
𝐶𝑖𝑘 ∗ 𝐶𝑙𝑗
tableau précédent, 𝐶𝑖𝑗←𝐶𝑖𝑗 ― 𝑃𝑖𝑣𝑜𝑡
Calculons par exemple la valeur de la case(Z,e3)= - 400
On se réfère au tableau précédent et on obtient :
3 1
1200 ∗ 1
case(Z,e3)= 0 - 𝟑
= - 400
1200 0
Troisième Tableau
𝑿𝟏 𝑿𝟐 𝒆𝟏 𝒆𝟐 𝒆𝟑 R R/Xi
𝒆𝟏 4 0 1 0 -1 12 3
𝒆𝟐 1 0 0 1 -1 6 6 Variable Sortante
𝑿′𝟏 1/3 1 0 0 1/3 6 18
Z 400 0 0 0 - 400 -7200
4
Variable Entrante
La variable entrante est X1 vue que c’est la plus grande valeur positive de Z
On calcule R/X1 : (3 , 6 , 18)
La variable sortante est donc e1 puisque 3 est le minimum de la colonne R/Xi
Le pivot est l’intersection entre (X1,e1) ce qui donne la valeur 4.
Après calcul des autres valeurs du nouveau tableau, on obtient :
Quatrième Tableau
𝑿𝟏 𝑿𝟐 𝒆𝟏 𝒆𝟐 𝒆𝟑 R R/Xi
𝑿′𝟐 1 0 1/4 0 -1/4 3
𝒆𝟐 0 0 -1/4 1 -3/4 3
𝑿′𝟏 0 1 -1/12 0 5/12 5
Z 0 0 -100 0 - 300 - 8400
Le critère d’arrêt
L’algorithme du simplexe s’arrête lorsque :
- Les Zi ≤ 0 pour un problème de Maximisation
- Les Zi ≥ 0 pour un problème de Minimisation.
On remarque que dans notre quatrième tableau les Zi ≤ 0.
Donc le critère d’arrêt est vérifié. La solution à notre problème est :
(X1 = 3 , X2 = 5 , Z = 8400)
5
TD N°1
Modélisation mathématique d’un problème
Résolution du problème par la méthode du Simplexe
Reprenons l’énoncé de l’exercice proposé au début du cours.
Enoncé du problème
Une entreprise prépare trois types de boites de fruits :
1. Une boite1 qui contient 0.45 kg de dattes, 0.67 kg d’abricots et
0.34 kg de pêches.
2. Une boite2 qui contient 0.56 kg de dattes, 0.34 kg d’abricots et
0.084 kg de pêches.
3. Une boite3 qui contient 0.45 kg de dattes, 0.22 kg d’abricots.
L’entreprise dispose de 33.6 kg de dattes, 25.2 kg d’abricots et de 10.08
kg de pêches. Elle gagne respectivement pour chaque boite 3 DA, 2 DA
et 1.5 DA.
- Donnez le modèle mathématique qui permet de maximiser le profit de
cette entreprise ?
- Puis le résoudre par la méthode du Simplexe ?
Indications
- Modélisation
Boite1 Boite2 Boite3 Contraintes
Dattes 0.45 0.56 0.45 33.6
Abricots 0.67 0.34 0.22 25.2
Pêches 0.34 0.084 0 10.08
Coûts 30 20 15
Max Z = 30 𝑋1 + 20 𝑋2 + 15 𝑋3
{
0.45 𝑋1 + 0.56 𝑋2 + 0.45 𝑋3 ≤ 33.6
0.67 𝑋1 + 0.34 𝑋2 + 0.22 𝑋3 ≤ 25.2
0.34 𝑋1 + 0.084 𝑋2 ≤ 10.08
6
Résoudre le système précédent par la méthode du Simplexe.
Après ajout des variables d’écart on obtient :
Tableau initial
𝑿𝟏 𝑿𝟐 𝑿𝟑 𝒆𝟏 𝒆𝟐 𝒆𝟑 R R/Xi
𝒆𝟏 0.45 0.56 0.45 1 0 0 33.6
𝒆𝟐 0.67 0.34 0.22 0 1 0 25.2
𝒆𝟑 0.34 0.084 0 0 0 1 10.08
Z 30 20 15 0 0 0 0
NB : Je vous laisse le soin de continuer les calculs….
Fin du premier chapitre.
