Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Recherche opérationnelle

Programmation linéaire
La recherche opérationnelle
La recherche opérationnelle (ou en abrégé RO) est la discipline
Pr. LAKHBAB des méthodes scientiques, telles que les mathématiques ou encore
[email protected]
l'informatique utilisables pour élaborer de meilleures décisions.
Faculté des Sciences Aïn Chock
2024-2025

Recherche Opérationnelle
Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Recherche opérationnelle - Optimisation

La modélisation
Pour un problème donné, on a besoin d'identier une fonction
objectif , qui sert pour déterminer la meilleure solution à un
1

La Recherche Opérationnelle n'a pas pour but de prendre des problème d'optimisation.
décisions, mais de clarier le contexte dans lequel ces décisions sont La fonction objectif dépend de quelques paramètres sur
prises en proposant des outils d'optimisation. lesquels on peut agir pour faire évoluer le système considéré :
2

L'optimisation
ces paramètres sont appelés : variables de décision.
est une discipline mathématique qui, bien qu'omniprésente depuis Et en n, on décrit les contraintes imposées aux variables de
décisions.
3

les origines, a pleinement pris son essor au cours du XXe siècle.

Optimiser c'est choisir parmi plusieurs possibilités celle qui répond
le mieux à certains critères. Un problème d'optimisation consiste alors à déterminer les variables
de décision conduisant aux meilleures conditions de fonctionnement
du système (ce qui revient à minimiser ou maximiser la fonction
objectif).
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Algorithme Problème d'optimisation : formulation et dénitions

Soient n un entier strictement positif, D ⊂ R un sous-ensemble n

Une fois le model est formulé, on élabore un algorithme non vide, et f : D −→ R une application sur D à valeurs réelles.
permettant de chercher la solution. La forme générale d'un problème d'optimisation est donnée par
Un algorithme est une suite nie d'opérations (élémentaires) qui, min f (x) ou max f (x) (1)
à partir de données, conduit à la solution d'un problème. x∈D x∈D

Le choix d'un tel algorithme est basé sur ces avantages, en coût est la variable de décision,
calculatoire et de sa supériorité par rapport aux implémentations x = (x1 , . . . , xn )T
l'ensemble D est le domaine admissible ou réalisable,
temporelles.
et f est la fonction objectif (appelée aussi : fonction coût ou
fonction économique).

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Dénition
⋆ Un minimum (ou minimum global) de f sur D est un point Terminologies
x∗ ∈ D , tel que
f (x ∗ ) ≤ f (x) ∀x ∈ D (2) : aectation des valeurs aux variables.
Solution
⋆ Lorsque l'inégalité (2) est stricte, on parlera de minimum strict. : solution pour laquelle toutes les
Solution réalisable
⋆ x est dit minimum local, si l'inégalité (2) est vériée sur un
∗ contraintes sont satisfaites.
voisinage V de x , avec V ⊂ D .
∗
Domaine réalisable : ensemble des solutions réalisables.
Une solution non réalisable est une solution pour la quelle une
Remarque
Les notions de maximum local et global sont dénies de façon tout des contraintes est violée.
à fait similaire. En fait, on peut facilement démontrer que les Solution optimale : solution réalisable qu'optimise (maximise
problèmes : ou minimise) la fonction objectif.
min f (x) et max f (x)
Remarques
sont équivalents dans le sens où ils ont même ensemble de solutions
x∈D x∈D

et : Modèle n'ayant aucune solution optimale, peut se produire si :

Le domaine réalisable est vide,
min f (x) = − max(−f (x)) ou max f (x) = − min(−f (x)) La fonction objectif est non borné.
x∈D x∈D x∈D
Ainsi la recherche d'un maximum pouvant se ramener à la
x∈D
Il n'y a pas nécessairement unicité de la solution optimale.
recherche d'un minimum. Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Synthèse des diérents problèmes de l'optimisation

la classication se fait suivant diérents critères :
Selon la nature des variables de décision : Optimisation
continue ou optimisation combinatoire (les variables à
optimiser sont discrètes dans ce dernier cas). Les problèmes de programmations linéaires sont généralement liés à
Selon la nature des contraintes : Optimisation sans des problèmes d'allocations de ressources limitées, de la meilleure
contraintes ou optimisation sous contraintes. façon possible, an de maximiser un prot ou de minimiser un
Selon la nature de l'objectif : coût.
Optimisation monocritère : une seule fonction objectif à
satisfaire.
Optimisation multicritère : plusieurs fonctions objectif
(préférences) souvent contradictoires à satisfaire.
Selon les propriétés spéciales des éléments du problème :
linéarité (optimisation linéaire ou optimisation non linéaire),
convexité (optimisation convexe ou optimisation non convexe)
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Les variables de décision

Exemple : Problème de production
Une usine produit deux types de ciments C et C , rapportant
respectivement 500Dh et 700Dh par tonne.
1 2

Une tonne du ciment C necéssite 40 min de calcination dans un

four à chaux et 20 min de broyage. Dénir les variables de décision : sur quoi porte la décision?
1

Une tonne du ciment C necéssite 30 min de calcination dans un Dans ce cas : combien produire de C et C ?
four à chaux et 30 min de broyage.
2 1 2
x : quantité du ciment C à produire par jour (en Tonne).
Le four et l'atelier de broyage sont disponibles respectivement 6h et 1 1
x : quantité du ciment C à produire par jour (en Tonne).
8h par jour. 2 2

Combien de ciment de chaque type peut-on produire par jour pour

maximiser le bénéce?

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Les contraintes La fonction objectif

Dénir les contraintes imposées aux variables de décisions :

Contrainte de calcination dans un four à chaux : L'objectif est de maximiser le bénéce de l'usine :
Une tonne du ciment C (Resp. C ) necéssite 40 min (Resp. x tonnes produites de C rapportent 500x Dh, et x tonnes
produites de C rapportent 700x Dh.
1 1 1 2
30 min) de calcination. Le four est disponible 6h par jour :
1 2

On veut maximiser z = 500x + 700x

2 2

40x + 30x ≤ 360

1 2 Le programme linéaire (P ) associé au problème est :
1 2

Contrainte de broyage : 
max z = 500x + 700x
Une tonne du ciment C (Resp. C ) necéssite 20 min (Resp. 40x + 30x ≤ 360

 1 2

30 min) de broyage. L'atelier de broyage est disponible 8h par

1 2
20x + 30x ≤ 480
1 2

(P)
jour : x ,x ≥ 0

 1 2

20x + 30x ≤ 480


1 2
1 2

Contraintes de non-négativité : x ≥ 0, x ≥ 0
1 2

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

La forme générale d'un programme linéaire est donnée par : Formes Matricielles
 Pn

 max z = cj xj
j=1


ou ∀i = 1, ..., m,

n
P
aij xj ≤, = ≥; bi
Forme Canonique Forme Standard

0 1
 j=1

  
xj ≥ ∀j = , ..., n.
  
max z = c T x
 
max z = cT x
 

où la première ligne représente la fonction objectif, la deuxième Ax≤b

0 0
Ax=b
représente les m contraintes et la troisième repésente la positivité

 

x≥ x≥
 

des variables. où c = (c , ..., c ) , x = (x , ..., x ) , b = (b , ..., b

T T
m)
T et
A = (a ) est une matrice d'ordre m × n.
1 n 1 n 1

Convention ij

Si les m contraintes sont de type ≤, la forme est dite

Canonique.
Si les m contraintes sont de type =, la forme est dite
Standard.
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Passage entre les formes Passage entre les formes

Inéquation −→ Equation
Equation −→ Inéquation
0
n
X n
X
aij xj ≤ bi ⇐⇒ aij xj + ei = bi , ei ≥
n
 P  n
P j=1 j=1
n

 aij xj ≤ bi 
 aij xj ≤ bi
j=1 j=1
 
0
n n
X
aij xj = bi ⇐⇒ n ⇐⇒ n
X X
P
aij xj ≥ bi
P
(−aij )xj ≤ −bi aij xj ≥ bi ⇐⇒ aij xj − ei = bi , ei ≥
j=1

 

j=1 j=1
 
j=1 j=1

La variable e est appelée variable d'écart.

i

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Passage entre les formes Etapes de la résolution graphique

1 Tracer les droites correspondant aux contraintes;

Déterminer le domaine réalisable en vériant le sens des
inégalités pour chaque contrainte;
2

Variable non contrainte −→ variable positive

x ∈ R ⇐⇒ ∃ x , x ≥ 0, x = x −
− xi−
3 Tracer les droites correspondant à la variation de l'objectif;
Faire glisser ces droites parallèlement jusqu'à faire monter z à
+ +
i i i i i

la valeur maximale tout en restant dans le domaine réalisable.

4

Le point commun à la droite et le domaine réalisable sera

notre optimum.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Tracer les droites correspondant aux contraintes :

Exemple 
max z = −x1 + x2
2 2


x1 − x2 ≥
2 2



(P) −x1 + x2 ≥ −
5
x1 + x2 ≤
0




x1 , x2 ≥


Dénir les droites correspondant aux contraintes :

1(D ) : 2x − x = 2
1 1 2
2(D ) : −x + 2x = −2
2 1 2
3(D ) : x + x = 5
3 1 2

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Déterminer le sens des inégalités pour chaque contrainte : Déterminer le domaine réalisable : 1

1. Noter que dans cet exemple, x1 , x2 ≥ 0

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Tracer les droites correspondant à la variation de l'objectif Détermine La solution optimale

Dans cet exemple z = −2x + 3x ⇐⇒ x = x + z . 2 1

On trace au moins deux droites, an de pouvoir déterminer le sens

1 2 2 3 1 3

de maximisation de z .
Pour z = 0, on a la droite (D ) d'équation x = x
4 2
2
3 1
Pour z = 3, on a la droite (D ) d'équation x = x + 1
5 2
2
3 1

Le maximum est réalisé au point d'intersection des droites (D ) et

7/3 de valeur z = 10/3
1

(D ), ainsi x =
Pr. LAKHBAB (FSAC) Programmation Linéaire
3
Pr. LAKHBAB
8/3
∗

(FSAC)
∗

Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Ensembles convexes
Dénition Dénitions
Un sous-ensemble C ⊂ V , d'un espace vectoriel V , est convexe si Soient x , . . . , x ∈ R , une combinaison convexe de
1 k n

et seulement si : x , . . . , x , est le vecteur

1 k

∀x, y ∈ C , (1 − λ)x + λy ∈ C , ∀λ ∈ [0, 1]

avec λ ≥ 0, ∀i = 1, . . . k et X λ = 1
k
X k
λi x i , i i

Propriétés i=1 i=1

L'intersection d'une collection arbitraire d'ensembles convexes Soit S ⊂ V , l'enveloppe convexe de S , notée co(S), est
est un ensemble convexe. l'ensemble déni comme l'intersection de tous les ensembles
Si C , D sont deux sous-ensembles convexes de V et β ∈ R, convexes contenant S .
alors les ensembles : Soit S ⊂ V , l'enveloppe convexe de S est le plus petit ensemble
C + D = {x ∈ Rn : x = c + d, c ∈ C , d ∈ D} convexe de V contenant S .
βC = {x ∈ Rn : x = βc, c ∈ C }
Pr. LAKHBAB sont convexes. (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Polyèdre Point extrême

Dénitions
Un polyèdre est un ensemble qui peut être décrit comme Dénition
{x ∈ R : Ax ≤ b, x ≥ 0}, Un point extrême (sommet) d'un polyèdre X est un point qui ne
peut pas être exprimé comme combinaison convexe d'autres points
n

où A ∈ M (R) et b ∈ R . m de X .
Un ensemble de la forme {x ∈ R : Ax = b, x ≥ 0} est un
m,n

Propriété
n

polyèdre en forme Standard.

Tout polyèdre convexe est l'enveloppe convexe de ses

Un polyèdre X est dit borné s'il existe une constante c > 0 telle que points extêmes.

∥ x ∥≤ c, ∀x ∈ X

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Problème considéré
Théorème
On considère un programme linéaire de maximisation d'une forme On considère le programme linéaire suivant :
linéaire z = c x sur un polyèdre convexe (déni à l'aide des
T

contraintes linéaire).  max z = c T x



Alors le maximum est atteint en un de ses sommets. (P) Ax = b

...

0 x≥

La résolution algébrique utilise la forme standard, où A est une

Preuve :

Corollaire matrice m × n de rang m (avec m, n ∈ N , m ≤ n).

le domaine des solution optimales est convexe.
∗

     
x1 c1 b1
Preuve : ...
Corollaire .. .. et ..
 x2   c2   b2 
x = , c =  b=
     

Un programme linéaire admet 0,1 ou innité de solutions optimales.

 
     
xn cn bm

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Bases de A
 
xB
Les bases de A sont les matrices m × m inversibles extraites de A.
Ax = [B N]
xN

Soit B une base de A. = BxB + NxN

On partitionne A sous la forme suivante : 2

Ainsi
A = [B N] B∈M (R) et N ∈ M (R)
Ax = b ⇐⇒ x = B b − B Nx
B
−1 −1
N
m,m m,n−m

On partitionne de même les vecteurs x et c . 

xB

c T x = [cBT cNT ]
et xN
   
x B c B m n−m
x= c= (x , c ∈ R ; x , c ∈ R )
= cBT (B −1 b − B −1 NxN ) + cNT xN
B B N N
x N c N

= cBT B −1 b + (cNT − cBT B −1 N)xN

2. On suppose que les colonnes de B sont les m premières colonnes de A

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Forme canonique par rapport à la base B

Dénitions
La forme canonique par rapport à la base B , du problème (P) x est dite solution réalisable si elle vérie les contraintes
∗
est donnée par : (Ax = b et x ≥ 0).
∗ ∗

x est dite solution de base si elle vérie

∗
 max z = cBT B −1 b + c T

N xN
xB = B −1 b − B −1 NxN
Ax = b et
(P̃) ∗ −1
0

x =B b
x =0
∗ B
xB , xN ≥ ∗


avec
N

Si en plus x ≥ 0, alors x est une solution de base

∗ ∗

réalisable.
T −1
cT T
N = cN − cB B N B

cN est appelé vecteur de coûts réduits.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On a (S) ⇐⇒ Ax = b,
Remarques où A = 10 01 01 11 , et b = 3

x = (x1 , x2 , x3 , x4 )T
6
Il y a au plus C bases valides.
m

Sous l'hypothèse que A est de plein rang, et si m = n, alors le Il y a au plus C = 6 bases.

n
2

problème (P) admet une solution de base unique.

4

1 0  , B = [A 1 0 ,
Exemple
 

0 1
B1 = [A.1 , A.2 ] = 2
.1 , A.3 ] =
0 1
Déterminer les bases et les bases réalisables du système linéaire 
1 1 , B = [A 
0 0 ,
suivant : +x = 3
.1
B = [A , A ] =
3
0 1 .4
4
.2 , A.3 ]=
1 1
0 1 , B = [A 0 1 .

x
x +x +x = 6
1 4
 
.2
1 1 .4 .3 , A.4
1 1
(S) B = [A , A ] = ]=
2 3 4 5 6

On note A la j colonne de A
.j eme

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On a det(B ) ̸= 0 =⇒ B est une base. Caractérisation des solutions de base réalisables Optimales
De même, on vérie que B , B , B et B sont des bases.
1 1

On a det(B ) = 0 =⇒ B n'est pas une base.

2 3 5 6
4 4

3  ≥ 0, Théorème
L'ensemble des points extrêmes correspond à l'ensemble des

B1−1 b =
6 solutions de bases réalisables.
3 ≥ 0,
 

6 
−1
B b=
2

−3
Preuve : ...

6 ≱ 0, Théorème

−1
B b=
3

3 ≥ 0, Si c̄ ≤ 0, alors la solution de base réalisable correspondante est

solution optimale du programme linéaire (P).
  N

3
−1
B b=
5

3 ≥ 0.
 

3
−1 Preuve : ...
B b=
6
Ainsi B , B , B et B sont des base réalisables, alors que B est
une base non réalisable.
1 2 5 6 3

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Preuve
Soit B une base réalisable vériant c̄ ≤ 0.
On se donne la formulation canonique par rapport à B
N


 max z = cBT B −1 b + c T
N xN Exemple
(P̃) xB = B −1 b − B −1 NxN
0
xB , xN ≥
Déterminer les bases optimales du programme linéaire suivant :
+2x


Soit x̃ la solution de base qui correspond à B .


Max x
+x = 3
 1 3

Alors x̃ = 0, x̃ = B b et z(x̃) = c B b + c 0 = c


x
+x = 6
1 4

−1 T −1 T T −1
N B BB b x +x
≥0
B N  2 3 4

Soit x = xx une solution réalisable quelconque


x , x , x , x

B 1 2 3 4
N

On a z(x) = c B b + |{z} T
B c −1
x
|{z}
T
N N
≤0 ≥0

≤ cBT B −1 b = z(x̃)
Ainsi x̃ est une solution optimale.
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Méthode de résolution naïve ! ! Principe de l'algorithme du Simplex

L'algorithme du Simplex a été présenté en 1947 par George B.

Une Méthode de résolution naïve consiste à Dantzig. Il est parmi les algorithmes les plus utilisés pour résoudre
1énumérer tous les sommets, les problèmes d'optimisation linéaire.
2calculer z sur ces points, Principe
3prendre le sommet pour lequel z est optimisé. Une itération de l'algorithme du Simplex consiste à passer de
base réalisable à base réalisable voisine, tout en améliorant
Limitation toujours la valeur de la solution associée.
Le nombre de sommets peut être très grand en général!!! A chaque itération de l'algorithme du simplex, une variable
hors-base va entrer dans la base, tandis qu'une variable en
base sortira de la base ⇝ pivotage.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Notations Soit B une base réalisable et x la solution de base associée.

Etant donné B une base de A, on note : On considère la forme canonique par rapport à la base B ,
 max z = cBT B −1 b + c T
B ensemble des indices ou des variables de base.

N xN
xB = B −1 b − B −1 NxN
N ensemble des indices ou des variables hors-base.
(P̃)

xB , xN ≥ 0
Ā = B A = B [B N] = [I B N] = [I N̄] = (ā ), avec
−1 −1 −1
Propriété
I est la matrice identitée d'ordre m.
m m ij

b̄ = B b .
m
s'il existe s ∈ N tel que c̄ > 0 , alors on peut construire une
a

solution meilleure, x̃ . Et dans ce cas

−1 s

Exemple Ou bien on met en évidence une autre base B̃ et une autre

+x = 3 solution réalisable x̃ telle que
1

1 0 0 1

 x
+x +x = 6 =⇒ A =
0 1 1 1 .
1 4  
(S) x
≥0
2 3 4

x , x , x , x
1 2 3 4 z(x̃) ≥ z(x)

On considère la base B = [A , A ] = 10 01 . On a Ou bien on peut augmenter indéniment la valeur de x̃ sans

 
.1 .3
2
sortir de l'ensemble des solutions réalisables, et dans ce cas
2
s

⋆ Selon les indices, B = {1, 3} ; et selon les variables,

z = +∞.
2
B = {x , x }
⋆ De la même manière N = {2, 4} ou N = {x , x }
2 1 3
2 2 2 4 a. c̄s une composante du vecteur Coût réduit c TN (= cNT − cBT B −1 N )
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Choix de la variable entrante Exemple

Soit B la base réalisable courante, on choisit une variable
hors-base dont le coût réduit est positif :
s ∈ N tel que c̄ > 0. s
Supposons que pour un problème donné, N = {2, 3, 5, 6} tel que
c̄ = 5/3, c̄ = 9/2, c̄ = −2, et c̄ = 1
Les variables candidate pour enter en base (x ∈ N /c̄ > 0) sont
2 3 5 6
Il peut y avoir plusieurs variables candidates pour entrer en base!! x , x et x .
2 3 6
s s

La règle de pivotage permet de choisir, parmi toutes les variables Si on adopte le 1 critère de Dantzig, la variable x entrera en
er

base ( elle a le plus grand coût réduit max{5/3, 9/2, 1}).

3
candidates, celle qui va entrer en base.
Si on adopte la règle de Bland, la variable x entrera en base
Exemples de règle de pivotage : (son indice est le plus petit 2 = min{2, 3, 6} )
2

Choisir la variable de plus grand coût réduit . a

Choisir la variable d'indice le plus petit . b

a. 1
er
critère de Dantzig

b. Règle de Bland

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On considère la formulation canonique par rapport à la base B , Choix de la variable sortante

 max z = cBT B −1 b + c T  max z = cBT b̄ + c T
 
N xN N xN
(P̃) xB = B −1 b − B −1 NxN ⇐⇒ xB = b̄ − N̄xN Ainsi

xB , xN ≥ 0 
xB , xN ≥ 0 (xB )i = b̄i − āis xs ; 1
∀i ∈ { , . . . , m}

Supposons que la variable x est choisie pour entrer en base, on Remarques

cherche à augmenter sa valeur , tout en restant au domaine
s
a La base est réalisable, donc b̄ ≥ 0, ∀i ∈ {1, . . . , m}
réalisable. Si ā ≤ 0, l'augmentation de x entrainera une augmentation
i

D'aprés (P̃), pour i ∈ {1, . . . , m}, on a de (x ) .

is s

Si ā > 0, l'augmentation de x entrainera une diminution de

B i

(x ) .
X X is s
(xB )i = b̄i − āij xj = b̄i − āij xj − āis xs = b̄i − āis xs
Dans ce cas, il faut faire attention à la positivité de (x ) !
B i
j∈N j∈N \{s}
B i

(les autres variables hors-base resteront nulles dans cette itération.)

(x ) ≥ 0 ⇐⇒ b̄ − ā x ≥ 0 ⇐⇒ x ≤
b̄ i
B i i is s s
a. dans l'itération précédente, xs était une variable hors-base, donc sa valeur ā is
était nulle.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Si ā ≤ 0, ∀i ∈ {1, . . . , m}, il n'y a pas de candidate pour Exemples

sortir de la base et le problème est non-borné (On peut
is

augmenter indéniment la valeur de x sans sortir de Supposons pour un problème donné, que x est la variable, 2

l'ensemble des solutions réalisables).

s

x
hors-base, sélectionnée pour entrer à la base, et que x = x
3

Sinon, La valeur maximale que peut prendre x , tout en B 1

 

restant au domaine réalisable est

s x4
On présente quatre cas possibles
b̄r
= min { } a
b̄i Exemple 1 
4  8
xs =
ārs āis >0 āis    
ā
Supposons que  ā  =  1/2  et b̄ =  2 . On a
12
Soit x la variable correspondant à la r ligne. eme
5
22
1
Alors x s'annule et sort de la base.
t
t
ā 32

a. 2
eme
critère de Dantzig ou critère de sortie
b̄ 8 2 , 1} = 1
4 1/2 5 5
i
min { } = min{ ,
Remarques ā āi 2 >0 i2

Pour rester à l'intérieur du domaine réalisable, il est obligatoire de Le minimum est vérié par la troisième ligne, ce qui correspond à la
respecter le deuxième critère de Dantzig. variable x , ainsi x sort de la base.
4 4
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Exemple 2  4

ā 9 
   
8 Exemple 3   
Supposons que  ā  =  −5/2  et b̄ =  2 . On a
12
22
1 1 ā 0  8
 

Supposons que  ā  =  −5/2  et b̄ =  2 .

12
ā 32

−2 1
22

b̄ 81 8 ā
Ici ā ≤ 0, ∀i ∈ {1, 2, 3}. Alors le problème est non borné,
32

91 9
i
min { } = min{ , } =
z = +∞.
i2
āāi 2 >0 i2 ∗

Le minimum est vérié par la première ligne, ce qui correspond à la

variable à x , ainsi x sort de la base.
3 3

3. avec xB = (x3 , x1 , x4 )T et x2 est la variable entrante. 4. avec xB = (x3 , x1 , x4 )T et x2 est la variable entrante.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme du Simplex Dual

Algorithme de Simplex
5
Soit B la base réalisable courante du programme linéaire,
1

Exemple 4  Calculer N̄ = B N = (ā ) et c̄ = c − c N̄ .

2 −1
ij
T
N
T
N
T
B
ā
 
4 8  Si c̄j ≤ 0 ∀j ∈ N
Supposons que  ā  =  1/3  et b̄ =  2 . On a
12
Alors la solution considérée est optimale. (Stop)
1/2 1
22 Sinon on considère J = {j ∈ N : c̄j > 0}
ā 32 n si
8 2 1 Si ∃j ∈ J tel que la colonne N̄ ≤ 0 j

4 1/3 , 1/2 } = 2 (Stop)

3
b̄ i
min { } = min{ , Alors z ∗ = +∞
āi 2 >0
ā i2
Sinon soit tel que c̄ > 0. Déterminer r tel que
s
Ici le minimum est vérié dans les lignes qui correspondent aux
s

variables x et x ; b̄r b̄i

=⇒ deux variables susceptibles de quitter la base!
3 4 = min { }
ārs āis >0 āis

Dans ce cas, on utilise la règle de Bland, c.à.d. parmi ces deux Déterminer t l'indice de la variable correspondant à la
variables, on choisit celle de plus petit indice. Ainsi x sort de la r ligne de la base.
base.
3 eme

Considérer la nouvelle Base B̃ = (B \ {t}) ∪ {s} et retourner

en (2).
4

5. avec xB = (x3 , x1 , x4 )T et x2 est la variable entrante.

Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Cas d'un problème de minimisation

Géométiquement , cet algorithme correspond à un
cheminement de point extrême en point extrême adjacent le
long de la frontière de X .
D'un point de vue algébrique, il correspond à déterminer une Théorème
suite de bases adjacentes B , B , . . . B et donc de solutions
1 2 q
Pour un problème de Minimisation, si c̄ ≥ 0, alors la solution de
de base x , x , . . . x telles que z(x ) ≤ z(x ) ≤ . . . ≤ z(x ).
1 2 q 1 2 q
base réalisable correspondante est solution optimale du programme
N

linéaire (P).
Dénition
Une solution de base est dite dégénérée si le vecteur x = B b a −1 Remarque
des composante nulle. Dans le cas d'un problème de minimisation, seul le critère d'entrée
B

sera modié :
Théorème Choisir s tel que c̄ < 0
Sous l'hypothèse de non-dégénéréscence, l'algorithme du
s

simplexe converge en un nombre ni d'itérations.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On peut résumer les éléments nécessaires au déroulement de
Algorithme du Simplex Dual

l'algorithme du Simplex, dans un tableau :

Pour faciliter la résolution "à la main", d'un programme linéaire, on
propose une nouvelle écriture à l'aide d'un tableau. xB xN
0 B b
z
On considère à nouveau la formulation canonique par rapport à une 0
Im B −1 N
-1 −c B b
−1

base B , cT
N
T
B
−1

 max z = cBT B −1 b + c T
et pour ne pas alourdir le tableau, on supprime la colonne

N xN
(P̃)

xB = B −1 b − B −1 NxN
xB , xN ≥ 0 correspondant à z
On'a pour les contraintes xB
Im
xN
B −1 N B −1 b
xB = B −1 b − B −1 NxN ⇐⇒ xB + B −1 NxN = B −1 b (3) 0 cTN −cBT B −1 b
⇐⇒ Im xB + B −1 NxN + z = B −1 b 0 (4)
Remarque
et pour la fonction objectif On a supposé, pour simplier, que les variables de base étaient les
m premières variables!
z = cBT B −1 b + c T
N xN ⇐⇒ 0x + c B
T
N xN − z = −cBT B −1 b (5) Si les variables de base se présentent dans un ordre quelconque,
est la matrice identitée d'ordre m. elles seront aisément identiées par le fait que les colonnes
correspondantes sont à une permutation près, les colonnes de I .
Im
m
Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Etant donnée une matrice A = (a ) (1 ≤ i ≤ m, 1 ≤ j ≤ n), telle Exemple

que l'élément a ̸= 0. La matrice D = (d ) (1 ≤ i, j ≤ m), dénie
ij

par
rs ij Résoudre le problème suivant à l'aide de la méthode du
Simplex
1

1 si j = i, j ̸= r
a

max z = x + 2x


1/a si j = i = r


 −3x + 2x ≤ 2
1 2



si
 
rs


−x + 2x ≤ 4
d = 1 2

ij

−a /a j = r , i ̸= r
0 sinon .
is rs
(P )
x +x ≤5
1 1 2




x ,x ≥ 0

est appelée matrice de pivotage sur l'élément a de A.
1 2




rs 1 2

Remarques (Adopter le premier critère de Dantzig)

La matrice D est inversible, Déterminer à chaque itération, la matrice de pivotage qui
permet de donner le tableau de la nouvelle itération.
2

Ax = b ⇐⇒ DAx = Db ,
Les tableaux [A|b] et [DA|Db] sont équivalents. a. c.à.d les tableaux du Simplex.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Cas de dégénéréscence Cas de dégénéréscence

Soit B la base réalisable courante, et x la solution correspondante, Il est possible après un certain nombre de changements de bases de
on a retrouver une base déjà rencontrée et de cycler indéniment.
On peut régler ce problème par l'utilisation de la règle de Bland.
z(x) = cBT B −1 b + c̄NT xN = cBT B −1 b + c̄j xj = cBT B −1 b
La règle de Bland
X

A chaque itération de l'algorithme du simplex

|{z}
j∈N
0

Dans le cas de dégénéréscence où b̄ = 0, on a θ = = 0. Alors la b̄r parmi toutes les variables susceplibles d'entrer en base (càd
valeur z de la nouvelle solution x̃ ne varie pas après le changement telles que c̄ > 0) choisir celle du plus petit indice.
r ārs

de base : parmi toutes les variables susceptibles de quitter la base (càd

s

z(x̃) = cBT B −1 b + c̄j xj +c̄s θ = cBT B −1 b = z(x)

toute les variablesb̄
: ā > 0; i = 1, . . . , m}), choisir celle du
X
b̄r i
x = t = min{ is

plus petit indice.

ārs
|{z}
j∈N \{s} 0 ā is

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On considère le programme linéaire suivant

Le dernier programme est équivalent à
max z = −x + 2x
max z = −x +2x


x +x ≤6

 1 2 

6
1 2
x − 3x ≥ 10
1 2
 
(P) 
x +x +x =
−x +3x 10
1 2 3

x ,x ≥ 0

 1 2
+x4 =−
0
1 2

1 2 

≥
On met le programme (P) sous la forme standard
x1 , x2 , x3 , x4


max z = −x +2x
Si on considère la base B = {x , x }, on a N = {x , x }, ainsi
x = x = 0.
 3 4 1 2

=6
1 2
1 2
On remplace dans le système linéaire, on trouve que x = 6 et


x +x +x
3 10
1 2 3


x = −10. Alors B est une base non réalisable!!

3
x − x −x =
≥0
 1 2 4
4

x , x , x , x

1 2 3 4

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On considère un programme linéaire sous forme canonique

 max z = c T x

Pour un problème linéaire sous forme Standard, il n y a pas
(P) Ax ≤ b toujours une solution de base réalisable évidente.

x≥ 0 Soit un programme linéaire sous forme standard
sa forme standard est donné par
 max z = c T x

 max z = c T x

(P) Ax = b
(PS ) Ax + e = b 0
0
x≥

x≥


Où e = (e , . . . , e ) est le vecteur des variables d'écarts.

1
T
Remarque
En cas de besoin, multiplier certaines contraintes par −1, pour
m

Dans le cas où b ≥ 0, on peut facilement déterminer une solution que le second membre b soit positif.
de base réalisable. Il sut de considérer la base On ne suppose pas que la matrice A ∈ M (R), est de plein
B = {e , e , . . . , e }, N = {x , x , . . . , x }
rang, ni qu'il existe bien des solutions réalisables!
m,n
Pour les variables Hors-Base, on a x = x = . . . = x = 0, alors
1 2 m 1 2 n

e = b ≥ 0 (ainsi B est une base réalisable).

1 2 n

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Un programme auxiliaire associé à (P) est donné par On considère les programmes linéaires suivants :
 Pm
 min za = i=1 ai Pm
 max z = c T x
 
(Pa ) Ax + a = b  min za = i=1 ai

x ≥ ,a ≥ 0 0 (P)

Ax = b
x≥ 0
(Pa )

Ax + a = b
x ≥ ,a ≥ 0 0
1 est le vecteur des variables auxiliaires.
a = {a1 , a2 , . . . , am }T
Proposition
Le problème (P ) est toujours un problème de minimisation, Le programme linéaire (P) admet une solution réalisable si et
quelque soit le type du problème initial.
2
a

La fonction z dépend de x et de a. seulement si le programme auxiliaire (P ) admet une solution

optimale, de valeur z = 0
a
3
∗
Le problème (P ) permet de donner une base réalisable ou
a
a

bien de détecter l'impossibilité.

4
a

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

On applique l'algorithme du Simplex au problème (P ). Soit z la ∗ On considère un programme linéaire sous la forme canonique
solution trouvée à la n des itérations.
a a
 n

Si z > 0, alors le problème initial (P) n'admet pas de solution

P
∗

 max z = cj xj

réalisable.
1
j=1


a

1

n
(P)
Si z = 0,
P
aij xj ≤ bi ∀i = , ..., m,
∗

0 1
2 j=1

a


si aucune variable auxiliaire n'est dans la base nale Bf , alors xj ≥ ∀j = , ..., n.

a

n de la phase 1, et on passe à la phase 2 du simplex, en

considérant Bf comme base de départ. On suppose que (P) admet une solution optimale x de valeur z ∗ ∗

b si la keme variable de Bf est une variable auxiliaire, alors

La méthode du Simplex permet à chacune de ses itérations
examiner la keme ligne du tableau du Simplex, et choisir
l'élément en colonne j de cette ligne tel que, j soit l'indice d'obtenir (améliorer) une borne inférieure sur z . ∗

d'une variable non auxiliaire et l'élément choisi soit non nul,

puis pivoter le tableau autour de cette élément. x 1 ⇝ x 2 ⇝ ... ⇝ x ∗
z 1 ≤ z 2 ≤ ... ≤ z ∗
Remarque
Si tous les éléments de la k ligne sont nuls, alors cette ligne
eme Question
correspond à une contrainte redondante et peut être Est-il possible d'obtenir une borne supérieure sur z ?? ∗
supprimée.
répéter l'étape (b) jusqu'à ce qu'aucune des variables
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Si on choisit les y , (i = 1, ..., m), telles que
Algorithme du Simplex Dual
i

On considère les m contraintes du programme linéaire (P). X

a y ≥c
m
∀ j = 1, ..., n
ij i j (7)
a x ≤ b ∀i = 1, ..., m,
n i=1
Soit x solution réalisable pour (P), on a x ≥ 0 ∀ j = 1, ..., n.
X
ij j i
j
j=1

Soient y , y , ..., y ≥ 0, on a Ainsi, X a y x ≥ c x , ∀ j = 1, ..., n =⇒ X X a y x ≥ X c x

m n m n
1 2 m ij i j j j ij i j j j
i=1 j=1 i=1 j=1
a x ≤ y b ∀i = 1, ..., m,
n

et d'après (6) on trouve

X
y i ij j i i
j=1 m n X
m n
En faisant la somme des m contraintes
X X X
yi bi ≥ aij yi xj ≥ cj xj
m n m i=1 j=1 i=1 j=1

Ainsi, pour tout x solution réalisable du problème (P), on a

X X X
yi aij xj ≤ yi bi
i=1 j=1 i=1 m n

Ce qui est équivalent à

X X
y i bi ≥ cj xj
i=1 j=1

(6) et en particulier pour la solution optimale x :

n X
X m m
X
∗
aij yi xj ≤ yi bi
j=1 i=1 i=1 n
X m
X
∗
z = cj xj∗ ≤ y i bi
Pr. LAKHBAB (FSAC) Programmation Linéaire
j=1 i=1

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Dénition
Le problème dual du problème (P) est donné par
m


Formulation Matricielle
P


 min w = yi bi
i=1
On considère le programme primal (P), son programme dual est

1

m
(D)
donné par (D)
P
aij yi ≥ cj ∀ j = , ..., n,
0 1

 i=1


yi ≥ ∀i = , ..., m.


 max z = c T x  min w = b T y
 
Exemple (P) Ax ≤ b (D) AT y ≥ c
Donner le programme dual du programme suivant 
x≥ 0 
y≥ 0
max z = x + 2x


 −3x + 2x ≤ 2

 1 2

−x + 2x ≤ 4
1 2


(P)
 x +x ≤5
1 2

x ,x ≥ 0


 1 2

1 2

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Remarques Exemple
Le problème (D) peut s'exprimer sous la forme
1
Montrer l'eet d'une contrainte primale de type (≥), sur le dual.
 − max −b T y

 Pn
(−A)T y ≤ −c
 max z = cj xj
0

j=1


y≥
 

 n
P
a1j xj ≤ b1

Le dual du dual est le primal.

2
(P) j=1

Le fait de mettre (P) sous la forme canonique, facilite la


 n
P
a2j xj ≥b2


construction du problème Dual (D). Néanmoins, le travail peut

3


 j=1
0 1



être fait quelque soit le type des contraintes ou des variables!


xj ≥ ∀j = , ..., n.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme du Simplex Dual
Primal Dual
Passage de (P) à (D) (forme canonique) Max Min
c : coecient de la f obj. z c : second membre
n

b : second membre b :coecient de la f obj. w n

y ≥0
P n
a x ≤b
ij j i i

Primal (P) Dual (D) j=1

n
y ≤0
Max Min
P
a x ≥b
ij j i i
j=1
n

c : coécient de la f obj. z c : second membre

P
n aij xj = bi yi ∈ R
b : second membre b :coecient de la f obj. w
j=1

0
n m
P
xj ≥ aij yi ≥ cj
Contrainte : Ax≤b Variable y ≥0 x ≤0
i=1
m

Variable x≥0 Contrainte : A y ≥c

P
T j aij yi ≤ cj
i=1
Pm
xj ∈ R aij yi = cj
i=1
Dual Primal
Table  Passage de (P) à (D) (cas général)
Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Théorème de la dualité faible

Lemme
Soit (P)/(D) un couple de programmes linéaires duaux :
Théorème
 max z = c T x  min w = b T y
Soit (x̄, ȳ ) un couple de solutions réalisables (P)/(D).
 

(P) Ax ≤ b
0 0
(D) AT y ≥ c
Si c x̄ = b ȳ , alors x̄ et ȳ sont des solutions optimales, pour (P)
T T
x≥ y≥
et (D) respéctivement.
 

Pour tout couple de solutions réalisables Primal/Dual, (x̄, ȳ ) , on a

a: un couple de solutions réalisables (P)/(D). Alors, d'après le

Preuve :

(x̄, ȳ )
Lemme précédent
T T
c x̄ ≤ b ȳ
a. x̄ (P) ȳ (D) c x̄ ≤ b y ∀y solution réalisable duale.
T T

Or, c x̄ = b ȳ , ainsi b ȳ ≤ b y ∀y solution réalisable duale

est solution réalisable pour et est solution réalisable pour

T T T T

D'après la construction du problème dual

Preuve :
Alors ȳ est une solution optimale pour le dual.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Théorèmes de la Dualité Forte Dual d'un programme linéaire NON Borné

Théorème Remarques
Si un des deux problèmes primal (P) OU dual (D) possède une Si la fonction z n'est pas majorée sur son domaine réalisable,
solution optimale avec valeur nie, alors la même chose est vraie alors le problème dual n'admet pas de solution réalisable.
pour l'autre problème, et les valeurs optimales des deux problèmes Inversement, si la fonction w n'est pas minorée sur son
sont égales z = max z = min w = w .
∗ ∗
domaine réalisable, alors le problème primal n'admet pas de
Théorème solution réalisable.
Si les deux problèmes primal (P) ET dual (D) ont des solutions Remarque
réalisables, alors chacun d'eux a une solution optimale et Le primal et le dual peuvent être simultanément non réalisables.
z ∗ = max z = min w = w ∗

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Théorème des Ecarts Complémentaires (TEC)

On reprend les deux programmes linéaires duaux :
 max z = c T x  min w = b T y
 

(P) Ax ≤ b
0
(D) AT y ≥ c
0 Théorème
x≥ y≥
Soit (x, y ) un couple de solutions réalisables Primal/Dual.
 

x et y sont optimales Primal/Dual si et seulement si

Remarque  (b − Ax) y = 0
Soit un couple de solutions réalisables Primal/Dual (x, y ). On a le
T


résultat suivant :  (b − Ax) y ≥ 0 ET

(A y − c) x = 0
T T

T

et On dit dans ce cas que x et y sont complémentaires.



(A y − c) x ≥ 0
T T


Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Théorème des Ecarts Complémentaires (TEC) Théorème des Ecarts Complémentaires (TEC)
On a De la même manière, on trouve
.. ..
m m

. (AT y − c)T x = (
P P
    ai 1 yi − c1 )x1 + · · · + ( ain yi − cn )xn
 . Par conséquent i=1 i=1
 
 n   n 
  P P
 =  bi −
  
..
b − Ax =  − a x aij xj
 b i   j=1 ij j

.. j=1
.. 0 ⇐⇒ (X a y − c )x = 0
m
1
  
   
(AT y − c)T x = ij i j j ∀j = , · · · , n
i=1
Ainsi n n Ainsi
(b − Ax)T y = (b1 −
P P
a1j xj )y1 + · · · + (bm − amj xj )ym
Donc
n
0 1

j=1 j=1
0
P
 (bi − aij xj )yi = ∀i = , · · · , m
 (b − Ax)T y =
 

ET ET

j=1


⇐⇒
0 ⇐⇒ (b − X a x )y = 0 1 y − c) x = 0
n

( a y − c )x = 0 1
(b − Ax)T y = ∀i = , · · · , m (AT T m
 
i ij j i
 P
∀j = , · · · , n

ij i j j

j=1

i=1

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Utilité du TEC
Connaissant la solution optimale de l'un des problèmes (P) ou Utilisation pratique du TEC
(D), le théorème des écarts complémentaires permet de Soit (x, y ) un couple de solutions optimales Primal/Dual.
retrouver directement la solution optimale de l'autre problème. à partir du (TEC), on remarque que
Le théorème permet aussi de vérier si une solution donnée est Si P a x < b =⇒ y = 0
n

optimale. 1

j=1
ij j i i

Notation 2 Si P a y > c =⇒ x = 0
m

i=1
ij i j j

La contrainte P a x ≤ b est serrée pour un point x̄ , si

n

j=1
ij j i 3 Si y > 0 =⇒ b − P a x = 0
i i
n
ij j
n j=1

Si x > 0 =⇒ P a y − c = 0
P
aij x̄j < bi m
4
j=1 j ij i j
i=1
La contrainte m
P
i=1
aij yi ≥ cj est serrée pour un point ȳ , si
m
P
aij ȳi > cj
i=1
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Interprétation économique de la dualité Problème de production (Fabricant de Yaourt)

Problème de production (Fabricant de Yaourt)
Une companie produit deux types de yaourts à la fraise A et B à On pose
partir de Fraise, de Lait et de Sucre. x : quantité de Yarourt de type A à fabriquer (en kilo).
1
Chaque type de yaourt doit A B x : quantité de Yarourt de type B à fabriquer (en kilo).
respecter les proportions Fraises 2 1 2
Le problème de la companie se modélise en programme linéaire :
suivantes de matières premières. Lait 1 2
Sucre 0 1 
max z = 40x + 50x
 2x + x ≤ 800

 1 2

Les matières premières sont en quantité limitée : 800 kilos de x + 2x ≤ 700

1 2



Fraises, 700 kilos de Lait et 300 kilos de sucre. La vente des yaourts
(P)
x ≤ 300
1 2

A rapportent 40 Dh par kilo et les yaourts B 50 Dh. x ,x ≥ 0


2




1 2

Quelles quantités de chacun des deux types de Yarourts, la

companie doit-elle fabriquer pour augmenter son bénéce?
Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Problème de production (Fabricant de Yaourt) Le problème dual

La companie acceptera de vendre toutes la matière première

Supposons à présent qu'un acheteur se présente pour acheter la uniquement si elle obtient pour chaque produit un prix de vente
matière première de la companie (le lait, les fraises, et le sucre). au moins égal au prot qu'elle ferait en vendant ses produits :
Quels prix unitaires y , y , y l'acheteur doit-il proposer à

2y + y ≥ 40
y + 2x + y ≥ 50
1 2
l'entreprise en question pour qu'elle accepte de vendre toute la
1 2 3
1 2 3
matière prmière? L'achteur voudrait minimiser le côut d'achat de la matière
première.
min 800y + 700y + 300y
1 2 3

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Le problème dual

On pose Notations
y : Prix unitaire d'achat des fraises (en Dh).
1 x : quantité du produit j ∀j = 1, ..., n.
y : Prix unitaire d'achat du lait (en Dh). b : quantité disponible de la ressource i ∀i = 1, ..., m.
j
2
y : Prix unitaire d'achat du sucre (en Dh). a : quantité de la ressource i utilisée pour la production d'une
i
2
Le deuxième problème se modélise comme suit : unité de produit j .
ij

c : prix de vente d'une unité du produit j .

min 800y + 700y + 300y
y : le prix unitaire d'achat de la ressource i
 j

2y + y ≥ 40

 1 2 3
i

y + 2x + y ≥ 50
1 2

(D)
y ,y ,y ≥ 0

 1 2 3

1 2 3

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme
Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Interprétation du primal Algorithme du Simplex Dual

a x ≤ b : ne pas consommer plus de ressource que l'on en
P n

Soient m, n ∈ N (m ≤ n), A est une matrice m × n de rang m,

ij j i

dispose.
j=1 ∗

c, x ∈ R , b ∈ R et B une base (quelconque) de A

n m

c x : maximiser le prot de la vente.

P n
max z = j j
 max z = c T x  max z = cBT B −1 b + cN T xN
 
j=1
(P) Ax = b (P ′ ) xB = B −1 b − B −1 NxN
Interprétation du dual 
x≥ 0 
xB , xN ≥ 0
Un acheteur souhaite acheter les ressources i, i ∈ {1, ..., m} à cette
entreprise. IL cherche donc le prix y d'une unité de ressource i Il arrive fréquemment que la base B ne soit pas réalisable
pour que
i

(B b ≱ 0), mais que, par contre c vérie la condition

−1

son prix totale d'achat w = P b y soit minimal. d'optimalité (c ≤ 0, pour un problème de maximisation). On dit
m N

alors que (P) est dual réalisable

i i N
i=1

la companie accepte de vendre : P a y ≥ c , j ∀j = 1, ..., n

n

i=1
ij i j

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire

Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme

Préléminaires
du Simplex Dual Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité

Choix de la variable sortante

Exemple

Soit B une base dual réalisable (vériant c ≤ 0, pour un problème


max −x1 −x2
3 4


de Maximisation).

− x1 −x2 +x3 =− N
4 5

(P)
 −x1 − x2 +x4 = −
0 On suppose que b̄ = B b ≱ 0 −1

Choisir r tel que b̄ < 0. En partique, on choisit la variable dont la


x1 , x2 , x3 , x4 ≥


La base B = {x , x } est dual réalisable, en eet c ≤ 0. valeur est la plus négative.

r
3 4 N

Remarque b̄ = min{b̄ : i = 1, . . . , m}
Au lieu d'appliquer la phase 1, pour rendre le problème primal
r i

réalisable, puis la phase 2, on applique l'algorithme de Simplex Soit t l'indice de la variable correspondant à la ligne r de la base.
Dual qui garde la dual réalisabilité, pour atteindre après un certain Alors x sort de la base, et le pivot sera dans la la ligne r du
tableau.
t
nombre d'itérations à une base réalisable.

Pr. LAKHBAB (FSAC) Programmation Linéaire Pr. LAKHBAB (FSAC) Programmation Linéaire
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme du Simplex Dual

Choix de la variable entrante Algorithme dual du Simplex

Soit B une base dual réalisable,
1

On rappelle que Si b̄ ≥ 0 ∀i = 1, ..., m

Alors la solution considérée est optimale. (Stop)
2
X i
xt + ārj xj = b̄r
j∈N
Sinon choisir r telle que b̄ = min{b̄ : i = 1, . . . , m} ;
Déterminer t l'indice de la variable correspondant à la ligne r
3

Si ā ≥ 0, ∀j ∈ N , alors le problème est non réalisable.

r i

Sinon, on choisit la variable d'entrée x de telle sorte que le

rj
de la base. Alors x sort de la base
vecteur des coûts réduits c̄ demeure négatif, lorsqu'on pivote Si tous les termes de la ligne r de la matrice N̄ sont ≥ 0
s t

le tableau autour de ā : Alors le problème est non réalisable (Stop).

4
N

Sinon, déterminer s tel que

rs

c̄ ≤ 0
ā rj 5
c̄ − j s
ā
| | = min{| |; ā < 0 et j ∈ N }
rs
c̄s c̄ j

Remarque
rj
ā rs ā rj

Dans le cas d'un problème de minimisation, c̄ doit rester positif, Alors, la variable d'entrée est x .
ainsi :
N

Considérer la nouvelle base B̃ = (B \ {t}) ∪ {s}, pivoter le

s

c̄ ≥ 0 nouveau tableau autour de ā , et retourner en (2).

6
ā rj
c̄ − j s rs
ā rs
Pr. LAKHBAB (FSAC) Programmation Linéaire

Bibliographie
Préléminaires Résolution algèbrique La méthode de Simplex Simplex Phase 1 Dualité Algorithme du Simplex Dual

Exemples

Résoudre par l'algorithme dual du simplexe les problèmes suivant : Optimisation combinatoire, méthodes mathématiques et

min z = 3x + x algorithmiques, Graphes et programmation linéaire.
 x − x ≤ −1 .
 1 2 Michel
 max z = −x − x
3x + x ≥ 4
1 2



−x − x ≤ −3
1 2 Sakarovitch


Programmation mathématique, Théorie et algorithmes.

 

+ 4x ≥ 5
1 2

(P ) (P )
2x + x ≤ 2
1 2 1 2
.
Michel
x
x ,x ≥ 0
1 2

x ,x ≥ 0
 
1 2
 
  Minoux

Cours de recherche opérationnelle I,

1 2


1 2

https ://pagesperso.g-scop.grenoble-inp.fr/ braunern/RO.pdf

Nadia Brauner

min z = 3x + 2x


 x +x ≥2
1 2
Programmation linéaire. Méthode du simplexe.



−x + x ≥ 3
1 2

http ://www.fsr.ac.ma/cours/maths/bernoussi/RO-
S. El Bernoussi

(P )
≥4
3 1 2
 x ELBERNOUSSI-2010-P1.pdf
x ,x ≥ 0


 1

1 2

Pr. LAKHBAB (FSAC) Programmation Linéaire