Définition d’un PL

• Un programme linéaire (PL) est:

– un problème d’optimisation
– consistant à maximiser (ou minimiser) une fonction objectif
linéaire de n variables de décision
– soumises à un ensemble de contraintes exprimées sous
forme d’équations ou d’inéquations linéaires.
• À l’origine, le terme programme a le sens de
planification opérationnelle
• mais il est aujourd’hui employé comme synonyme de
problème (d’optimisation).
• La terminologie est due à Dantzig, inventeur de
l’algorithme du simplexe. 2
Formulation mathématique

3
 Terminologie (1)
• Les variables x1, . . . , xn sont appelées variables
de décision du problème.
• La fonction linéaire à optimiser est appelée
fonction objectif (ou fonction économique ou
fonction de coût).
• Les contraintes prennent la forme d’équations et
d’inéquations linéaires.
• Les contraintes de la forme:

sont appelées des contraintes de bornes.

4
 Terminologie (2)
• Une solution est une affectation de valeurs aux
variables du problème.
• Une solution est admissible si elle satisfait
toutes les contraintes du problème (y compris
les contraintes de bornes).
• La valeur d’une solution est la valeur de la
fonction objectif en cette solution.
• Le domaine admissible D d’un PL est l’ensemble
des solutions admissibles du problème.

5
 Représentation Géométrique
• L’ensemble des solutions d’une inéquation
(linéaire) correspond à un demi-espace
dans IRn (un demi-plan dans IR2).

6
 Représentation graphique des
contraintes d’inégalité
• L’intersection d’un nombre fini de demi-plans est
un ensemble convexe.
• L’ensemble des solutions d’un système
d’équations et d’inéquations (linéaires)
correspond à l’intersection des demi-espaces et
des hyperplans associés à chaque élément du
système.
• Cette intersection, appelée domaine admissible,
est convexe et définit un polyèdre dans IRn (une
région polygonale dans IR2).

7
 Hypothèses de la programmation
Linéaire
• La linéarité des contraintes et de la fonction
objectif.
– L’additivité des effets.
– La proportionnalité des gains/coûts et des
consommations de ressources.
• La divisibilité des variables.
• Lors de la modélisation d’un problème réel,
l’impact de ces hypothèses sur la validité du
modèle mathématique doit être étudié.
• Cette analyse peut mener à choisir un modèle
différent (non linéaire, stochastique, ...) et est
essentielle pour la phase d’interprétation des
résultats fournis par le modèle.
8
 Intérêts de la PL
• Malgré les hypothèses sous-jacentes assez restrictives,
de nombreux problèmes peuvent être modélisés par des
programmes linéaires.
• Exemples
– la gestion de production,
– l’économie,
– la distributique,
– les télécommunications,…
• Il existe des algorithmes généraux (et des codes les
mettant en oeuvre) permettant de résoudre efficacement
des programmes linéaires (même lorsque le nombre de
variables et de contraintes est important).
• Exemple Cplex
9
Exemple de programme linéaire
(en fichier .lp) de CPLEX

10
 Le problème de transport
• On désire acheminer des marchandises de n
dépôts à m points de vente
• On connaît :
– cij , i = 1..n et j = 1..m, coût de transport (i, j),
– Xi, i = 1..n, stocks des dépôts,
– Dj , j = 1..m, niveaux de demande aux points de vente.
• On recherche, pour chaque couple (i, j), la
quantité (positive) xij à transporter du dépôt Xi au
point de vente Dj .

11
 Formulation en PL
• Programme linéaire

Critère: coût total de transport

Demande de
chaque dépôt

Offre de chaque
point de vente

12
 Modélisation d’un problème en PL
• Une usine est Machine Main Profit
d’oeuvre
spécialisée dans la
production de deux P1 2h/unité 3h/unité 25D/unité
produits P1 et P2. P2 2h/unité 2h/unité 20D/unité
• Chaque produit
nécessite total 240 h 140h
– un certain nombre
d’heures de machine
– et un certain nombre Stratégie de production
d’heures de main
d’œuvre. pour maximiser le profit

13
Formulation du programme linéaire
• Variables de décision
– x1: nombre d’unités de produits P1
– x2: nombre d’unités de produits P2
• Fonction objectif:
– z=25x1+15x2
• Contraintes:
– 2x1+2x2≤240
– 3x1+x2≤140
• Contraintes de borne (non négativité des
variables)
– x10 et x2 0

14
 Programme linéaire: forme
canonique
Max Z=f(x1,x2)=25x1+15x2 Formulation matricielle
sc
2x1+2x2≤240  x1 
Max f(x1,x2 )  25 15 
3x1+x2≤140
 x2 
x10 et x2 0
 2 2  x1   240
sous      
 3 1  x2   140
avec x1  0 et x2  0

15
Résolution graphique d’un PL dans
le plan
• Les lignes de niveau de la fonction objectif sont des
droites parallèles dans IR2.
• Il existe des solutions admissibles de valeur z si la ligne
de niveau associée à cette valeur intersecte le domaine
admissible D du problème.
• Pour déterminer la valeur maximale atteignable par une
solution admissible,
– il suffit de faire glisser le plus loin possible une ligne de niveau
de la fonction objectif, dans le sens du gradient, jusqu’à ce
qu’elle touche encore tout juste D.
– Les points de contact ainsi obtenus correspondent aux solutions
optimales du PL.

16
 Exemple de résolution graphique
• Max z = x1 + 4x2
• s.c.
x1 − x2 ≤ 2
2x1 + x2 ≤ 5
x2 ≤ 3
x1 0, x2 0
• de solution optimale :
x1 = 1, x2 = 3 et z = 13.

17
 Exemple: Problème de maximisation
avec des contraintes ≤
1. Transformer le programme en forme standard.
2. Solution initiale à l’origine : tableau initial
– Variables de base et leurs coefficients
– Quantité
– Matrice des coefficients
3. Représenter le tableau simplexe initial à l’origine.
4. Si (j, cj-zj≤0) alors
Retourner la solution optimale (donnée par le dernier tableau)
5. Choisir colonne pivot
6. Choisir ligne pivot
• L’augmentation de x1 est restreinte par deux limites (ratio-test)
• 240/2 limite des heures machines
• 140/3 limite dû à la main d’œuvre
7. Développer un nouveau tableau simplexe
18
 Exemple: Problème de maximisation
avec des contraintes ≤
• Itérations sur les tableaux
– NP: nombre pivot
– LP ligne pivot
– L: ligne de la matrice de coefficients (!=ligne pivot)
– TLP=LP/NP: transformée de la ligne pivot
– aL: coef de la matrice se trouvant à l’intersection de la
ligne transformée (!= ligne pivot) avec la colonne pivot
8. Retour à l’étape 4

19
 Algorithme de simplexe tabulaire
• Si un problème est solvable par la méthode de
simplexe alors
1. Transformer le programme en forme standard.
2. Représenter le tableau simplexe initial à l’origine.
3. Si (j, cj-zj≤0) alors
• Retourner la solution optimale (donnée par le
dernier tableau)
4. Choisir colonne pivot
5. Choisir ligne pivot
6. Développer un nouveau tableau simplexe
7. Revenir à l’étape 3.

20
 Simplexe pour pb de minimisation
avec contraintes 
• Min C=24x1+20x2
• Sc Sc
x1+x2 30 x1+x2-S1+A1=30
x1+2x240 x1+2x2-S2+A2=40
x10 et x20 x10 x20 S10 S20 A10 A20
• Première étape:
– Transformer le problème sous une forme standard
– A l’origine (0,0), x1+x2-S1=30 donne S1=-30
– Non conforme à l’hypothèse de non négativité des variables
d’écart.
– Utiliser une variable artificielle: x1+x2 30  x1+x2-S1+A1=30
– à l’origine x1=0, x2=0, S1=0 A1=30 ,
–  Variable de base
• la solution n’est pas réalisable 21
 – Transformer les inégalités sup en égalité
• Variables d’écart (Si) et des variables artificielles (Ai)

• Les variables d’écart ont un effet nul sur la

fonction objective.
• Les variables artificielles ont un coefficient =M
(contribution unitaire)
– M : un nombre entier positif très élevé pour s’assurer
de son élimination de la base.
• Min C=24x1+20x2+0S1+0S2+MA1+MA2
• Sc
x1+x2-S1+A1=30
x1+2x2-S2+A2=40
x10 x20 S10 S20 A10 A20

22
Application de la méthode simplexe
• Initialement ( à l’origine) A1 et A2 sont les
variables de base
• Sélectionner la variable entrante par
rapport à zj-cj maximal ( cj-zj minimal)

23
 Minimisation avec contraintes
mixtes
• Max Z=4x1+3X2
Sc x1+x2=10
x1 + 3x2≤20
2x1-x215
x10 x20
• Forme standard
• Max Z=4x1+3X2+0S1+0S2-MA1-MA2
Sc x1+ x2 + A1 =10
x1 +3x2 + S1 = 20
2x1 -x2 -S2 +A2 =15
x10, x20 , S10, S20, A10, A20
• On utilise les cj-zj pour critère d’entrée des variables
• Exercice d’application

24
 Cas de quantités négatives
• Simplexe ne s’applique plus
• Se ramener à des quantités positives

25
 Cas d’un problème impossible
• Ensemble des solutions réalisables est vide
• Exemple:
Min x1+x2
Sc x1-x2 1
-x1+x21
x10, x20
• Simplexe:
– Solution optimale avec des variables artificielle non
nulles
• graphiquement

26
 Cas d’une solution infinie
• Pas de solution
• Dans le cas d’un problème de maximisation
– la fonction objectif peut être augmentée indéfiniment
• Exemple
• Max Z=x1+x2
Sc 5x1-x2 10
3x1-x2 ≤9
x1 0, x2 0
• Graphiquement
• Simplexe:
– tous les ratio-tests sont négatifs ou nulles
– la variable entrante n’a pas de limite sur sa valeur d’entrée
27
 Cas de solutions multiples
• Plusieurs solutions mais toutes optimales de même
valeur
– Convexité
• Exemple
– Max z=45x1+15x2 (de pente -3)
Sc 2x1+2x2 ≤240 (de pente -1)
3x1+ X2≤140 (de pente -3)
x10, x20
• Graphiquement
• Simplexe:
– Dans le tableau optimal, l’une des variables hors base admet un
cj-zj nul
– Existence d’autres solutions en entrant cette variable dans la
base.

28
 Dualité
• À tout programme linéaire, on associe un
second PL appelé dual du premier
• Le premier PL est appelé Primal.
• Théorème:
– Si un programme linéaire admet une solution
optimale alors son dual possède également
une solution optimale.
– les valeurs de ces deux solutions sont égales.

29
 Illustration
• Problème primal : Planification de production
• n biens à produire
– xj : quantité de biens j produite
– cj : recette unitaire due au bien j
• Objectif : Maximiser la recette totale
• m ressources à utiliser
– bi : quantité de ressource i disponible
– aij : consommation de ressource i par unité de bien j
produite
• Contraintes : ne pas consommer plus que les
quantités disponibles :
30
• Problème dual : Une autre entreprise
s’intéresse à l’achat de toutes nos ressources
• yi : prix de rachat d’une unité de ressource i
• Objectif : minimiser le prix total de rachat

• Contraintes : assurer que les prix offerts sont

compétitifs pour l’entreprise

31
 Propriétés liées à la dualité

• Le sens d’optimisation est toujours inversé entre un PL

et son dual.
• (primal) PL de max sc ≤ → (dual) PL de min sc 
• Remarque : on transforme le PL en max sc ≤ ou en PL
de min sc  (en multipliant les contraintes par -1).
• Contrainte (Primal) → Variable (Dual)
• Variable (Primal ) → Contrainte (Dual)
• Si un PL a n variables et m contraintes, son dual a m
variables et n contraintes.
• Si (Primal) une contrainte = → la variable associée(Dual)
est sans contrainte de signe.
• Si (Primal) variable sans contrainte de signe → la
contrainte associée (dual) est une =.
• La dualisation est une opération involutive
– le dual du dual est le problème de départ.
32
• A l’optimum
– La valeur de cj-zj pour une variable d’écart du
primal = la valeur de la variable de décision
du dual
– La valeur cj-zj de pour une variable de
décision du primal = la valeur de la variable
d’écart du duale

33
Théorème des écarts complémentaires

34
 Intérêt de la dualité
• Interprétation économique
• Peut être plus facile à résoudre,
– L’une des deux formulations est souvent
avantageuse en complexité de calcul.
• Si l’on nous propose une solution du
primal, pour vérifier son optimalité il suffit
de résoudre le système d’équations (de
variables yi ) qui en découle.

35
 Interprétation économique de la
dualité
• La variable duale associée à une
contrainte correspond au coût de cette
contraintes dans la solution courante
• Si cette contrainte est saturée, ce coût est
positif.
• Il est nul si cette contrainte n’est pas
saturée

36
 Interprétation économique
• Supposons que les contraintes du système:
– Contraintes de stock de matières premières
– Contraintes de main d’œuvre
– Contraintes d’heures machines
• S1=0 et cj-Zj(S1)=-5/6
– Prix qu’on est disposé à payer pour l’achat d’une unité de mat
première supplémentaire
• S2=0 et cj-Zj(S2)=-2/3
– Prix qu’on est disposé à payer pour une unité de main d’œuvre
• S3=80/3
– On n’a pas à payer plus puisqu’on dispose encore de cette
ressource!

37
 Étude de sensibilité
• L’étude du comportement de la solution
optimale d’un PL si on varie ses données.
• Analyse de sensibilité sur les coefficients de
variables dans la fonction objective (les cj).
• Analyse de sensibilité sur le second membre
des contraintes.
• Analyse de sensibilité sur les coefficients de
la matrice des contraintes.

38
Avantage de passer de la forme canonique
à la forme standard
• On obtient immédiatement une solution de
base réalisable qui sert de solution de
départ pour l’algorithme du simplexe.
• Tableau initial :Les variables de base sont
les variables d’écart.

39
 Algorithme de simplexe duale
• Algorithme de simplexe primal:
– Se déplacer d’une solution de base réalisable vers une solution
de base réalisable
– Jusqu’à trouver une solution optimale.
– Il suppose la connaissance d’une solution de base réalisable de
départ
• Algorithme de simplexe dual:
– Se déplacer d’une solution de base non réalisable mais optimale
vers une solution de base non réalisable mais optimale
– Jusqu’à trouver une solution réalisable.
– Il suppose la connaissance d’une solution de départ
• de base non réalisable
• optimale

40
 Algorithme dual (minimisation)
1. Construire une base de départ non réalisable pour laquelle  j :
Zj-cj≤ 0
Multiplier toutes les contraintes par -1.
2. Si  i : bi  0, stop : la solution actuelle est réalisable et
optimale
Sinon aller en 3.
3. Sélectionner une bi < 0, qui a la valeur négative la plus forte
soit br (critère de sortie)
4. Si tous les arj  0, stop : le problème n'admet pas de solution
réalisable
Sinon aller en 5.
5. Pour tous les arj < 0, chercher celui qui réalise le min((Zj-cj)/arj)
(critère d'entrée)
ars qui réalise le minimum devient le pivot. Aller en 6.
6. Effectuer un pivotage simplexe avec ars comme pivot et aller en
2. 41
 Exemple
• min 2000 x1 + 3000 x2 • min 2000 x1 + 3000 x2
1,6 x1 + 0,8 x2  80 • -1,6 x1 - 0,8 x2 ≤ -80
0,2 x1 + 0,4 x2  20 -0,2 x1 - 0,4 x2 ≤- 20
0,1 x1 + 0,1 x2  8 -0,1 x1 - 0,1 x2 ≤- 8
x1 et x2  0 x1 et x2  0

42
br négative
la plus forte

43
44
45
• Le coût optimal est de
180000=2000x60+3000x20
46
 Autres méthodes
• L’algorithme du simplexe n’est pas un
algorithme polynomial pour la programmation
linéaire.
• En 1979, Khachiyan a développé le premier
algorithme polynomial pour la programmation
linéaire : la méthode de l’ellipsoïde.
• En 1984, Karmarkar propose la méthode de
points intérieurs (polynomiale).

47