51 CHAPITRE 4.
PROGRAMMATION LINÉAIRE
La transformation réciproque consiste à poser A0 := A Im , b0 = b et c0 := (c, 0).
Concrètement, cela revient à ajouter des variables d’écart y et à considérer le programme
Min cT x
s.c. Ax + y = b
x, y ≥ 0.
Passage de la forme standard à la forme inéquationnelle et réciproquement
A
Pour passer de la forme standard à la forme inéquationnelle, on pose A0 := −A ,
−In
b
b0 := −b , c0 := c. Le programme
0
0
Min c T x
s.c. A0 x ≤ b0 ,
est alors clairement équivalent au programme (4.3).
La transformation réciproque est un peu plus subtile. On a alors le programme linéaire
sous forme standard suivant :
Min c0T x0
s.c. A0 x0 = b0 (4.5)
0
x ≥ 0,
avec A0 := A −A Im , b0 := b et c0 := (c, −c, 0). Il faut montrer que toute solution
optimale de l’équation (4.1) donne une solution optimale de ce programme et réciproquement.
Pour ce faire, nous allons montrer que toute solution réalisable de l’équation (4.1) donne une
solution réalisable de même coût pour ce programme.
Prenons une solution réalisable x du programme (4.1). On construit les variables u, v ∈
R et y ∈ Rm de la manière suivante
n
yi := bi − (Ax)i pour j = 1, . . . , m
et
xj si xj ≥ 0 −xj si xj ≤ 0
uj := et vj := pour j = 1, . . . , n.
0 sinon, 0 sinon,
Il est alors aisé de vérifier que x0 := (u, v, y) est une solution réalisable du programme (4.5),
et que l’on a bien cT x = cT u − cT v.
Réciproquement, soient x0 = (u, v, y) une solution réalisable du programme (4.5). Posons
x := u − v. Le vecteur x est alors une solution réalisable du programme (4.3), et l’on a bien
cT x = cT u − cT v.
CHAPITRE 4. PROGRAMMATION LINÉAIRE 52
4.2.2 Préliminaires
Dans la suite, on supposera sans perte de généralité, que la matrice A de la forme standard
(4.3) est de plein rang, c’est-à-dire que les m lignes sont linéairement indépendantes. En effet,
on peut tester l’existence d’une solution réalisable en résolvant l’équation Ax = b (par des
pivots de Gauss par exemple). S’il y a une solution réalisable et si les lignes de A ne sont pas
linéairement indépendantes, alors forcément l’équation correspondante est redondante et on
peut la supprimer. D’où
Hypothèse : Nos programmes linéaires sous forme standard seront tels que A est de plein
rang.
4.2.3 Solutions basiques réalisables
On suppose toujours que A est une matrice m × n, de plein rang. Pour introduire la
notion de solution basique, nous introduisons la notation suivante : pour une partie B ⊆
{1, 2, . . . , n}, on note AB la sous-matrice de A réduite aux colonnes indicées par les éléments
de B.
Par exemple, si
1 2 0 3 3 1
A = 0 8 9 3 4 4 ,
5 6 0 7 1 1
et si B = {1, 4, 5} alors
1 3 3
AB = 0 3 4 .
5 7 1
Une notation semblable sera utilisée pour les vecteurs : si x = (5, 4, 5, 1, 1, 2) et B =
{1, 4, 5}, alors xB = (5, 1, 1).
Remarquons que pour une partie B fixée, on peut réécrire l’égalité Ax = b sous la forme
AB xB + AN xN = b, (4.6)
où N est le complémentaire de B dans {1, . . . , n}.
Une partie B ∈ {1, 2, . . . , n} à m éléments est appelée base si la matrice AB est inver-
sible. Dans ce cas, on peut réécrire le système Ax = b dans la base B en transformant
l’écriture (4.6) en
xB + A−1 −1
B AN xN = AB b.
La solution x̃ du système Ax = b obtenue en posant x̃B := A−1 B b et x̃N := 0 est une solution
basique. Si cette solution basique est réalisable (par rapport au programme linéaire (4.3)),
i.e. si A−1
B b ≥ 0, alors on dit que x̃ est une solution basique réalisable, et que B est une base
réalisable.
On a alors le théorème important suivant qui constitue la base de l’algorithme du sim-
plexe.
