Programmation linéaire et Optimisation

Chapitre 1

Un p r o b lè m e d’optimisation l i né a i r e en dimension 2

On considère le cas d’un fabricant d’automobiles qui propose deux modèles à la vente, des
grosses voitures et des petites voitures. Les voitures de ce fabriquant sont tellement à la mode
qu’il est certain de vendre tout ce qu’il parvient à produire, au moins au prix catalogue actuel de
16000 euros pour les grosses voitures, et 10000 euros pour les petites voitures. Son problème vient
de l’approvisionnement limité en deux matières premières, le caoutchouc et l’acier. La construction
d’une petite voiture nécessite l’emploi d’une unité de caoutchouc et d’une unité d’acier, tandis
que celle d’une grosse voiture nécessite une unité de caoutchouc mais deux unités d’acier.
Sachant que son stock de caoutchouc est de 400 unités et son stock d’acier de 600 unités, combien
doit-il produire de petites et de grosses voitures au moyen de ces stocks afin de maximiser son
chiffre d’affaire ?
Nous appellerons x le nombre de grosses voitures produites, y le nombre de petites voitures
produites, et z le chiffre d’affaire résultant. Le problème se traduit alors sous la forme
maximiser z = 16000x + 10000y
sous les contraintes x + y ≤ 400 (1.1)
2x + y ≤ 600
x ≥ 0, y ≥ 0.

1.1 Solution graphique

Un tel système, parce qu’il ne fait intervenir que deux variables, peu se résoudre assez
facilement de manière graphique, en hachurant la zone correspondant aux contraintes, et en
traçant les lignes de niveaux (ici des lignes parallèles) de la fonction à maximiser (cfr. graphique
ci-dessous). On obtient ainsi la solution optimale x = 200 et y = 200,
qui correspond à z = 5200000. Elle est unique dans ce cas précis, et correspond à un
“sommet” de la zone de contraintes.

1
1.2 Sensibilité à la variation des stocks

Observons comment la solution du problème évolue lorsqu’on modifie certaines données de départ,
par exemple une augmentation du stock de caoutchouc ou du stock d’acier.

Imaginons que le stock d’acier soit de 700 au lieu de 600, le nouveau problème s’écrit

maximiser z = 16000x + 10000y

sous les contraintes x + y ≤ 400
(1.2)
2x + y ≤ 700
x ≥ 0, y ≥ 0.

Toujours de manière graphique, on s’aperçoit que la solution optimale est maintenant donnée
par x = 300 et y = 100, ce qui correspond à z = 5800000. Autrement dit, une augmentation de
100 unités d’acier a un impact de 600000 euros sur le chiffre d’affaire. On dira alors que le prix
marginal de l’unité d’acier est de 6000 euros.

2
 Si le stock d’acier passe à 800, la solution optimale devient x = 400 et y = 0 et le chiffre
d’affaire z = 6400000. Augmenter le stock d’acier au-d e l à de 800, sans changer le stock de
caoutchouc, n’a plus aucune influence sur la solution optimale, car y est contraint à rester positif.

Imaginons maintenant que le stock d’acier reste f i xé à 600 mais que le stock de caou- tchouc
passe de 400 à 500. Le nouveau problème s’écrit

maximiser z = 16000x + 10000y

sous les contraintes x + y ≤ 500
(1.3)
2x + y ≤ 600
x ≥ 0, y ≥ 0.

Toujours de manière graphique, on s’aperçoit que la solution optimale est maintenant donnée
par x = 100 et y = 400, ce qui correspond à z = 5600000. Autrement dit, une augmentation de
100 unités de caoutchouc à un impact de 400000 euros sur le chiffre

3
d’affaire. On dira alors que le prix marginal de l’unité de caoutchouc est de 4000 euros.

Si le stock de caoutchouc passe à 600, la solution optimale devient x = 0 et y = 600

et le chiffre d’affaire z = 6000000. Augmenter le stock de caoutchouc au-d e l à de 600,
sans changer le stock d’acier, n’a plus aucune influence sur la solution optimale, car x est contraint à rester
positif.

4
1.3 Le p r ob lèm e dual du concurrent

Supposons maintenant que le fabricant d’automobile possède un concurrent qui, pour honorer
des commandes en trop grand nombre, se propose de lui racheter tous ses stocks. Ce dernier doit faire
une offre de prix (la même, disons u) pour chaque unité de caoutchouc et une offre de prix (disons v)
pour chaque unité d’acier. Pour que l’offre soit acceptée, il faut que le prix p ayé par le concurrent
soit au moins é ga l à ce que le fabriquant pourrait en tirer en produisant des voitures. Le
problème du concurrent s’écrit ainsi

minimiser p = 400u +600v

sous les contraintes u + v ≥ 10000
(1.4)
u + 2v ≥ 16000
u ≥ 0, v ≥ 0.

Une analyse graphique fournit la solution optimale u = 4000 et v = 6000, ce qui corres- pond à un
prix global p = 5200000. On remarque (nous verrons par la suite que ce n’est pas un hasard) que la
solution optimale du problème du concurrent (on parlera de problème dual, par opposition au
problème primal du fabriquant) correspond aux prix marginaux du problème du fabricant, et que
le prix minimal que puisse proposer le concurrent est
ég a l au chiffre d’affaire maximal du fabricant.

5
Chapitre 2

Un p r o b lè m e d’optimisation l i né a i r e en dimension s u pér i eure

Dans ce chapitre, nous allons décrire un problème de transport optimal assimilable à un

problème d’optimisation linéaire en dimension 6. De ce fait, il ne sera plus possible de le résoudre
au moyen de la méthode graphique du chapitre précédent.
Notre fabricant d’automobiles possède trois chaˆınes de montage M1, M2 et M3, tandis que son
stock d’acier provient de deux aciéries A1 et A2. Les coûts de transport d’une unité d’acier
d’une aciérie vers une usine de montage sont donnés par le tableau suivant :

M1 M2 M3
A1 9 16 28
A2 14 29 19
Les besoins de production des chaˆınes de montage diffèrent, ainsi que les capacités de production
des aciéries, et sont données par les deux tableaux suivants :

M1 142
A1 206
M2 266
A2 394
M3 192

Il s’agit donc pour le fabricant de déterminer le plan de transport des unités d’acier produites
vers les chaˆınes de montage afin de minimiser le c o ût total de transport. Pour i = 1, 2 et j = 1, 2,
3, notons xij le nombre d’unités d’acier acheminées depuis l’aciérie Ai vers la chaˆıne de montage
Mj. Le problème de transport optimal peut alors s’écrire :

minimiser t = 9x11 +16x12 +28x13 +14x21 +29x22 +19x23

sous les contraintes 𝑥11 +x12 +x13 ≤ 206,
𝑥21 +x22 +x23 ≤ 394,
𝑥11 +x21 ≥ 142,
𝑥12 +x22 ≥ 266,
𝑥13 +x23 ≥ 192,
x11, x12, x13, x21, x22, 𝑥23 ≥ 0.

Nous verrons par la suite qu’il est possible de traiter un tel problème de manière
systématique, par le biais d’une réduction à une forme standard suivie d’un algorithme

6
 qui porte le nom de méthode du simplexe. Toutefois, dans ce cas précis, cela nous mènerait à des
manipulations trop fastidieuses pour êt re réa l i sées sans l’aide d’un ordinateur. A sa place, nous
allons procéder à un certain nombre de remarques ad hoc qui vont nous permettre de poursuivre
les calculs à la main.
La remarque principale ici est que dans la mesure o ù la somme des capacités productions des
aciéries (206 + 394 = 600) est égale à la somme des besoins de production des trois chaˆınes de
montage (142 + 266 + 192 = 600), chacune des 5 premières inégalités dans le problème
d’optimisation ci-dessus doit nécessairement être une égalité. Si on omet momentanément de
s’occuper des contraintes xij ≥ 0 (i = 1, 2, j = 1, 2, 3), les contraintes restantes se réduisent à un
système de 5 équations à 6 inconnues, que nous pouvons tenter de résoudre par la méthode du
pivot de Gauss (cfr. Algèbre linéaire L1).
On récrit le sous-système des contraintes d ’é g alité sous la forme (on choisit l’ordre des
équation afin de faciliter le pivot de Gauss) :

x11 +x21 = 142,

x12 +x22 = 266,
x13 +x23 = 192,
x11 +x12 +x13 = 206,
x21 +x22 +x23 = 394.
On échelonne ensuite (méthode du tableau) :
1 0 0 1 0 0 | 142 1 0 0 1 0 0 | 142
0 1 0 0 1 0 | 266 0 1 0 0 1 0 | 266
0 0 1 0 0 1 | 192 → 0 0 1 0 0 1 | 192 →
1 1 1 0 0 0 | 206 0 1 1 −1 0 0 | 64
(0 0 0 1 1 1 | 394) (0 0 0 1 1 1 | 394)

1 0 0 1 0 0 | 142 1 0 0 1 0 0 | 142
0 1 0 0 1 0 | 266 0 1 0 0 1 0 | 266
0 0 1 0 0 1 | 192 → 0 0 1 0 0 1 | 192 →
0 0 1 −1 −1 0 | − 202 0 0 0 −1 −1 −1 | − 394
(0 0 0 1 1 1 | 394 ) (0 0 0 1 1 1 | 394 )

1 0 0 1 0 0 | 142 1 0 0 0 −1 −1 | − 252
0 1 0 0 1 0 | 266 0 1 0 0 1 0 | 266
( )→ ( )
0 0 1 0 0 1 | 192 0 0 1 0 0 1 | 192
0 0 0 1 1 1 | 394 0 0 0 1 1 1 | 394

La forme échelonnée laisse apparaˆıtre les variables x22 et x23 comme libres, desquelles on déduit
x21 = 394 − x22 − x23,
x13 = 192 − x23, (2.1)
x12 = 266 − x22,
x11 = −252 + x22 + x23.
On exprime ensuite le c o ût t uniquement en termes des variables libres x22 et x23 :
t = 9(−252 + x22 + x23) + 16(266 − x22) + 28(192 − x23)
+ 14(394 − x22 − x23) + 29x22 + 19x23 (2.2)
= 8x22 − 14x23 + 12880.

7
Afin de minimiser t il est donc opportun de choisir x23 le plus grand possible, et x22 le plus
petit possible. C’est à ce niveau qu’il nous est nécessaire de faire réapparaı̂tre les contraintes xij
≥ 0 (i = 1, 2, j = 1, 2, 3), sans lesquelles t pourrait être rendu aussi négatif que souhaité. En
examinant les équation (2.1), on se convainc assez rapidement que le meilleur choix est obtenu en
prenant x23 = 192 (afin de satisfaire mais saturer la contrainte x13 ≥ 0), et ensuite x22 = 60 (afin de
satisfaire mais saturer la contrainte x11 ≥ 0). On

propose alors la solution suivante

x11 = 0,
x12 = 206, (2.3)
x13 = 0,
x21 = 142,
x22 = 60,
x23 = 192,
comme candidat à êt re le transport optimal. Pour vérifier notre intuition, on choisit d’ex- primer
cette fois le système (2.1) uniquement en termes des variables x11 et x13 (on com- prendra ce choix
dans un instant), ce qui donne (on n’a en ré a l i té besoin que d’exprimer x22 et x33 puisqu’elles
seules interviennent dans l’expression de t dans (2.2)) :

x22 = 60 + x11 + x13,

x23 = 192 − x13. (2.4)

On obtient ainsi l’expression

t = 8x22 − 14x23 + 12880

= 8(60 + x11 + x13) − 14(192 − x13) + 12880 (2.5)
= 8x11 + 22x13 + 10672.

Comme x11 ≥ 0 et x13 ≥ 0 par contrainte, on a nécessairement t ≥ 10672 quel que soit le choix de
xij (i = 1, 2, j = 1, 2, 3) satisfaisant l’ensemble des contraintes. Par ailleurs, le choix proposé en
(2.3) fournit t = 10672 et satisfait à l’ensemble des contraintes. Il s’agit donc effectivement de la
solution optimale.

Pour terminer cet exemple par une synthèse, observons que nous sommes parvenus à récrire le
problème d’optimisation initial sous la forme d’un système linéaire augmenté de contraintes de
positivité de toutes les variables. Nous avons ensuite détermi né le rang du système linéaire en
question et exprimé de diverses manières possibles (deux en l’occur- rence) la fonction à optimiser
(ici t) en termes de variables libres pour ce système linéaire. Nous nous sommes a rrê té s lorsque les
coefficients des variables libres dans l’expression de la fonction à optimiser furent tous positifs ou
nuls, et avons conclu que les égaler à zé r o fournissait une solution assurément optimale.

Dans le chapitre qui suit, nous reprenons cette démarche de manière un peu plus systématique sur
un exemple initialement en dimension 3.

8
Chapitre 3

Mé t h o d e du simplexe : un a p e r ç u par l’exemple

Considérons le problème d’optimisation linéaire :

maximiser z = 5x1 +4x2 +3x3

sous les contraintes 2x1 +3x2 +x3 ≤ 5,
(3.1)
4x1 +x2 +2x3 ≤ 11,
3x1 +4x2 +2x3 ≤ 8,
x1, x2, x3 ≥ 0.
Afin de se ramener à un système d’équations plutôt que d’inéquations, on introduit les
variables d’écart x4, x5, x6 et l’on écrit le problème ci-dessus sous la forme

x4 = 5 −2x1 −3x2 −x3,

(3.2)
x5 = 11 −4x1 −x2 −2x3,
x6 = 8 −3x1 −4x2 −2x3,
avec pour but de maximiser z sous z les
= contraintes
5x1additionnelles
+4x2 +3xx3,i ≥ 0, (i = 1, · · · , 6). Il est a i sé
(et recommandé) de vérifier que si (x1, x2, x3, x4, x5, x6) est une solution optimale de ce dernier
problème, alors les (x1, x2, x3) correspondants constituent une solution optimale du problème
(3.1). Inversement, si (x1, x2, x3) est une solution optimale de (3.1), alors (x1, x2, x3, 5 − 2x1 − 3x2
−x 3 , 11 − 4x1 −x 2 − 2x3, 8 − 3x1 − 4x2 − 2x3) constitue une solution optimale de (3.2).
Le système (3.2) possède la solution (non optimale) (0, 0, 0, 5, 11, 8) (l’usage est d’ap- peler
solution réalisable tout choix de variables satisfaisant à l’ensemble des contraintes (cfr. le
chapitre suivant)).
On observe que dans l’expression z = 5x1 + 4x2 + 3x3, une augmentation de x1 entraˆıne une
augmentation de z. L’idée première est alors d’augmenter x1 autant que possible (sans modifier ni x2
ni x3) tant qu’aucune des variables d’écart x4, x5 ou x6 ne devient négative. Le choix maximal est
donc x1 = min(5/2, 11/4, 8/3) = 5/2, lorsque x4 devient nulle, et qui fait passer à la solution
réalisable (5/2, 0, 0, 0, 1, 1/2).
On récrit le système (3.2) en exprimant cette fois (x1, x5, x6) (ainsi que z) en termes

9
de (x2, x3, x4), au moyen de l’équation

5 3 1 1
𝑥1 = − 𝑥2 − 𝑥3 − 𝑥4
2 2 2 2

Ceci donne, après substitutions :

5 3 1 1
𝑥1 = − 𝑥2 − 𝑥3 − 𝑥4
2 2 2 2

𝑥5 = 1 + 5𝑥2 + 2𝑥4
(3.3)
1 1 1 3
𝑥6 = + 𝑥2 − 𝑥3 + 𝑥4
2 2 2 2

25 7 1 5
𝑧= − 𝑥2 + 𝑥3 − 𝑥4
2 2 2 2

Cette fois, on observe que dans l’expression z = 25/2 − 7/2x2 + 1/2x3 − 5/2x4, une
augmentation de x3 (c’est ici le seul choix possible) entraˆıne une augmentation de z. A
nouveau, on augmente donc x3 autant que possible (sans modifier ni x2 ni x4) tant qu’aucune des
variables (dites variables en bases (cfr. Chapitre 5)) x1, x5 ou x6 ne devient négative. Le choix
maximal est donc x3 = min((5/2)/(1/2), (1/2)/(1/2)) = 1, lorsque x6 devient nulle, et qui fait
passer à la solution réalisable (2, 0, 1, 0, 1, 0).
On récrit le système (3.3) en exprimant cette fois (x1, x3, x5) (ainsi que z) en termes de (x2, x4,
x6), au moyen de l’équation

x3 = 1 + x2 + 3x4 − 2x6.

Ceci donne, après substitutions :

x1 = 2 −2x2 −2x4 +x6,

x3 = 1 +x2 +3x4 −2x6, (3.4)
x5 = 1 +5x2 +2x4 ,
z = 13 −3x2 −x4 −x6.
Puisque les coefficients de x2, x4 et x6 intervenant dans l’expression de z ci-dessus sont tous
négatifs ou nuls, on déduit que la solution réalisable
x1 = 2,
x2 = 0,
x3 = 1,
x4 = 0, (3.5)
x5 = 1,
x6 = 0,

est une solution optimale, pour laquelle z = 13.

Avant de formaliser l’algorithme du simplexe, et d’en découvrir les bases théoriques, voyons
une deuxième méthode pour l’aborder et qui consiste à placer les calculs en tableau (toutes les
10
variables se retrouvant du même c ô t é du signe d’égalité) plutôt que sous forme dictionnaire comme
ci-dessus. L’avantage de cette deuxième façon de présenter les choses (mais qui est bien s ûr
équivalente à la première) et qu’elle se rapproche plus de la méthode bien connue du pivot de Gauss

11
Considérons donc maintenant le problème d’optimisation linéaire

maximiser z= x1 +5x2 +x3

sous les contraintes x1 +3x2 +x3 ≤ 3,
−x1 +3x3 ≤ 2, (3.6)
2x1 +4x2 −x3 ≤ 4,
x1 +3x2 −x3 ≤ 2,
x1, x2, x3 ≥ 0.
On introduit les variables d’écart x4, x5, x6, x7 (il y a une contrainte supplémentaire par rapport au
problème précédent) et on récrit le problème sous la forme

maximiser z= x1 +5x2 +x3

sous les contraintes x1 +3x2 +x3 +x4 = 3,
−x1 +3x3 +x5 = 2,
(3.7)
2x1 +4x2 −x3 +x6 = 4,
x1 +3x2 −x3 +x7 = 2,
x1, x2, x3 x4, x5, x6, x7 ≥ 0.
On adopte alors la notation sous forme de tableau :

1 3 1 1 0 0 0 | 3
−1 0 3 0 1 0 0 | 2
2 4 −1 0 0 1 0 | 4
1 3 −1 0 0 0 1 | 2
1 5 1 0 0 0 0 | 0

La dernière ligne du tableau correspond à un expression possible de z comme fonction affine

des variables x1, · · · , x7, l’opposé du terme constant se trouvant en bas à droite du tableau. On part de
la solution réalisable (0, 0, 0, 3, 2, 4, 2) et puisque le terme en x1 dans la dernière ligne du tableau
(=1) est positif, on va augmenter x1 (sans modifier ni x2 ni x3) jusqu’à ce que l’une des variables
x4, x5, x6 ou x7 devienne nulle. Ceci se produit pour x1 = 2 pour lequel à la fois x6 et x7 deviennent
nuls. On choisit donc de faire rentrer x1 en base, et de faire sortir (par exemple) x6. Cela donne

1 3 1 1 0 0 0 | 3 1 3 1 1 0 0 0 | 3
−1 0 3 0 1 0 0 | 2 −1 0 3 0 1 0 0 | 2
2 4 −1 0 0 1 0 | 4 1 2 −1/2 0 0 1/2 0 | 4
1 3 −1 0 0 0 1 | 2 1 3 −1 0 0 0 1 | 2
1 5 1 0 0 0 0 | 0 1 5 1 0 0 0 0 | 0

0 1 3/2 1 0 -1/2 0 | 1
0 2 5/2 0 1 ½ 0 | 4

1 2 −1/2 0 0 ½ 0 | 2
0 1 −1/2 0 0 -1/2 1 | 0
0 3 3/2 0 0 -1/2 0 | -2

et fournit une solution réalisable pour laquelle x1 = 2, x4 = 1, x5 = 4, x7 = 0 (et les variables

hors base sont toujours nulles : x2 = x3 = x6 = 0). Puisque le coefficient de x2
dans la nouvelle expression de z est positif, on fait ensuite rentrer x2 en base, et on doit faire sortir
12
 x7 sans pouvoir en rien augmenter x2 ! Cela donne

0 1 3/2 1 0 -1/2 0 | 1 0 0 2 1 0 0 -1 | 1
0 2 5/2 0 1 ½ 0 | 4 0 0 7/2 0 1 3/2 -2 | 4
→ 1 0 1/2 0 0 3/2 -2 | 2
1 2 −1/2 0 0 ½ 0 | 2
0 1 −1/2 0 0 -1/2 1 | 0 0 1 −1/2 0 0 -1/2 1 | 0
0 3 3/2 0 0 -1/2 0 | -2 0 0 3 0 0 1 -3 | -2

et fournit la solution réalisable( 2, 0, 0, 1, 4, 0, 0). On fait ensuite rentrer x3 en base (son coefficient
dans l’expression de z vaut maintenant 3) et on fait sortir x4 (qui s’annule lorsque x3 = 1/2). Cela
donne

0 0 2 1 0 0 -1 | 1 0 0 2 1 0 0 -1/2 | 1/2
0 0 7/2 0 1 3/2 -2 | 4 0 0 7/2 0 1 3/2 -2 | 4
→ 1 0 1/2 0 0 3/2 -2 | 2
1 0 ½ 0 0 3/2 -2 | 2
0 1 -1/2 0 0 -1/2 1 | 0 0 1 −1/2 0 0 -1/2 1 | 0
0 0 3 0 0 1 -3 | -2 0 0 3 0 0 1 -3 | -2

0 0 1 ½ 0 0 -1/2 | 1/2
→ 0 0 0 -7/4 1 3/2 -1/4 | 9/4
1 0 0 -1/4 0 3/2 -7/4 | 7/4
0 1 0 ¼ 0 -1/2 ¾ | ¼
0 0 0 -3/2 0 1 -3/2 | -7/2

et fournit la solution réalisable(7/4,1/4,1/2,0,0,0,0). On fait ensuite rentrer x6 et sortir x1

(qui s’annule en premier lorsque lorsque x6 = 7). Cela
6 donne

0 0 1 ½ 0 0 -1/2 | 1/2 0 0 1 ½ 0 0 -1/2 | 1/2

0 0 0 -7/4 1 3/2 -1/4 | 9/4 0 0 0 -7/4 1 0 3/2 | 9/4
1 0 0 -1/4 0 3/2 -7/4 | 7/4 → 2/3 0 0 0 0 1 -7/6 | 7/6
0 1 0 ¼ 0 -1/2 ¾ | ¼ 0 1 0 ¼ 0 0 1/6 | ¼
0 0 0 -3/2 0 1 -3/2 | -7/2 0 0 0 -3/2 0 0 -1/3 | -7/2

0 0 1 ½ 0 0 -1/2 | 1/2
-1 0 0 -3/2 1 0 3/2 | ½
→ 2/3 0 0 -1/6 0 1 -7/6 | 7/6
1/3 1 0 1/6 0 0 1/6 | 5/6
-2/3 0 0 -4/3 0 0 -1/3 | -14/3

13
et fournit finalement la solution optimale (0,5/6,1/2,0,1/2,7/6,0) pour laquelle z=14/3.

14
Chapitre 4

Formes générale, canonique et

standard d’un problème
d’optimisation linéaire

Dans ce chapitre, nous définissons la forme générale d’un problème d’optimisation

linéaire, ainsi que la forme canonique et la forme standard. Nous montrons également
qu’un problème sous forme générale peut être transformé d’abord en un problème équivalent
sous forme canonique, puis enfin sous un problème équivalent sous forme standard. Dans
les chapitres qui suivront, nous nous restreindrons donc à fournir un algorithme de
résolution pour les problèmes sous forme standard.
Définition 4.1. On appelle problème d’optimisation linéaire sous forme générale un
problème de la forme
maximiser F (X)
(4.1)
sous les contraintes X ∈ RQ , G1 (X) ≤ 0, · · · , GP (X) ≤ 0,

où P, Q ∈ N∗ , F : RQ → R est une forme linéaire sur RQ et G1 , · · · , GP sont des

applications affines définies sur RQ et à valeurs réelles. On dit que la fonction F est la
fonction objectif et que les fonctions G1 , · · · , GP sont les contraintes.
Remarque 4.2. On pourrait bien sûr traiter de manière équivalente les problèmes de
minimisation. Il n’y a toutefois aucune perte de généralité à ne traiter que les problèmes de
maximisation. De fait, minimiser une fonctionnelle F revient à maximiser la fonctionnelle
−F. Dans le même esprit, on pourrait considérer des contraintes de la forme Gi (X) ≥ 0
ou même Gi (X) = 0. Dans le premier cas il suffit alors de récrire la contrainte sous la
forme −Gi (X) ≤ 0, et dans le second de la dédoubler en deux contraintes : Gj (X) ≤ 0 et
−Gi (X) ≤ 0.
Définition 4.3. On dit que X ∈ RQ est une solution réalisable du problème (4.1) si
X satisfait aux contraintes, autrement dit si G1 (X) ≤ 0, · · · , GP (X) ≤ 0. L’ensemble P
de toutes les solutions réalisables d’un problème d’optimisation est appelé son ensemble
réalisable.
Définition 4.4. On dit que X ∈ RQ est une solution optimale du problème (4.1) si
X est une solution réalisable du problème (4.1) et si de plus, quelle que soit la solution

13
réalisable Y ∈ RQ du problème (4.1) on a nécessairement F (Y ) ≤ F (X). Autrement dit,
une solution réalisable est optimale si elle maximise la fonction objectif sur l’ensemble
réalisable.

Remarque 4.5. Anticipant un peu sur le Chapitre 12, on affirme que l’ensemble P est
un polyèdre dans R2 , c’est-à-dire une intersection finie de demi-espaces fermés de R2 . Si
P est de plus borné (cela n’est pas nécessairement le cas), et puisque la fonction objectif
est une fonction continue, l’existence d’au moins une solution optimale est alors garantie
par le théorème des bornes atteintes. Dans tous les cas, nous verrons que si la fonction
est majorée sur P, alors le problème de maximisation a toujours au moins une solution.

Un même problème d’optimisation linéaire peut se récrire de diverses manières équivalentes

les unes aux autres. Parmi ces versions, nous distinguerons les formes canoniques et les
formes standards.

Définition 4.6. On appelle problème d’optimisation linéaire sous forme canonique un

problème de la forme
Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj ≤ bi (i = 1, · · · , p), (4.2)
xj ≥ 0 (j = 1, · · · , q),

où p, q ∈ N∗ , et où les cj (1 ≤ j ≤ q), les aij (1 ≤ i ≤ p, 1 ≤ j ≤ q), et les bi (1 ≤ i ≤ p)

sont des constantes réelles.

En écriture matricielle, un problème sous forme canonique s’écrit donc

maximiser cT x
sous les contraintes Ax ≤ b,
x ≥ 0,

où c = (c1 , · · · , cq )T et (la variable) x = (x1 , · · · , xq )T sont des vecteurs colonnes à q

lignes, A = (aij )1≤i≤p,1≤j≤q est une matrice à p lignes et q colonnes, et b = (b1 , · · · , bp )T
est un vecteur colonne à p lignes.
Il est immédiat que tout problème d’optimisation linéaire sous forme canonique est
un problème d’optimisation linéaire sous forme générale. En effet, la fonction à maximi-
ser dans (4.2) est bien une forme linéaire, les contraintes xj ≥ 0 s’écrivent de manière
équivalente sous la forme Gj P(x) ≤ 0 avec Gj (x) = −xj qui est bien une fonction af-
q
Pq les contraintes j=1 aij xj ≤ bi se récrivent sous la forme Hj (x) ≤ 0 où
fine, et enfin
Hj (x) = j=1 aij xj − bi est également affine.
Nous allons montrer maintenant que la résolution de n’importe quel problème d’op-
timisation linéaire sous forme générale peut se ramener à la résolution d’un problème
d’optimisation linéaire sous forme canonique. Pour ce faire, on récrit tout d’abord (4.1)
sous la forme étendue (c’est-à-dire que l’on rend explicite F et G1 , · · · , GP ) :
PQ
maximiser f l Xl
Pl=1
Q (4.3)
sous les contraintes l=1 Gkl Xl − Bk ≤ 0 (k = 1, · · · , P ).

14
On introduit alors les variables fictives X1+ , · · · , XQ+ et X1− , · · · , XQ− et on considère le
problème
PQ + −
maximiser
PQ l=1 fl (Xl − Xl )
+ − (4.4)
sous les contraintes l=1 Gkl (Xl − Xl ) ≤ Bk (k = 1, · · · , P ),
+ −
Xl ≥ 0, Xl ≥ 0 (l = 1 · · · , Q).
Le problème (4.4) est un problème d’optimisation linéaire sous forme canonique. En effet,
il suffit de choisir p = P et q = 2Q et de poser (x1 , · · · , xq ) := (X1+ , · · · , XQ+ , X1− , · · · , XQ− ).
Le lecteur vérifiera que si (X1+ , · · · , XN+ , X1− , · · · , XN− ) est une solution réalisable (resp.
optimale) de (4.4), alors (X1+ − X1− , · · · , XQ+ − XQ− ) est une solution réalisable (resp. opti-
male) de (4.3). Inversement, si (X1 , · · · , XQ ) est une solution réalisable (resp. optimale) de
(4.3), alors (X1+ , · · · , XQ+ , X1− , · · · , XQ− ), où pour 1 ≤ l ≤ Q on a défini Xl+ := max(Xl , 0)
et Xl− := − min(Xl , 0), est une solution réalisable (resp. optimale) de (4.4).
Définition 4.7. On appelle problème d’optimisation linéaire sous forme standard un
problème de la forme
Pn
maximiser cj x j
Pj=1
n
sous les contraintes j=1 aij xj = bi (i = 1, · · · , m),
xj ≥ 0 (j = 1, · · · , n),
où m, n ∈ N∗ , et où les cj (1 ≤ j ≤ n), les aij (1 ≤ i ≤ m, 1 ≤ j ≤ n), et les bi
(1 ≤ i ≤ m), sont des constantes réelles.

En écriture matricielle, un problème sous forme standard s’écrit donc

maximiser cT x
sous les contraintes Ax = b,
x ≥ 0,

où c = (c1 , · · · , cn )T et (la variable) x = (x1 , · · · , xn )T sont des vecteurs colonnes à n

lignes, A = (aij )1≤i≤m,1≤j≤n est une matrice à m lignes et n colonnes, et b = (b1 , · · · , bm )T
est un vecteur colonne à m lignes.
Remarque 4.8. Sans perte de généralité, on peut supposer que dans un problème sous
forme standard, les lignes de A sont linéairement indépendantes (si ce n’est pas le cas soit
certaines contraintes sont redondantes, soit l’ensemble des contraintes est vide). Dans la
suite, lorsque nous parlerons de problème sous forme standard, nous supposerons implici-
tement que les lignes de A sont linéairement indépendantes, autrement dit que
rang(A) = m,
ce qui implique également que n ≥ m.

A tout problème d’optimisation linéaire sous forme canonique, ont peut associer un
problème d’optimisation linéaire sous forme standard de la manière suivante. Soit le
système sous forme canonique
Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj ≤ bi (i = 1, · · · , p), (4.5)
xj ≥ 0 (j = 1, · · · , q).

15
On pose m = p et n = p + q, et on considère le système
Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj + xq+i = bi (i = 1, · · · , m), (4.6)
xj ≥ 0 (j = 1, · · · , n).

Il est aisé (et c’est un bon exercice) de vérifier que si le vecteur (x1 , · · · , xq )T est une
solution réalisable (resp. optimale) du problème (4.5), alors le vecteur
q q
X X
T
(x1 , · · · , xn ) := (x1 , · · · , xq , b1 − a1j xj , · · · , bp − apj xj )T
j=1 j=1

est solution réalisable (resp. optimale) du problème (4.6). Inversement, si le vecteur

(x1 , · · · , xq , xq+1 , · · · , xq+p )T est solution réalisable (resp. optimale) du problème (4.6),
alors (x1 , · · · , xq )T est solution réalisable (resp. optimale) du problème (4.5). Le problème
(4.6) peut se récrire sous forme matricielle comme

maximiser c̄T x̄
sous les contraintes Āx̄ = b̄, (4.7)
x̄ ≥ 0,

où x̄ := (x1 , · · · , xp+q )T ,

c̄T := (c1 , · · · , cq , 0, · · · , 0),

 
a11 · · · a1q 1 0 0 ··· 0
a21 · · · a2q 0 1 0 ··· 0
Ā :=  .. ..  ,
 
 . .
ap1 · · · apq 0 0 ··· 0 1

b̄ := b.

De par sa structure particulière (elle contient la matrice identité de taille q dans sa partie
droite), la matrice Ā est nécessairement de rang égal à m = p, quelle que soit A.

Définition 4.9. Dans la suite, nous dirons qu’un problème d’optimisation linéaire est
sous forme standard canonique s’il est de la forme (4.7)

Remarque 4.10. Même si les méthodes présentées ci-dessus permettent de ramener de

manière systématique n’importe quel problème d’optimisation linéaire sous forme générale
en des problèmes d’optimisation linéaire sous forme canonique ou standard, dans la pra-
tique il peut arriver (c’était le cas dans le chapitre précédent) que ce ne soit pas la plus
économe en nombre de variables. Dans ces cas, il est bien entendu plus avantageux d’uti-
liser la réduction rendant le problème standard le plus compact possible (i.e. avec le moins
de contraintes ou le moins de variables possible).

16
Chapitre 5

Solutions de base d’un problème

sous forme standard

Dans ce chapitre, nous mettons en évidence certaines solutions réalisables (dites de

base) pour un problème d’optimisation linéaire sous forme standard. Ces solutions se
révéleront suffisantes pour la recherche d’une solution optimale.
Considérons le problème d’optimisation linéaire sous forme standard
maximiser cT x
sous les contraintes Ax = b, (5.1)
x ≥ 0,
où c = (c1 , · · · , cn )T et (la variable) x = (x1 , · · · , xn )T sont des vecteurs colonnes à n
lignes, A = (aij )1≤i≤m,1≤j≤n est une matrice à m lignes et n colonnes vérifiant rang(A) =
m, et b = (b1 , · · · , bm )T est un vecteur colonne à m lignes. Sans perte de généralité, on
peut supposer que n > m, car si n = m l’ensemble réalisable contient au plus un point.
On note
     
a11 a1k a1n
A1 :=  ...  , · · · , Ak =  ...  , · · · , An =  ...  ,
     
am1 amk amn
les colonnes de la matrice A. Par hypothèse sur le rang de A, on peut trouver m colonnes
parmi A1 , · · · , An qui soient linéairement indépendantes. En général, ce choix n’est pas
unique. On note
n o
Γ := γ : {1, · · · , m} → {1, · · · , n} strictement croissante .

Pour γ ∈ Γ, on note Aγ la matrice carrée de taille m

 
a ··· a1γ(m)

 1γ(1)
Aγ = Aγ(1) , · · · , Aγ(m) =  ... ..  .
. 
amγ(1) · · · amγ(m)
Finalement, on définit n o
B := γ ∈ Γ t.q. rang(Aγ ) = m .

17
Remarque 5.1. On a bien sûr
n!
]B ≤ ]Γ = .
m!(n − m)!

Pour chaque γ ∈ Γ, on note γ̂ l’unique application strictement croissante de {1, · · · , n−

m} dans {1, · · · , n} telle que



γ {1, · · · , m} ∪ γ̂ {1, · · · , n − m} = {1, · · · , n}
(autrement dit, γ̂ fournit en ordre croissant les indices complémentaires à ceux atteints
par γ).
Définition 5.2. Etant fixé un choix de γ ∈ B, on dit que les variables xγ(1) , · · · , xγ(m)
sont les variables en base (pour γ), tandis que les variables xγ̂(1) , · · · , xγ̂(n−m) sont les
variables hors base (pour γ).

Pour x ∈ Rn et γ ∈ B, on note

T
T
xB := xγ(1) , · · · , xγ(m) , xN := xγ̂(1) , · · · , xγ̂(n−m) .
On note aussi

T
T
cB := cγ(1) , · · · , cγ(m) , cN := cγ̂(1) , · · · , cγ̂(n−m) ,
et enfin
B := Aγ , N := Aγ̂ .
On remarque alors que le système Ax = b se récrit sous la forme
BxB + N xN = b,
qui est équivalent, puisque B est inversible lorsque γ ∈ B, au système
xB = B −1 b − B −1 N xN . (5.2)
Définition 5.3. On appelle solution de base du système Ax = b associée au choix de base
γ ∈ B la solution x∗ définie par
x∗B = B −1 b, x∗N = (0, · · · , 0)T .
Définition 5.4. (Solution de base réalisable) On dit que la solution de base x∗ du système
Ax = b associée au choix de base γ ∈ B est une solution de base réalisable si de
plus elle vérifie les contraintes de (5.1), c’est-à-dire si toutes les composantes de x∗ sont
positives. Dans ce cas, on dit aussi que la base γ est une base réalisable, et on note
R l’ensemble des bases réalisables. On dit que la solution de base réalisable x∗ est non
dégénérée si toutes les composantes de x∗B sont strictement positives.
Corollaire 5.5. Etant fixée γ ∈ B, pour x ∈ Rn solution de Ax = b, on a
xB = x∗B − B −1 N xN , et cT x = cT x∗ + dT x,
où le vecteur d est défini par les relations
dTN = cTN − cTB B −1 N
et
dTB = (0, · · · , 0).

18
Démonstration. La première égalité découle de manière directe de la définition de x∗ .
Pour la seconde, on écrit
cT x = cTB xB + cTN xN
et l’on substitue xB par B −1 b − B −1 N xN . Ceci donne

cT x = cTB B −1 b+ cTN − cTB B −1 N xN = cTB x∗B + cTN − cTB B −1 N xN = cT x∗ + cTN − cTB B −1 N xN ,

d’où la conclusion.
Définition 5.6. On dit que le vecteur d est le vecteur des prix marginaux associé à
la base γ.
Remarque 5.7. La terminologie pour vecteur des prix marginaux apparaı̂tra plus claire-
ment dans le Chapitre 10 lorsque nous aborderons les problèmes duaux ; il serait en fait
plus juste d’attribuer ce nom à −d plutôt qu’à d. Cette notion a été vaguement esquissée
dans le premier chapitre, lorsque nous avons évoqué le problème du concurrent.
Proposition 5.8. Soit γ une base réalisable et x∗ la solution de base associée à γ. Si le
vecteur des prix marginaux d n’a que des composantes négatives, alors x∗ est une solution
optimale du problème (5.1).

Démonstration. Si x est une solution réalisable quelconque de (5.1), on a par le Corollaire

5.5
cT x = cT x∗ + dTN xN ≤ cT x∗ .
De fait, le produit matriciel dTN xN est négatif puisque les composantes de d (et donc dN )
sont supposées négatives et celles de xN positives (car x est réalisable).

La remarque qui suit est à la base de la technique du tableau (cfr. Chapitre 3) pour
l’implémentation de la méthode du simplexe.
Remarque 5.9. On peut transformer le problème 5.1 en le problème équivalent suivant
maximiser −z
sous les contraintes Ax = b,
(5.3)
cT x + z = 0,
x ≥ 0,

où z est une variable scalaire réelle (non nécessairement positive). Ce dernier problème
peut se récrire sous la forme matricielle
maximiser c̄T x̄
sous les contraintes Āx̄ = b̄, (5.4)
x ≥ 0,

où x̄T := (x1 , · · · , xn , z), c̄T = (0, · · · , 0, −1), et où

   
A 0 b
Ā := T et b̄ := .
c 1 0

Si γ : {1, · · · , m} → {1, · · · , n} est un élément de B alors γ̄ : {1, · · · , m + 1} →

{1, · · · , n + 1} définie par γ̄(j) = γ(j) si j ∈ {1, · · · , m} et γ̄(m + 1) = n + 1 est

19
telle que les colonnes Āγ̄(1) , · · · , Āγ̄(m+1) sont linéairement indépendantes. Par analogie
avec les notations utilisées plus haut, on notera

B̄ = Āγ̄ = (Āγ̄(1) , · · · , Āγ̄(m+1) ),

qui est par conséquent une matrice carrée inversible de taille m + 1. On remarque que le
système Āx̄ = b̄ est équivalent au système

B̄ −1 Āx̄ = B̄ −1 b̄,

et on explicite ensuite l’expression de B̄ −1 Ā et B̄ −1 b̄. On a

B −1
   
B 0 −1 0
B̄ = T d’où B̄ = ,
cB 1 −cTB B −1 1

et donc
B −1 B −1 A
      −1 
−1 0 A 0 0 B A 0
B̄ Ā = = T = ,
−cTB B −1 1 cT 1 c − cTB B −1 A 1 dT 1

et
B −1 b
 
−1
B̄ b̄ = .
−cTB B −1 b
Finalement, pour chaque i ∈ {1, · · · , m},

(B −1 A)γ(i) = (0, · · · , 0, 1, 0, · · · , 0)T ,

où l’unique 1 est placé en ième position.

20
Chapitre 6

Pivot à partir d’une solution de base

réalisable : critère de Dantzig

Au chapitre précédent, nous avons associé à tout choix de base γ ∈ B une solution de
base x∗ , et nous avons fournit un critère (la Proposition 5.8) permettant de s’assurer que
x∗ soit une solution optimale.
Dans ce chapitre, nous présentons une méthode permettant, étant donné un choix
de base γ ∈ B pour laquelle la solution de base x∗ est réalisable mais le critère de la
Proposition 5.8 n’est pas vérifié, de déterminer un autre choix de base δ ∈ B dont la
solution de base associée y ∗ est réalisable et vérifie de plus
cT y ∗ ≥ cT x ∗ .
Cette méthode opère au moyen d’un pivot, au sens où les ensembles γ({1, · · · , m}) et
δ({1, · · · , m}) ne diffèrent que par un élément.
Reprenons donc le problème d’optimisation linéaire sous forme standard (5.1) du cha-
pitre précédent :
maximiser cT x
sous les contraintes Ax = b,
x ≥ 0,
où n > m ∈ N∗ , c = (c1 , · · · , cn )T et (la variable) x = (x1 , · · · , xn )T sont des vecteurs
colonnes à n lignes, A = (aij )1≤i≤m,1≤j≤n est une matrice à m lignes et n colonnes vérifiant
rang(A) = m, et b = (b1 , · · · , bm )T est un vecteur colonne à m lignes.
Soit γ ∈ B, x∗ la solution de base du système Ax = b associée à γ et supposons que
x∗ soit réalisable mais que l’une au moins des composantes du vecteur d soit strictement
positive.
On note n o
Eγ := j ∈ {1, · · · , n − m} t.q. dγ̂(j) > 0 .
(par construction on a nécessairement dγ(i) = 0 pour tout i ∈ {1, · · · , m})
Supposons J ∈ Eγ fixé (nous verrons différents critères pour ce faire ci-dessous). On
définit l’ensemble
n o
Sγ,J := i ∈ {1, · · · , m} t.q. (B −1 N )iJ > 0 .

21
Lemme 6.1. Si Sγ,J = ∅ alors le problème d’optimisation (5.1) n’a pas de solution opti-
male car la fonction objectif n’est pas bornée supérieurement sur l’ensemble réalisable.

Démonstration. Soit t > 0 fixé quelconque. On définit le vecteur x ∈ Rn par les relations

xγ̂(j) = 0 si j ∈ {1, · · · , n − m} \ {J},

xγ̂(J) = t,
xγ(i) = x∗γ(i) − t(B −1 N )iJ si i ∈ {1, · · · , m}.

Par construction,
xB = x∗B − B −1 N xN ,
de sorte que
Ax = b.
De plus, puisque t ≥ 0, puisque x∗ est réalisable, et puisque (B −1 N )iJ ≤ 0 pour tout
i ∈ {1, · · · , m} par hypothèse, on a
x ≥ 0,
et on déduit donc que x est une solution réalisable. Enfin, on a

cT x = cT x∗ + tdTγ̂(J) .

Comme t ≥ 0 était quelconque et que dγ̂(J) > 0, on déduit que la fonction objectif n’est
pas bornée supérieurement sur l’ensemble réalisable.

Supposons maintenant que la fonction objectif soit bornée supérieurement sur l’en-
semble réalisable et fixons I ∈ Sγ,J (là aussi nous verrons différents critères de choix par
la suite). Dans tous les cas, on a

Lemme 6.2. Soit δ l’unique application strictement croissante de {1, · · · , m} dans {1, · · · , n}
telle que




δ {1, · · · , m} = γ {1, · · · , m} \ γ {I} ∪ γ̂ {J} .
Alors δ ∈ B.

(Autrement dit les colonnes de A associées aux variables en base obtenues en faisant
sortir de la base initiale la variable xγ(I) et en y faisant rentrer la variable xγ̂(J) sont
linéairement indépendantes).

Démonstration. Par définition des matrices B et N (pour la base γ), on a

m
X
Aγ̂(J) = (B −1 N )iJ Aγ(i) .
i=1

Puisque (B −1 N )IJ > 0 (et donc 6= 0) par hypothèse sur I, et puisque la famille (Aγ(i) )1≤i≤m
est une base de Rm , on déduit que Aγ̂(J) n’est pas combinaison linéaire des seuls Aγ(i) avec
i ∈ {1, · · · , m} \ {I}. Il s’ensuit que δ définit une famille de m vecteurs libres de Rm , et
donc que δ ∈ B par définition de B.

22
Lemme 6.3. (Critère de Dantzig) Sous les hypothèse du lemme précédent, si de plus
x∗γ(I) x∗γ(i)
= tJ := min
(B −1 N )IJ i∈Sγ,J (B −1 N )iJ
alors δ est une base réalisable. De plus, si y ∗ désigne la solution de base réalisable associée
à la base δ, alors
cT y ∗ ≥ cT x ∗ ,
l’inégalité étant stricte si tJ 6= 0.

Démonstration. On procède de manière assez semblable à la démonstration du Lemme

6.1. Soit y ∈ Rn défini par

yγ̂(j) = 0 si j ∈ {1, · · · , n − m} \ {J},

xγ̂(J) = tJ ,
yγ(i) = x∗γ(i) − tJ (B −1 N )iJ si i ∈ {1, · · · , m}.

Par construction,
yB = x∗B − B −1 N yN ,
de sorte que
Ay = b.
Aussi, par définition de tJ on a
y≥0
et on déduit donc que y est une solution réalisable. De plus

yγ(I) = x∗γ(I) − tJ (B −1 N )IJ = 0,

et par construction
yγ̂(j) = 0 si j ∈ {1, · · · , n − m} \ {J}.
Il s’ensuit que, relativement à la base δ,

yN = 0.

Par conséquent, y = y ∗ est l’unique solution de base (on sait qu’elle est aussi réalisable)
associée à la base δ, et on a

cT y ∗ = cT y = cT x∗ + dγ̂(J) tJ ≥ cT x∗ ,

l’inégalité étant stricte si tJ > 0.

Dans la méthode présentée ci-dessus, et permettant de passer de la base réalisable γ à

la base réalisable δ, il se peut que les indices J puis I des variables entrantes puis sortantes
ne soient pas déterminés de manière unique (si Eγ n’est pas réduit à un élément, et si
le maximum tJ est atteint pour plusieurs indices I). Dans ces cas, et avec l’optique par
exemple de rendre la méthode algorithmique (et donc déterministe) en vue de la program-
mer sur un ordinateur, il faut y adjoindre un ou des critères additionnels permettant de
déterminer I et J de manière univoque. Nous allons décrire deux tels critères (on peut
imaginer beaucoup d’autres variantes) :

23
Définition 6.4 (Critère naturel). On appelle variable entrante selon le critère naturel la
variable xγ̂(J) telle que

dγ̂(J) = max dγ̂(j) et J= min j.

j∈Eγ j∈Eγ ,dγ̂(j) =dγ̂(J)

(autrement dit la variable sortante est dans ce cas une de celles associées aux plus grands
coefficients positifs de d, et parmi celles-ci celle de plus petit indice)
On appelle variable sortante selon le critère naturel la variable xγ(I) telle que

x∗γ(i)
 
I = min i ∈ Sγ,J t.q. = tJ .
(B −1 N )iJ

(autrement dit la variable entrante est dans ce cas celle de plus petit indice parmi les
variables satisfaisant au critère de Dantzig étant donnée la variable entrante J)

Définition 6.5 (Critère de Bland). On appelle variable entrante selon le critère de Bland
la variable xγ̂(J) telle que
J = min j.
j∈Eγ

(autrement dit la variable sortante est dans ce cas celle associée au premier coefficient
strictement positif de d)
On appelle variable sortante selon le critère de Bland la variable xγ(I) telle que

x∗γ(i)
 
I = min i ∈ Sγ,J t.q. = tJ .
(B −1 N )iJ

(autrement dit la variable entrante est dans ce cas celle de plus petit indice parmi les
variables satisfaisant au critère de Dantzig étant donnée la variable entrante J)

24
Chapitre 7

Non cyclicité sous le critère de Bland

Le chapitre précédent nous fournit une (en réalité deux suivant que l’on applique le
critère naturel ou celui de Bland) méthode pour passer d’une base réalisable γ à une
base réalisable δ tout en augmentant (au sens non strict) la fonction objectif. Puisqu’il
n’y a qu’un nombre fini de bases réalisables (au plus Cnm ), les itérées de cette méthode
nous conduiront assurément à une solution optimale à condition que la fonction objectif
soit majorée et que nous puissions démontrer que l’algorithme ne cycle pas, c’est-à-dire
qu’aucune des bases réalisables obtenues par les différentes itérations ne peut être égale
à la base initiale γ. Cette condition n’est pas vérifiée en général pour le critère naturel (il
existe un célèbre contre-exemple du à Beale (1955)). A l’inverse, Bland (1974) à démontré
que la cyclicité est proscrite suivant son critère :
Théorème 7.1. (Bland) L’itération de la méthode du Chapitre 6 avec le critère de Bland
garantit la non-cyclicité des bases réalisables produites, et par conséquent atteint une
solution optimale en un nombre fini d’étapes si la fonction objectif est majorée.

Démonstration. La démonstration se fait par l’absurde et n’est pas des plus éclairantes.
On la fournit néanmoins par souci de complétude. Supposons donc que l’itération de la
méthode engendre un cycle. Cela implique bien sûr que la fonction objectif soit constante
tout au long du cycle, et donc qu’à chaque étape on ait tJ = 0, de sorte que la solution
de base x∗ est elle aussi constante tout au long du cycle. Appelons K le plus grand indice
(parmi {1, · · · , m}) pour lequel la variable xK se retrouve à la fois en base et hors base
dans deux itérations différentes du cycle. Appelons aussi γ la base réalisable correspondant
à une étape du cycle (que nous fixons) où xK est appelée à rentrer en base, et δ la base
réalisable correspondant à une étape du cycle (que nous fixons) où xK est appelée à sortir
de la base.
Faisant référence à la remarque 5.9 du Chapitre 5, on augmente le système Ax = b en
le système Āx̄ = b̄, que l’on récrit sous les deux formes équivalentes

B̄γ−1 Āx̄ = B̄γ−1 b̄ et B̄δ−1 Āx̄ = B̄δ−1 b̄,

où Bγ et Bδ se réfèrent à la matrice B du Chapitre 5 suivant que l’on choisit γ ou δ comme

base réalisable. De plus,
 −1   −1 
−1 Bγ A 0 −1 Bδ A 0
B̄γ Ā = et B̄δ Ā = .
dTγ 1 dTδ 1

25
On note H le sous-espace vectoriel de Rn+1 engendré par les lignes de Ā. Une première
remarque importante est que puisque Bγ et Bδ sont inversibles, H est aussi le sous-espace
vectoriel engendré par les lignes de B̄γ−1 Ā ou par celles B̄δ−1 Ā. En particulier, on a


h := dTγ 1 ∈ H. (7.1)

De plus, par définition de K et de γ, et en vertu du critère de Bland,

(dγ )k ≤ 0, ∀k < K,
(7.2)
(dγ )K > 0.

Venons en maintenant à l’étape correspondant à la base δ. Puisque xK est destinée à

sortir de la base à cette étape, en particulier xK est en base à ce moment, et on peut donc
écrire K = δ(I) pour un certain I ∈ {1, · · · , m}. Soit xE la variable destinée à rentrer en
base à l’étape correspondant à la base δ. Par définition de K on a donc E ≤ K et d’autre
part
(dδ )E > 0, et (Bδ−1 A)IE > 0. (7.3)

On définit le vecteur f ∈ Rn+1 par

fδ(i) := (B̄δ−1 Ā)iE ∀i ∈ {1, · · · , m},

fE := −1,
fn+1 := (dδ )E ,
les autres composantes de f étant nulles.

On prétend que quel que soit i ∈ {1, · · · , m + 1}, on a

n+1
X
(B̄δ−1 Ā)il fl = 0,
l=1

autrement dit le vecteur f est orthogonal à l’espace vectoriel engendré par les lignes de
B̄δ−1 Ā, c’est-à-dire H. En effet, pour 1 ≤ i ≤ m on a, par définition de f ,
n+1
X m
X
−1
(B̄δ Ā)il fl = (Bδ−1 A)iδ(j) fδ(j) + (Bδ−1 A)iE fE = (Bδ−1 A)iδ(i) fδ(i) − (Bδ−1 A)iE = 0,
l=1 j=1

où on a utilisé le fait que (Bδ−1 A)iδ(j) = δij (symbole de Kronecker). D’autre par, pour
i = m + 1 on a
n+1
X m
X
(B̄δ−1 Ā)il fl = (dδ )δ(j) fδ(j) + (dδ )E fE + fn+1 = 0 − (dδ )E + (dδ )E = 0,
l=1 j=1

où on a ici utilisé le fait que (dδ )δ(j) ≡ 0.

Comme h ∈ H et f ∈ H⊥ , on déduit que
n+1
X
hl fl = 0.
l=1

26
Pour l = n + 1, on a hn+1 fn+1 = (dδ )E > 0 par (7.3), et par conséquent il existe au moins
un indice L ∈ {1, · · · , n} pour lequel hL fL < 0. En particulier, hL 6= 0 et donc xL est une
variable hors base γ. Aussi, fL 6= 0, et par conséquent ou bien xL est une variable en base
δ ou bien L = E. Dans l’un ou l’autre cas, on conclut que xL est une variable qui rentre
et sort de la base à différentes étapes du cycle, et par définition de K cela implique que
L ≤ K. Enfin, hK = (dγ )K > 0 par (7.2) et fK = (Bδ−1 A)IE > 0 par (7.3). Il s’ensuit que
L < K. Dès lors hL = (dγ )L ≤ 0 par (7.2), d’où on déduit que hL < 0, et finalement que
fL > 0. Comme fE = −1 on ne peut donc avoir L = E, et d’un argument précédent on
conclut que xL est une variable en base pour δ (rappelons que xL est à l’inverse hors base
γ, et donc que x∗L = 0). Dès lors, si L = δ(J), on a alors à l’étape correspondant à la base
δ,

(Bδ−1 A)JE > 0 car fL > 0,

x∗δ(J) = 0 car x∗δ(J) = x∗L ,
L < K.

Le critère de Bland nous interdit alors de faire sortir la variable xK , ce qui constitue la
contradiction cherchée.

27
Chapitre 8

Détermination d’une première

solution de base réalisable

Le Chapitre 6 nous a fourni un moyen de passer d’une base réalisable à une autre
base réalisable plus avantageuse du point de vue de la fonction objectif. Il nous reste
néanmoins à déterminer, en vue d’initialiser la méthode, comment obtenir une première
base réalisable. Ceci constitue l’objet du chapitre présent.
Considérons un problème d’optimisation linéaire sous forme canonique :
maximiser cT x
sous les contraintes Ax ≤ b, (8.1)
x ≥ 0,
où c = (c1 , · · · , cq )T et (la variable) x = (x1 , · · · , xq )T sont des vecteurs colonnes à q
lignes, A = (aij )1≤i≤p,1≤j≤q est une matrice à p lignes et q colonnes, et b = (b1 , · · · , bp )T
est un vecteur colonne à p lignes.
Définition 8.1. On dit que le problème sous forme canonique (8.1) est un problème de
première espèce si toutes les composantes du vecteur b sont positives. Dans le cas inverse,
ou si le problème n’est pas sous forme canonique, on dit qu’il s’agit d’un problème de
deuxième espèce.
Comme indiqué au Chapitre 4, au problème (8.1) ont peut associer un problème
équivalent sous forme standard : on explicite (8.1) comme
Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj ≤ bi (i = 1, · · · , p), (8.2)
xj ≥ 0 (j = 1, · · · , q),
on pose m = p et n = p + q, et on considère le système
Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj + xq+i = bi (i = 1, · · · , m), (8.3)
xj ≥ 0 (j = 1, · · · , n).
Ce dernier problème se récrit sous forme matricielle comme
maximiser c̄T x̄
sous les contraintes Āx̄ = b̄, (8.4)
x̄ ≥ 0,

28
où x̄ = (x1 , · · · , xp+q )T ,

c̄T = (c1 , · · · , cq , 0, · · · , 0),

 
a11 · · · a1q 1 0 0 ··· 0
a21 · · · a2q 0 1 0 ··· 0
Ā =  .. ..  ,
 
 . .
ap1 · · · apq 0 0 ··· 0 1

b̄ = b.

De par la forme de Ā, on obtient directement le

Lemme 8.2. Si toutes les composantes de b sont positives (i.e. si le problème sous forme
canonique est de première espèce), alors le problème sous forme standard (8.3) possède
comme base réalisable celle obtenue en ne retenant en base que les m variables d’écart.

Démonstration. En effet, en posant γ({1, · · · , m}) = {n − m + 1, · · · , n}, on s’aperçoit

que B̄ := Āγ n’est autre que la matrice identité de taille m (en particulier γ ∈ B), et par
conséquent
x̄∗B = (B̄)−1 b̄ = b̄ = b
n’a que des composantes positives. La conclusion suit alors la définition de base réalisable,
puisque d’autre part par construction x̄∗N = (0, · · · , 0).

Venons en maintenant au cas général d’un système de deuxième espèce. Nous com-
mençons par le cas d’un système sous forme standard (nous savons que tout problème
d’optimisation peut se ramener sous cette forme). Nous verrons ensuite une deuxième
manière de procéder, moins gourmande en nombre de variables additionnelles, qui s’ap-
plique lorsque l’on part d’un système sous forme canonique de deuxième espèce.
Soit donc le problème d’optimisation linéaire sous forme standard

maximiser cT x
sous les contraintes Ax = b, (8.5)
x ≥ 0,

où c = (c1 , · · · , cn )T et (la variable) x = (x1 , · · · , xn )T sont des vecteurs colonnes à n

lignes, A = (aij )1≤i≤m,1≤j≤n est une matrice à m lignes et n colonnes, de rang égal à m,
et b = (b1 , · · · , bm )T est un vecteur colonne à m lignes.
Sans perte de généralité, on peut supposer que toutes les composantes de b sont
positives, sinon il suffit de les multiplier, ainsi que les lignes correspondantes de A, par −1
(ce qui revient à remplacer une égalité entre deux quantités par l’égalité de leurs quantités
opposées, ce qui est bien sûr équivalent).
On introduit alors la variable “fictive” y = (y1 , · · · , ym )T ∈ Rm et on considère le
problème d’optimisation linéaire

maximiser −y1 − y2 − · · · − ym
sous les contraintes Ax + y = b, (8.6)
x, y ≥ 0.

29
Notons que la fonction objectif de ce dernier problème n’a aucun lien avec la
fonction objectif du problème de départ. Par contre, si le problème (8.5) possède
une solution réalisable, alors le maximum du problème (8.6) est égal à zéro, et inverse-
ment. L’avantage du problème (8.6) est qu’il possède, comme dans le cas des problèmes
de première espèce, une solution de base réalisable évidente donnée par (x1 , · · · , xn ) =
(0, · · · , 0) et (y1 , · · · , ym ) = (b1 , · · · , bm ) (d’où le choix d’écrire le système de départ avec b
n’ayant que des composantes positives). L’itération de la méthode du chapitre 6 appliquée
à (8.6) permet par conséquent de s’assurer si le maximum de (8.6) vaut 0, auquel cas le
sommet optimal en lequel se termine l’algorithme détermine une solution réalisable de
(8.5) et l’itération de la méthode du chapitre 6 peut alors être appliquée directement à
(8.5). Si par contre le maximum de (8.6) est strictement négatif, alors l’ensemble réalisable
de (8.5) est vide et par conséquent il est vain de tenter de résoudre (8.5).
Revenons maintenant au cas d’un problème sous forme canonique
maximiser cT x
sous les contraintes Ax ≤ b, (8.7)
x ≥ 0,
que l’on a transformé via les variables d’écart en le problème sous forme standard cano-
nique
maximiser c̄T x̄
sous les contraintes Āx̄ = b̄, (8.8)
x̄ ≥ 0,
où x̄ := (x1 , · · · , xp+q )T ,

c̄T := (c1 , · · · , cq , 0, · · · , 0),

 
a11 · · · a1q 1 0 0 ··· 0
a21 · · · a2q 0 1 0 ··· 0
Ā :=  .. ..  ,
 
 . .
ap1 · · · apq 0 0 ··· 0 1

b̄ := b,
et faisons l’hypothèse que b possède au moins une composante strictement négative (de
sorte que le problème soit de deuxième espèce). Plutôt que d’introduire p nouvelles va-
riables comme dans le procédé ci-dessus, on en introduit une seule (appelons la xp+q+1 )
et on considère le problème d’initialisation
maximiser −xp+q+1
sous les contraintes Ā¯x̄¯ = b, (8.9)
x̄¯ ≥ 0,

où x̄¯ := (x1 , · · · , xp+q+1 )T et

 
a11 · · · a1q 1 0 0 ··· 0 −1
a21 · · · a2q 0 1 0 ··· 0 −1
Ā¯ =  .. .. ..  .
 
 . . . 
ap1 · · · apq 0 0 · · · 0 1 −1

30
Comme plus haut, le problème (8.8) possède une solution de base réalisable si et seulement
si le maximum du problème (8.9) est égal à zéro. Ce dernier problème possède une solution
de base réalisable relativement facile à déterminer. Pour ce faire, soit i0 ∈ {1, · · · , p} un
indice tel quel
bi0 = min bi < 0.
i∈{1,··· ,p}

On prétend qu’en choisissant pour variables en base les variables {xq + 1, · · · , xq+p+1 } \
{xp+i0 } on obtient une base réalisable. En effet, les variables hors base étant fixées à zéro,
le système (8.9) se ramène à

xp+q+1 = −bi0 (se lit dans la ligne i0 ),

xp+i = bi + xp+q+1 (pour tout i 6= i0 ).

Ainsi, xp+q+1 > 0 par définition de i0 et aussi

xp+i = bi − bi0 ≥ 0

pour tout i 6= i0 . La suite de l’analyse suit alors les mêmes lignes que ci-dessus dans le
cas d’un problème sous forme standard quelconque.

31
Chapitre 9

Description algorithmique de la
méthode du simplexe

Dans ce chapitre, on traduit sous forme algorithmique la méthode développée dans

les chapitres précédents afin de résoudre un problème d’optimisation linéaire que l’on
supposera (le Chapitre 4 nous garantit que cela n’enlève aucune généralité) sous forme
standard :
maximiser cT x
sous les contraintes Ax = b, (9.1)
x ≥ 0,
où c = (c1 , · · · , cn )T et (la variable) x = (x1 , · · · , xn )T sont des vecteurs colonnes à n
lignes, A = (aij )1≤i≤m,1≤j≤n est une matrice à m lignes et n colonnes, de rang égal à m,
et b = (b1 , · · · , bm )T est un vecteur colonne à m lignes de composantes toutes positives.
Etape 1 : Soit on connaı̂t une base réalisable pour (9.1), auquel cas on passe à l’étape
2, soit on n’en connaı̂t pas et considère alors le problème (8.6) du Chapitre 8 pour lequel
on dispose d’une base réalisable évidente. On passe alors à l’étape 2 pour ce dernier
problème, et on laisse momentanément en suspend la résolution de (9.1).
Etape 2 : On dispose d’une base réalisable. Si le vecteur des prix marginaux pour
cette base réalisable n’a que des composantes négatives, la solution de base réalisable
correspondant à la base réalisable courante est un optimum pour le problème en question,
on passe alors directement à l’Etape 3. Sinon, on applique la méthode décrite dans le
Chapitre 6. Celle-ci permet soit de déterminer que le problème d’optimisation en question
n’est pas majoré (cfr. Lemme 6.1), auquel cas on passe directement à l’Etape 4, soit
de déterminer une nouvelle base réalisable meilleure (au sens non strict) concernant la
fonction objectif. Dans ce dernier cas, on applique par défaut le critère naturel pour le
choix des variables entrantes et sortantes, sauf si celui-ci conduit à une augmentation non
stricte de la fonction objectif, auquel cas on applique le critère de Bland. On retourne
ensuite en début d’Etape 2 avec cette nouvelle base réalisable.
Etape 3 : On dispose d’une solution optimale pour le problème en question. S’il s’agit
du problème initial (9.1), on passe à l’Etape 6. S’il s’agit du problème (8.6), ou bien
le maximum est strictement négatif, auquel cas le problème (9.1) possède un ensemble
réalisable vide et on passe à l’Etape 5, ou bien le maximum est égal à zéro, ce qui fournit
une base réalisable pour (9.1), et on retourne à l’Etape 1.

32
 Etape 4 : On sort de l’algorithme avec la conclusion que la fonction objectif du
problème d’optimisation 9.1 n’est pas majorée sur l’ensemble réalisable.

Etape 5 : On sort de l’algorithme avec la conclusion que l’ensemble réalisable du

problème d’optimisation 9.1 est vide.

Etape 6 : On sort de l’algorithme avec une solution optimale.

Il est vivement conseillé au lecteur de tenter d’implémenter l’algorithme ci-dessus dans

son langage de programmation préféré. La procédure en question recevra en entrée la
matrice A ainsi que les vecteurs b et c et fournira en sortie une solution optimale (s’il en
existe, sinon elle en indiquera l’une des deux raisons possibles) ainsi que la valeur optimale
de la fonction objectif.

33
Chapitre 10

Dualité en programmation linéaire

Considérons à nouveau un problème d’optimisation linéaire sous forme canonique

Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj ≤ bi (i = 1, · · · , p), (10.1)
xj ≥ 0 (j = 1, · · · , q),
où p, q ∈ N∗ , et où les cj (1 ≤ j ≤ q), les aij (1 ≤ i ≤ p, 1 ≤ j ≤ q), et les bi (1 ≤ i ≤ p)
sont des constantes réelles.
A supposer que (10.1) possède au moins une solution optimale x∗ , la méthode du
simplexe permet, à chacune de ses étapes, d’obtenir (et d’améliorer) une borne inférieure
sur la valeur optimale cT x∗ de la fonction objectif.
Une question naturelle, mais qui va dans la direction opposée, est celle de savoir s’il
est possible d’obtenir une borne supérieure sur la valeur cT x∗ , et cela sans être obligé de
parcourir l’algorithme du simplexe jusqu’à ce qu’il aboutisse à une solution optimale. De
fait, on peut imaginer que dans certains cas on puisse être intéressé à encadrer avec plus
ou moins de précision la valeur cT x∗ , sans toutefois requérir sa valeur exacte (par exemple
si les calculs sont coûteux ou si le temps est compté).
Pour ce faire, partons des p contraintes d’inégalités
q
X
aij xj ≤ bi (i = 1, · · · , p),
j=1

et faisons en une somme pondérée au moyen de p coefficients positifs yi :

p q p
!
X X X
yi aij xj ≤ y i bi .
i=1 j=1 i=1

En récrivant le terme de gauche de l’inégalité précédente, on obtient

q p p
!
X X X
aij yi xj ≤ yi b i ,
j=1 i=1 i=1

de sorte que si
p
X
aij yi ≥ cj (j = 1, · · · , q), (10.2)
i=1

34
alors nécessairement pour toute solution réalisable x ≡ (x1 , · · · , xq ) de (10.1) on a
q p
X X
cj x j ≤ yi bi .
j=1 i=1

En particulier,
c T x ∗ ≤ bT y
quel que soit y ≡ (y1 , · · · , yp ) vérifiant (10.2) et tel que y ≥ 0. Autrement dit, pour obtenir
une borne supérieure sur la valeur optimale de la fonction objectif du problème (10.1), il
suffit de connaı̂tre une solution réalisable du problème dual de (10.1), que nous définissons
plus précisément maintenant :
Définition 10.1 (Problème primal et dual). Le problème dual de (10.1) est le problème
Pp
minimiser Pi=1 bi y i
p
sous les contraintes i=1 aij yi ≥ cj (j = 1, · · · , q), (10.3)
yi ≥ 0 (i = 1, · · · , p).
On dit aussi que (10.1) est le problème primal de (10.3).

Remarquons que sous forme matricielle, les problèmes primal et dual s’écrivent donc
maximiser cT x minimiser bT y
sous les contraintes Ax ≤ b, 7→ sous les contraintes AT y ≥ c,
x ≥ 0, y ≥ 0.
Remarquons aussi que le problème dual est équivalent au problème d’optimisation linéaire
sous forme canonique
maximiser (−b)T y
sous les contraintes (−A)T y ≤ −c,
y ≥ 0,
l’optimum du second étant égal à l’opposé de l’optimum du premier 1 . Dès lors, on peut
appliquer au problème dual tout ce que nous avons développé jusqu’ici concernant le
problème primal, en particulier l’algorithme du simplexe, ce qui permet déjà de donner
une réponse à la question évoquée en tête de chapitre.
Finalement, remarquons que puisque le problème dual (10.3) est lui-même (équivalent à)
un problème primal, on peut considérer son problème dual à lui aussi. On s’aperçoit de
suite que ce dernier n’est autre que le problème primal du départ, autrement dit le dual
du problème dual est égal au problème primal qui est donc aussi un problème dual !
Répétant alors l’argumentaire nous ayant conduit à la définition 10.1, on obtient di-
rectement le
Théorème 10.2. Si x est une solution réalisable du problème primal (10.1), et y une
solution réalisable du problème dual (10.3), alors nécessairement
cT x ≤ bT y.
En particulier, si cT x = bT y alors x est une solution optimale du primal et y est une
solution optimale du dual.
1. En effet, cela suit la formule classique − maxy (−f (y)) = miny (f (y)) avec f (y) = bT y.

35
Corollaire 10.3. Si la fonction objectif du problème primal est non majorée sur son
ensemble réalisable, alors le problème dual ne possède aucune solution réalisable. Inverse-
ment, si la fonction objectif du problème dual est non minorée sur son ensemble réalisable,
alors le problème primal ne possède aucune solution réalisable.

Attention au fait que les réciproques des énoncés du Corollaire 10.3 sont fausses en
général.
Un résultat plus difficile est le théorème de dualité suivant

Théorème 10.4 (Théorème de dualité de Gale, Kuhn et Tucker). Le problème

primal (10.1) possède une solution optimale x∗ si et seulement si le problème dual (10.3)
possède une solution optimale y ∗ . Dans ce cas, on a nécessairement
q p
X X
cj x∗j = bi yi∗ .
j=1 i=1

Démonstration. Au vu du Théorème 10.2, et de la remarque sur le dual du dual, il suffit

de montrer que si x∗ ≡ (x∗1 , · · · , x∗q ) est une solution optimale du problème primal, alors
il existe une solution réalisable y ∗ ≡ (y1∗ , · · · , yp∗ ) du dual pour laquelle
q p
X X
cj x∗j = bi yi∗ .
j=1 i=1

Partant donc du problème primal

Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj ≤ bi (i = 1, · · · , p),
xj ≥ 0 (j = 1, · · · , q),

introduisons les p variables d’écart

q
X
xq+i := bi − aij xj , (i = 1, · · · , p),
j=1

et récrivons le problème primal sous forme standard

Pq
maximiser cj x j
Pj=1
q
sous les contraintes j=1 aij xj + xq+i = bi (i = 1, · · · , p), (10.4)
xj ≥ 0 (j = 1, · · · , q + p),

ou sous forme matricielle

maximiser c̄T x̄
sous les contraintes Āx̄ = b̄,
x̄ ≥ 0,

36
avec (cfr. Chapitre 4)

x̄ = (x̄1 , · · · , x̄q , x̄q+1 , · · · , x̄q+p ),

c̄T = (c1 , · · · , cq , 0, · · · , 0),
 
a11 · · · a1q 1 0 0 ··· 0
a21 · · · a2q 0 1 0 ··· 0
Ā =  .. ..  ,
 
 . .
ap1 · · · apq 0 0 ··· 0 1

b̄ = b.

Appelons γ la base Pq réalisable pourP (10.4) correspondant à la solution optimale x̄∗ =

(x1 , · · · , xq , b1 − j=1 a1j xj , · · · , bp − qj=1 apj x∗j ), et soit d¯ ≡ (d1 , · · · , dq , dq+1 , · · · , dq+p ) le
∗ ∗ ∗

vecteur des prix marginaux correspondants. Alors pour toute solution (non nécessairement
réalisable ! - cfr Corollaire 5.5) x̄ de (10.4) on a
q p q
X X X
c̄ x̄ = c̄ x̄ + d¯T x̄ = cT x∗ +
T T ∗


dj x̄j + dq+i bi − aij x̄j
j=1 i=1 j=1
" p
# q
" p
# (10.5)
X X X
T ∗
= c x − bi (−dq+i ) + dj − aij dq+i x̄j .
i=1 j=1 i=1

En choisissant pour x̄ l’unique solution pour laquelle x̄1 = · · · = x̄q = 0 on obtient de

(10.5)
p
X
T ∗
c x = bi (−dq+i ). (10.6)
i=1

En choisissant pour x̄ l’unique solution pour laquelle x̄1 = · · · = x̄q = 0 sauf pour un
certain j ∈ {1, · · · , q} pour lequel x̄j = 1, on obtient, par (10.5) et en tenant compte de
(10.6),
p
X
dj − aij dq+i = cj . (10.7)
i=1
∗
Par ailleurs, puisque x̄ est une solution optimale, nécessairement le vecteur des prix mar-
ginaux d¯ en cette solution est négatif. D’autre part j ∈ {1, · · · , q} a été choisi quelconque.
Ainsi, de (10.7) on obtient
p
X
aij (−dq+i ) = cj − dj ≥ cj , j = 1, · · · , q. (10.8)
i=1

Il s’ensuit que le vecteur y ∗ ≡ (y1∗ , · · · , yp∗ ) := (−dq+1 , · · · , −dq+p ) est une solution
réalisable du problème dual (10.3), et par (10.6) on a

c T x ∗ = bT y ∗ ,

ce qui termine la démonstration.

La démonstration du théorème précédent permet également d’affirmer le

37
Corollaire 10.5 (Solution optimale du dual et prix marginaux). Si le problème
primal (10.1) possède une solution optimale x∗ , et si d¯ ≡ (d1 , · · · , dq , dq+1 , · · · , dq+p )
désigne le vecteur des prix marginaux pour la base réalisable correspondant à x∗ , alors
une solution optimale du problème dual (10.3) est fournie par
(y1∗ , · · · , yp∗ ) := (−dq+1 , · · · , −dq+p ).
Théorème 10.6 (Prix marginaux et problème dual). Supposons que le problème
primal (10.1) possède une solution optimale x∗ non dégénérée. 2 Alors il existe ε > 0 tel
que si les variations t1 , · · · , tp des contraintes vérifient la condition de petitesse
|ti | ≤ ε ∀ i ∈ {1, · · · , p},
l’optimum du problème primal modifié
Pq
maximiser cj x j
Pj=1q
sous les contraintes j=1 aij xj ≤ bi + ti (i = 1, · · · , p), (10.9)
xj ≥ 0 (j = 1, · · · , q),
est encore atteint et est donné par
p
X
∗
T
c x + ti yi∗ ,
i=1

où (y1∗ , · · · , yp∗ ) désigne une (en fait l’unique) solution optimale du problème dual (10.3).

Démonstration. Le problème dual de (10.9) est donné par

Pp
minimiser Pi=1 (bi + ti )yi
p
sous les contraintes i=1 aij yi ≥ cj (j = 1, · · · , q), (10.10)
yi ≥ 0 (i = 1, · · · , p).
La variation des contraintes du primal se traduit donc par une variation de la fonction
objectif du dual, mais les contraintes du dual ne sont pas modifiées. En particulier, les
solutions de base réalisables de (10.10) et de (10.3) sont identiques. Par hypothèse, x∗
est non-dégénérée, et par conséquent y ∗ est l’unique solution optimale de (10.3). En effet,
le corollaire précédent (utilisé en renversant le rôle du primal et du dual) implique que
les prix marginaux du dual correspondant aux variables d’écart du dual sont donnés par
x∗ , et sont donc tous strictement négatifs, il s’ensuit que l’optimum du dual est atteint
et uniquement atteint en y ∗ . Puisque y ∗ est l’unique solution optimale de (10.3), il existe
r > 0 tel que
p p
X X
∗
bi y i ≥ bi y i + r
i=1 i=1
quelle que soit la solution de base réalisable (y1 , · · · , yp ) de (10.3) (et donc de (10.10))
différente de y ∗ . Par continuité et finitude (il n’y a qu’un nombre fini de solutions de base
réalisables), on déduit alors qu’il existe ε > 0 tel que
p p
X X
(bi + ti )yi∗ > (bi + ti )yi
i=1 i=1

2. On rappelle qu’une solution de base est dite non dégénérée si aucune des composantes correspondant
aux variables en base n’est nulle.

38
quelle que soit la solution de base réalisable (y1 , · · · , yp ) de (10.10) différente de y ∗ , et
quels que soient t1 , · · · , tp vérifiant |ti | ≤ ε pour chaque i ∈ {1, · · · , p}. En particulier,
pour
Pp de tels ti ∗le problème dual (10.10) possède un optimum dont la valeur est donnée par
i=1 (bi + ti )yi . Le Théorème de dualité 10.4 assure alors que (10.9) possède également
un optimum, dont la valeur optimale, égale à celle du dual (10.10), est donnée par
p p p q p p
X X X X X X
(bi + ti )yi∗ = bi yi∗ + ti yi∗ = cj x∗j + ti yi∗ T
=c x ++∗
ti yi∗ .
i=1 i=1 i=1 j=1 i=1 i=1

Ceci termine la démonstration.

Il est conseillé au lecteur de relire la partie du premier chapitre consacrée au problème

du concurrent à la lumière du Corollaire précédent.

Remarque 10.7 (Sur le choix du primal ou du dual pour l’application de l’algo-

rithme du simplexe). Dans certains cas, il est plus intéressant d’appliquer l’algorithme
du simplexe à un problème dual (ou plûtot à sa forme standard associée) plutôt qu’au
problème primal. Considérons en effet un primal ayant p = 1000 contraintes pour seule-
ment q = 100 inconnues. La forme standard associée au primal (après introduction des
variables d’écart) aura m = 1000 contraintes pour n = p + q = 1100 inconnues. L’algo-
rithme du simplexe dans ce cas nécessite à chaque étape de résoudre un système de taille
1000 × 1000. A l’inverse, le problème dual possède p = 100 contraintes pour q = 1000
inconnues. Le problème standard qui lui est associé possède donc m = 100 contraintes
pour n = p + q = 1100 inconnues. L’algorithme du simplexe dans ce deuxième cas ne
nécessite plus donc à chaque étape “que” de résoudre un système de taille 100 × 100, ce
qui constitue un gain énorme. En résumé, il est donc préférable de considérer en priorité
la version (primale ou duale) qui possède le moins de contraintes.

Théorème 10.8 (Théorème des écarts complémentaires). Soient x ≡ (x1 , · · · , xq )

et y = (y1 , · · · , yp ) deux solutions réalisables respectivement du problème primal (10.1)
et du problème dual (10.3). Une condition nécessaire et suffisante pour que x et y soient
optimaux simultanément est que
p
X
∀ j ∈ {1, · · · , q}, si xj > 0 alors aij yi = cj
i=1
et (10.11)
q
X
∀ i ∈ {1, · · · , p}, si yi > 0 alors aij xj = bi .
j=1

Démonstration. Elle reprend le schéma du début de chapitre concernant les bornes supérieures
et inférieures sur la fonction objectif.
Puisque x est une solution réalisable du primal et que y ≥ 0,
p q p
!
X X X
aij xj yi ≤ b i yi .
i=1 j=1 i=1

39
Inversement, puisque y est une solution réalisable du dual et que x ≥ 0,
q p q
!
X X X
aij yi xj ≥ cj x j .
j=1 i=1 j=1

Par ailleurs, en développant on obtient bien sûr que

p q q p
! !
X X X X
aij xj yi = aij yi xj .
i=1 j=1 j=1 i=1

Ainsi,
q q p p q p
! !
X X X X X X
cj x j ≤ aij yi xj = aij xj yi ≤ bi y i . (10.12)
j=1 j=1 i=1 i=1 j=1 i=1

Nous pouvons maintenant démontrerPla conditionP nécessaire. Si x et y sont optimales,

alors par le Théorème de dualité on a qj=1 cj xj = pi=1 bi yi et par conséquent chacune
des deux inégalités de (10.12) est une égalité. Les inégalités de (10.11) s’ensuivent.
Inversement pour la condition suffisante. Si les inégalités de (10.11)
P sont vérifiées,
P alors
les deux inégalités de (10.12) sont des égalités et par conséquent qj=1 cj xj = pi=1 bi yi .
Il s’ensuit du Théorème 10.2 que x et y sont optimales.

Corollaire 10.9. Soit x une solution réalisable du problème primal. Alors x est opti-
male
Pq si et seulement si il existe une solution P réalisable y du problème dual pour laquelle
p
a x
j=1 ij j = b i pour tout i vérifiant y i > 0 et i=1 aij yi = cj pour tout j vérifiant xj > 0.

40
 THEORIE DE LA METHODE GRAPHIQUE
La méthode graphique permet la résolution de problèmes linéaires simples de manière intuitive et
visuelle. Cette méthode est limitée à des problèmes de deux ou trois variables de décisions puisqu’il
n’est pas possible d’illustrer graphiquement plus de trois dimensions.
Bien qu’en général on puisse difficilement trouver des problèmes avec deux ou trois variables de
décision, cette méthodologie de résolution est cependant très utile. Lors de la reproduction graphique
de situations possibles, tels que l’existence d’une solution optimale unique, des solutions optimales
alternatives, la non-existence de solution et l’absence de partie bornée, offre une aide visuelle pour
interpréter et comprendre l’algorithme de la méthode du Simplexe, beaucoup plus sophistiquée et
abstraite.
Présentons les étapes du processus de résolution des problèmes par la méthode des graphes :
1 Créer un système de coordonnées cartésiennes, dans lequel chaque variable de décision
est représentée par un axe.
2 Etablir une échelle de mesure pour chacun des axes appropriés à sa variable associée.
3 Dessiner dans le système de coordonnées les contraintes du problème, y compris celles de non-
négativité (qui seront les propres axes). Chaque inéquation précise une région qui sera le demi-
plan délimité par la ligne droite qu’on obtient en considérant la contrainte concernée comme une
égalité. Par contre si une équation détermine une région, c’est la ligne droite, elle-même.
4 Faire l’intersection de toutes les régions qui déterminent la région ou l’espace faisable (qui est
un ensemble convexe). Si cette région est vide, alors il n’y a pas de point qui satisfait toutes les
contraintes simultanément, de sorte que le problème, ne sera pas résolu, dit infaisable. Sinon,
passez à l’étape suivante.
5 Représenter la fonction objectif soit Z = a𝑋1 + b𝑋2. Pour ce faire, on pose Z = 𝑍0, 𝑍0 étant une
constante. On obtient ainsi une droite dont tous les points fournissent la même valeur 𝑍0. En
général, on prend 𝑍0 = 0. On a donc à représenter la droite (d) d’équation a𝑋1 + b𝑋2 = 0.
6 Ici, il s’agit de trouver le couple (𝑋1, 𝑋2) qui maximise ou minimise la fonction objectif. Cela
implique l’augmentation de 𝑍0. Il suffit d’éloigner la droite (d) de l’origine (en respectant 𝑋1 ≥ 0
& 𝑋2 ≥ 0). Elle sera donc déplacée jusqu’à l’extrême limite où il n’y aura plus qu’un point
d’intersection (éventuellement un segment, dans ce cas on résout le système d’équation formé
par l’équation de la fonction objectif à ce niveau et celle du support du segment) avec la région
des solutions admissibles. Ce glissement n’est possible que lorsque la fonction est bornée. Le
glissement se fait vers le haut dans le cas d’une maximisation et vers le bas dans le cas d’une
minimisation. Par ailleurs, il faut noter que la solution optimale se trouve nécessairement sur le
pourtour de la région des solutions admissibles.

41
 Exercices d’application

Exercice 1 :
Une entreprise fabrique des électrophones et des postes de télévision en noir et blanc. 140
ouvriers travaillent à la fabrication. Le prix de revient, pièces et main d’œuvre, d'un poste de TV
est de 400kF. Il n'est que de 300kF pour un électrophone. Les services comptables de
l'entreprise donnent la consigne de ne pas dépasser par semaine la somme de 240000kF, pièces
et main d'œuvre. Chaque ouvrier travaille 40 heures par semaine. Les chefs de service estiment
qu'il faut 10h de main d'œuvre pour fabriquer un électrophone et 5h seulement pour fabriquer un
poste de TV. Les services commerciaux ne peuvent vendre plus de 480 postes de TV et 480
électrophones par semaine. Les prix de ventes sont tels que l'entreprise, tous frais payés, fait un
bénéfice de 240kF par poste de TV et de 160 kF par électrophone. On désigne par x le nombre
d'électrophones et y le nombre de postes de télévision fabriqués par semaine.
1- Déterminer les quatre contraintes de fabrication.
2- Tracer dans le plan le polygone des points M (x, y) pour lesquels la
fabrication est possible.

3- Déterminer le bénéfice b par semaine en fonction de x et y.

4-Déterminer la fabrication qui assure un bénéfice maximum.

Résolution :
1- Les quatre contraintes données par l'énoncé sont :

* 300x + 400y ≤ 240000 : constantes sur le prix de revient

* 10x + 4y ≤ 5600 : constantes sur le nombre d'heures par semaine
* x ≤ 480 ; y ≤ 480 : les 2 constantes sur le total des ventes

2- Polygone des contraintes

42
3- Bénéfice en fonction de x et y B
(x ; y) = 160x + 240y.
Ajoutons cette droite dans le polygone des contraintes.
4- Solution graphique du problème
Elle correspond au point L (160 ; 480).
Bénéfice Maximum = 140 800 francs.

Exercice 2 :
Une usine fabrique 3 composants, A, B et C en utilisant le même processus de production
pour chacun. Une unité de A prend 1 heure, une unité de B prend 0,75 heure et une unité de C
prend 0,5 heure. De plus, C doit être fini à la main, une activité prenant 0,25 heure par unité.
Chaque semaine, le temps de production total (hors finition à la main) ne doit pas dépasser 300
heures et la finition à la main ne doit pas dépasser 45 heures.

43
Les composants sont finalement assemblés pour fabriquer deux produits finis.
Un produit est composé d'une unité de A et d'une unité de C vendues à 30 livres tandis que
l'autre est composé de deux unités de B et d'une unité de C et se vend à 45 livres. Au maximum
130 unités du premier produit et 100 unités du deuxième produit peuvent être vendues chaque
semaine. Formulez le problème de la planification de la production hebdomadaire pour
maximiser le total des recettes sous forme de problème.

Résolution :
Formulons le problème de la planification de la production hebdomadaire.
Soit r cette recette, x la quantité du premier produit et celle du deuxième produit. Ainsi x, y ≥
0.
Le premier produit est composé d'une unité de A et d'une unité de C tandis que le deuxième est
composé de deux unités de B et d'une unité de C. Or une unité de A, B et C prend
respectivement 1 heure; 0,75 heure et 0,5 heure à produire sachant que le temps total de
production hebdomadaire ne doit pas dépasser 300 heures. Alors, on a :
x(1 + 0,5) + y(1,5 + 0,5) ≤ 300.
Par ailleurs, C doit être fini à la main et nécessite 0,25 heure par heure. Or le premier et le
deuxième produit sont composés chacun d'une unité de C et la finition à la main de C ne doit
pas dépasser 45 heures.
Donc, on a : 0,25x + 0,25y ≤ 45.
De plus, au maximum 130 unités du premier produit et 100 unités du deuxième produit sont
vendus par semaine. Soit :
x ≤ 130 et y ≤ 100.
Le problème obtenu est le suivant :
Maximisons r = 30x + 45y sous les contraintes :

𝑥(1 + 0,5) + 𝑦(1,5 + 0,5) ≤ 300

0,25𝑥 + 0,25𝑦 ≤ 45
𝑥 ≤ 130 =>
𝑦 ≤ 100
{ 𝑥, 𝑦 ≥ 0

3𝑥 + 4𝑦 ≤ 600
𝑥 + 𝑦 ≤ 180
𝑥 ≤ 130
𝑦 ≤ 100
{ 𝑥, 𝑦 ≥ 0
Procédons à la résolution graphique.
Le graphe obtenu est le suivant :

44
 250

200

150

100

50

0
-200 -150 -100 -50 0 50 100 150 200 250
-50

-100

-150

Légende :
: droite d’équation 𝑥 + 𝑦 = 180
: droite d’équation 30𝑥 + 45𝑦 = 0
: droite d’équation 3𝑥 + 4𝑦 = 600
: droite d’équation 𝑦 = 100
: droite d’équation 𝑥 = 130
La partie hachurée en gris correspond au domaine réalisable.
Après glissement de la droite d’équation 30x + 45y = 0, les solutions optimales sont : x = 66,7
et y = 100
Soit r = 6501 livres.

Exercice 3 :
Dans un gymnase, un groupe d’élèves se charge de la distribution de pains au chocolat et de
croissants lors de la pause de 10 heures. Pour pouvoir satisfaire la demande, ils doivent disposer
au minimum de 108 pains et de 96 croissants. Deux boulangers proposent pour le même prix :
l’un le lot A comprenant 12 pains au chocolat et 8 croissants, l’autre le lot B composé de 9 pains
au chocolat et 12 croissants.
Déterminer le nombre de lots A et le nombre de lots B qui doivent être achetés pour satisfaire la
demande au moindre coût.

Résolution :
Formulation du problème
Soient A le nombre de lots de type A et B celui de type B. Données
• Lot A : 12 pains au chocolat et 8 croissants

45
 • Lot B : 9 pains au chocolat et 12 croissants
• Minimum requis : 108 pains au chocolat et 96 croissants Ainsi
les contraintes se traduisent par :
12A + 9B ≥ 108 ( pains au chocolat ) et 8A + 12B ≥ 96 ( croissants ).
Il s’agira de minimiser le coût c’est-à-dire d’optimiser le nombre de lots. Soit Z cette
fonction. Comme le prix de A et B n’a pas été donné, on a simplement : Z = A + B. Le
problème obtenu est :
Minimisons Z = A + B sous les contraintes :

12𝐴 + 9𝐵 ≥ 108
{ 8𝐴 + 12𝐵 ≥ 96
𝐴, 𝐵 ≥ 0

Le graphique est :

On obtient au final A = 6 et B = 4 comme solutions optimales. Ainsi il faudra 6 lots A et 4 lots B.

Soit Z = 10.

46