V.2. Optimisation à données affines (Programmation linéaire)
forme canonique d’un programme linéaire ; une autre présentation est la forme
dite standard (1) :
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax = b
x 0.
(5.14)
On passe de la forme canonique (avec A, b, c) à la forme standard, de la manière
suivante :
a i , x b i
dans R n
devient
Il existe u i 0 tel que
a i , x + u i = b i
;
d’où
⎛
⎜
⎝
Ax b
x 0
dans R n
⎞
⎟
⎠ devient
Ax + I m u = b
x 0, u 0
.
Le programme linéaire de (5.13) est transporté dans R n × R m à présent :
P
⎧
⎪ ⎨
⎪ ⎩
Maximiser c
, x
A
x
= b
,
x
0
où x
= (x, u) ∈ R n × R m ,
(5.15)
avec A
= [A | I m ] ∈ M m,n+m (R), b
= b et c
= (c, 0) .
Les problèmes d’optimisation (5.13) et (5.15) sont équivalents au sens où résoudre l’un permet de résoudre l’autre. Ainsi tous les résultats sur les programmes
linéaires formulés sous la forme standard ont des contreparties sur les programmes
linéaires formulés sous une forme canonique, et vice versa.
La résolution d’un programme linéaire est interprétée géométriquement
comme suit : Si C est le polyèdre convexe fermé définissant les contraintes, maximiser c, x pour x ∈ C revient à chercher à s’appuyer sur C avec un hyperplan
d’équation c, x = constante ; l’ensemble des solutions (lorsqu’il y en a) est une
face de C exposée par c.
– Soit C un polyèdre convexe fermé de R n décrit de la manière suivante :
Ax = b
x 0
, avec A ∈ M m,n (R) de rang m.
(5.16)
(1) Ces appellations ne sont pas universelles, certains auteurs les permutent même. Canonique
doit être compris ici au sens de « naturelle, toujours possible dans l’espace des variables x » ;
standard au sens de « on peut toujours s’y ramener, quitte à ajouter des variables ».
169
forme canonique d’un programme linéaire ; une autre présentation est la forme
dite standard (1) :
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax = b
x 0.
(5.14)
On passe de la forme canonique (avec A, b, c) à la forme standard, de la manière
suivante :
a i , x b i
dans R n
devient
Il existe u i 0 tel que
a i , x + u i = b i
;
d’où
⎛
⎜
⎝
Ax b
x 0
dans R n
⎞
⎟
⎠ devient
Ax + I m u = b
x 0, u 0
.
Le programme linéaire de (5.13) est transporté dans R n × R m à présent :
P
⎧
⎪ ⎨
⎪ ⎩
Maximiser c
, x
A
x
= b
,
x
0
où x
= (x, u) ∈ R n × R m ,
(5.15)
avec A
= [A | I m ] ∈ M m,n+m (R), b
= b et c
= (c, 0) .
Les problèmes d’optimisation (5.13) et (5.15) sont équivalents au sens où résoudre l’un permet de résoudre l’autre. Ainsi tous les résultats sur les programmes
linéaires formulés sous la forme standard ont des contreparties sur les programmes
linéaires formulés sous une forme canonique, et vice versa.
La résolution d’un programme linéaire est interprétée géométriquement
comme suit : Si C est le polyèdre convexe fermé définissant les contraintes, maximiser c, x pour x ∈ C revient à chercher à s’appuyer sur C avec un hyperplan
d’équation c, x = constante ; l’ensemble des solutions (lorsqu’il y en a) est une
face de C exposée par c.
– Soit C un polyèdre convexe fermé de R n décrit de la manière suivante :
Ax = b
x 0
, avec A ∈ M m,n (R) de rang m.
(5.16)
(1) Ces appellations ne sont pas universelles, certains auteurs les permutent même. Canonique
doit être compris ici au sens de « naturelle, toujours possible dans l’espace des variables x » ;
standard au sens de « on peut toujours s’y ramener, quitte à ajouter des variables ».
169