PROGRAMMATION
LINÉAIRE
20 Juin 2020
2.0
Table of contents
Objectives 3
I - Chapitre III : Algorithme du Simplexe 4
1. Position du problème ...................................................................................................................................... 4
2. Amélioration de la fonction objectif .............................................................................................................. 4
3. Schéma de l'Algorithme du Simplexe ............................................................................................................. 7
4. Tableaux du Simplexe ..................................................................................................................................... 8
5. Initialisation de l'Algorithme du Simplexe .................................................................................................... 11
5.1. Solution réalisable initiale .......................................................................................................................................................... 11
5.2. Méthode du Big-M (méthode de la base artificielle) ................................................................................................................... 12
5.3. Méthode des deux Phases ........................................................................................................................................................... 14
6. Quiz: .............................................................................................................................................................. 17
Objectives
Ce module a pour objectifs de sensibiliser l'étudiant à l'importance pratique des
problèmes d'optimisation linéaires, de maîtriser l'ensemble numérique sous-jacent, et de
pouvoir utiliser ces techniques dans des problèmes pratiques.
Près-requis
Pour que les étudiants puissent assimilés ce cours il faut bien avoir au moins ces
connaissances ci-dessous :
Mathématiques et informatique générale,
Métriser le calcul matricielle.
3
Chapitre III : Algorithme du Simplexe
Chapitre III : Algorithme
du Simplexe I
1. Position du problème
Soit le problème de programmation linéaire suivant :
où , , et
2. Amélioration de la fonction objectif
Le principe de l'algorithme du Simplexe est de déterminer une solution optimale en se déplaçant de sommet en
sommet de façon à améliorer la fonction objectif. Le déplacement se fait à partir de la solution de base de
départ vers une solution de base réalisable en suivant une arête le long de laquelle l'objectif s'ccroit.
Soit une solution de base réalisable et la matrice de base associée. Si le critère
d'optimalité (2.10) est vérifie alors x est une solution optimale du problème (3.1) (théorème 2.6) sinon, deux cas
peuvent se présenter :
1. Il existe un indice dans tel que est strictement négatif auquel correspond le vecteur non
positif auquel cas le problème (3.1) n'admet pas de solution optimale (théorème 2.7).
2. Pour tout indice négatif dans le vecteur contient des composantes positives alors une
itération de l'algorithme du simplexe consiste à construire une autre solution réalisable de base telle
que .
La construction d'une nouvelle solution réalisable basique doit assurer un accroissement maximal de la
fonction objectif, pour cela, il faudrait choisir dans la relation (2.16) le paramètre aussi grand que possible et
choisir l'indice tel que :
Le paramètre aussi grand que possible, doit aussi être choisi de telle sorte que le vecteur donné par la
relation (2.16) soit une solution réalisable. Pour cela, il faudrait avoir :
En posant on aura :
4
Amélioration de la fonction objectif
Pour on a :
Pour on a :
Ainsi, le vecteur construit par la relation (2.16) sera une solution réalisable pour le problème (3.1), si
Dans le cas contraire, c'est à dire, si
le vecteur aura des composantes négatives et par conséquent il ne sera pas une solution réalisable. Ainsi, la
plus grande valeur telle que le vecteur soit une solution réalisable est :
Dans le cas où x est une solution réalisable de base non dégénérée, la valeur de sera strictement positive et en
vertu de la relation (2.17) on aura :
Montrons que la solution est une solution réalisable de base.
On a :
pour la composante d'indice on aura :
En remplaçant les valeurs de et dans la relation (3.9) on aura :
alors :
5
Amélioration de la fonction objectif
Le vecteur possède ainsi n-m composantes nulles.
On note :
où
La matrice est une base réalisable si les vecteurs sont linéairement indépendants. On a :
A_B=(I,J_B)
on a alors
On fait sortir le vecteur de la base et pour y entrer le vecteur .
De la relation (3.11) on déduit :
De la relation (3.10) on a:
Formons une matrice de la manière suivante :
où
De la relation (3.12) on a :
6
Schéma de l'Algorithme du Simplexe
donc est inversible et on a :
Le calcul de selon le relation (3.2) peut s'avérer peut efficace si est relativement grand, on peut alors
calculer les éléments overline{u}_{ij} de la matrice en fonction de ceux de la matrice et des
composantes du vecteur
où
3. Schéma de l'Algorithme du Simplexe
Supposons que nous avons obtenu une solution réalisable de base , la base correspondante
, ainsi que la matrice inverse .
Une itération de l'algorithme du simplexe se résume alors dans les étapes suivantes :
- Étape 1 : Calculer le vecteur des potentiels
- Étape 2 : Calculer le vecteur des estimations
- Étape 3 : Si , alors x est une solution optimale pour le problème (3.1), terminer le
processus de résolution, sinon
- Si et le vecteur , le problème (3.1) n'admet pas de solution
finie
- Sinon
1. Calculer l'indice tel que :
2. Calculer les composantes du vecteur
3. Calculer
4. Calculer où
5. Poser et
6. Calculer par la relation (3.14)
- Étape 4 : Poser et aller à Étape 1.
7
Tableaux du Simplexe
Note:Remarque 3.1.
Dans le cas où toutes les solutions réalisables basiques dans le problème de programmation linéaire (3.1) sont
non dégénérées, la croissance stricte de la fonction objectif à chaque itération empêche de passer deux fois par
le même point extrême, et comme le nombre de points extrêmes est fini, il en résulte que l'algorithme du
simplexe construit une solution optimale en un nombre fini d'itérations.
4. Tableaux du Simplexe
Les tableaux du simplexe sont une autre façon de présenter les calculs algébriques et les opérations que l'on fait
sur le système d'équations en effectuant les calculs sur le tableau des coefficients qui porte le nom de tableau
Simplexe.
Example
Considérons le problème de programmation linéaire suivant :
La mise sous forme standard du programme linéaire (3.15) écrit sous forme canonique, consiste `a ajouter des
variables dites variables d'écart aux contraintes du problème (3.15) afin de transformer toutes les
inégalités en égalités. En ajoutant ainsi trois variables d'écart on obtient le problème (3.15) sous sa forme
standard :
est une solution réalisable de base avec
on a : , , , , et
Le premier tableau du simplexe sera construit comme suit :
8
Tableaux du Simplexe
La valeur de Z est donnée par
Les composantes du vecteur des estimations sont données par :
L'indice tel que
Le paramètre tel que :
La nouvelle base est alors : et le nouveau tableau du simplexe est :
Dans cette deuxième itération de l'algorithme on trouve :
La nouvelle base est alors : et le nouveau tableau du simplexe est :
9
Tableaux du Simplexe
Dans la troisième itération, la nouvelle solution de base et la nouvelle valeur de l'objectif valent :
Le vecteur des estimations la solution courante est optimale.
Example:problème non borné
Résoudre par la méthode du simplexe le problème de programmation linéaire suivant :
On écrit le problème (3.17) sous forme standard en ajoutant deux variables décart et , on aura :
En dressant le premier tableau du simplexe on aura :
La variable doit entrer en base et la variable doit quitter la base. La nouvelle base est ainsi . Le
nouveau tableau du simplexe sera :
10
Initialisation de l'Algorithme du Simplexe
La variable est seule candidate à y entrer en base. Comme tous les coefficients de la colonne sont non
positifs, on en conclut que le problème est non borné.
5. Initialisation de l'Algorithme du Simplexe
Dans les cas précédemment traités par l'algorithme du simplexe, on a supposé l'existence d'une solution
réalisable de base initiale, ce qui n'est pas toujours le cas dans les problèmes de programmation linéaires. Nous
verrons dans ce qui suit deux méthodes permettant d'initialiser l'algorithme du simplexe. Considérons le
problème de programmation linéaire suivant :
où A est une matrice et un vecteur de et
5.1. Solution réalisable initiale
En introduisant m variables d'écart dans les contraintes du problème (3.18), on obtient
le problème linéaire suivant :
Le vecteur est une solution réalisable pour le problème (3.19). De plus, on a la base
alors le vecteur est une solution réalisable basique pour le problème (3.19).
Note
Les problèmes (3.18) et (3.19) sont équivalents.
11
Méthode du Big-M (méthode de la base artificielle)
5.2. Méthode du Big-M (méthode de la base artificielle)
Considérons le problème de programmation linéaire suivant :
où A est une matrice et un vecteur de et
En introduisant m variables artificielles dans les contraintes et la fonction objectif du
problème (3.20), on obtient le problème auxiliaire suivant, appelé le M-problème défini par :
Le problème (3.21) admet une solution réalisable de base et
Fundamental:Théorème 3.1.
Si l'ensemble X des solutions réalisables du problème (3.20) est vide, alors toute solution optimale
du problème (3.21) est telle que .
~~et~~ est une solution optimale du probème (3.21)
Preuve.
Supposons ,~~ est une solution optimale du probème (3.21) et
alors est une solution réalisable pour le problème (3.20) c'est à dire X n'est pas vide (contradiction avec
l'hypothèse).
Fundamental:Théorème 3.2.
Si le vecteur est une solution optimale pour le problème (3.21), alors est une solution
optimale pour le problème (3.20).
est une solution optimale pour le problème (3.21) est une solution optimale pour
le probl`eme (3.20)
Fundamental:Théorème 3.3.
Si est une solution optimale dans le problème M-problème (3.21) alors est aussi une
solution optimale dans le -problème de type (3.21), pour tout .
est une solution optimale pour le problème (3.21) , est une solution
optimale pour le -problème
12
Méthode du Big-M (méthode de la base artificielle)
Fundamental:Théorème 3.4.
Si est une solution optimale du problème (3.20), alors pour un (M>0) suffisamment grand, le vecteur
est une solution optimale du problème (3.21).
Example
Résoudre par la M-méthode le problème de programmation linéaire suivant :
En introduisant deux variables artificielles et on aura le problème auxiliaire suivant :
Itération 1
On construit le premier tableau du simplexe :
La nouvelle base est
Itération 2
13
Méthode des deux Phases
La nouvelle base est
Itération 3
Le critère d'optimalité étant vérifié , alors le vecteur est une solution optimale
pour le problème (3.23). Mais en vertu du théorème 3.1, l'ensemble des solutions réalisables du problème (3.22)
est vide.
Fundamental:Théorème 3.5.
si il existe une solution optimale pour le M-problème telle que , alors .
Note
Cependant, la méthode du big-M pose certains problèmes, notamment lorsque le programme linéaire est résolu
par ordinateur. Contrairement aux calculs à la main, le recours à un ordinateur nécessite en effet le choix d'une
valeur numérique pour M. Cette valeur doit être beaucoup plus grande que n'importe quel autre coefficient de
la fonction objectif. Si M est trop petit, on peut trouver une solution avec une variable artificielle positive dans
la base, ce qui indique un problème non réalisable, alors qu'en réalité il est tout à fait réalisable.
5.3. Méthode des deux Phases
Comme son nom l'indique, cette méthode consiste à résoudre un problème de programmation linéaire en deux
parties.
La première partie, appelée phase I, consiste à résoudre un problème auxiliaire correspondant au problème
original en utilisant une fonction objectif artificielle et annuler toutes les variables artificielles. Si l'on ne peut
pas annuler toutes les variables, alors le problème n'est pas réalisable.
14
Méthode des deux Phases
La phase II consiste à remplacer la fonction objectif artificielle de la phase I par la vraie fonction objectif à
maximiser. On utilise alors la solution réalisable de base obtenue à la fin de la phase I.
Soit le problème de programmation linéaire suivant :
et considérons le problème auxiliaire suivant, correspondant au problème linéaire (3.24) :
où , ,
Le vecteur est une solution réalisable de base pour le problème (3.25) avec la matrice unité comme
base associée à .
Note
La fonction objectif du problème (3.25) est bornée supérieurement par zéro, par conséquent le problème (3.25)
admet toujours une solution optimale.
Fundamental:Théorème 3.6.
Soit une solution réalisable basique optimale du problème (3.25), nous avons alors le théorème
suivant :
1. Si alors est un point extrême
2. Si alors
Note
Si la solution réalisable basique correspond à une base comprenant des vecteurs colonnes
artificiels, alors il est tout à fait commode d'utiliser les transformations de Gauss-Jordan pour les faire sortir de
la base.
Example
Résoudre par la méthode des deux phases le problème de programmation linéaire suivant :
PHASE I
On définit le problème auxiliaire correspondant au problème (3.26) :
15
Méthode des deux Phases
Une solution réalisable basique évidente pour le problème (3.27) est
Itération 1
La nouvelle base est :
Itération 2
La nouvelle base est
Itération 3
Le critère d'optimalité étant vérifié, la solution courante est optimale pour le
problème (3.27). On utilise ainsi cette solution comme solution de base réalisable initiale pour résoudre le
problème (3.26).
16
Quiz:
PHASE II
Itération 1
La nouvelle base est
Itération 2
Le critère d'optimalité étant vérifié, la solution courante est optimale pour le problème (3.26)
avec .
6.
Quiz:
Exercice 01 :
On a le problème de programmation linéaire suivant :
Résoudre le problème par la méthode du simplexe
Solution
On ajoutant des variables d’écart, on obtient la forme standard suivante :
Le premier tableau du simplexe est donné ci-dessous
17
Quiz:
Le tableau final ainsi que La solution optimale est donnés
comme suit :
Exercice 02 :
Résoudre par la méthode du Big-M le problème suivant :
Solution
La forme standard associée au problème est :
Le M-problème auxiliaire associé au problème s’écrit :
Le premier tableau est donné comme suit :
18
Quiz:
Le tableau final ainsi que la solution optimale sont donnés
comme suit :
x^*=(x_1^*,x_2^*)=(0,2)
19
