Chapitre 4
Optimisation linéaire (Programmation linéaire)
1 Introduction
L’optimisation (programmation) linéaire est une technique mathématique permettant de déterminer la
meilleure solution d’un problème dont les données et les inconnues satisfont à une série d’équations et
d’inéquations linéaires. La programmation linéaire a été formulée par George Bernard Dantzig en 1947
et connaît un développement rapide par suite de son application directe à la gestion scientifique des
entreprises. Le facteur expliquant l’essor de la programmation linéaire est la construction d’ordinateurs
puissants qui ont permis de traiter les problèmes concrets de taille très grande. On l’applique surtout en
gestion et en économie appliquée. On peut citer les domaines d’application de la programmation
linéaire qui sont : les transports, les banques, les industries lourdes et légères, l’agriculture, les chaînes
commerciales, la sidérurgie, et même le domaine des applications militaires.
Les méthodes de résolution sont la méthode du simplexe, méthode duale du simplexe, méthodes des
potentiels, méthode lexicographique et des méthodes récentes appelées méthodes des points intérieurs.
Dans ce chapitre on va s’intéresser à la méthode graphique, la méthode du Simplexe et duale du
simplexe.
Le problème d’optimisation linéaire PL (Programmation linéaire) consiste à chercher une solution du
problème d’optimisation suivant :
Soumise à des contraintes linéaires :
∑
{
Avec la condition de positivité des variables :
1
[Link]/Optimisation linéaire
2 Forme standard et forme canonique d’un programme linéaire
Forme standard
Définition (Forme standard). Un programme linéaire est sous forme standard lorsque toutes ses
contraintes sont des égalités et toutes ses variables sont non-négatives.
Représentation matricielle
Forme canonique
Définition (Forme canonique). Un programme linéaire est sous forme canonique lorsque toutes ses
contraintes sont des inégalités et toutes ses variables sont non-négatives.
Représentation matricielle
Tout programme linéaire peut s’écrire sous forme standard et sous forme canonique.
3 Méthodes de résolution d’un P.L
3.1 Solution graphique
Exemple 1 : Soit le problème d’optimisation linéaire suivant :
La solution se trouve sur l’un des sommets de l’ensemble des contraintes, pour déterminer cette
solution, on va suivre les étapes suivantes :
2
[Link]/Optimisation linéaire
Etape 1 : Chercher tous les sommets délimitant les solutions réalisables.
Etape 2 : Evaluer la fonction objective en ces sommets.
Etape 3 : Comparer les valeurs obtenues et extraire la solution optimale.
Les sommets : O (0, 0), A (0, 5), B (4, 3), et C (6, 0)
Inconvénient :
Cette méthode est applicable aux PL de petites dimensions.
3.2 Solution Algébrique : Algorithme du simplexe
Le principe de la méthode du simplexe est de trouver la solution optimale en passant d’un sommet
(sommet du polygone convexe des contraintes; L’ensemble des contraintes est un polygone convexe) à
un autre et d’éviter de calculer tous les sommets. A partir d’un sommet donné, la méthode calculera
une suite de sommets adjacents l’un par rapport au précédent et qui améliore la fonction objective. On
explore seulement les sommets qui permettent d’augmenter la fonction objectif ⇒ on réduit le nombre
de solution de base à explorer.
Forme canonique d’un PL
3
[Link]/Optimisation linéaire
{
Transformer le système d’inéquation en un système d’équation
Forme standard d’un PL
On introduit des variables artificielles (d’écart) constituant une solution de base réalisable pour un
problème augmenté, et au cours de cette phase, on cherche à éliminer ces variables de l'ensemble des
variables de base.
On introduit les variables d’écart, on obtient le problème en forme standard suivant :
Méthode de résolution :
Exemple 2 : Soit l’exemple suivant
Forme canonique d’un PL :
Forme standard d’un PL :
4
[Link]/Optimisation linéaire
Forme matricielle
, ( ) ( )
( ) ( )
Remarque :
Linprog : Code utilisée pour résoudre le problème selon la méthode du simplex avec Matlab
Etape 1 : Construire le tableau initial
On forme le tableau initial c’est à dire le point de départ x = (0, 0, : : : , 0).
Pour {
Les variables de base sont , , et la solution de base est (0, 0, 2 , 3, 6) ce qui correspond à
l’origine dans le plan. Les autres variables sont appelées variables hors base
Variable de base bi Rapport
2 -2/3 La base associée est la
3 3/2 matrice identité, I.
6 6/1
0
Examiner les coefficients de la fonction objective (Z)
PL(Max) : Si tous les coefficients
PL(Min) : Si tous les coefficients
Etape 2 : Choix de la variable entrante dans la base (La colonne de pivot)
Pour cela, on choisit l’indice j tel quel
{ | }
Si aucun choix est possible, on a atteint la solution optimale et l’algorithme se termine.
Sinon, on passe à l’étape suivante.
5
[Link]/Optimisation linéaire
Pour un problème de minimisation, on modifie le critère en choisissant l’indice j tel que
{ | }
Dans cet exemple le plus grand coefficient , la fonction Z varie plus rapidement en fonction de
la variable . Donc, on choisit la première colonne comme colonne de pivot ( devient variable de
base)
La variable entre dans la base ( ) mais une variable doit sortir.
Etape 3 : Choix de la variable sortante (La ligne de pivot)
Pour cela, on choisit l’indice i en utilisant le critère du quotient
{ | }
Dans l’exemple ( )
La ligne de pivot sera la deuxième : i = 2. Les variables de base deviennent { }
où « j » est la colonne de pivot de l’étape 2.
Le critère du quotient impose que .
Etape 4 : Pivotage
L’intersection de la colonne et la ligne donne le Pivot LP/P
On applique la procédure d’élimination de Gauss-Jordan autour du pivot situé à l’intersection de la
ligne i et de la colonne j. Ensuite, on divise la ligne i par le pivot (LP/p) pour le mettre égal à 1. Puis on
retourne à l’étape 2 et on recommence.
On procède à élimination de Gauss-Jordan autour du pivot . La ligne Lk du tableau du simplexe
(à cette itération) est modifiée par :
Ceci modifie la dernière colonne du tableau du simplexe par
qui doit être positif car sera la nouvelle solution de base.
6
[Link]/Optimisation linéaire
Si , on obtient
( )
Si , on obtient
Donc, aucun changement.
Si , on a
car et les .
Donc seulement les valeurs sont à considérer et, selon le calcul ci-dessus, on a que
{ | }
V. B bi
13/2
3/2
9/2
-3
25/2
9/2
3/2
-15/2
Donc la solution : Z=15/2 avec 9/2 et
7
[Link]/Optimisation linéaire
4 Cas particuliers du simplexe
Cas 1: les coefficients de la fonction objective sont égaux
Soit l’exemple précèdent (exemple 1)
Forme canonique d’un PL :
Forme standard d’un PL : {
Etape 1 : On forme le tableau initial
Pour {
La solution de base est (0, 0, 18, 10) ce qui correspond à l’origine
dans le plan.
Variable de base bi Rapport
18 18/3 ou 18/2
10 10/1 ou 10/2
Examiner les coefficients de la fonction objective (Z)
P(Max) : tous les coefficients
P(Min) : tous les coefficients
Etape 2 / 3
Pour notre exemple les coefficients de la fonction objective sont égaux (égale 50) ce qui implique que
les variables entrantes soient ou .
Dans ce cas on calcule le rapport et on prend le plus petit rapport positif puis on choisit le plus grand de
deux ( ) : ( )
8
[Link]/Optimisation linéaire
Donc et =
Etape 4 : Pivotage (LP/P)
L’intersection de la colonne et la ligne donne le pivot (pivot=3)
V.B bi Rapport
6 9
4 3
-300
-350
Donc la solution est : Z=350 avec
Exemple 2 : Soit le PL suivant :
Forme canonique d’un PL : {
Forme standard d’un PL : {
9
[Link]/Optimisation linéaire
VB bi R
7 7/1
9 9/2
0
Les variables entrantes soient ou
VB bi
7
2
-84
Les l’optimum est atteint
Cas 2 égalité des plus petits rapports positifs
Soit le PL suivant :
V.B bi R
7 7/1=7
14 14/2=7
0
7
0
-56
Remarque :
Le plus petit rapport positif, Pivot (1 ou 2) ?
10
[Link]/Optimisation linéaire
∑
pour toutes les
lignes
Cas 3 Solution non borné.
Ce type de problème est rare en pratique.
11
[Link]/Optimisation linéaire
