Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme

ard d’un Programme Linéaire Polyèdre et Sommets

S OMMAIRE

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET 1 P ROGRAMMATION L INÉAIRE

A LGORITHME DU S IMPLEXE

2 F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE

31 décembre 2021 3 P OLYÈDRE ET S OMMETS

Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE I A LGORITHME DU S IMPLEXE II
P ROGRAMMATION L INÉAIRE P ROGRAMMATION L INÉAIRE

On désignera par z,
En général, un problème de programmation linéaire a la forme
suivante : n
X
min c > x z := c > x =


 ci xi .
A1 x ≤ b1 ,

i=1
(L)
A x ≥ b2 ,
 2 On note que les égalités et inégalités dans (L) sont prises au


A3 x = b3 ,
sens vectoriel et on pose
avec x ∈ Rn , c ∈ Rn ; A1 , A2 et A3 sont respectivement des
matrices d’ordre m1 × n, m2 × n, m3 × n ; b1 ∈ Rm1 , b2 ∈ Rm2 et X := {x ∈ Rn | A1 x ≤ b1 , A2 x ≥ b2 , A3 x = b3 },
b3 ∈ Rm3 .
l’ensemble des contraintes.
Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE I A LGORITHME DU S IMPLEXE II
F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE

D ÉFINITION
P ROBLÈME DE MAXIMISATION
Un programme linéaire est dit sous forme standard s’il est écrit
Si le programme est un problème de maximisation, on peut se
sous la forme
ramèner à une minimisation puisque
 min c > x


(L) Ax = b,
max z = − min(−z).
x ≥ 0,

x∈X x∈X

où x ∈ Rn , A une matrice d’ordre m × n et b ∈ Rm .

Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE III A LGORITHME DU S IMPLEXE IV
F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE

VARIABLES D ’ ÉCART
C ONTRAINTES DE POSITIVITÉ
Les contraintes de type A1 x ≤ b1 peuvent se mettre sous forme
On peut toujours supposer que les composantes de x sont de contarintes d’égalité en introduisant des variables d’écrat.
positives ou nulles. En effet, si une composante xi est sans En effet, si A1 x ≤ b1 alors il existe s ∈ Rm1 , s ≥ 0 tel que
contrainte de signe, on écrira xi = xi0 − xi00 avec xi0 ≥ 0 et xi00 ≥ 0. A1 x + s = b1 (s = b1 − A1 x).
Dans le cas particulier où une composante xi est minorée De même, les contraintes de type A2 x ≥ b2 peuvent également
(xi ≥ α par ex.) on posera tout simplement xi0 = xi − α et se mettre sous forme de contarintes d’égalité en introduisant
introduire la contrainte xi0 ≥ 0. des variables d’écrat. Si A2 x ≥ b2 alors il existe t ∈ Rm2 , t ≥ 0
tel que A2 x − t = b2 .
Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE V A LGORITHME DU S IMPLEXE VI
F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE

E XEMPLE

max z = −5x1 − 3x2 + 7x3
max z = −5(x10 − 2) − 3x2 + 7(x30 − x300 )

 

 3x1 − 5x2 + 3x3 ≤ 5 
3(x10 − 2) − 5x2 + 3(x30 − x300 ) ≤ 5

 

 −4x1 − 9x2 + 4x3 ≤ −4

 

−4(x10 − 2) − 9x2 + 4(x30 − x300 ) ≤ −4


(L) x2 ≤ 4 (L)
 x1 ≥ −2

 
 x2 ≤ 4
2(x 0 − 2) + 4x2 + 6(x30 − x300 ) = 7
 
2x1 + 4x2 + 6x3 = 7
 
 0 1

 

x1 , x2 , x30 , x300 ≥ 0

x2 ≥ 0


Les variables x1 et x3 sont sans contrainte de signe. Puisque

x1 ≥ −2 on pose x10 = x1 + 2. On pose aussi x3 = x30 − x300 .

Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE VII A LGORITHME DU S IMPLEXE VIII
F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE

On transforme ensuite la maximisation en minimisation et on

On introduit ensuite les variables d’écart.
rend le second membre positif ou nul.
min z = 5x10 + 3x2 − 7x30 + 7x300 − 10

min z = 5x10 + 3x2 − 7x30 + 7x300 − 10
 
0 0 00

 3x1 − 5x2 + 3x3 − 3x3 + s1 = 11
 

3x10 − 5x2 + 3x30 − 3x300 ≤ 11

 
x2 + s2 = 4

 
(L)

x2 ≤ 4

(L) 4x10 + 9x2 − 4x30 + 4x300 − t1 = 12
4x10 + 9x2 − 4x30 + 4x300 ≥ 12


  2x 0 + 4x2 + 6x 0 − 6x 00 = 11

 01 3 3

2x 0 + 4x2 + 6x30 − 6x300 = 11
 

x1 , x2 , x30 , x300 , s1 , s2 , t1 ≥ 0

 01


x1 , x2 , x30 , x300 ≥ 0
Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE IX A LGORITHME DU S IMPLEXE I
F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

En posant

3 −5 3 −3 1 0 0
 Par la suite, et sauf indication contraire, on va considérer des
 0 1 0 0 0 1 0  programmes sous la forme standard
A= 
 4 9 −4 4 0 0 −1 
 min c > x

2 4 6 −6 0 0 0
(L) Ax = b,
x ≥ 0,

c = (5, 3, −7, 7, 0, 0, 0)> x = (x10 , x2 , x30 , x300 , s1 , s2 , t1 )>
b = (11, 4, 12, 11)> on obtient la forme standard où A est une matrice de dimension m × n,
b = (b1 , . . . , bm )> ∈ Rm , c = (c1 , . . . , cn )> ∈ Rn et
 min c > x

x = (x1 , . . . , xn )> ∈ Rn .
(L) Ax = b,
x ≥ 0.


Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE II A LGORITHME DU S IMPLEXE III
D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

D ÉFINITION
On appelle R EMARQUE
1 On suppose que n > m.
1 n : le nombre de variables,
2 m : le nombre de contraintes, 2 On suppose que rang(A) = m, où rang(A) est le rang de la
3 x : le vecteur des inconnues (variables de décisions), matrice A sans perte de généralité puisque si rang(A) < m,
n alors certaines contraintes seraient redondantes ; c’est à
X
4 z=c x => ci xi : la fonction objectif (fonction dire qu’elles résulteraient des autres contraintes.
i=1
économique).
Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE I A LGORITHME DU S IMPLEXE II
D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

4 Solution de base : une solution du système Ax = b avec

On utilsera par la suite les définitions suivantes :
xN = 0 ∈ Rn−m . On a
1 Base : toute sous-matrice carrée d’ordre m inversible
extraite de A. Ax = b ⇐⇒ BxB + NxN = BxB = b.
Soit B une base et supposons que A = (B, N) (quitte à
permuter les colonnes de A). De même soit xB (resp. cB ) le Donc x est solution de base, si −1
et seulement
 si, xB = B −1 b
B b
vecteur extrait de x (resp. c) dont les indices des et xN = 0. C’est à dire x =
0
composantes correspondent aux indices
 descolonnes de
Une solution de base est réalisable si xB := B −1 b ≥ 0.
 
xB cB 5
B. On écrira alors x = et c = .
xN cN 6 Une base est réalisable si B −1 b ≥ 0.
2 xB : le vecteur des variables de base. 7 Une base est dégénérée si xB := B −1 b a des
3 xN : le vecteur des variables hors-base. composantes nulles.

Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE I A LGORITHME DU S IMPLEXE II
P OLYÈDRE ET S OMMETS P OLYÈDRE ET S OMMETS

D ÉFINITION
Un point x ∈ X est un point extrême (ou sommet), s’il ne peut
P ROPOSITION
pas s’exprimer comme combinaison convexe d’autres points de
L’ensemble X := {x ∈ Rn | Ax = b, x ≥ 0} est convexe. C’est à X distincts de x. C’est à dire que x est un point extrême de X ,
dire que si et seulement si, il n’existe pas de couple (x1 , x2 ) ∈ X × X ,
x1 6= x2 , et λ ∈]0, 1[ tels que x = λx1 + (1 − λ)x2 .
∀α ∈ [0, 1], ∀x, y ∈ X , αx + (1 − α)y ∈ X .

On l’appelle polyèdre. T HÉORÈME

L’ensemble des points extrêmes de X est identique à
l’ensemble de toutes les solutions de base réalisables.
Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE III A LGORITHME DU S IMPLEXE IV
P OLYÈDRE ET S OMMETS P OLYÈDRE ET S OMMETS

P REUVE
Soit x une solution de base réalisable. Par l’absurde supposons D’autre part, Ax1 = Ax2 = b entraîne que Bx1B = Bx2B = b.
que x n’est pas un sommet. Alors D’où x1B = x2B = xB (d’après l’unicité de xB ) et par suite
x = x1 = x2 . Ce qui contredit l’hypothèse. Donc x est un
∃(x1 , x2 ) ∈ X ×X , x1 6= x2 et λ ∈]0, 1[ tels que x = λx1 +(1−λ)x2 .
sommet.
Les variables hors-base sont nulles puisque x est une solution Supposons maintenant que x est un sommet de X et montrons
de base. Soit I l’ensemble des indices des variables hors-base. que x est une solution de base.
Donc Soit J = {j ∈ I | xj > 0} et montrons que la famille (aj )j∈J , où aj
λx1i + (1 − λ)x2i = 0 ∀i ∈ I, est une colonne de A est libre lorsque J n’est pas vide.
Si J = ∅, alors x = 0 ∈ X et donc b = 0 et quelque soit la base
où x1i et x2i sont les composantes d’inces i ∈ I, respectives de B, B −1 b = 0 et 0 est la seule solution de base réalisable.
x1 et x2 . Puisque x1 ∈ X et x2 ∈ X alors x1i ≥ 0 et x2i ≥ 0, et
donc x1i = x2i = 0 pour tout i ∈ I.

Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE V A LGORITHME DU S IMPLEXE VI
P OLYÈDRE ET S OMMETS P OLYÈDRE ET S OMMETS

On choisit r > 0 pour que les points y et z définis par leur

composantes yj et zj respectivement par
Supposons J 6= ∅ et que (aj )j∈J est liée. Alors
X yj = xj + r λj si j ∈ J et yj = 0 si j 6∈ J,
∃λj , j ∈ J, non tous nuls tels que λj aj = 0.
j∈J zj = xj − r λj si j ∈ J et zj = 0 si j 6∈ J,
appartiennent à X . Tenant compte de ce qui précède, on a
P
D’un autre côté on a j∈J xj aj = b (i.e. Ax = b) et donc
X X xj
(xj + r λj )aj = b et (xj − r λj )aj = b ∀r ∈ R. y ∈ X ⇐⇒ r ≤ − pour les j tels que λj < 0,
λj
j∈J j∈J
xj
z ∈ X ⇐⇒ r ≤ pour les j tels que λj > 0.
λj
Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets Programmation Linéaire Forme standard d’un Programme Linéaire Polyèdre et Sommets

C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET C HAPITRE 3 : P ROGRAMMATION L INÉAIRE ET

A LGORITHME DU S IMPLEXE VII A LGORITHME DU S IMPLEXE VIII
P OLYÈDRE ET S OMMETS P OLYÈDRE ET S OMMETS

Soit
n xj o nx
j
o
α = min − | λj < 0 et β = min | λj > 0 .
j∈J λj j∈J λj
C ONSÉQUENCE
Si 0 < r < min{α, β} alors y ∈ X et z ∈ X . On a 12 y + 21 z = x Le polyèdre X = {x ∈ Rn | Ax = b, x ≥ 0} a un nombre fini de
avec x 6= y 6= z ; c’est à dire que x n’est pas un point extrême. points extrêmes inférieur ou égal à Cnm (le nombre de
Ce qui est absurde. D’où la famille (aj )j∈J est libre. En combinaisons de m colonnes de A parmi n).
complétant, si nécessaire, cette famille en une base
B = (aj )j∈J∪J 0 , on aura BxB = b où xB est le sous-vecteur de x
les indices des composantes sont dans J ∪ J 0 , puisqu’on a
dont P
déjà j∈J xj aj = b et xj = 0 pour j ∈ J 0 . D’où x est une solution
de base réalisable.