Plan

N
BE

BE
1 Propriétés de base des problèmes linéaires
Forme standard

EL

EL
Algorithme du simplexe Solution de base
Théorème fondamental de la PL

UJ

UJ
2 Méthode du simplexe

BO

BO
Yassine Boujelben
[email protected] Pivots
Points extrêmes adjacents
INE

INE
Tableau du simplexe

Chapitre 2 3 Construction d’un tableau initial

SS

SS
Problématique
Méthode en deux phases
YA

YA
Méthode du grand M

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 1 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 2 / 60

Propriétés de base des problèmes linéaires Forme standard Propriétés de base des problèmes linéaires Forme standard

Table of Contents Forme standard d’un modèle linéaire

EN

EN
1 Propriétés de base des problèmes linéaires On dit qu’un modèle linéaire P est mis sous forme standard Ps s’il se
LB

LB
Forme standard présente sous la forme suivante :
Solution de base
JE

JE
min z = c1 x1 + c2 x2 + . . . + cn xn
Théorème fondamental de la PL
OU

OU
2 Méthode du simplexe sous les contraintes :
Pivots
EB

EB
a11 x1 + a12 x2 + . . . + a1n xn = b1
Points extrêmes adjacents
Tableau du simplexe a21 x1 + a22 x2 + . . . + a2n xn = b2
.. ..
SIN

SIN
. .
3 Construction d’un tableau initial
Problématique am1 x1 + am2 x2 + . . . + amn xn = bm
S

S
Méthode en deux phases x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0
YA

YA
Méthode du grand M
où les bi (1 ≤ i ≤ m) sont non-négatives.

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 3 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 4 / 60
 Propriétés de base des problèmes linéaires Forme standard Propriétés de base des problèmes linéaires Forme standard

Notation matricielle compacte Remarques et hypothèses

N
Remarques

BE

BE
1 On peut toujours mettre un modèle linéaire quelconque sous

EL

EL
forme standard
minimiser ⃗cT ⃗x (1) 2 L’ensemble des contraintes technologiques forment un système

UJ

UJ
sous les contraintes ⃗ = ⃗b et ⃗x ≥ 0
Ax ⃗ de m équations à n variables.
d’équations linéaires (A)

BO

BO
Hypothèses
⃗x : vecteur colonne de dimension n ;
INE

INE
1 n > m car sinon pas de problème
⃗cT : vecteur ligne de dimension n ; ⃗ sont linéairement indépendants ; rang(A)
⃗ =m
2 Les lignes de A
⃗ : matrice m × n ;
A
SS

SS
⃗b : vecteur colonne de dimension m ; Rappel : rang d’une matrice
YA

YA
⃗ de dimension quelconque est l’ordre de la
Le rang d’une matrice A
⃗
plus grande sous-matrice carrée régulière que l’on peut extraire de A
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 5 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 6 / 60

Propriétés de base des problèmes linéaires Forme standard Propriétés de base des problèmes linéaires Forme standard

Transformations P et Ps sont équivalents

EN

EN
1 Maximiser cx revient à minimiser −cx On considère le modèle linéaire P suivant :
Variables d’écart : Pour transformer une contrainte d’inégalité
LB

LB
2
min z = c1 x1 + c2 x2 + . . . + cn xn
ai x ≤ bi en une contrainte d’égalité, on introduit une nouvelle
JE

JE
variable si , appelée variable d’écart, et on écrit sous les contraintes :
OU

OU
ai x + si = bi et si ≥ 0 a11 x1 + a12 x2 + . . . + a1n xn ≤ b1
a21 x1 + a22 x2 + . . . + a2n xn ≤ b2
EB

EB
.. ..
Augmenter la taille du problème . .
si s’interprète comme la quantité de ressources inutilisées
SIN

SIN
am1 x1 + am2 x2 + . . . + amn xn ≤ bm
3 Variables d’excédent : Pour transformer une contrainte x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0
d’inégalité ai x ≥ bi en une contrainte d’égalité, on introduit une
S

S
nouvelle variable si , appelée variable d’excédent, et on écrit Transformer P en un problème équivalent sous forme standard Ps /
YA

YA
1 Ps linéaire
ai x − si = bi et si ≥ 0
2 Une solution de Ps est aussi une solution de P
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 7 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 8 / 60
 Propriétés de base des problèmes linéaires Forme standard Propriétés de base des problèmes linéaires Forme standard

Ps est linéaire Une solution de Ps est solution de P

N
Ps : Supposons que nous avons trouvé ⃗x et ⃗s qui sont une solution

BE

BE
n m
X X optimale de Ps , c-à-d :
min z = ci xi + 0.sj

EL

EL
i=1 j=1 n
X
ci xi est min (2)

UJ

UJ
a11 x1 + a12 x2 + . . . + a1n xn + s1 = b1 i=1

BO

BO
a21 x1 + a22 x2 + . . . + a2n xn + s2 = b2 h i  ⃗x  h i
.. .. A⃗|I = ⃗b (3)
. . ⃗s

INE

INE
am1 x1 + am2 x2 + . . . + amn xn + sm = bm Montrons que ⃗x est une solution optimale de P , c-à-d :
xi ≥ 0, sj ≥ 0 n
SS

SS
X
ci xi est min ✓ (4)
i=1
YA

YA
Les variables d’écart ne coûtent rien h i h i
⃗ [⃗x] ≤ ⃗b
A (5)
Ps est linéaire
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 9 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 10 / 60

Propriétés de base des problèmes linéaires Forme standard Propriétés de base des problèmes linéaires Solution de base

Preuve Table of Contents

EN

EN
1 Propriétés de base des problèmes linéaires
LB

LB
Forme standard
Solution de base
JE

JE
On considère la contrainte (i) Théorème fondamental de la PL
OU

OU
ai1 x1 + ai2 x2 + . . . + ain xn + si = bi (6) 2 Méthode du simplexe
Pivots
EB

EB
si si = 0 ⇒ contrainte vérifiée ; Points extrêmes adjacents
si si > 0 ⇒ ai1 x1 + ai2 x2 + . . . + ain xn = bi − si < bi □ Tableau du simplexe
SIN

SIN
⇒ Une solution optimale de Ps est forcément optimale de P
3 Construction d’un tableau initial
Problématique
S

S
Méthode en deux phases
YA

YA
Méthode du grand M

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 11 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 12 / 60
 Propriétés de base des problèmes linéaires Solution de base Propriétés de base des problèmes linéaires Solution de base

Rappel Base

N
BE

BE
Un ensemble de vecteurs {⃗a1 , ⃗a2 , . . . , ⃗ak } est dit linéairement ⃗ = ⃗b
On considère le système d’équations Ax

EL

EL
dépendant s’il existe des scalaires λ1 , λ1 , . . . , λk , non tous nuls / ⃗ est composée de n colonnes :
A

UJ

UJ
k
X ⃗ = [(⃗a1 ), (⃗a2 ), . . . , (⃗an )]
A
λi⃗ai = 0 (7)

BO

BO
i=1
Supposons qu’à partir de ces n colonnes (n vecteurs (⃗ai )) , nous
Si un tel ensemble de scalaires n’existe pas, les vecteurs sont dit choisissons m veceturs l.i
INE

INE
linéairement indépendants (l.i.) ⃗
Nous formons une matrice B(m × m) carrée, régulière
⃗ est une base du système.
⇒ B
⃗ = nombre de colonnes l.i.
Rang(A)
SS

SS
il reste (n − m) colonnes hors base
= nombre de lignes l.i.
À ces colonnes correspondent des variables xj hors base
YA

YA
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 13 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 14 / 60

Propriétés de base des problèmes linéaires Solution de base Propriétés de base des problèmes linéaires Solution de base

Solution de base Définitions

EN

EN
On peut écrire :
LB

LB
⃗b = x1⃗a1 + x2⃗a2 + . . . + xm⃗am + xm+1⃗am+1 + . . . + xn⃗an
| {z }
JE

JE
hors base après réarrangement
Une solution de base est dite réalisable si ⃗xB ≥ 0
OU

OU
Si on fixe les xj à 0, il reste :
Une base correspondant à une solution de base réalisable est
⃗b = x1⃗a1 + x2⃗a2 + . . . + xm⃗am appelée base réalisable
EB

EB
Une solution de base est dite dégénéréee si le vecteur ⃗xB a des
⃗ = [(⃗a1 ), (⃗a2 ), . . . , (⃗am )]
B ⇒ ⃗ xB = ⃗b
B⃗ composantes nulles.
m×m
SIN

SIN
⇒
⃗ −1⃗b
⃗xB = B
S

S
⃗ du
(⃗xB , ⃗0) est une solution de base (associée à la base B)
YA

YA
⃗
système A⃗x = b
Les composantes de ⃗xB sont appelées variables de base
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 15 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 16 / 60
 Propriétés de base des problèmes linéaires Théorème fondamental de la PL Propriétés de base des problèmes linéaires Théorème fondamental de la PL

Table of Contents Théorème fondamental de la PL

N
Théorème fondamental de la PL

BE

BE
1 Propriétés de base des problèmes linéaires
Forme standard ⃗ est une matrice
Étant donné un PL sous forme standard (1) où A

EL

EL
Solution de base ⃗ = m,
m × n, m < n et rang(A)
Théorème fondamental de la PL s’il existe une solution réalisable, alors il existe une solution de

UJ

UJ
1

base réalisable ;
2 Méthode du simplexe

BO

BO
Pivots 2 s’il existe une solution réalisable optimale, alors il existe une
Points extrêmes adjacents solution de base réalisable optimale.
INE

INE
Tableau du simplexe
Théorème : Équivalence entre solutions de base et points extrêmes
3 Construction d’un tableau initial
SS

SS
Problématique Soient A⃗ matrice m × n, m < n et rang(A)
⃗ = m ; K polyèdre convexe
Méthode en deux phases ⃗ x = ⃗b, ⃗x ≥ 0}. Un vecteur ⃗x
(sous forme standard) défini par K = {⃗x | A⃗
YA

YA
Méthode du grand M est un point extrême de K si et seulement si ⃗x est une solution de
⃗ x = ⃗b.
base réalisable du système A⃗

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 17 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 18 / 60

Propriétés de base des problèmes linéaires Théorème fondamental de la PL Propriétés de base des problèmes linéaires Théorème fondamental de la PL

Conséquences Algorithme du simplexe

EN

EN
Si on a une matrice de m lignes et n colonnes, le nombre
maximum de bases est donné par :
LB

LB
 
n n!
JE

JE
=
m m!(n − m)!
Utilise le théorème fondamental de façon efficace :
OU

OU
⇒ Th. fondamental : La solution optimale se trouve parmi les Calculer des solutions de base toujours réalisables
solutions de base Calculer des solutions où z augmente d’une itération à l’autre.
EB

EB
Algorithme : Pivotage : passage d’un sommet à un sommet adjacent plus
1 Énumérer toutes les bases et calculer dans chaque cas la solution rentable.
SIN

SIN
de base ⃗xB = B⃗ −1⃗b
Pn
2 Parmi les solution réalisables, calculer z = i=1 ci xi
3 Garder la meilleure.
S

S
YA

YA
En pratique, inutilisable !
On a besoin d’une méthode qui ne fait pas une énumération
complète des solutions de base.
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 19 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 20 / 60
 Méthode du simplexe Pivots Méthode du simplexe Pivots

Table of Contents Rappels : Pivot dans un système linéaire

N
BE

BE
1 Propriétés de base des problèmes linéaires On considère le système d’équation linéaire :
Forme standard

EL

EL
Solution de base a11 x1 + a12 x2 + . . . + a1n xn = b1 (8)
Théorème fondamental de la PL a21 x1 + a22 x2 + . . . + a2n xn = b2 (9)

UJ

UJ
.. ..
2 Méthode du simplexe . .

BO

BO
Pivots am1 x1 + am2 x2 + . . . + amn xn = bm (10)
Points extrêmes adjacents
INE

INE
Tableau du simplexe
3 Construction d’un tableau initial On peut former des combinaisons linéaires de rangées sans
SS

SS
Problématique changer la valeur de la solution.
Méthode en deux phases Méthode de Gauss : Ramener le système sous sa forme
YA

YA
Méthode du grand M canonique

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 21 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 22 / 60

Méthode du simplexe Pivots Méthode du simplexe Pivots

Méthode de Gauss Forme canonique

EN

EN
On obtient enfin un système sous forme canonique :
1 On divise l’équation (8) par a11 pour avoir un coefficient 1 : x1 + . . . +0 + y1,m+1 xm+1 + y1,m+2 xm+2 + . . . + y1,n xn = y1,0
LB

LB
+ x2 + . . . +0 + y2,m+1 xm+1 + y2,m+2 xm+2 + . . . + y2,n xn = y2,0
a12 a1n b1
JE

JE
x1 + x2 + . . . + xn = (11) .... ....
a11 a11 a11 .. ..
OU

OU
2 On soustrait des multiples de l’équation (11) des autres équations ... +xm + ym,m+1 xm+1 + ym,m+2 xm+2 + . . . + ym,n xn = ym,0
| {z }
pour avoir des 0 dans la première colonne au-dessous de x1 .
EB

EB
variables hors base
Exemple : pour la 2ième équation, on veut annuler a21 donc
(11) × (−a21 ) + (9)
⃗ −1⃗b :
La solution de base correspondante est ⃗xB = B
SIN

SIN

a12

b1
x1 = y1,0
0 + a22 + (−a21 ) x2 + . . . + . = b2 − a21 .. ..
a11 a11 .=.
S

S
YA

YA
3 On répète pour chaque rangée. xm = ym,0
xm+1 = xm+2 = . . . = xn = 0

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 23 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 24 / 60
 Méthode du simplexe Pivots Méthode du simplexe Pivots

Représentation linéaire sous forme de tableau Première interprétation du pivot

N
BE

BE
a11 a12 ... a1n b1
a21 a22 ... a2n b2
Tableau initial : . .. .. .. Étant donné un tableau sous forme canonique correspondant à

EL

EL
.. . ... . . une base
am1 am2 ... amn bm ⃗ = [(⃗a1 ), . . . , (⃗ap ), . . . , (⃗am )]

UJ

UJ
B
On veut changer la base :

BO

BO
Tableau sous forme canonique :
1 . . .. . . y1,m+1 . . . y1,q ... y1,n y1,0 ⃗ = [(⃗a1 ), . . . , (⃗aq ), . . . , (⃗am )]
B
1 . . .. . . y2,m+1 . . . y2,q ... y2,n y2,0
INE

INE
.. .. .. .. .. .. .. .. ..
. . . . .. . . . . . . . . . On veut remplacer une des variables de base xp par une autre
actuellement hors base xq
SS

SS
. . .1 . . . yp,q ... yp,n yp,0
.. .. .. .. .. .. .. .. .. Comment calculer le nouveau tableau ?
YA

YA
. . . . .. . . . . . . . . .
. . .. . . 1 ym,m+1 ... ym,q ... ym,n ym,0

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 25 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 26 / 60

Méthode du simplexe Pivots Méthode du simplexe Pivots

Pivot Exemple
EN

EN
LB

LB
On appelle yp,q le pivot, on a toujours yp,q ̸= 0
JE

JE
1 Diviser la rangée p par yp,q pour avoir 1 dans cette position On considère le système sous forme canonique :
2 On fait des combinaisons linéaires de rangées pour avoir des 0
OU

OU
dans les positions yi,q = 0, i ̸= p x1 + x4 + x5 − x6 = 5
Appelons les coefficients du nouveau tableau sous forme x2 + 2x4 − 3x5 + x6 = 3
EB

EB
′ , nous avons :
canonique yij
x3 − x4 + 2x5 − x6 = 1
ypj
(
′ =y −
SIN

SIN
yij ij ypq yiq i ̸= p Faire entrer les variables x4 , x5 et x6 en base.
′ ypj
ypj = ypq i=p
S

S
YA

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 27 / 60

YA
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 28 / 60
 Méthode du simplexe Pivots Méthode du simplexe Pivots

Conclusion Deuxième interprétation du pivot

N
⃗ x = ⃗b, peut être interprété dans E m
Le système d’équations A⃗

BE

BE
Si on a une solution de base réalisable et si on choisit un pivot comme une équation vectorielle.
quelconque

EL

EL
1 Il n’y a aucune raison que la nouvelle solution de base soit x1⃗a1 + x2⃗a2 + . . . + xn⃗an = ⃗b (12)

UJ

UJ
réalisable
On cherche une représentation de ⃗b (c.l.) en terme des ⃗ai ’s
Pm
2 La valeur de z = i=1 ci yi0 . Après le pivot, même si
′ m ′
≥ 0 ⇒ z ′ = i=1 ci yi0

BO

BO
P
yi0 , on n’a aucune garantie que la valeur de En général, cette représentation n’est pas unique (m < n)
la nouvelle solution réalisable n’est pas supérieure à l’ancienne.
⃗ = [⃗a1 , . . . , ⃗am ], alors cette
Or, si on choisit une base B
Si on veut utiliser des opérations de pivot pour chercher une
INE

INE
solution optimale réalisable, alors on ne doit pas choisir le pivot de représentation sera unique
façon arbitraire si on veut conserver des solutions :
x1⃗a1 + x2⃗a2 + . . . + xm⃗am = ⃗b (13)
SS

SS
1 réalisables ;
2 non croissantes.
Les xi ’s forment la représentation de ⃗b dans la base B
⃗
YA

YA
Simplexe : choix du pivot qui respecte les 2 conditions
On a forcément une représentation des vecteurs hors base ⃗aj ,
⃗
j = m + 1, . . . , n en terme de la base courante B
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 29 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 30 / 60

Méthode du simplexe Pivots Méthode du simplexe Points extrêmes adjacents

Représentation des vecteurs hors base Table of Contents

EN

EN
Théorème 1 Propriétés de base des problèmes linéaires
LB

LB
Forme standard
⃗ sont donnés
Les coefficients de la représentation de ⃗aj dans la base B Solution de base
JE

JE
par le vecteur ⃗yj = [yij ] : Théorème fondamental de la PL
OU

OU
⃗aj = y1j⃗a1 + y2j⃗a2 + . . . + ymj⃗am 2 Méthode du simplexe
Pivots
EB

EB
Points extrêmes adjacents
Tableau du simplexe
1 0 0 1 1 -1 5
SIN

SIN
Exemple : 0 1 0 2 -3 1 3 3 Construction d’un tableau initial
0 0 1 -1 2 -1 -1 Problématique
S

S
Méthode en deux phases
YA

YA
⃗a4 = 1⃗a1 + 2⃗a2 − 1⃗a3 Méthode du grand M

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 31 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 32 / 60
 Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Points extrêmes adjacents

Détermination de la variable qui sort Effet de l’entrée d’une variable arbitraire

N
BE

BE
Supposons que nous avons une solution de base réalisable, On a déjà une représentation de ⃗aq dans la base courante :

EL

EL
quelle variable sort de la base ?
⃗aq = y1q⃗a1 + y2q⃗a2 + . . . + ymq⃗am (15)
⃗b = x1⃗a1 + x2⃗a2 + . . . + xm⃗am

UJ

UJ
(14)
On multiplie (15) par ϵ > 0 et soustraire de (14) :
⃗x = (x1 , x2 , . . . , xm , 0, 0, . . . , 0)

BO

BO
⃗b = (x1 − ϵy1q )⃗a1 + (x2 − ϵy2q )⃗a2 + . . . + (xm − ϵymq )⃗am + ϵ⃗aq

INE

INE
Hypothèse Une c.l. de ⃗b d’au plus (m + 1) vecteurs
Toute solution de base réalisable est non dégénérée : si ϵ = 0, on retrouve l’ancienne solution de base réalisable
SS

SS
xi > 0 i = 1, . . . , m On fait augmenter ϵ (xq ) qui était 0 dans la solution courante
⃗ x = ⃗b soit
Les x1 , . . . , xm doivent s’ajuster pour que le système A⃗
YA

YA
Supposons qu’on a choisi de faire entrer ⃗aq (q > m) en base
toujours vérifié

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 33 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 34 / 60

Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Points extrêmes adjacents

Variable qui sort critère de sortie

EN

EN
 
xi
LB

LB
x′1 = x1 − ϵy1q ϵ = min | yiq > 0 (16)
i yiq
..
JE

JE
.
x′i = xi − ϵyiq si i∗ est le i pour lequel se produit le minimum, alors la variable
OU

OU
x′i∗ = 0 et la colonne i∗ sort de la base
...
Si on a plusieurs x′i qui s’annulent pour la même valeur de ϵ alors
EB

EB
x′m = xm − ϵymq la nouvelle solution est dégénérée.
Si tous les yiq ≤ 0, alors tous les x′i croient (ou restent constants)
SIN

SIN
quand ϵ augmente ⇒ On ne peut plus obtenir des nouvelles
Pour un i donné : solutions de base réalisables.
si yiq > 0 alors x′i décroît quand ϵ augmente ;
S

S
Toutefois, on remarque qu’on peut trouver des solutions
si yiq ≤ 0 alors x′i augmente ou reste fixe quand ϵ augmente ;
YA

YA
réalisables x′i ≥ 0 avec des coefficients très grands ⇒ l’ensemble
On fait augmenter ϵ jusqu’à ce que un des x′i pour lequel yiq > 0 des solutions réalisables n’est pas borné
devienne égale à 0
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 35 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 36 / 60
 Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Points extrêmes adjacents

Détermination de la variable qui sort : sommaire Détermination de la variable qui entre

N
BE

BE
Sommaire

EL

EL
Étant donné une solution de base réalisable et un vecteur ⃗aq hors base
Choix des pivots pour résoudre un programme linéaire
quelconque, on peut trouver soit une nouvelle solution de base

UJ

UJ
Solution réalisable (yiq > 0)⇒ Colonne qui sort
réalisable ayant ⃗aq dans sa base et un vecteur original qui sort, soit L’idée de la méthode du simplexe pour déterminer la colonne qui

BO

BO
l’ensemble des solutions réalisables n’est pas borné. entre est de choisir celle qui donne une nouvelle solution de base
réalisable pour laquelle la fonction-objectif décroît.
Supposons qu’on a le tableau sous forme canonique :
INE

INE
On veut exprimer l’effet sur la fonction-objectif de faire augmenter
1 0 0 2 4 6 4 un des xj hors base
0 1 0 1 2 3 3
SS

SS
0 0 1 -1 2 1 1
YA

YA
On veut faire entrer ⃗a4 .

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 37 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 38 / 60

Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Points extrêmes adjacents

Solution générale Considération de la fonction-objectif

EN

EN
Supposons que nous avons une solution de base réalisable Pour la solution de base :
z0 = c1 x1 + c2 x2 + . . . + cm xm (19)
LB

LB
(xB⃗, 0) = (y1,0 , y2,0 , . . . , ym,0 , 0, . . . , 0) (17)
Si on attribue des valeurs arbitraires aux variables hors base
JE

JE
avec un tableau ayant la matrice identité dans les m 1ière colonnes xm+1 , . . . , xn , nous déterminons les valeurs des autres variables :
OU

OU
⃗b n
a⃗1 a⃗2 a⃗m am+1
⃗ a⃗q a⃗n X
x1 = y10 − y1j xj (20)
1 . . .. . . y1,m+1 ... y1,q ... y1,n y1,0
EB

EB
j=m+1
1 . . .. . . y2,m+1 ... y2,q ... y2,n y2,0 n
.. .. .. .. .. .. .. .. .. X
. . . . .. . . . . . . . . . x2 = y20 − y2j xj (21)
SIN

SIN
. . .1 . . . yp,q ... yp,n yp,0 j=m+1
.. .. .. .. .. .. .. .. .. ..
. . . . .. . . . . . . . . . .
S

S
. . .. . . 1 ym,m+1 ... ym,q ... ym,n ym,0
YA

YA
n
X
xm = ym0 − ymj xj (22)
z = c1 x1 + c2 x2 + . . . + cn xn (18) j=m+1

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 39 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 40 / 60
 Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Points extrêmes adjacents

Expression de z en fonction des variables hors base Coût réduit

N
On définit :

BE

BE
En utilisant (20-22), on peut éliminer x1 , . . . , xm de (18) :
zj = c1 y1j + c2 y2j + . . . + cm ymj j = m + 1, . . . , n

EL

EL
   
Xn X n
z= c1 y10 − c1 y1j xj  + . . . + cm ym0 − cm ymj xj  donc

UJ

UJ
j=m+1 j=m+1 n

BO

BO
X
+cm+1 xm+1 + . . . + cn xn z= ci xi = z0 + (cm+1 − zm+1 )xm+1 + . . . + (cn − zn )xn
i=1
= z0 + {cm+1 − [c1 y1,m+1 + c2 y2,m+1 + . . . + cm ym,m+1 ]} xm+1 n
INE

INE
X
+ {cm+2 − [c1 y1,m+2 + c2 y2,m+2 + . . . + cm ym,m+2 ]} xm+2 = z0 + (cj − zj )xj
.. i=m+1
.
SS

SS
+ {cn − [c1 y1,n + c2 y2,n + . . . + cm ym,n ]} xn
Coût réduit
YA

YA
rj = cj − zj est appelé coût réduit

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 41 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 42 / 60

Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Points extrêmes adjacents

Critère d’entrée en base Cas particulier

EN

EN
Actuellement, xm+1 = xm+2 = . . . = xn = 0
Lorsque xj augmente, le coût réduit rj permet d’ajuster les
LB

LB
x1 , . . . , x m
JE

JE
Laquelle de ces variables hors base doit-on faire augmenter ?
L’effet de faire entrer xj sur la fct-obj est défini par rj Si on a une colonne / rj < 0 et yij ≤ 0 ∀i
OU

OU
si rj > 0 : augmenter xj revient à faire croître z On peut faire croître x′j autant qu’ont veut en conservant une
On choisit de faire entrer uniquement les variables dont rj < 0 solution réalisable
EB

EB
N’importe quelle variable de coût réduit négatif peut entrer en Puisque rj < 0, donc z décroît (−∞), la solution est non bornée.
base
SIN

SIN
mais quel j ?
S

S
Critère d’arrêt (optimalité)
YA

YA
Si tous les rj ≥ 0, l’algorithme s’arrête : cette solution de base
réalisable est optimale
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 43 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 44 / 60
 Méthode du simplexe Points extrêmes adjacents Méthode du simplexe Tableau du simplexe

Variable qui entre Table of Contents

N
BE

BE
1 Propriétés de base des problèmes linéaires
Forme standard

EL

EL
Quelle xj choisir pour faire entrer en base parmi celles telles que Solution de base
rj < 0 Théorème fondamental de la PL

UJ

UJ
xj telle que rj est le plus négatif. 2 Méthode du simplexe

BO

BO
La variable dont le taux de décroissance de la fonction-objectif Pivots
est le plus grand. Points extrêmes adjacents
INE

INE
Le coût réduit rj mesure le coût de la variable xj relatif à la base Tableau du simplexe
courante
3 Construction d’un tableau initial
SS

SS
Le coût réduit relatif à une variable en base est nul.
Problématique
Méthode en deux phases
YA

YA
Méthode du grand M

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 45 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 46 / 60

Méthode du simplexe Tableau du simplexe Méthode du simplexe Tableau du simplexe

Tableau du simplexe Exemple : FRB

EN

EN
Objectif : Mettre toutes les informations nécessaires au
déroulement de l’algorithme du simplexe ensemble
LB

LB
max z =1000x1 + 1200x2
On suppose qu’on a une solution de base réalisable et que le 10x1 + 5x2 ≤ 200
JE

JE
tableau correspondant à A⃗ ⃗ x = ⃗b est sous forme canonique
2x1 + 3x2 ≤ 60
Comment obtenir une solution de base réalisable initiale ?
OU

OU
⃗ x = ⃗b sous forme x1 ≤ 34
En plus des rangées correspondant à A⃗
canonique, nous ajoutons en bas du tableau une rangée x2 ≤ 14
EB

EB
contenant les coûts réduits rj et l’opposée de la valeur de la x1 ≥ 0
fonction-objectif courante.
x2 ≥ 0
SIN

SIN
1 On ajoute une variable indépendante (−z)
2 On ajoute la contrainte c1 x1 + c2 x2 + . . . + cn xn − z = 0
3 On suppose que (−z) est toujours en base : on ne met pas la
S

S
1 Mettre le problème sous forme standard
colonne (z) dans le tableau parce qu’elle est toujours (0, 0, . . . , 0, 1)
YA

YA
2 Résoudre le problème FRB avec la méthode du simplexe.
Initialement, la dernière rangée du tableau du simplexe est formée
Spécifier pour chaque itération la solution de base courante et le
par les ci et un second membre nul
sommet correspondant
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 47 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 48 / 60
 Construction d’un tableau initial Problématique Construction d’un tableau initial Problématique

Table of Contents Modèle FRB modifié

N
BE

BE
1 Propriétés de base des problèmes linéaires P: max z =1000x1 + 1200x2 Ps : min z = − 1000x1 − 1200x2
Forme standard 10x1 + 5x2 ≤ 200 10x1 + 5x2 + s1 = 200

EL

EL
Solution de base
2x1 + 3x2 = 60 2x1 + 3x2 = 60
Théorème fondamental de la PL

UJ

UJ
x1 ≤ 12 x1 + s3 = 12
2 Méthode du simplexe x2 ≥ 6 x2 − s 4 = 6

BO

BO
Pivots
x1 , x2 ≥ 0 x1 , x2 , s1 , s3 , s4 ≥ 0
Points extrêmes adjacents
Le signe "−" qui affecte s4 l’empêche de jouer le rôle d’une
INE

INE
Tableau du simplexe
variable de base
3 Construction d’un tableau initial La contrainte de type "=" garde la même écriture, et
SS

SS
Problématique généralement, ne comporte pas de variable qui, tout en étant
Méthode en deux phases
YA

YA
absente des autres contraintes, admet dans cette contrainte le
Méthode du grand M coefficient +1
⇒ Rend difficile la construction du tableau initial
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 49 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 50 / 60

Construction d’un tableau initial Méthode en deux phases Construction d’un tableau initial Méthode en deux phases

Table of Contents Principe

EN

EN
1 Propriétés de base des problèmes linéaires Phase I : Résoudre un problème auxiliaire.
LB

LB
Forme standard Phase II : Résoudre le vrai problème
Solution de base
JE

JE
Théorème fondamental de la PL
X
P0 : min z = ci xi
OU

OU
i
2 Méthode du simplexe
⃗ = ⃗b
Ax
Pivots
EB

EB
Points extrêmes adjacents ⃗x ≥ 0
Tableau du simplexe
SIN

SIN
3 Construction d’un tableau initial On ajoute des variables artificielles yi aux équations de P0 sous
Problématique
S

S
forme standard qui proviennent de contraintes technologiques de
Méthode en deux phases
YA

YA
signe "≥" ou "="
Méthode du grand M
yi = si si "≤"

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 51 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 52 / 60
 Construction d’un tableau initial Méthode en deux phases Construction d’un tableau initial Méthode en deux phases

Phase I Phase II

N
On résout avec l’algorithme du simplexe le problème PI :

BE

BE
m

EL

EL
X
PI : min zi = yi Le tableau initial de la phase II s’obtient en modifiant le dernier
i=1

UJ

UJ
tableau de la première phase de la façon suivante :
Ax ⃗ = ⃗b
⃗ + Iy 1 les colonnes associées aux variables artificielles sont supprimées ;

BO

BO
⃗x, ⃗y ≥ 0 2 la rangée des coûts réduits est remplacée par les coefficients ci de
la fonction objectif z ;
⃗ b
⃗ 0 et y = 3 les coûts réduits sont recalculés à partir des nouveaux coefficients
INE

INE
Solution de base réalisable initiale x =
de base pour faire apparaître des 0 dans les colonnes
À la solution de PI : correspondant aux variables de base
Si zi > 0 → P0 n’a pas de solution réalisable
SS

SS
⃗ 0 = ⃗b →
En effet, si P0 admet une solution réalisable x⃗0 alors Ax
yi = 0 ∀i → zi = 0
YA

YA
Si zi = 0 ⇒ On démarre la méthode du simplexe sur P0 avec la
base optimale de PI

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 53 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 54 / 60

Construction d’un tableau initial Méthode en deux phases Construction d’un tableau initial Méthode en deux phases

Exemple Exemple : phase I

EN

EN
LB

LB
PI : min z =y2 + y4 (29)
Ps : min z = − 1000x1 − 1200x2 (23) 10x1 + 5x2 + s1 = 200 (30)
JE

JE
10x1 + 5x2 + s1 = 200 (24) 2x1 + 3x2 + y2 = 60 (31)
OU

OU
2x1 + 3x2 = 60 (25) x1 + s3 = 12 (32)
x1 + s3 = 12 (26) x 2 − s 4 + y4 = 6 (33)
EB

EB
x2 − s4 = 6 (27) x1 , x2 , s1 , s3 , s4 ≥ 0 (34)
x1 , x2 , s1 , s3 , s4 ≥ 0 (28)
SIN

SIN
x1 x2 s1 y2 s3 s4 y4 b
Les contraintes (31) et (33) proviennent de contraintes d’égalité et de 10 5 1 0 0 0 0 200 Ce tableau n’est pas encore
S

S
type (≥), on leurs ajoute des variables artificielles y2 et y4 et on résout 2 3 0 1 0 0 0 60 sous forme canonique. Les
YA

YA
le problème de la phase I. 1 0 0 0 1 0 0 12 coûts réduits des variables
0 1 0 0 0 -1 1 6 en base doivent être nuls
0 0 0 1 0 0 1 0
Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 55 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 56 / 60
 Construction d’un tableau initial Méthode en deux phases Construction d’un tableau initial Méthode en deux phases

Déroulement de la phase I Suite

N
BE

BE
x1 x2 s1 y2 s3 s4 y4 b x1 x2 s1 y2 s3 s4 y4 b
10 5 1 0 0 0 0 200 20/3 0 1 -5/3 0 0 0 100

EL

EL
Tableau initial sous forme
2 3 0 1 0 0 0 60 2/3 0 0 1/3 0 1 -1 14 Tableau optimal de la phase
canonique de la phase I. x2

UJ

UJ
1 0 0 0 1 0 0 12 1 0 0 0 1 0 0 12 I.
entre ; y4 sort ; pivot=1
0 1 0 0 0 -1 1 6 2/3 1 0 1/3 0 0 0 20

BO

BO
-2 -4 0 0 0 1 0 -66 0 0 0 1 0 0 1 0
x1 x2 s1 y2 s3 s4 y4 b x1 x2 s1 s3 s4 b
INE

INE
10 0 1 0 0 5 -5 170 20/3 0 1 0 0 100
Tableau initial de la phase II
2 0 0 1 0 3 -3 42 Tableau non optimal. s4 2/3 0 0 0 1 14
non encore sous forme
1 0 0 0 1 0 0 12 entre ; y2 sort ; pivot=3 1 0 0 1 0 12
SS

SS
canonique.
0 1 0 0 0 -1 1 6 2/3 1 0 0 0 20
YA

YA
-2 0 0 0 0 -3 4 -42 -1000 -1200 0 0 0 0

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 57 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 58 / 60

Construction d’un tableau initial Méthode du grand M Construction d’un tableau initial Méthode du grand M

Table of Contents Méthode du grand M

EN

EN
1 Propriétés de base des problèmes linéaires
LB

LB
Forme standard
Solution de base Combiner les phases I et II :
JE

JE
Théorème fondamental de la PL 1 Ajouter les variables artificielles
On ajoute à la fonction-objectif z un terme de pénalité pour chaque
OU

OU
2
2 Méthode du simplexe variable artificielle et on procède en une phase unique
Pivots
EB

EB
Points extrêmes adjacents max zM = 1000x1 + 1200x2 − M a2 − M a4
Tableau du simplexe où M est une constante positive, dont la valeur, sans être précisée,
SIN

SIN
dépasse largement tous les autres nombres présents dans le
3 Construction d’un tableau initial
modèle.
Problématique
S

S
Méthode en deux phases
YA

YA
Méthode du grand M

Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 59 / 60 Yassine Boujelben [email protected] Algorithme du simplexe Chapitre 2 60 / 60