1

Chapitre 2Programmation Linéaire

Master Informatique Décisionnelle et Intelligence appliquée à la gestion

Hend BouziriMaître Assistant, ESSEC de Tunis

LARODEC ISGLaboratoire de Recherche Opérationnelle, de DEcision et de

Contrôle de processus

2

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.

3

Formulation mathématique

4

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.

5

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.

6

L’ensemble des solutions d’une équation (linéaire) correspond à:

7

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).

8

9

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 polyhèdre dans IRn (une région polygonale dans IR2).

10

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.

11

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

12

Exemple de programme linéaire (en fichier .lp) de CPLEX

13

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 .

14

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

15

Modélisation d’un problème en PL

• Une usine est spécialisée dans la production de deux produits P1 et P2.

• Chaque produit nécessite – un certain nombre

d’heures de machine – et un certain nombre

d’heures de main d’œuvre.

Stratégie de production pour maximiser le profit ?

machine Main d'oeuvre Profit

P1 2h/unité 3h/unité 25DT/unité

P2 2h/unité 1h/unité 15DT/unité

total 240 140

16

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

17

Programme linéaire: forme canonique

Max Z=f(x1,x2)=25x1+15x2

sc2x1+2x2≤240

3x1+x2≤140

x1≥0 et x2≥ 0

Formulation matricielle

Max f ( x1 ,x 2 )=( 25 15 ) (x1

x2)

sous (2 23 1 )(x1

x2)≤(240

140 )avec x1≥0 et x2≥0

18

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.

19

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.

20

Algorithme de simplexe

● Transformer le modèle sous forme standard :

● S1 : valeur d'heures machines non utilisées● S2 : valeur d'heures mains d'oeuves non utilisées

Max Z=f(x1,x2)=25x1+15x2+0 S1+0 S2

sc2x1+2x2+S1=240

3x1+x2+S2=140

x1≥0 et x2≥ 0

21

Définitions

● La variable d'écart est la quantité qui ajoutée au membre gauche d'une contrainte, permet de transformer la contrainte en égalité.

● Dans le modèle, on dispose de n+m variables.● On appelle variables hors base les variables fixées à

0. Les variables restantes sont dites de base.● Une solution de base réalisable est une solution de

base qui en plus vérifie les contraintes de positivité.● Graphiquement un sommet du polygne correspond à

une solution de base réalisable

22

Algorithme de simplexe

● Idée : se déplacer d'une solution de base réalisable vers une autre qui lui est adjacente.

● Comment choisir le point de départ ?● Le point d'origine : (x1=0, x2=0, S1=240, S2= 140) : la

base● Se déplacer vers une autre extrémité du polygone :

● Choisir la variable avec le coef objectif le plus élevé.● D'où le sens de déplacement.

23

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.

24

Algorithme de simplexe tabulaire

• Si un problème est solvable par la méthode de simplexe alors

• Transformer le programme en forme standard.

• (*)Représenter le tableau simplexe initial à l’origine.

– Variables de bases

– Quantité

– Matrice des coefficients Si (∀j, cj-zj≤0) alors

Retourner la solution optimale (donnée par le dernier tableau) Choisir colonne pivot (variable entrante à la base) Choisir ligne pivot (variable sortante de la base) Développer un nouveau tableau simplexe (VB, Qté, Matrice des

coefs) Revenir à l'étape (*)

25

Algorithme de simplexe tabulaire

• 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

26

Simplexe pour pb de minimisation avec contraintes ≥

• Min C=24x1+20x2

• Scx1+x2 ≥30x1+2x2≥40x1≥0 et x2≥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

Sc x1+x2-S1+A1=30

x1+2x2-S2+A2=40

x1≥0 x2≥0 S1≥0 S2≥0 A1≥0 A2≥0

27

– 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 – 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

• Scx1+x2-S1+A1=30 x1+2x2-S2+A2=40x1≥0 x2≥0 S1≥0 S2≥0 A1≥0 A2≥0

28

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)

29

Maximisation 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

•

30

Cas de quantités négatives

• Simplexe ne s’applique plus

• Se ramener à des quantités positives• Exemple

• x1+x2≥-8 devient -x1-x2≤8

31

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 artificielles non

nulles

• graphiquement

32

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 ≥103x1-x2 ≤9x1≥ 0, x2 ≥0

• Graphiquement • Simplexe:

– tous les ratio-tests sont négatifs ou nuls – la variable entrante n’a pas de limite sur sa valeur d’entrée

33

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.

34

35

É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.

36

Analyse de sensiblité sur les cj

37

Analyse de sensibilité sur les bi

38

Autres méthodes• Simplexe : se déplace de point extrême en point

extrême le long de la frontière du polyèdre. Il y a un nombre fini de points extrêmes– 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.– Impact théorique important, mais performances pratiques

mauvaises.

• En 1984, Karmarkar propose les méthodes de points intérieurs : polynomiales et efficaces en pratique sur des problèmes creux de grande taille.