Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

S OMMAIRE

C HAPITRE 4 : P ROGRAMMATION
M ATHÉMATIQUE C ONVEXE 1 P ROGRAMMATION L INÉAIRE

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

4 janvier 2012

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE I C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE 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
> z := c > x =

 min 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 Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE I C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE II

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

D ÉFINITION
Un programme linéaire est dit sous forme standard s’il est écrit
sous la forme C ONTRAINTES DE POSITIVITÉ
 min c > x

On peut toujours supposer que les composantes de x sont
(L) Ax = b,
positives ou nulles. En effet, si une composante xi est sans
x ≥ 0,

contrainte de signe, on écrira xi = xi0 − xi00 avec xi0 ≥ 0 et xi00 ≥ 0.
où x ∈ Rn , A une matrice d’ordre m × n et b ∈ Rm . Dans le cas particulier où une composante xi est minorée
(xi ≥ α par ex.) on posera tout simplement xi0 = xi − α et
P ROBLÈME DE MAXIMISATION introduire la contrainte xi0 ≥ 0.
Si le programme est un problème de maximisation, on peut se
ramèner à une minimisation puisque

max z = − min(−z).
x∈X x∈X

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE III C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE IV

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

E XEMPLE
VARIABLES D ’ ÉCART 
max z = −5x1 − 3x2 + 7x3
Les contraintes de type A1 x ≤ b1 peuvent se mettre sous forme 


 3x1 − 5x2 + 3x3 ≤ 5
de contarintes d’égalité en introduisant des variables d’écrat.


 −4x1 − 9x2 + 4x3 ≤ −4


En effet, si A1 x ≤ b1 alors il existe s ∈ Rm1 , s ≥ 0 tel que
(L) x2 ≤ 4
A1 x + s = b1 (s = A1 x − b1 ).
x1 ≥ −2


De même, les contraintes de type A2 x ≥ b2 peuvent également


 2x1 + 4x2 + 6x3 = 7


se mettre sous forme de contarintes d’égalité en introduisant 
x2 ≥ 0

des variables d’écrat. Si A2 x ≥ b2 alors il existe t ∈ Rm2 , t ≥ 0
tel que A2 x − t = b2 . Les variables x1 et x3 sont sans contrainte de signe. Puisque
x1 ≥ −2 on pose x10 = x1 + 2. On pose aussi et x3 = x30 − x300 .
Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE V C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE VI

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


 max z = −5(x10 − 2) − 3x2 + 7(x30 − x300 ) rend le second membre positif ou nul.
3(x10 − 2) − 5x2 + 3(x30 − x300 ) ≤ 5


0 0 00
 
 min0 z = 5x1 + 3x 2 − 7x3 + 7x3 − 10

−4(x10 − 2) − 9x2 + 4(x30 − x300 ) ≤ −4

 
(L) 
 3x1 − 5x2 + 3x30 − 3x300 ≤ 11
x2 ≤ 4 

x2 ≤ 4

 
 2(x10 − 2) + 4x2 + 6(x30 − x300 ) = 7

 (L)

 0 4x10 + 9x2 − 4x30 + 4x300 ≥ 12
x1 , x2 , x30 , x300 ≥ 0


2x 0 + 4x2 + 6x30 − 6x300 = 11


 01


x1 , x2 , x30 , x300 ≥ 0

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE VII C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE VIII

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

En posant
 
On introduit ensuite les variables d’écart. 3 −5 3 −3 1 0 0
 0 1 0 0 0 1 0 
 0 0 00 A= 
 min0 z = 5x1 + 3x 2 − 7x3 + 7x3 − 10 9 −4 0 −1
  4 4 0 



 3x1 − 5x2 + 3x30 − 3x300 + s1 = 11 2 4 6 −6 0 0 0
x2 + s2 = 4

(L)

 4x10 + 9x2 − 4x30 + 4x300 − t1 = 12 c = (5, 3, −7, 7, 0, 0, 0)> x = (x10 , x2 , x30 , x300 , s1 , s2 , t1 )>
2x 0 + 4x2 + 6x30 − 6x300 = 11

b = (11, 4, 12, 11)> on obtient la forme standard

 01


x1 , x2 , x30 , x300 , s1 , s2 , t1 ≥ 0
 min c > x


(L) Ax = b,
x ≥ 0.

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE IX C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE X

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

Par la suite, et sauf indication contraire, on va considérer des D ÉFINITION

programmes sous la forme standard On appelle
1 n : le nombre de variables,
 min c > x


(L) Ax = b, 2 m : le nombre de contraintes,

x ≥ 0,

3 x : le vecteur des inconnues (variables de décisions),
Xm
où A est une matrice de dimension m × n, 4 z = c>x = ci xi : la fonction objectif (fonction
b = (b1 , . . . , bm )> ∈ Rm , c = (c1 , . . . , cn )> ∈ Rn et i=1
x = (x1 , . . . , xn )> ∈ Rn . économique).

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE XI C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE I

F ORME STANDARD D ’ UN P ROGRAMME L INÉAIRE D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

On utilsera par la suite les définitions suivantes :

R EMARQUE
1 Base : toute sous-matrice carrée d’ordre m inversible
extraite de A.
1 On suppose que n > m.
Soit B une base et supposons que A = (B, N) (quitte à
2 On suppose que rang(A) = m, où rang(A) est le rang de la permuter les colonnes de A). De même soit xB (resp. cB ) le
matrice A sans perte de généralité puisque si rang(A) < m, vecteur extrait de x (resp. c) dont les indices des
alors certaines contraintes seraient redondantes ; c’est à composantes correspondent aux indices
 descolonnes de
dire qu’elles résulteraient des autres contraintes.
 
xB cB
B. On écrira alors x = et c = .
xN cN
2 xB : le vecteur des variables de base.
3 xN : le vecteur des variables hors-base.
Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE II C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE III

D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

P ROPOSITION
4 Solution de base : une solution du système Ax = b avec
L’ensemble X := {x ∈ Rn | Ax = b, x ≥ 0} est convexe. C’est à
xN = 0 ∈ Rn−m . On a
dire que
Ax = b ⇐⇒ BxB + NxN = BxB = b. ∀α ∈ [0, 1], ∀x, y ∈ X , αx + (1 − α)y ∈ X .
Donc x est solution de base, si −1
et seulement
 si, xB = B −1 b On l’appelle polyèdre.
B b
et xN = 0. C’est à dire x =
0
D ÉFINITION
5 Une solution de base est réalisable si xB := B −1 b ≥ 0.
Un point x ∈ X est un point extrême (ou sommet), s’il ne peut
6 Une base est réalisable si B −1 b ≥ 0. pas s’exprimer comme combinaison convexe d’autres points de
7 Une base est dégénérée si xB := B −1 b a des X distincts de x. C’est à dire que x est un point extrême de X ,
composantes nulles. 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 .

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE IV C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE V

D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

P REUVE
Soit x une solution de base réalisable. Par l’absurde supposons
que x n’est pas un sommet. Alors

T HÉORÈME ∃(x1 , x2 ) ∈ X ×X , x1 6= x2 et λ ∈]0, 1[ tels que x = λx1 +(1−λ)x2 .

L’ensemble des points extrêmes de X est identique à
Les variables hors-base sont nulles puisque x est une solution
l’ensemble de toutes les solutions de base réalisables.
de base. Soit I l’ensemble des indices des variables hors-base.
Donc
λx1i + (1 − λ)x2i = 0 ∀i ∈ I,
où x1i et x2i sont les composantes d’inces i ∈ I, respectives de
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 Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE VI C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE VII

D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

D’autre part, Ax1 = Ax2 = b entraîne que Bx1B = Bx2B = b. P

D’où x1B = x2B = xB (d’après l’unicité de xB ) et par suite D’un autr coté on a j∈J xj aj = b (i.e. Ax = b) et donc
x = x1 = x2 . Ce qui contredit l’hypothèse. Donc x est un X X
sommet. (xj + r λj )aj = b et (xj − r λj )aj = b ∀r ∈ R.
Supposons maintenant que x est un sommet de X et montrons j∈J j∈J
que x est une solution de base.
Soit J = {j ∈ I | xj > 0} et montrons que la famille (aj )j∈J , où aj On choisit r > 0 pour que les points y et z définis par leur
est une colonne de A est libre lorsque J n’est pas vide. composantes yj et zj respectivement par
Si J = ∅, alors x = 0 ∈ X et donc b = 0 et quelque soit la base
yj = xj + r λj si j ∈ J et yj = 0 si j 6∈ J,
B, B −1 b = 0 et 0 est la seule solution de base réalisable.
Si J 6= ∅. Supposons que (aj )j∈J est liée. Alors zj = xj − r λj si j ∈ J et zj = 0 si j 6∈ J,
appartiennent à X .
X
∃λj , j ∈ J, non tous nuls tels que λj aj = 0.
j∈J

Programmation Linéaire Forme standard d’un Programme Linéaire Programmation Linéaire Forme standard d’un Programme Linéaire

C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE VIII C HAPITRE 4 : P ROGRAMMATION M ATHÉMATIQUE IX

D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES D ÉFINITIONS ET P ROPRIÉTÉS G ÉNÉRALES

Si 0 < r < min{α, β} alors y ∈ X et z ∈ X . On a 12 y + 21 z = x

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