Recherche Opérationnelle : Notes de cours
Pr :
Imane EL MALKI
email :
[Link]@[Link]
6 novembre 2023
TABLE DES MATIÈRES Table des matières
Table des matières
1 Programmation Linéaire 2
2 Résolution Graphique 3
3 Algorithme du Simplexe 3
3.1 Forme Standard : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 Algorithme du Simplexe : Cas général de maximisation 4
4.1 Choix de la variable entrante : . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2 Choix de la variable sortante : . . . . . . . . . . . . . . . . . . . . . . . . 4
4.3 Règles de calcul : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Rapport - Recherche Opérationnelle : Notes de cours 1
1 Programmation Linéaire
1 Programmation Linéaire
Variables de décisions :
x1 , x2 , x3 , ..., xn
Contraintes du modèle :
a11 x1 + a12 x2 + ... + a1n xn ≤ b1 ( ou ≥ b1 )
a21 x1 + a22 x2 + ... + a2n xn ≤ b2 ( ou ≥ b2 )
..
.
am1 x1 + am2 x2 + ... + amn xn ≤ bm ( ou ≥ bm )
x1 , x2 , ..., xn ≥ 0
Fonction Objectif :
Le responsable de décision veut maximiser ou minimiser une fonction des variables de
décisions.
M ax Z = c1 x1 + c2 x2 + ... + cn xn ci ∈ R, i = 1, ..., n
M in Z = c1 x1 + c2 x2 + ... + cn xn ci ∈ R, i = 1, ..., n
⇒ Programme Linéaire :
Maximiser ou minimiser la fonction objectif :
Z = c1 x1 + c2 x2 + ... + cn xn
Sous contraintes :
a11 x1 + a12 x2 + ... + a1n xn ≤ b1 ( ou ≥ b1 )
a21 x1 + a22 x2 + ... + a2n xn ≤ b2 ( ou ≥ b2 )
..
.
am1 x1 + am2 x2 + ... + amn xn ≤ bm ( ou ≥ bm )
x1 , x2 , ..., xn ≥ 0
Rapport - Recherche Opérationnelle : Notes de cours 2
3 Algorithme du Simplexe
2 Résolution Graphique
Voir les exemples du cours
3 Algorithme du Simplexe
3.1 Forme Standard :
Soit le programme linéaire :
M ax Z = 87x1 + 147x2 + 258x3
s.c 15x1 + 21x2 + 30x3 ≤ 1260
x1 + 2x2 + 3x3 ≤ 90
x1 + x2 + x3 ≤ 84
x1 , x2 , x3 ≥0
⇒ Forme Standard :
• On pose e1 = 1260 − 15x1 − 21x2 − 30x3 ≥ 0.
Alors, on peut écrire la 1ere contrainte sous la forme,
15x1 + 21x2 + 30x3 +e1 =1260 avec e1 ≥ 0
• On pose e2 = 90 − x1 − 2x2 − 3x3 ≥ 0.
Ainsi, on peut écrire la 2eme contrainte sous la forme,
x1 + 2x2 + x3 +e2 =90 avec e2 ≥ 0
• On pose e3 = 84 − x1 − x2 − x3 ≥ 0.
Donc, on obtient,
x1 + x2 + x3 +e3 =84 avec e3 ≥ 0
Finalement la forme standard du PL est :
M ax Z = 87x1 + 147x2 + 258x3
s.c 15x1 + 21x2 + 30x3 + e1 = 1260
x1 + 2x2 + 3x3 + e2 = 90
x1 + x2 + x3 + e3 = 84
x1 , x2 , x3 , e1 , e2 , e3 ≥0
Remarque : de la forme canonique à la forme standard
Rapport - Recherche Opérationnelle : Notes de cours 3
4 Algorithme du Simplexe : Cas général de maximisation
Forme canonique Forme standard
1) a1 x1 + a2 x2 + ... + an xn ≤ b1 1) a1 x1 + a2 x2 + ... + an xn +e = b1 avec e ≥ 0
2) a1 x1 + a2 x2 + ... + an xn ≥ b1 2) a1 x1 + a2 x2 + ... + an xn −e = b1 avec e ≥ 0
3) a1 x1 + a2 x2 + ... + an xn = b1 3) a1 x1 + a2 x2 + ... + an xn =b1
4) Si xi ≤ 0 4) On pose x∗i = −xi ≥ 0
On change les xi en x∗i dans toutes les lignes du P.L
5) Si x ∈ R 5) On pose x = x+ − x− x+ = max(x, 0) ≥ et
x− = max(−x, 0) ≥ 0. Et on écrit tous les x du P.L
en (x+ − x− )
4 Algorithme du Simplexe : Cas général de maximisa-
tion
4.1 Choix de la variable entrante :
On choisit la variable qui a le plus grand coefficient positif dans la fonction objectif,
c-à-d, dans la dérnière ligne du tableau on choisit la colonne ”j” qui correspond à la plus
grande valeur positive.
On a les possibilités suivantes :
1- Si tous les termes de la colonne ”j” sont négatifs ou nuls, alors on dit que l’ensemble
réalisable est non borné et max Z = +∞.
2- S’il existe un terme positif de la colonne ”j”, alors xj est la variable entrante dans
la base.
4.2 Choix de la variable sortante :
On divise la colonne du second membre B par les élèments de la colonne ”j”. Et la
variable sortante correspond à la plus petite valeur positive.
4.3 Règles de calcul :
Rappel :
La colonne ”j” de la variable entrante est appelée colonne pivot Cpivot .
La ligne de la variable sortante est appelée ligne pivot Lpivot .
L’intersection entre la ligne pivot et la colonne pivot est dite pivot.
Règles de calcul :
– Les coefficients de la ligne du pivot sont divisés par le pivot.
– Les coefficients de la colonne du pivot sont tous nuls sauf le pivot qui devient = 1.
– Les autres coefficients sont obtenus par la règle :
case∗ (i) = case(i) − Cpivot (i) ∗ Lpivot (i)
Rapport - Recherche Opérationnelle : Notes de cours 4
4.3 Règles de calcul : 4 Algorithme du Simplexe : Cas général de maximisation
case∗ : nouvelle valeur,
case : ancienne valeur,
i : case i dans la ligne où on travaille.
Remarque : Pour la case valeur de Z ( intersection entre la colonne B et la dernière
ligne du tableau).
– Si on travaille avec la même règle cité en rouge, on trouve Z = α ≤ 0.
Alors, Max Z = −α ≥ 0
– Si on travaille avec :
case∗ (i) = case(i)+Cpivot (i) ∗ Lpivot (i)
On trouve par la suite que Z = β ≥ 0, alors, Max Z = β.
Rapport - Recherche Opérationnelle : Notes de cours 5
