Programmation Linéaire

Filière : Génie Energétique et Electrique (G2E)

Prof. Mustapha El Moudden

Département : Sciences et Technologies Industrielles (STIN)

Ecole Nationale des Sciences Appliquées d’El Jadida (ENSAJ)
Université Chouaı̈b Doukkali (UCD)

Année Universitaire : 2023–2024

1 / 54
Plan du Cours

1. Modélisation

2. Formes d’un programme linéaire

3. Résolution graphique

4. Méthode du simplexe

5. Dualité en programmation linéaire

2 / 54
Section 1 : Modélisation

3 / 54
Problème de production

Example
• Un fabricant produit 2 types de yaourts A et B à partir de Fraise, de Lait et de
Sucre. Chaque yaourt doit respecter les proportions suivantes de matières premières :
Yaourt A Yaourt B
Fraise 2 1
Lait 1 2
Sucre 0 1
• On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre.
• La vente de 1 Kg de yaourts A et B rapporte respectivement 4$ et 5$.
• Le fabricant cherche à maximiser son profit.

4 / 54
Modélisation

Modélisation :
• Sur quelles quantités peut-on travailler ?

• Que cherche-t-on à optimiser ?

• Quelles sont les contraintes du problème ?

5 / 54
Modélisation

Modélisation :
• Sur quelles quantités peut-on travailler ?
- Les quantités de yaourts A et B produites
- On parle de variables
- On les notera xA et xB

• Que cherche-t-on à optimiser ?

• Quelles sont les contraintes du problème ?

6 / 54
Modélisation

Modélisation :
• Sur quelles quantités peut-on travailler ?

• Que cherche-t-on à optimiser ?

- Le profit z à maximiser
- Calculé à partir de xA et xB
- On parle de fonction objectif ou économique
- z = 4xA + 5xB

• Quelles sont les contraintes du problème ?

6 / 54
Modélisation

Modélisation :
• Sur quelles quantités peut-on travailler ?

• Que cherche-t-on à optimiser ?

• Quelles sont les contraintes du problème ?

- Première contrainte : 800 Kg de fraises disponibles
- La quantité utilisée dépend de la production : 2xA + xB
- Donc 2xA + xB ⩽ 800

6 / 54
Modélisation
Modélisation :
• Sur quelles quantités peut-on travailler ?
variables : xA et xB

• Que cherche-t-on à optimiser ?

max z = 4xA + 5xB

• Quelles sont les contraintes du problème ?

2xA + xB ⩽ 800 (fraises)

xA + 2xB ⩽ 700 (lait)
xB ⩽ 300 (sucre)
xA , xB ⩾ 0 (positivité)

7 / 54
Modélisation : Programme linéaire

Notre programme linéaire est :

max z = 4xA + 5xB

s.c. 2xA + xB ⩽ 800
xA + 2xB ⩽ 700
xB ⩽ 300
xA , xB ⩾ 0.

8 / 54
Section 2 : Formes d’un programme linéaire

9 / 54
Forme générale d’un programme linéaire
La forme générale d’un programme linéaire s’écrit :

X n
max/min z = cj xj (1)







 j=1
Xn ⩽
s.c. ai,j j = bi , i = 1, 2, · · · , m (2)
x



⩾



 j=1
j = 1, 2, · · · , n (3)

xj ⩾ 0,

(1) La fonction objectif (ou économique) à optimiser. Ex : Il s’agit de maximiser (max)

dans le cas d’un profit ou de minimiser (min) dans le cas d’une perte ou d’un coût.
(2) Les inégalités et/ou égalités (équations et/ou inéquations) qui définissent les
contraintes économiques.
(3) Les contraintes de positivité.
10 / 54
Solutions réalisable et optimale

Définitions :
• On appelle solution réalisable tout n-uplet (x1 , · · · , xn ) vérifiant les contraintes.
• On appelle solution optimale toute solution réalisable qui optimise la fonction
objectif.
• L’ensemble des solutions réalisables d’un programme linéaire est appelé domaine
réalisable.
Lorsque ce domaine est non vide, on dit que le PL est réalisable.

11 / 54
Forme matricielle d’un programme linéaire
– Notations :
x = (x1 , x2 , · · · , xn )⊤ ∈ Rn×1 , c = (c1 , c2 , · · · , cn ) ∈ R1×n
A = (ai,j ) ∈ Rm×n , b = (b1 , b2 , · · · , bm )⊤ ∈ Rn×1

– Les deux formes matricielles suivantes sont utilisées :

• Forme canonique : (utilisée lors de la résolution graphique)
max z = c ⊤x (max ou min)
s.c. Ax ⩽ b
x ⩾ 0.
• Forme standard : (utilisée lors de la résolution algébrique)
max z = c ⊤x (max ou min)
s.c. Ax = b
x ⩾ 0.
12 / 54
Adaptation au forme standard
• min z = − max(−z)

• Si xi de signe quelconque, on écrit xi = xi+ − xi− , avec xi+ ⩾ 0 et xi− ⩾ 0.

Pn
• Si j=1 aij xj
⩽ bi , il y a deux cas :
⋆ bi ⩾ 0 : on écrit nj=1 aij xj + si = bi , si ⩾ 0. (si : variable d’écart)
P
⋆ bi < 0 : on multiplie l’inégalité par −1, pour se ramener au cas développé
ci-dessous.
Pn
• Si j=1 aij xj ⩾ bi , il y a deux cas :
⋆ bi ⩽ 0 : on multiplie l’inégalité par −1, pour se ramener au cas développé
précédemment.
⋆ bi > 0 : on écrit nj=1 aij xj − ti = bi , ti ⩾ 0. (ti : variable artificielle)
P

13 / 54
Adaptation au forme standard
Example
Étant donné le programme linéaire suivant :


 min −x1 +x2
s.c. −2x1 +x2 ⩾ 3


 x1 +x2 ⩽ 1
x1 ⩾ 0 et x2 qlq.


• La variable x2 de signe qlq, donc on introduit deux variables positives x21 et x22 , avec
x2 = x21 − x22 .
• Le problème prend alors la forme suivante :
x1 −x21 +x22

 max
s.c. −2x1 +x21 −x22 −x3

=3

1
x1 +x2 −x2 2 +x4 = 1


x1 , x21 , x22 , x3 , x4 ⩾ 0

14 / 54
Section 3 : Résolution graphique

15 / 54
Résolution graphique
• On considère le programme linéaire sous forme canonique suivant :

 min / max z = c ⊤ x


(P) s.c. Ax ⩽ b
x ⩾0


• On note X le polyèdre associé aux contraintes :

X = {x ∈ Rn | Ax ⩽ b, x ⩾ 0}.

Théorème :
Si le problème (P) admet une solution optimale, alors l’optimum (minimum ou
maximum) est atteint en un sommet du polyèdre X .

16 / 54
Utilisation et Principe

Utilisation :
La méthode graphique est une méthode simple et s’applique à des problèmes de
programmation linéaire à deux variables.

Principe de la méthode :
• Consiste à dessiner le polyèdre convexe représentant l’ensemble des contraintes et à
parcourir les sommets jusqu’à trouver celui qui optimise la fonction objectif.
• Les contraintes économiques et de signe sont représentées graphiquement par des
demi-plans dont l’intersection est un ensemble convexe.
• Les solutions, si elles existent, appartiennent donc à l’ensemble des solutions
réalisables.

17 / 54
Étapes
Étapes :
• Créer un système de coordonnées cartésiennes, dans lequel chaque variable de
décision est représentée par un axe.
• Dessiner les contraintes du problème.
Une inéquation précise une région qui sera le demi-plan limité par la ligne droite
obtenue en considérant la contrainte comme égalité.
L’intersection de toutes les régions détermine le domaine réalisable (qui est un
ensemble convexe).
• Déterminer les sommets du polygone qui forme le domaine réalisable.
Ces points seront les candidats à la solution optimale.
• Chercher la direction de diminution (augmentation) de la valeur de z, et déplacer
parallèlement la droite de la fonction objectif suivant cette direction jusqu’au dernier
sommet de la région.
Ce sommet représente solution optimale. 18 / 54
Exemple

Example
Considérons le programme linéaire suivant :


 max 3x1 +2x2
 s.c. 2x1 +x2 ⩽ 18


2x1 +3x2 ⩽ 42
3x1 +x2 ⩽ 24




x1 , x2 ⩾ 0


Résoudre graphiquement ce programme linéaire.

19 / 54
Exemple (cont.)

20 / 54
Exemple (cont.)
• Les sommets de l’ensemble réalisable (du polygone ABCDE) et les valeurs
correspondantes de la fonction objectif z = 3x1 + 2x2 :
Sommet Coordonnées (x1 , x2 ) Valeur de z
A (0,0) 0
B (0,14) 28
C (3,12) 33
D (6,6) 30
E (8,0) 24

• Le point C fournit la plus grande valeur à la fonction z et l’objectif c’est de

maximiser. Donc ce point représente la solution optimale :

z = 33 et (x1 , x2 ) = (3, 12).

21 / 54
Exercice

Exercice :
Considérons le programme linéaire suivant :

 min x1 − x2

s.c. 2x1 + x2 ⩾ 2


 x1 + 3x2 ⩽ 5
x1 ⩾ 0, x2 ⩾ 0


Résoudre ce problème en utilisant la méthode graphique.

22 / 54
Exercice (cont.)

23 / 54
Section 4 : Méthode du simplexe

24 / 54
Principes
• La résolution par la méthode du simplexe utilise la forme standard :
 max z = c ⊤ x

(max ou min)
(P) s.c. Ax = b
x ⩾0


où x ∈ Rn , c ∈ Rn , b ∈ Rm et A ∈ Rm×n avec m ⩽ n et rang(A) = m.

• Soit X := {x ∈ Rn | Ax = b, x ⩾ 0} .
Définitions :
• L’ensemble des indices B est appelé base de A si la matrice AB , extraite de A, est
inversible.
• Soit B une base de A. On partitionne la matrice A, les vecteurs x et c sous la forme :

A = (AB , AN ) , x = (xB , xN )⊤ , c = (cB , cN )⊤

xB ∈ Rm sont des variables de base et xN ∈ Rn−m sont des variables hors base.
25 / 54
Principes (cont.)
Example
Si la matrice A est donnée par :
 
1 2 2 1 3
A= 2 1 0 5 1 
2 0 1 4 3

et l’ensemble d’indices B est donné par B = {1, 3, 4} (les colonnes 1, 3, et 4 de A).

• Alors N = {2, 5}. Dans ce cas m = 3, et la matrice AB est donnée par :
 
1 2 1
AB =  2 0 5  et det (AB ) = 29 ̸= 0
2 1 4
• Donc AB est inversible, ainsi B = {1, 3, 4} est une base. De plus xB = (x1 , x3 , x4 )⊤
sont les variables de base, et xN = (x2 , x5 )⊤ sont les variables hors-base.
26 / 54
Principes (cont.)
• On suppose, pour faciliter la présentation, que les colonnes de bases sont les m
premières colonnes. On a donc :
Ax = b ⇐⇒ AB xB + AN xN = b
⇐⇒ xB = A−1 −1
B b − AB AN xN .

Définitions :
• La solution x = (xB , xN )⊤ du système Ax = b obtenue en posant xB := A−1
B b et
xN := 0 est appelée solution de base.
• De plus, on dit que x est une solution de base réalisable si A−1
B b ⩾ 0.

Théorème (Identification des sommets) :

Toute solution de base x = (xB , xN )⊤ telle que xB := A−1
B b et xN := 0 est un sommet du
polytope X .
27 / 54
Principes (cont.)
• Ainsi, on écrit :
c ⊤ x = cB⊤ xB + cN⊤ xN = cB⊤ A−1 −1 ⊤


B b − AB AN xN + cN xN
 
= cB⊤ A−1
B b + c ⊤
N − c ⊤ −1
A
B B AN xN

Définitions :
• Le vecteur c̄N⊤ := cN⊤ − cB⊤ A−1
B AN est appelé vecteur des coûts réduits.
• Le problème (P) s’écrit sous la forme (appelée forme canonique dans la base B) :
−1
 max z = cB⊤ AB b + c̄N⊤ xN

(max ou min)
−1 −1
s.c. xB = AB b − AB AN xN
xB , xN ⩾ 0


Théorème d’optimalité :
Soit x une solution de base réalisable. Si c̄N ⩽ 0, alors x est optimale.
28 / 54
Algorithme du simplexe
Étape 0. Choisir une base réalisable B et poser k = 0.
Étape 1. A l’itération k, on a une base B et la solution de base correspondante

⊤
x = A−1 B b, 0 . Calculer b̄ = A−1 ⊤ ⊤ −1
B b et c̄N = cN − cB AB AN .
Étape 2. Si c̄N ⩽ 0, Stop; le maximum est atteint. Sinon, calculer
n o
c̄j := max c̄k | c̄k > 0
k∈N

Soit aj la colonne de A d’indice j. Calculer āj := A−1B aj .

• Si āj ⩽ 0, Stop; le maximum égal à +∞.
• Sinon, calculer  
b̄i b̄k
:= min | ākj > 0
āij k∈B ākj

Étape 3. La variable xj rentre en base, et la variable xi sort de la base. On construit

ensuite la nouvelle base réalisable en faisant le pivotage.
Étape 4. Faire k ←− k + 1 et retourner à l’Étape 1.
29 / 54
Tableau du simplexe
• On écrit le problème sous forme canonique dans la base B :
−1
 max z = z̄ + c̄N⊤ xN
 
 b̄ = AB b
−1 ⊤
s.c. xB = b̄ − AB AN xN avec z̄ = c b̄
 ⊤ B⊤
xB , xN ⩾ 0 c̄N = cN − cB⊤ A−1
B AN


 xB = b̄
• La solution de base associée à B est : x =0
 N
z = z̄
• On peut représenter le programme précédent par le tableau (appelé tableau du
simplexe) :
x SB
−1
xB AB A b̄
−z c̄ ⊤ −z̄
où c̄ ⊤ = (c̄B , c̄N ) avec : c̄B = 0 et c̄N⊤ = cN⊤ − cB⊤ A−1
B AN , et −z̄ est l’opposé du coût.
30 / 54
Application
Example
Considérons le programme linéaire suivant :


 max z = 20x1 + 25x2
s.c. 2x1 + 3x2 ⩽ 40


 4x1 + 2x2 ⩽ 48
x1 , x2 ⩾ 0


Attention : Simplexe exige toujours d’écrire le PL sous forme standard.

• On écrit le programme linéaire sous forme standard, en introduisant les variables
d’écart x3 , x4 ⩾ 0 : 

 max z = 20x1 + 25x2
s.c. 2x1 + 3x2 + x3 = 40


 4x1 + 2x2 + x4 = 48
x1 , x2 , x3 , x4 ⩾ 0

31 / 54
Application (cont.)

• On considère B = {3, 4}, la sous-matrice de A d’ordre 2 réduite aux colonnes 3 et 4

(les indices de B) est  
1 0
AB = ,
0 1
c’est une matrice identité d’ordre 2, ainsi elle est inversible. B est donc une base.
Les variables de base sont {x3 , x4 }, et les variables hors-base sont {x1 , x2 }.
• Ainsi  
40
A−1
B b =b = ⩾0
48
Donc B est une base réalisable et la solution de base réalisable est (0, 0, 40, 48).
• Alors on va commencer à tracer le premier tableau de simplexe.

32 / 54
Application (cont.)
• Le 1er tableau du simplexe :
x1 x2 x3 x4
x3 2 3 1 0 40
x4 4 2 0 1 48
20 25 0 0 0
• On cherche la variable qui va entrer en base :
x1 x2 x3 x4
x3 2 3 1 0 40
x4 4 2 0 1 48
20 25 0 0 0
On a c̄N⊤ = (20, 25) ⩽̸ 0. La solution de base n’est pas optimale : il y a des coûts
réduits positifs. On va choisir 25 le plus positif1 . Donc, la variable x2 va entrer en
base.
1
Règle de Dantzig, mais on peut choisir 20 et on va arriver à la même solution optimale vers la fin.
33 / 54
Application (cont.)
• On cherche la variable qui va sortir de base :

40 ÷ 3 = 40/3
48 ÷ 2 = 24

On choisit la variable qui correspond au plus petit quotient, dans ce cas, la variable
x4 .
x1 x2 x3 x4
x3 2 3 1 0 40
x4 4 2 0 1 48
20 25 0 0 0
L’intersection de la colonne de variable qui entre en base x2 et la ligne de variable qui
sort de base x3 est appelé le pivot ā32 = 3 (élément en jaune).
34 / 54
Application (cont.)

Règles de pivotage :
• Dans la 1ère ligne, on remplace x3 par x2 (et on garde x4 )
• Les coefficients de la ligne du pivot sont divisés par le pivot.
• Les coefficients de la colonne du pivot (sauf le pivot) sont nuls.
• Si la ligne de pivot rencontre une colonne en un 0, alors la colonne est inchangée.
• Si une ligne rencontre la colonne de pivot en un 0, alors la ligne est inchangée.

x1 x2 x3 x4
x2 . . . . .
x4 . . . . .
. . . . .

35 / 54
Application (cont.)

Règles de pivotage :
• Dans la 1ère ligne, on remplace x3 par x2 (et on garde x4 )
• Les coefficients de la ligne du pivot sont divisés par le pivot.
• Les coefficients de la colonne du pivot (sauf le pivot) sont nuls.
• Si la ligne de pivot rencontre une colonne en un 0, alors la colonne est inchangée.
• Si une ligne rencontre la colonne de pivot en un 0, alors la ligne est inchangée.

x1 x2 x3 x4
x2 2/3 1 1/3 0 40/3
x4 . . . . .
. . . . .

35 / 54
Application (cont.)

Règles de pivotage :
• Dans la 1ère ligne, on remplace x3 par x2 (et on garde x4 )
• Les coefficients de la ligne du pivot sont divisés par le pivot.
• Les coefficients de la colonne du pivot (sauf le pivot) sont nuls.
• Si la ligne de pivot rencontre une colonne en un 0, alors la colonne est inchangée.
• Si une ligne rencontre la colonne de pivot en un 0, alors la ligne est inchangée.

x1 x2 x3 x4
x2 2/3 1 1/3 0 40/3
x4 . 0 . . .
. 0 . . .

35 / 54
Application (cont.)

Règles de pivotage :
• Dans la 1ère ligne, on remplace x3 par x2 (et on garde x4 )
• Les coefficients de la ligne du pivot sont divisés par le pivot.
• Les coefficients de la colonne du pivot (sauf le pivot) sont nuls.
• Si la ligne de pivot rencontre une colonne en un 0, alors la colonne est inchangée.
• Si une ligne rencontre la colonne de pivot en un 0, alors la ligne est inchangée.

x1 x2 x3 x4
x2 2/3 1 1/3 0 40/3
x4 . 0 . 1 .
. 0 . 0 .

35 / 54
Application (cont.)
Règles de pivotage :
• Les autres coefficients sont obtenus par la règle :
 
CPivot × LPivot
EC −
Pivot
avec
EC : élément concerné
CPivot: élément de la colonne du pivot
LPivot: élément de la ligne du pivot

x1 x2 x3 x4
x2 2/3 1 1/3 0 40/3
x4 . 0 . 1 .
. 0 . 0 . 36 / 54
Application (cont.)
Règles de pivotage :
• Les autres coefficients sont obtenus par la règle :
 
CPivot × LPivot
EC −
Pivot
avec
EC : élément concerné
CPivot: élément de la colonne du pivot
LPivot: élément de la ligne du pivot

x1 x2 x3 x4
x2 2/3 1 1/3 0 40/3
x4 8/3 0 −2/3 1 64/3
10/3 0 −25/3 0 −1000/3 36 / 54
Application (cont.)
• On suit les mêmes étapes précédentes :
x1 x2 x3 x4 quotient
x2 2/3 1 1/3 0 40/3 40/3 ÷ 2/3 = 20
x4 8/3 0 −2/3 1 64/3 64/3 ÷ 8/3 = 8
10/3 0 −25/3 0 −1000/3
La variable x1 entre en base et x4 sort de base.
• D’après les opérations de pivotage on obtient le 3ème tableau du simplexe :
x1 x2 x3 x4
x2 0 1 1/2 −1/4 8
x1 1 0 −1/4 3/8 8
0 0 −15/2 −5/4 −360
• On a c̄N = (−15/2, −5/4) ⩽ 0, la solution est donc optimale :
x = (8, 8, 0, 0) et z = 360.
37 / 54
Application (cont.)

• La solution de notre problème de départ est :

   
x1 8
=
x2 8

et sa valeur maximale est égale à z = 360.

38 / 54
Cas divergent
Example
Considérons le programme linéaire suivant :


 max z = 2x1 + x2
s.c. x1 − x2 ⩽ 10


 x1 − 3x2 ⩽ 5
x1 , x2 ⩾ 0


• On écrit le programme linéaire sous forme standard, en introduisant les variables

d’écart x3 , x4 ⩾ 0 : 

 max z = 2x1 + x2
s.c. x1 − x2 + x3 = 10


 x1 − 3x2 + x4 = 5
x1 , x2 , x3 , x4 ⩾ 0


39 / 54
Cas divergent (cont.)
• Le tableau initial du simplexe :
x1 x2 x3 x4
x3 1 −1 1 0 10
x4 1 −3 0 1 5
2 1 0 0 0
Les variables de base sont {x3 , x4 } et la solution de base est (0, 0, 10, 5).
• On choisit la variable avec le plus grand coût réduit comme variable entrante (x1
dans notre cas). Le plus petit quotient est 5 qui correspond à la variable x4 (la
variable sortante) :
x1 x2 x3 x4 quotient
x3 1 −1 1 0 10 10 ÷ 1 = 10
x4 1 −3 0 1 5 5÷1=5
2 1 0 0 0
Les variables de base deviennent {x3 , x1 }. 40 / 54
Cas divergent (cont.)
• D’après les opérations de pivotage, on obtient le 2ème tableau du simplexe :
x1 x2 x3 x4 quotient
x3 0 2 1 −1 5 5 ÷ 2 = 5/2
x1 1 -3 0 1 5
0 7 0 −2 -10
On choisit la variable avec le plus grand coût réduit > 0 comme variable entrante (x2
dans notre cas). Le seul ratio > 0 correspond à la variable x3 .
• D’après les opérations de pivotage, on obtient le 3ème tableau:
x1 x2 x3 x4
x2 0 1 1/2 −1/2 5/2
x1 1 0 3/2 −1/2 25/2
0 0 −7/2 1/2 −55/2
Dans notre cas, le coût réduit 1/2 > 0 et les ratios sont tous < 0. Alors on est
devant un problème non borné.
41 / 54
Section 5 : Dualité en programmation linéaire

42 / 54
Problème dual
Définition :
Soient A ∈ Rm×n , b ∈ Rm , c ∈ Rn et x ∈ Rn , y ∈ Rm .
A tout programme linéaire P (”dit primal”), on associe un programme linéaire D (”dit
dual”) :
 max z(x) = c ⊤ x w (y ) = b ⊤ y
 
 min
(P) s.c. Ax ⩽ b (D) s.c. A⊤ y ⩾ c
x ⩾0 y ⩾0
 

z(x) = c ⊤ x  max w (y ) = b ⊤ y
 
 min
(P) s.c. Ax ⩾ b (D) s.c. A⊤ y ⩽ c
x ⩾0 y ⩾0
 

Théorème :
Le dual du dual est le primal.
43 / 54
Écriture du programme dual
• Le tableau suivant donne des règles permettant de passer d’un programme linéaire
général à son problème dual :
Primal Dual
max z min w

variable xj ⩾ 0 contrainte j est ⩾

variable xj ⩽ 0 contrainte j est ⩽
variable xj ∈ R contrainte j est =

contrainte i est ⩾ variable yi ⩽ 0

contrainte i est ⩽ variable yi ⩾ 0
contrainte i est = variable yi ∈ R

44 / 54
Écriture du programme dual (cont.)
Example
On considère le programme linéaire suivant :


 max −2x1 + x2 + 3x3
 s.c. 2x1 + x2 − x2 ⩽ 8


(P) −x1 + x3 ⩾ 1
x1 + 2x2 + 3x3 = 9




x1 ⩾ 0, x2 ⩾ 0, x3 qlq


• Déterminons la matrice A, et les vecteurs c et b :

     
−2 2 1 −1 8
c =  1  , A =  −1 0 1 , b= 1 
3 1 2 3 9

45 / 54
Écriture du programme dual (cont.)
• Pour la fonction objectif, on a :

max c ⊤ x −→ min b ⊤ y = 8y1 + y2 + 9y3

• Pour les contraintes, on a :

    
2 −1 1 y1 2y1 − y2 + y2
A⊤ y =  1 0 2   y2  =  y1 + 0y2 + 2y3 
−1 1 3 y3 −y1 + y2 + 3y3

Donc, on obtient

x1 ⩾ 0 −→ 2y1 − y2 + y2 ⩾ −2
x2 ⩾ 0 −→ y1 + 0y2 + 2y3 ⩾ 1
x3 qlq −→ −y1 + y2 + 3y3 = 3

46 / 54
Écriture du programme dual (cont.)
• Pour les contraintes de signe, on a :

1ère contrainte ⩽ −→ y1 ⩾ 0
2ème contrainte ⩾ −→ y2 ⩽ 0
3ème contrainte = −→ y3 qlq

• Le problème dual s’écrit donc comme suit :



 min 8y1 + y2 + 9y3
s.c. 2y1 − y2 + y2 ⩾ −2



(D) y1 + 0y2 + 2y3 ⩾ 1
−y 1 + y2 + 3y3 = 3




y1 ⩾ 0, y2 ⩽ 0, y3 qlq


47 / 54
Théorèmes de dualité
Théorème (faible de dualité) :
Soient x une solution réalisable d’un problème linéaire (P) et y une solution réalisable du
problème dual (D) associé à (P). Alors :
• z(x) ⩽ w (y )
• Si z(x) = w (y ) alors x et y sont des solutions optimales de (P) et (D)
respectivement.

Théorème (fort de dualité) :

Si le problème primal (P) admet une solution réalisable optimale x, alors le problème dual
(D) admet lui aussi une solution réalisable optimale y et de plus on a :

z(x) = w (y ).

48 / 54
Exercice
Exercice (Programmation linéaire) :
On considère le programme linéaire suivant :


 max x1 + 3x2
 s.c. x1 + x2 ⩽ 14


−2x1 + 3x2 ⩽ 12
2x1 − x2 ⩽ 12




x1 , x2 ⩾ 0


1. Résoudre le problème en utilisant la méthode graphique.

(On prendra comme unité 1 unité = 1 cm).
2. Écrire le programme linéaire sous forme standard.
3. Résoudre le problème en utilisant la méthode des tableaux.
49 / 54
Exercice (cont.)
• On écrit le programme linéaire sous forme standard, en introduisant les variables
d’écart x3 , x4 , x5 ⩾ 0: 

 max x1 + 3x2
 s.c. x1 + x2 + x3 = 14


−2x1 + 3x2 + x4 = 12
2x 1 − x2 + x5 = 12




x1 , x2 , x3 , x4 , x5 ⩾ 0


• On considère B = {3, 4, 5}, la matrice de base est : AB = I3 , c’est une matrice

inversible. Donc B est une base. Les variables de base sont {x3 , x4 , x5 }, et les
variables hors-base sont {x1 , x2 }. Ainsi
 
14
A−1
B b =b =
 12  ⩾ 0
12
B est une base réalisable et la solution de base réalisable est : (0, 0, 0, 14, 12, 12).
50 / 54
Exercice (cont.)
• Le tableau initial est alors :
x1 x2 x3 x4 x5 ratio
x3 1 1 1 0 0 14 14 ÷ 1 = 14
x4 −2 3 0 1 0 12 12 ÷ 3 = 4
x5 2 −1 0 0 1 12
1 3 0 0 0 0
On choisit la variable avec le plus grand coût réduit comme variable entrante (x2
dans notre cas). Le plus petit ratio est 4 qui correspond à la variable x4 (la variable
sortante).
• D’après les opérations de pivotage, on obtient le 2ème tableau :
x1 x2 x3 x4 x5
x3 5/3 0 1 1/3 0 10
x2 −2/3 1 0 1/3 0 4
x5 4/3 0 0 1/3 1 16
3 0 0 −1 0 −12 51 / 54
Exercice (cont.)
x1 x2 x3 x4 x5 ratio
x3 5/3 0 1 1/3 0 10 10 ÷ 5/3 = 6
x2 −2/3 1 0 1/3 0 4
x5 4/3 0 0 1/3 1 16 16 ÷ 4/3 = 12
3 0 0 −1 0 −12
• On choisit la variable avec le coût réduit > 0 comme variable entrante (x1 dans notre
cas). Le plus petit ratio est 6 qui correspond à la variable x3 (la variable sortante).
• D’après les opérations de pivotage, on obtient le 3ème tableau :
x1 x2 x3 x4 x5
x1 1 0 3/5 1/5 0 6
x2 0 1 2/5 7/15 0 8
x5 0 0 −4/5 −1/15 1 8
0 0 −9/5 −8/5 0 −30
• On arrête car c̄N ⩽ 0 et on a l’optimum : x1 = 6, x2 = 8, x5 = 8 et x3 = x4 = 0
puisqu’ils sont hors base. En ce point la valeur de z est 30. 52 / 54
La Fin

53 / 54