CHENNOUFI KAWTHER GROUPE 1
1 INTRODUCTION :
La méthode du simplexe est un algorithme fondamental en optimisation linéaire, développé par
George Dantzig en 1947. Elle permet de résoudre des problèmes de programmation linéaire en
identifiant la solution optimale parmi un ensemble de solutions réalisables.
2 ALGORITHM DU SIMPLEX:
a) Forme canonique d'un
Programme Linéaire Max z = c1 x1 + c 2 x2
+ +cn xn
a11 x1 + a12 x2 +............+ a1n xn b1
a21 x1 + a22 x2 +............+ a2n xn b2
............................................................................
am1 x1 + am2 x2 +............+ amn xn bm
x1 0 ; x2 0 ; .........; xn 0
b) Forme standard d'un Programme Linéaire
On transforme les inégalités des contraintes économiques en égalités par introduction de
variables supplémentaires positives ou nulles appelées variables d'écart.
ai1 x1 + ai2 x2 + .......... + ain xn bi devient ai1 x1 + ai2 x2 +.............+ ain xn + ti bi
D’où la forme standard
Max z = c1 x1 + c2 x2 + ..........+ cn xn
a11 x1 + a12 x2 + .......... + a1n xn + t1 b1
a21 x1 + a22 x2 + .......... + a2n xn + t2 b2
............................................................................
am1 x1 + am2 x2 +............+ amn xn + tm bm
x1 0 ; x2 0 ; .........; xn 0 ; t1 0 ;t2 0 ; .........; tm 0
c) Résolution
Pour démarrer l'algorithme, il est nécessaire d'avoir une solution initiale. Dans le cas
simple, l'origine est solution, c.à.d. que la première solution est
x1 0 ; x2 0; .........; xn 0 ; t1 b1 ; t2 b2 ; .........; tm bm (ceci suppose que
les bi ne soient pas négatifs pour satisfaire les contraintes de signe)
L'algorithme, basé sur la méthode du pivot de Gauss pour la résolution des systèmes
d'équations linéaires, est présenté sous forme de tableau.
Soit à résoudre le programme linéaire suivant sous sa forme canonique
Max z = 1200 x1 + 1000 x2
3 x1 + 4 x2 160
6 x1 + 3 x2 180
x1 0 ; x2 0
* Forme standard
Max z = 1200 x1 + 1000 x2 + 0 t1 + 0 t2
3 x1 +4 x2 + 1 t1 + 0 t2 160
6 x1 +3 x2 + 0 t1 + 1 t2 180
x1 0 ; x2 0 ; t1 0 ; t2 0
* Tableau 0
On ne conservant que les coefficients des équations ci-dessus, on obtient le
tableau de départ
Ce tableau nous donne la première solution admissible :
- Les variables Hors Base (HB) sont nulles: x1 0 ; x2 =0 (t1 et t2 en rouge ne sont
pas hors base; elles ne sont présentes que pour rappeler qu'il s'agit des colonnes
des coefficients de ces deux variables)
- Les valeurs des variables dans la Base (B) se lisent dans la colonne C: t1 = 160
et t2 =180
- La dernière cellule (intersection de C et ) donne la valeur de -z : -z = 0 donc z =
0
- La ligne donne les valeurs marginales ou taux marginal de substitution; elles
s'interprètent de la manière suivante: à ce stade de la solution, une
augmentation de 1 unité de x1 ferait accroître la fonction objectif de 1200, et une
augmentation de 1 unité de x2 ferait accroître la fonction objectif de 1000.
* Tableau 1
On augmente la fonction objectif en faisant entrer une variable dans la base,
prenant la place d'une variable qui va sortir de la base.
3 CRITÈRE DE SÉLECTION DE LA VARIABLE ENTRANT DANS LA
BASE:
On sélectionne la variable HB ayant le plus grand coefficient positif dans la ligne
∆
x1 entre donc dans la base
Pour sélectionner la variable sortant de la base, il est nécessaire de rajouter une
colonne R au tableau, obtenue en faisant le rapport membre à membre de la
colonne C et de la colonne de la variable entrant dans la base (x1)
Remarques sur la colonne R:
- Un 0 dans la colonne C est remplacé par un infiniment petit positif
pour effectuer le calcul de R
- Dans la colonne R on ne tient pas compte des valeurs négatives ou indéterminées
Critère de sélection de la variable sortant de la base:
On sélectionne la variable dans la Base ayant le plus petit coefficient positif
dans la colonne R .
t2 sort donc de la base
En appliquant les règles de algorithm de Gauss Jordan on obtient le tableau 1:
Ce tableau nous donne la deuxième solution admissible:
- Les variables Hors Base (HB) sont nulles: x2 0 ; t2 =0 (x1 et t1 en rouge
ne sont pas hors base; elles ne sont présentes que pour rappeler qu'il s'agit
des colonnes des coefficients de ces deux variables)
- Les valeurs des variables dans la Base (B) se lisent dans la colonne C: t1 =
70 et x1 =30
- La dernière cellule (intersection de C et ) donne la valeur de -z : -z = -
36000 donc z = 36000
- La ligne donne les valeurs marginales ou taux marginal de substitution; elles
s'interprètent de la manière suivante: à ce stade de la solution, une
augmentation de 1 unité de x2 ferait accroître la fonction objectif de 400, et une
augmentation de 1 unité de t2 ferait diminuer la fonction objectif de 200 (il est à
noter qu'une augmentation de 1 unité de la variable d'écart t2 revient à diminuer
le second membre de l'équation correspondante de 1 unité).
* Tableau 2:
d'où le tableau 2
Ce tableau nous donne la troisième solution admissible:
- Les variables Hors Base (HB) sont nulles: t1 = 0 ; t2 = 0 (x1 et x2 en
rouge ne sont pas hors base; elles ne sont présentes que pour rappeler qu'il
s'agit des colonnes des coefficients de ces deux variables)
- Les valeurs des variables dans la Base (B) se lisent dans la colonne C: x2 = 28
et x1 =16
- La dernière cellule (intersection de C et ∆) donne la valeur de -z : -z = -
47200 donc z = 47200
Critère d'arrêt des itérations:
Si tous les coefficients de la ligne D, relatifs aux variables HB, sont négatifs ou
nuls, la solution trouvée est optimale.