Programme linéaire sous sa forme canonique :
programme linéaire sous forme canonique
Un programme linéaire sous sa forme canonique est :
• Un problème de Maximisation, sous contraintes Inférieure ou égale, dont toutes les
variables sont positives.
• Un problème de Minimisation, sous contraintes Supérieure ou égale, dont toutes les
variables sont positives.
Passage à la forme canonique :
Si le programme linéaire ne correspond pas à ces critères, il faut transformer les
contraintes ou la fonction objectif selon les opérations suivantes :
max 𝑧 = − min(−𝑧) ;
𝑥 + 𝑦 ≥ 𝑏 est équivalent à −𝑥 − 𝑦 ≤ −𝑏 ;
𝑥 + 𝑦 = 𝑏 est équivalent à 𝑥 + 𝑦 ≥ 𝑏 𝑒𝑡 𝑥 + 𝑦 ≤ 𝑏.
Forme canonique matricielle :
La forme canonique est souvent représentée sous une forme matricielle :
le vecteur des coefficients de la fonction objectif : 𝑐 de taille n, 𝑐 = (𝑐1 , … , 𝑐𝑛 );
la matrice des coefficients de la partie gauche des contraintes : 𝐴 de taille m × n ;
le vecteur des constantes de la partie droite des contraintes : 𝑏 de taille m,
𝑏1
𝑏 =( ⋮ );
𝑏𝑛
𝑥1
le vecteur des variables : 𝑥 de taille n, 𝑥 = ( ⋮ ).
𝑥𝑛
max 𝑧 = 𝑐𝑥 min 𝑧 = 𝑐𝑥
𝐴𝑥 ≤ 𝑏 𝐴𝑥 ≥ 𝑏
𝑠. 𝑐 { 𝑠. 𝑐 {
𝑥≥0 𝑥≥0
Programme linéaire sous forme standard
Un problème de Maximisation (ou de Minimisation), sous contraintes de type égalités,
dont toutes les variables sont positives.
Opt 𝑧 = 𝑐𝑥
𝐴𝑥 = 𝑏
𝑠. 𝑐 {
𝑥≥0
Opt= max ou min.
Proposition. Tout programme linéaire peut être mis sous la forme standard.
L’algorithme du simplexe
L’algorithme du simplexe est la plus célèbre méthode pour la résolution numérique des
programmes linéaires. Analytiquement parlant, l’algorithme consiste à passer
itérativement d’une solution de base réalisable non dégénérée x, à une solution de base
réalisable non dégénérée voisine (Deux solutions de base sont dites voisines si leurs bases
respectives ne diffèrent qu’en un et un seul élément ) x′, en laquelle la valeur de Z est
plus élevée, partant d’un point x0. La méthode du simplexe se décompose en deux phases
essentielles :
Phase I : procédure d’initialisation
Déterminer une première solution de base réalisable, i.e les coordonnées d’un premier
sommet de l’ensemble des solutions réalisables D. Si cette procédure échoue, cela
signifie que D est vide, donc le problème est impossible (les contraintes ne peuvent être
satisfaites simultanément). Sinon, le domaine des solutions réalisables n’est pas vide ; et
soit x0 une (première) solution de base réalisable (trouvée).
Phase II : procédure itérative
Calculer, à partir d’une solution de base réalisable (trouvée en phase I), une autre
solution de base réalisable donnant une valeur meilleure de la fonction objectif. Cette
transformation consiste à faire entrer (selon un critère d’entrée) une variable hors base
dans la base et à faire sortir (selon un critère de sortie) une variable de base hors base.
Géométriquement, une itération consiste à passer d’un sommet de D à un autre sommet
de D adjacent au précédent (dans le sens où elles sont les deux extrémités d’une arête de
D). Leurs coordonnées correspondent à deux solutions de base réalisables dont les
ensembles d’indices de base (donc aussi hors base) ne diffèrent que d’un seul indice.
Cette caractéristique permettra de déterminer relativement aisément la nouvelle
solution de base réalisable à partir de l’ancienne.
Comme tout algorithme, il existe une procédure d’arrêt de l’algorithme : deux tests
d’arrêt mettent en évidence, respectivement que :
- une solution optimale est déterminée ;
- il n’existe pas de solution optimale finie : D est non borné et Z peut y tendre vers l’infini.
Critère d’entrée: La variable hors base 𝑥𝑟 de coefficient 𝑐𝑟 dans la fonction objectif le
plus élevé est la variable candidate à entrer en base. En cas d’égalité on fait un choix
arbitraire.
Critère de sortie: La variable 𝑥𝑠 qui doit sortir de la base est telle que:
𝑏𝑖 𝑏
= min{𝑎 𝑖 , 𝑎𝑖𝑟 > 0} 𝒂𝒔𝒓 : est appelé pivot.
𝑎𝑠𝑟 𝑖𝑟
Critère d’arrêt: Pour un problème de maximisation, l’algorithme s’arrête lorsque tous
les coefficients 𝑐𝑗 , 𝑗 ∈ 𝐽 sont négatifs ou nuls.
Renouvellement du tableau du simplexe
Le nouveau tableau s’obtient par les formules suivantes:
Ligne pivot: (celle qui contient le pivot)
Nouvel élément= Ancien élément / pivot
𝑎̂𝑠𝑗 = 𝑎𝑠𝑗 /𝑎𝑠𝑟
Autres éléments:
Nouvel élément= Ancien élément - Elément correspondant à la colonne pivot* Elément
correspondant à la nouvel ligne pivot.
𝑎̂𝑖𝑗 = 𝑎𝑖𝑗 − 𝑎𝑖𝑟 × 𝑎𝑠𝑗
Algorithme du Simplexe (le cas de max)
(0) Mettre le programme linéaire sous sa forme standard ;
(1) Recherche d’une solution de base réalisable de départ ;
(2) Construire le premier tableau du simplexe ;
(3) Tester si 𝑐𝑗 < 0, ∀ 𝑗 ∈ {1, … , 𝑛}
Si oui, terminer la solution courante est optimale.
Si non, aller en (4) ;
(4) Soit 𝑐𝑟 = Max {𝑐𝑗 / 𝑐𝑗 > 0, 𝑗 ∈ 𝐽}, la variable 𝑥𝑟 entre en base ;
(5) Tester Si 𝑎𝑖𝑟 0 ∀ 𝑟 ∈ {1, … , 𝑚}
Si oui, le problème ne possède pas de solution optimale finie.
Si non, aller en (6) ;
(5) Déterminer la variable sortante 𝑥𝑠 par
𝑏𝑖 𝑏
= min{𝑎 𝑖 , 𝑎𝑖𝑟 > 0} 𝒂𝒔𝒓 : est appelé pivot ;
𝑎𝑠𝑟 𝑖𝑟
(6) Renouveler le tableau en utilisant les formules ci-dessus, aller en (3).
