PROGRAMMATION LINEAIRE

Prof. Adama COULIBALY

UFR Mathématiques et Informatique,
Université FHB de Cocody, Abidjan

28 novembre 2022
Table des matières

1 Formulation d’un programme linéaire 2

1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Forme standard, forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Modélisation sous forme de programmes linéaires . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Etapes de la modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Résolution des programmes linéaires 7

2.1 Résultats théoriques fondamentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Notions sur les polyèdres convexes et sommets . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Existence de solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1 Solution de base réalisable d’un programme linéaire . . . . . . . . . . . . . . . . . 9
2.3.2 Forme canonique d’un programme linéaire par rapport à une base . . . . . . . . . 12
2.3.3 Caractérisation des bases réalisables optimales . . . . . . . . . . . . . . . . . . . . 13
2.3.4 Algorithme primal du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.5 Convergence de l’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.6 Méthode des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.7 Méthode du grand M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Dualité en programmation linéaire 24

3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Propriétés de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Algorithme dual Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1
Chapitre 1

Formulation d’un programme linéaire

1.1 Définitions
Définition 1.1.1 Un programme linéaire dans Rn est un problème qui consiste à déterminer les valeurs à
affecter à des variables x1 , · · · , xn en vue d’optimiser (minimiser ou maximiser) une application linéaire
de ces variables compte tenu de certaines contraintes (équations ou inéquations linéaires) auxquelles sont
soumises les valeurs de ces variables.
∑
Si l’application linéaire est Z : Rn → R qui à x ∈ Rn associe Z(x) = nj=1 cj xj et les contraintes
sont :  ∑n

 j=1 aij xj ≥ bi , i = 1, · · · , m1

 ∑n a x ≤ b , i = m + 1, · · · , m
ij j i 1 2
∑j=1


n
j=1 aij xj = bi , i = m2 + 1, · · · , m


xj ≥ 0, j = 1, · · · , n.
on le note symboliquement :
∑
min (max) Z(x) = nj=1 cj xj (1)
 ∑n

 j=1 aij xj ≥ bi , i = 1, · · · , m1 (2a)

 ∑n a x ≤ b , i = m + 1, · · · , m
ij j i 1 2 (2b)
∑j=1


n
j=1 aij xj = bi , i = m2 + 1, · · · , m (2c)


xj ≥ 0, j = 1, · · · , n (3)

La fonction Z est appelée fonction-objectif ou fonction économique du programme linéaire, les condi-
tions dans la partie (2) sont les vraies contraintes ((2a) et (2b) étant les contraintes d’inégalité, (2c) les
contraintes d’égalié) et les conditions dans la partie (3) sont les contraintes de signe.
Pour tout i et j, les coefficients aij , bi et les cj sont des constantes données, les xj sont les variables.

Remarque 1.1.1 Dans cette définition, on peut ramener toutes les contraintes d’inégalité à des inégalités
de même type. Il suffit en effet de multiplier la contrainte par −1 le cas échéant.
Par convention les contraintes d’inégalité pour un problème de minimisation sont du type ” ≥ ” et les
contraintes d’inégalité pour un problème de maximisation sont du type ” ≤ ”

On peut donc dire qu’un programme linéaire est de la forme :

∑
min (max) Z(x) = nj=1 cj xj
 ∑n
 ∑j=1 aij xj ≥ (≤) bi , i = 1, · · · , m1 (P )
n
j=1 aij xj = bi , i = m1 + 1, · · · , m

xj ≥ 0, j = 1, · · · , n

2
Définition 1.1.2 Etant donné le programme linéaire (P ), on appelle solution réalisable ou acceptable
tout élément x de Rn qui vérifie toutes les contraintes.

On remarque alors que l’ensembles des solutions réalisables du programme linéaire (P ) est :
 ∑n 
 ∑ j=1 aij xj ≥ (≤) bi , i = 1, · · · , m1 
n
P = x ∈ Rn : j=1 aij xj = bi , i = m1 + 1, · · · , m .
 
xj ≥ 0, j = 1, · · · , n

C’est un sous-ensemble de Rn ; il peut être vide, non vide et borné, non vide et non borné.

1.2 Forme standard, forme canonique

Dans cette partie on considère la relation suivante.
Pour u et v dans Rn on note

u ≤ v ⇔ ui ≤ vi ∀ i = 1, · · · , n.

Définition 1.2.1 Un programme linéaire est sous forme standard si les vraies contraintes sont des
égalités et les variables sont astreintes à être non négatives. En d’autres termes, le problème est sous
la forme
∑n
{ ∑(max) Z = j=1 cj xj
min
n
j=1 aij xj = bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n

Si on pose A = (aij ) ∈ Mm,n (R), c = (cj ) ∈ M1,n (R), et

b = (bi ) ∈ Mm,1 (R), on a la notation matricielle

min(max)
{ Z = cx
Ax = b
x ∈ Rn , x ≥ 0
On a la proposition suivante.

Proposition 1.2.1 Tout programme linéaire peut se mettre sous forme standard

Preuve : Il suffit de transformer les contraintes d’inégalité en contraintes d’égalité en considérant les
équivalences suivantes :
∑n ∑n
aij xj ≥ bi ⇔ aij xj − si = bi , si ≥ 0
j=1 j=1

∑
n ∑
n
aij xj ≤ bi ⇔ aij xj + si = bi , si ≥ 0
j=1 j=1

Définition 1.2.2 La variable si introduite pour passer d’une contrainte d’inégalité à une contrainte
d’égalité est appelée variable d’écart.

Remarque 1.2.1 Le passage à la forme standard augmente le nombre de variables dans le programme
linéaire.

3
Définition 1.2.3 Un programme linéaire est sous forme canonique si les vraies contraintes sont des
inégalités et les variables sont astreintes à être non négatives. Pour les problèmes de minimisation on a
∑n
min Z =
{ j=1 cj xj
∑n
≥ bi , i = 1, · · · , m
j=1 aij xj
xj ≥ 0, j = 1, · · · , n

et pour les problèmes de maximisation on a

∑
max Z = nj=1 cj xj
{ ∑n
j=1 aij xj ≤ bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n

En considérant les mêmes notations que ci-dessus, on obtient respectivement pour la minimisation et
la maximisation la notation matricielle suivante :

min Z = cx
{ max
{ Z = cx
Ax ≥ b Ax ≤ b
x ∈ Rn , x ≥ 0 x ∈ Rn , x ≥ 0

Proposition 1.2.2 Tout programme linéaire peut se mettre sous forme canonique

Preuve : Il suffit de transformer les contraintes d’égalité en contraintes d’inégalité en considérant l’une
des équivalences suivantes :

∑
n { ∑n
j=1 aij xj ≥ bi ,
∑
aij xj = bi ⇔
− nj=1 aij xj ≥ −bi
j=1

ou

∑
n { ∑n
j=1 aij xj ≤ bi ,
∑
aij xj = bi ⇔
− nj=1 aij xj ≤ −bi
j=1

Remarque 1.2.2 Le passage à la forme canonique augmente le nombre de contraintes dans le programme
linéaire.

1.3 Modélisation sous forme de programmes linéaires

1.3.1 Etapes de la modélisation
Pour modéliser un problème sous forme d’un programme linéaire, on peut procéder en quatre étapes :
le choix des variables, la détermination des contraintes, la détermination de la fonction-objectif et enfin
le résumé.
Etape 1 : choix des variables
Dans cette étape on choisit les variables de décision : en général elles permettent de définir la fonction-
objectif.
Etape 2 : détermination des contraintes
A ce niveau il faut d’abord signaler les contraintes de signe des variables qui ne sont pas indiquées
dans le texte. Les variables sont en général non négatives en tant que quantités de matière. Ensuite on

4
détermine les contraintes structurelles qui sont liées au texte. Il ne faut pas oublier d’indiquer les éléments
du texte qui engendrent les contraintes structurelles.
Etape 3 : détermination de la fonction-objectif
Dans cette partie, on définit la fonction-objectif qui est soit un bénéfice soit un coût de production.
Etape 4 : résumé
On termine la modélisation par un résumé qui signale le type de problème à résoudre. Pour un coût
de production il s’agira naturellement d’un programme linéaire de minimisation et pour un problème de
gain d’un programme linéaire de maximisation.

Remarque 1.3.1 (Hypothèse de linéarité) Pour modéliser un problème sous forme d’un programme
linéaire, on prend en compte les hypothèses de linéarité sur la fonction-objectif et les contraintes struc-
turelles. Cela signifie par exemple que, pour fabriquer une unité d’un produit donné, si on utilise une
matière première à la hauteur de α, alors pour en fabriquer x unités, on utilisera la matière première
à la hauteur de αx. En outre si la vente d’une unité de ce produit conduit à un bénéfice de c unités
monétaires, alors la vente de x unités de ce produit conduira à un bénéfice de cx unités monétaires.

Cette hypothèse de linéarité sera prise en compte automatiquement pour tous les cas de modélisation
en programmation linéaire.

1.3.2 Quelques exemples

Exemple 1
Un ébéniste fabrique des bureaux sous deux modèles : le modèle ”luxe” et le modèle ”standard”.
Des études de marché ont montré que, pour l’année à venir, les possibilités de vente s’élèvent à 300
unités pour le modèle ”luxe” et à 400 unités pour le modèle ”standard”. L’approvisionnement en bois est
suffisant pour pouvoir fabriquer annuellement 500 bureaux quel que soit le type. Par ailleurs, le temps
de fabrication d’un bureau sous le modèle ”luxe” est double de celui d’un bureau de type ”standard” : la
capacité annuelle de fabrication est telle que, si tous les bureaux fabriqués étaient du type ”standard”,
on pourrait en fabriquer 700 au maximum.
La vente d’un bureau sous le modèle ”luxe” conduit à une marge unitaire sur coût variable égale à 7,
celle d’un bureau de type ”standard” : 5.
On se propose de rechercher le programme annuel de fabrication conduisant au profit global maximal.
Exemple 2
Une société fabrique, entre autres choses, deux articles P1 et P2 qu’elle vend à des grossistes aux prix
respectifs de 320 et 500 unités monétaires.
La fabrique des produits P1 et P2 nécessite l’utilisation dans un ordre quelconque de 3 types de
machines M1, M2 et M3 pendant des temps exprimés en minutes dans le tableau suivant :

M1 M2 M3
P1 20 50 10
P2 30 50 40

Pour cette fabrication, ces machines sont disponibles au cours d’un mois :
300h pour les machines M1
500h pour les machines M2
200h pour les machines M3.
Les marges sur coûts variables, en pourcentage du prix de vente s’élèvent à 25 pour P1, 20 pour P2.
Comment maximiser la marge sur coûts variables ? Formuler ce problème sous forme d’un programme
linéaire.
Exemple 3

5
 Une fermière veille à ce que ses poulets absorbent chaque jour 24 unités de fer et 8 unités de vitamines.
Le maı̈s procure 2 unités de fer et 5 unités de vitamines. Une nourriture à base d’os procure 4 unités
de fer et 1 unité de vitamines. Le millet procure 2 unités de fer et 1 unité de vitamines.
Comment cette fermière devra-t-elle mélanger ces trois aliments de façon à satisfaire au moindre coût
les exigences d’ingestion quotidiennes de ses poulets, sachant que les trois aliments coûtent respectivement
4000, 2000 et 6000 unités monétaires. Formuler seulement le problème à résoudre.
Exemple 4
Un atelier de finition d’une entreprise fabrique des pièces mécaniques de deux types : A et B, à partir
des pièces que lui fournit l’atelier de moulage ; ces pièces brutes permettent la fabrication de l’un ou
l’autre des types A et B, indifféremment.
La capacité journalière de production de l’atelier de moulage est de 130 unités.
Ces pièces moulées subissent ensuite, dans l’atelier de finition, un usinage et un traitement thermique.
L’usinage d’une pièce de type A nécessite 2 heures de travail sur machine, celui d’une pièce de type
B nécessite 3 heures.
Le traitement thermique demande 3 heures pour une pièce de type A et 1 heure pour une de type B.
Les disponibilités en main d’oeuvre sont telles que 340 heures-machine peuvent être effectuées à l’usinage
et 290 heures au traitement thermique, chaque jour.
Après fabrication, les pièces sont ensuite vérifiées. Compte tenu des effectifs des vérificateurs, 90 pièces
de type A et 100 de type B peuvent être vérifiées par jour.
L’entreprise commercialise ces pièces : la marge unitaire sur coût variable pour les pièces de type A
est évaluée aux trois quarts de celle relative aux pièces de type B.
Ecrire le programme linéaire permettant de déterminer un programme journalier optimal de fabrica-
tion pour l’atelier de finition.
Exemple 5
Une exploitation agricole décide de consacrer au maximum 16 hectares à la culture des céréales C1 ,
C2 , C3 , C4 , C5 .
Elle doit pour cela utiliser trois types d’engrais : e1 , e2 , e3 qu’elle ne possède qu’en quantités limitées
(8 pour e1 , 4 pour e2 et 9 pour e3 ).
Les années précédentes ont montré que les quantités d’engrais nécessaires par hectare de culture des
différentes céréales sont les suivantes :

C1 C2 C3 C4 C5
e1 1 1 0 2 0
e2 1 0 2 0 0
e3 0 2 0 0 1

De plus, l’agriculteur est en droit d’attendre pour l’année prochaine, au vu des récoltes précédentes
et du marché actuel, un bénéfice moyen net par hectare de 3 pour C1 , 4 pour C2 , 1 pour C3 , 7 pour C4
et 2 pour C5 .
Dans ces conditions, déterminer le programme linéaire conduisant à une exploitation optimale de
cette activité.

6
Chapitre 2

Résolution des programmes linéaires

2.1 Résultats théoriques fondamentaux

2.1.1 Notions sur les polyèdres convexes et sommets
On commence cette section par quelques rappels classiques.

Définition
{ 2.1.1 Un hyperplan} dans Rn est un sous-espace affine de dimension n−1. Il est de la forme :
∑n
H = x ∈ Rn : j=1 aj xj = α où aj ∈ R pour tout j = 1, · · · n et α ∈ R sont donnés.

Dans Rn tout hyperplan divise l’espace en deux demi-espaces ∑

fermés de frontière cet hyperplan.
n
Par exemple si H est un hyperplan défini par H = {x ∈ Rn : j=1 aj xj = α}, les ensembles

∑
n ∑
n
{x ∈ R :n
aj xj ≥ α} et {x ∈ R :
n
aj xj ≤ α}
j=1 j=1

sont les demi-espaces fermés de frontière H et les ensembles

∑
n ∑
n
{x ∈ R :n
aj xj > α} et {x ∈ R :
n
aj xj < α}
j=1 j=1

sont les demi-espaces ouverts de frontière H.

Définition 2.1.2 Un polyèdre convexe C de Rn est l’intersection

(éventuellement vide) d’un nombre fini de demi-espaces fermés et/ou d’hyperplans.
C’est-à-dire :  

 ai x ≤ bi , i = 1, · · · , p1 , 

C = x ∈ R : ai x ≥ bi , i = p1 + 1, · · · , p2 ,
n

 

ai x = bi , i = p2 + 1, · · · , m
où les ai sont dans M1,n (R) et les bi , dans R, i = 1, · · · , m.
Dans ce cas les hyperplans Hi = {x ∈ Rn : ai x = bi , i = 1, · · · , m} sont dits hyperplans frontières du
polyèdre C.

Remarque 2.1.1 1) Dans cette définition on peut toujours supposer qu’on a un seul type d’inégalité.
2) L’ensemble des solutions réalisables d’un programme linéaire est polyèdre convexe.

Définition 2.1.3 Soit C un polyèdre convexe de Rn . Un point x ∈ C est un sommet de C s’il existe
a ∈ M1,n (R) tel que ax < ay pour tout y ∈ P, y ̸= x.

On montre qu’un point x ∈ Rn est un sommet d’un polyèdre C si et seulement s’il appartient à C et
est intersection de n hyperplans frontières de C linéairement indépendants.

7
2.1.2 Existence de solution optimale
Nous avons considéré depuis le début à la fois, les problèmes de maximisation de les problèmes
de minimisation. Il faut noter que tout problème de maximisation peut se ramener à un problème de
minimisation. En effet, on a :

Proposition 2.1.1
max Z(x) = − min −Z(x).
x∈C x∈C

Sans perdre de généralités, nous allons considérer en théorie dans tout ce qui suit un problème de
minimisation.
Soit le programme linéaire :
min Z(x) (P),
x∈C

L’ensemble des solutions réalisables de P peut être soit :

- vide ;
- non vide et borné ;
- non vide et non borné.

Définition 2.1.4 Etant donné le programme linéaire P, une solution optimale est une solution réalisable
c’est-à-dire un élément x∗ de C qui vérifie :

Z(x∗ ) ≤ Z(x), ∀ x ∈ C.

Dans ce cas la valeur Z ∗ = Z(x∗ ) est dite valeur optimale du programme linéaire.

Etant donné le programme linéaire P, on a les trois situations suivantes :

- l’ensemble des solutions réalisables est vide : C = ∅, dans ce cas on dit que le programme est
impossible ;
- l’ensemble des solutions réalisables n’est pas vide (C ̸= ∅) et non borné, mais la fonction-objectif Z
n’est pas minorée sur C. Le minimum vaut alors Z ∗ = −∞ : on dit que le programme est non borné ;
- l’ensemble des solutions réalisables n’est pas vide et la fonction-objectif Z est minorée sur C. Alors
P a une solution optimale (pas forcément unique) : on dit que le programme linéaire a un optimum fini.
On montre que :

Théorème 2.1.1 Etant donné le programme linéaire P, si son ensemble des solutions réalisables est
non vide, fermé et borné alors il possède une solution optimale.

Nous avons dans ce qui suit la propriété dite propriété fondamentale de la programmation linéaire.

Théorème 2.1.2 Si un programme linéaire possède une solution optimale, alors son ensemble des so-
lutions réalisables contient au moins un sommet et l’un d’entre eux est solution optimale du programme
linéaire.

Pour déterminer cette solution optimale, nous avons plusieurs méthodes.

8
2.2 Méthode graphique
La méthode graphique est l’une des premières méthodes utilisées pour résoudre les programmes
linéaires.
On considère le programme linéaire (P ).
On suppose que (P ) admet une solution optimale. Pour résoudre ce problème par la méthode gra-
phique, on peut procèder de la façon suivante :
- dessiner le polyèdre des solutions réalisables dans un repère (de préférence orthonormé),
- considérer les lignes de niveau de la fonction-objectif passant par les différents sommets,
- éliminer tous les sommets dont les lignes de niveau rencontrent l’intérieur du polyèdre des solution
réalisables,
- prendre comme solution optimale, tout sommet ayant la plus petite ordonnée sur la droite portée
et orientée par le vecteur gradient de la fonction-objectif. Ce sommet est tel que la ligne de niveau qui y
passe ne rencontre pas l’intérieur du polyèdre des solutions réalisables.
On rappelle que les lignes de niveau de la fonction-objectif Z, sont les droites d’équation : Z(x) = cte
avec cte ∈ R est une constante. Les lignes de niveau sont des droites perpendiculaires au vecteur gradient
de la fonction-objectif. Le vecteur gradient de la fonction-objectif est obtenu en considérant ses dérivées
partielles par rapport aux variables.
A titre d’exemples, résoudre graphiquement les programmes linéaires suivants :
1) 
min Z = 2x1 + 3x2 2) 
min Z = x1 + x2 min Z = 2x1 − 3x2
3) 

 x1 + x2 ≤ 4 
 2x1 + x2 ≥ 12  x1 − x2 ≥ 5

 
 6x1 + 2x2 ≥ 8
 5x1 + 8x2 ≥ 74 x2 ≥ 5
 
x1 + 5x2 ≥ 4 
 x + 6x2 ≥ 24 x1 , x2 ≥ 0
 1

 x1 ≤ 3 x1 , x 2 ≥ 0



 x ≤3
 2
x 1 , x2 ≥ 0
4) 
max Z = 3x1 + 2x2 5) 
max Z = 6x1 + 5x2 6) 
max Z = x1 + x2
 −2x1 + x2 ≤ 1
  x1 + x2 ≥ 8
  −2x1 + x2 ≤ 1

  
x1 + x2 ≤ 3 −2x1 + 3x2 ≤ 6 x1 + x2 ≤ 3

 x ≤2 
 x − x2 ≥ 2 
 x ≤2
 1  1  1
x 1 , x2 ≥ 0 x 1 , x2 ≥ 0 x1 , x 2 ≥ 0
Cette méthode est limitée car elle ne s’applique qu’à des programmes linéaires où le nombre de
variables est faible (au maximum 3 variables). Nous allons nous intéresser dans ce qui suit à une méthode
algébrique, la méthode du simplexe.

2.3 Méthode du simplexe

On considère le programme linéaire sous la forme standard : suivant.

Z ∗ = min Z = cx
{
Ax = b (P L)
x ∈ Rn , x ≥ 0

où A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R) avec rangA = m < n.
Notons C le polyèdre convexe des solutions réalisables de (P L).

2.3.1 Solution de base réalisable d’un programme linéaire

Etant donné le programme linéaire (P L), on a les définitions suivantes :

Définition 2.3.1 On appelle base de (P L), toute sous-matrice extraite de A, carrée d’ordre m et régulière.

9
Définition 2.3.2 Soit B une base de (P L), les variables associées aux colonnes de B sont appelées
variables de base associées à B, et les autres, variables hors base ou libres associées à B.

Remarque 2.3.1 Dans la pratique, on représente une base par son ensemble de variables de base ou
par son ensemble des indices des variables de base. Cela permet d’éviter certaines indéterminations. En
effet, si on considère un programme dont le système des vraies contraintes est :
{
x1 − x2 + x3 − x4 + x5 = 4
x1 + x2 + x3 + x4 + x5 = 1
on sait que ( )
1 −1
B=
1 1
est une base mais il est difficile de dire quelles sont les variables de base associées.

Remarque 2.3.2 La matrice A des vraies contraintes du programme linéaire (P L) étant dans Mm,n (R)
et de rang m, il possède au plus Cm
n bases.

Soit B une base de (P L). Notons N la sous-matrice de A constituée des colonnes des variables hors
base. Moyennant une permutation on peut supposer que les colonnes de B sont les m premières colonnes
de A. On peut donc supposer que A est sous la forme ( (matrices
) blocs) A = (B, N ). De même on peut
xB
décomposer le vecteur variable x sous la forme x = où xB est constitué des variables de base et
xN
xN des variables hors base. Le système Ax = b s’écrit alors :
BxB + N xN = b ⇐⇒ xB + B −1 N xN = B −1 b. (2.1)
On obtient : xB = B −1 b − B −1 N xN ). A chaque fois qu’on se donne xN , on obtient alors xB .

Définition 2.3.3 On appelle solution de base de (P L) associée (ou relative) à la base B, la solution
particulière x(B) du système
( Ax
) = b obtenue en fixant les variables hors base à zéro (en prenant xN = 0).
B b−1
On a donc : x(B) =
0

Exemple 2.3.1
Considérons le programme linéaire ci-dessous où c quelconque est une matrice ligne à 5 colonnes.
∗
 = min Z = 2x1 − 3x2
Z
 x1 − x2 + x3 = 5
(P L)
x2 + x4 = 5

xi ≥ 0, i = 1, · · · , 4
La matrice des vraies contraintes est :
( )
1 −1 1 0
A=
0 1 0 1
Il est immédiat que rangA = 2. Il y a cinq bases possibles (seul I = {1, 3} est exclu)
I1 = {1, 2}, I2 = {1, 4}, I3 = {2, 3}, I4 = {2, 4}, I5 = {3, 4}.
avec les solutions de base :
         
10 5 0 0 0
 5   0   5   −5   0 
x(I1 ) =   
 0  , x(I2 ) = 
 , x(I3 ) = 
 
 , x(I4 ) = 
 
 , x(I5 ) = 
 
.
0 10 0 5 
0 5 0 10 5

10
Définition 2.3.4 On dit qu’une base B de (P L) est une base réalisable, si la solution de base x(B)
associée à B, est telle que x(B) ≥ 0, c’est-à-dire B −1 b ≥ 0. Dans ce cas, x(B) est dite solution de base
réalisable de (P L).

Exemple 2.3.2 Dans l’exemple (2.3.1), les bases I1 , I2 , I3 et I5 sont réalisables.

Exemple 2.3.3
Considérons le programme linéaire suivant :

 Z = 2x1 − 9x2 + 4x3 + 10x4 − 3x5

min
 7x1 + 3x2 + 10x3 + 5x4 + 8x5 = 37
5x1 + 4x2 + 7x3 + 10x4 + 3x5 = 26

x ∈ R5 , x ≥ 0
I = {x1 , x3 } est une base réalisable. En effet, si on note B la matrice associée à I, on a :
( ) ( ) ( )
7 10 −1 −7 10 −1 1
B= , B = et B b = ≥ 0.
5 7 5 −7 3
La solution de base réalisable associée est x(B) = (1, 0, 3, 0, 0)T .

Définition 2.3.5 Une base réalisable B de (P L) est dite dégénérée si le vecteur xB = B −1 b contient au
moins une composante nulle.

Exemple 2.3.4
Considérons le programme linéaire suivant :

 Z = −3x1 − 2x2
min
 4x1 + 3x2 + x3 = 18


4x1 + x2 + x4 = 8

 4x1 − x2 + x5 = 8

x ∈ R5 , x ≥ 0
Soit I = {1, 3, 5}. La matrice associée à I est
 
4 1 0
B= 4 0 0 
4 0 1
On a det B = −4 ̸= 0 ; donc I est une base.
   
0 14 0 2
B −1 =  1 −1 0  et B −1 b =  10  ≥ 0.
0 −1 1 0
La base est alors réalisable ; mais le vecteur B −1 b a une composante nulle. Donc la base I est dégénérée.

Définition 2.3.6 Le programme linéaire (P L) est dit dégénéré s’il possède une base réalisable dégénérée.

Définition 2.3.7 On dit que deux bases B et B ′ sont adjacentes, si les colonnes qui les constituent ne
diffèrent que d’un seul élément.

Exemple 2.3.5 Dans l’exemple (2.3.1), les bases I1 et I2 sont adjacentes.

On montre que :
Proposition 2.3.1 Etant donné un programme linéaire sous forme standard, si l’ensemble des solutions
réalisables est non vide, il contient au moins une solution de base réalisable. En outre, si le programme
possède une solution optimale, alors il possède une solution de base réalisable optimale.

11
2.3.2 Forme canonique d’un programme linéaire par rapport à une base
On vient de voir que si (P L) possède un optimum fini, il existe au moins une base réalisable optimale.
C’est pour cela qu’on s’intéresse dans ce qui suit aux conditions d’optimalité des solutions de base
réalisables.
Soit B une base de (P L). On note I l’ensemble des indices des variables de base et J l’ensemble des
indices des variables hors base.
On peut supposer que B est formée des m premières colonnes de A et donc A est de la forme (matrices
blocs) A = (B, N ) où N est la sous-matrice
( ) formée par les colonnes de A qui ne sont pas dans B. De
xB
même on peut partitionner x = où xB est constitué des variables de base et xN des variables
xN
hors base.
Le système Ax = b est alors équivalent à

BxB + N xN = b ⇔ xB + B −1 N xN = B −1 b. (2.2)

On peut aussi partitionner c de la façon suivante : c = (cB , cN ) où cB est formé des coefficients des
variables de base et cN des coefficients des variables hors base. On a alors :

Z(x) = cx = cB xB + cN xN .

En remplaçant xB par sa valeur (xB = B −1 b − B −1 N xN ), on a :

Z(x) = cB B −1 b + (cN − cB B −1 N )xN . (2.3)

Posons
 = B −1 A, ĉ = c − cB B −1 A, Ẑ = cB B −1 b (2.4)

Donc ĉB = 0 et ĉN = cN − cB B −1 N .

On remarque qu’on a Z(x(B)) = cB B −1 b = Ẑ.

Définition 2.3.8 Le programme linéaire :

Z ∗ = min Z = ĉx + Ẑ
{
Âx = b̂
x ∈ Rn , x ≥ 0;

est appelé forme canonique (ou forme équivalente) de (P L) par rapport à la base B.
Les coefficients de ĉ relatifs aux variables hors base sont appelés couûts réduits.

Remarque 2.3.3 Ecrire un programme linéaire sous forme canonique par rapport à une base, c’est
écrire sa fonction-objectif ainsi que ses variables de base en fonction des seules variables hors base.

Exemple 2.3.6

La forme canonique du programme linéaire de l’exemple (2.3.3) par rapport à la base I = {x1 , x3 } est :

 Z = 14 + 5x2 + 60x4 − 27x5

min
 x1 + 19x2 + 65x4 − 26x5 = 1
x3 − 13x2 − 45x4 + 19x5 = 3

x≥0

12
2.3.3 Caractérisation des bases réalisables optimales
On peut à présent donner les conditions d’optimalité pour une solution de base réalisable.

Théorème 2.3.1 Une condition suffisante pour que B soit une base réalisable optimale est ĉ ≥ 0.

Preuve : Dans (P L) on a la contrainte xN ≥ 0. Donc pour toute solution réalisable x de (P L), on aura :

Z(x) = cB B −1 b + (cN − cB B −1 N )xN ≥ cB B −1 b = Z(x(B)).

Par suite x(B) est une solution optimale de (P L). 

Remarque 2.3.4 Pour un problème de maximisation la condition suffisante d’optimalité est ĉ ≤ 0.

Théorème 2.3.2 Soit k dans J tel que ĉk < 0. Si Âk , la colonne associée à la variable xk dans la
matrice  est telle que Âk ≤ 0, alors on peut diminuer indéfiniment la fonction objectif, ce qui signifie
que (z ∗ = −∞). On dit alors que l’optimum de (P L) est non borné ou que (P L) n’admet pas de solution
optimale à distance finie.

Preuve : Considérons dans le système Ax = b la solution x(α) obtenue en imposant aux variables hors
base les valeurs suivantes :
xj = 0 ∀ j ∈ J − k et xk = α.
On obtient alors
xi = b̂i − αâik ∀i ∈ I.
La solution x(α) est réalisable pour tout α ≥ 0.
On a : ∑
Z(x(α)) = Ẑ + ĉj xj = Ẑ + αĉk
j∈J

Comme ĉk < 0, on a Z(x(α)) qui tend vers −∞ pour λ tendant vers +∞. Donc Z ∗ = −∞. 

Exemple 2.3.7

Considérons le programme linéaire suivant :

 Z = −x1 − 2x2
min

 −2x1 + x2 + x3 = 2

−x1 + 2x2 + x4 = 5

 x − 4x2 + x5 = 4
 1
x ∈ R5 , x ≥ 0
Soit I = {1, 2, 5}. La matrice associée à I est :
 
−2 1 0
B =  −1 2 0 
1 −4 1

On a :
   
− 23 1
3 0 1
3
B −1 =  − 13 2
3 0 , B −1 b =  8
3
 ≥ 0.
− 23 7
3 1 43
3
Donc c’est une base réalisable. La forme canonique par rapport à cette base est :

13
  Z =2 − 3 −
17 4 5
min 3 x3 + 3 x4

 x1 − 3 x3 + 3 x4 = 3
1 1

x2 − 13 x3 + 23 x4 = 83

 x − 2 x + 7 x = 43
 5 3 3 3 4 3
x≥0
La colonne de la variable hors base x3 est négative dans cette forme. On remarque que
 1 2 
3 + 3α
 8 + 1α 
 3 3 
x(α) =   α 

 0 
43 2
3 + 3α

est réalisable quel que soit α ≥ 0 et Z(x(α)) = − 17

3 − 3 α qui tend vers −∞ quand α tend vers +∞. Le
4

problème est alors non borné.

Remarque 2.3.5 On a les mêmes résultats dans le cas des problèmes de maximisation si on remplace
la condition ĉk < 0 par ĉk > 0 dans le théorème (2.3.2).

Dans le théorème qui suit on montre que si pour tout k ∈ J tel que ĉk < 0, on a Âk  0 alors il existe
une base réalisable qui améliore la fonction-objectif Z.

Théorème 2.3.3 Soit B une base réalisable, on note I et J respectivement les ensembles des indices
des variables de base et hors base, b̂ = B −1 b, Â = B −1 A et ĉ = c − cB B −1 A. Soit k ∈ J tel que ĉk < 0 et
Âk  0. Soit l tel que [ ]
b̂l b̂i
= min : i ∈ I, âik > 0 .
âlk âik

Alors la matrice B ′ associée aux variables dont les indices sont dans I ′ = I − l + k est une base réalisable
adjacente à B. Et on a
b̂l
Z(x(B ′ )) = Z(x(B)) + ĉk .
âlk

Remarque 2.3.6 Si la base B est non dégénérée, on a : Z(x(B ′ )) < Z(x(B)). c’est-à-dire que la
décroissance est stricte.

Dans le cas de non dégénérescence, la condition suffisante vue dans lethéorème (2.3.1) ci-dessus est
aussi nécessaire.

Théorème 2.3.4 Si le problème (P L) est non dégénéré i.e. ne possède pas de base réalisable dégénérée,
une condition nécessaire et suffisante pour que B soit optimale est ĉ ≥ 0.

2.3.4 Algorithme primal du simplexe

L’algorithme primal du simplexe contient deux phases : la phase 1 et la phase 2.
Phase 1
Dans cette phase on détermine une première solution de base réalisable du problème. Si cette procédure
échoue, cela signifie que le polyèdre des solutions réalisables D du problème est vide.
Phase 2

14
 Dans cette partie, on calcule à partir de la solution réalisable obtnue dans la phase 1 une autre solution
de base réalisable donnant une meilleure valeur de la fonction-objectif. Géométriquement, une itération
consiste à passer d’un sommet de D à un sommet de D ; ce nouveau sommet est adjacent au premier en
ce sens qu’ils sont les extrémités d’une arête de D.
Nous donnons ici une itération de la phase 2 de l’algorithme du simplexe.
Phase 2 de l’algorithme du simplexe
Dans une itération de la phase 2 de l’algorithme du simplexe appliqué au problème (P L) on procède
comme suit.
Début
On suppose qu’on dispose d’une base réalisable de depart B. Soit I et J respectivement les ensembles
des indices des variables de base et hors base.
1) Calculer b̂ = B −1 b, Â = B −1 A et ĉ = c − cB B −1 A.
2) Tester ĉ.
a) Si ĉ ≥ 0, stop : ”La base B est optimale.”
b) S’il existe k ∈ J tel que ĉk < 0 avec Âk ≤ 0, stop : ”Le problème est non bornée i.e. la valeur
optimale est infinie.”
c) Autrement effectuer un changement de base.
3) Changement de base
a) Test d’entrée : Soit k ∈ J tel que

ĉk = min [ĉj : j ∈ J, ĉj < 0] .

La variable correspondante xk rentre dans la base on l’appelle variable rentrante.

b) Test de sortie : Soit l tel que
[ ]
b̂l b̂i
= min : i ∈ I, âik > 0 .
âlk âik

La variable xl sort de la base on l’appelle variable sortante.

c) On considère la nouvelle base réalisable encore notée B dont les ensembles des indices de variables
de base et hors base sont respectivement

I := I − l + k et J := J − k + l

Aller à 1).
Fin

Remarque 2.3.7 Dans le cas d’un problème de maximisation, il n’est pas nécessaire de transformer le
problème en un problème de minimisation afin d’appliquer l’algorithme du simplexe. Il suffit de considérer
les modifications suivantes :
2 − a) Si ĉ ≤ 0 stop : ”la base B est optimale.”
2 − b) S’il existe k ∈ J tel que ĉk > 0 avec Âk ≤ 0 stop : ”le problème est non bornée i.e. la valeur
optimale est infinie.”
3 − a) Test d’entrée : Soit k ∈ J tel que

ĉk = max [ĉj : j ∈ J, ĉj > 0] .

La variable correspondante xk rentre dans la base.

Les autres instructions restent valables.

15
2.3.5 Convergence de l’algorithme du simplexe
On a le résultat suivant

Théorème 2.3.5 Si à chaque base réalisable rencontrée dans résolution du problème (P L) la solution
de base associée est non dégénérée, l’algorithme se termine en un nombre fini d’itérations par l’une des
deux situations suivantes :
i) obtention d’une solution de base réalisable optimale de (P L)
ii) absence de solution optimale à distance finie.

Ce théorème montre la convergence de l’algorithme du simplexe en l’absence de dégénérescence.

On montre que

Proposition 2.3.2 Si à une itération de l’algorithme du simplexe l’ensemble

{ [ ]}
b̂l b̂i
L= l: = min : i ∈ I, âik > 0
âlk âik

contient plus d’un élément, alors le problème (P L) est dégénéré i.e. il existe une base dégénérée.

2.3.6 Méthode des tableaux

C’est une mise en œuvre manuelle de l’algorithme du simplexe.
Soit à résoudre le programme linéaire (P L)

Z ∗ = min Z = cx
{
Ax = b
x ∈ Rn , x ≥ 0

toujours avec A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R) et rangA = m < n.
On suppose qu’on dispose d’une base réalisable de départ B Les ensembles des indices des variables
de base et hors-base sont I et J.
La forme canonique de (P L) par rapport à B est :

b
Z ∗ = min Z = ĉx + Z
{
Âx = b̂
x ∈ Rn , x ≥ 0

On sait que  = (Im , B −1 N ), ĉ = (0, cN − cB B −1 N ), b̂ = B −1 b.

On définit :

Définition 2.3.9 On appelle tableau simplexe complet de (P L) par rapport à la base réalisable B, le
tableau à m + 1 lignes et n + 1 colonnes ci-dessous :
xi i ∈ I xj j ∈ J

xi
 b̂
i∈I

ĉ −Ẑ

Définition 2.3.10 On appelle tableau simplexe de (P L) par rapport à la base réalisable B, le tableau à
m + 1 lignes et n − m + 1 colonnes ci-dessous

16
 xj j ∈ J

xi
ÂN = B −1 N b̂
i∈I

ĉN −Ẑ

A partir du tableau simplexe on peut écrire la forme canonique de (P L) par rapport à la base B et
inversement.
On définit :

Définition 2.3.11 Dans le tableau simplexe, on appelle pivot l’élément qui est à l’intersection de la
colonne de la variable rentrante et de la ligne de la variable sortante.
Dans ce cas la ligne correspondante est dite ligne du pivot et la colonne, colonne du pivot.

La méthode des tableaux consiste à écrire les tableaux simplexes relatifs aux différentes bases ren-
contrées dans la résolution du programme (P L) à l’aide de l’algorithme du simplexe. Il faut donc
déterminer pour deux bases successives dans l’algorithme du simplexe B et B ′ comment passer du tableau
simplexe relatif à B à celui relatif à B ′ .
Pour obtenir le tableau simplexe de (P L) relatif à B ′ à partir de celui relatif à B on utilise le cadre
du tableau simplexe relatif à B et on considère les règles suivantes.
1) Permuter les variables sortante et rentrante ;
2) Remplacer le pivot par son inverse ;
3) Diviser les autres éléments de la ligne du pivot par le pivot ;
4) Diviser les autres éléments de la colonne du pivot par le pivot ; et changer de signe ;
5) Pour les autres éléments du tableau, appliquer la règle du rectangle suivante :
Règle du rectangle
Soit l ∈ I la ligne du pivot et k ∈ J la colonne du pivot.
âik âlj
Pour i ∈ I − l et j ∈ J − k, l’élément âij est remplacé par âij − âlk .
On note alors
âik âlj
âij := âij −
âlk

Cette règle s’applique à tous les éléments du tableau.

Remarque 2.3.8 Si une ligne intersecte la colonne du pivot par un zéro, la ligne reste inchangée.
Si une colonne intersecte la ligne du pivot par un zéro, la colonne reste inchangée.

Dans la méthode des tableaux une base sera désignée indifféremment par la matrice elle-même ou par
l’ensembles des indices des variables de base associées.

Exemple 2.3.8

 Z = −3x1 + 2x2
min

 2x1 + x2 ≤ 5

x1 − x2 ≤ 1

 x + 2x2 ≤ 3
 1
x 1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :

17
  Z = −3x1 + 2x2
min

 2x1 + x2 + x3 = 5

x1 − x2 + x4 = 1

 x + 2x2 + x5 = 3
 1
xi ≥ 0, i = 1, · · · , 5
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En outre le programme est déjà
sous forme canonique par rapport à cette base. Les tableaux simplexes sont les suivants. :
x1 x2 x4 x2
x3 2 1 5 x3 -2 3 3
x4 1 -1 1 ← x1 1 -1 1
TS1 TS2
x5 1 2 3 x5 -1 3 2 ←
-3 2 0 3 -1 3
↑ ↑
x4 x5
x3 -1 -1 1
x1 2/3 1/3 5/3
TS3
x2 -1/3 1/3 2/3
8/3 1/3 11/3

On est à l’optimum car la condition d’arrêt de l’algorithme est vérifiée.

Une solution optimale du problème initial est x∗ = ( 53 , 32 )T et la valeur optimale est Z ∗ = − 11
3 .

Exemple 2.3.9

max
 Z = 6x1 + 5x2

 x1 + x2 ≤ 8

−2x1 + 3x2 ≤ 6

 x − x2 ≤ 2
 1
x1 , x 2 ≥ 0
On écrit le programme sous forme standard. On obtient :

max
 Z = 6x1 + 5x2

 x1 + x2 + x3 = 8

−2x1 + 3x2 + x4 = 6
 x1 − x2 + x5 = 2


xi ≥ 0, i = 1, · · · , 5
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En outre le programme est déjà
sous forme canonique par rapport à cette base. Les tableaux simplexes sont les suivants.
x1 x2 x5 x2
x3 1 1 8 x3 -1 2 6 ←
x4 -2 3 6 x4 2 1 10
TS1 TS2
x5 1 -1 2 ← x1 1 -1 2
6 5 0 -6 11 -12
↑ ↑
x5 x3
x2 -1/2 1/2 3
x4 5/2 -1/2 7
TS3
x1 1/2 1/2 5
-1/2 -11/2 -45

18
 Tous les coefficients de la fonction-objectif sont négatifs ou nuls on est donc à l’optimum. Une solution
optimale du problème initial est x∗ = (5, 3)T et la valeur optimale est Z ∗ = 45.

Exemple 2.3.10

 Z = −3x1 + 5x2
min
 −2x1 + 3x2 ≤ 6
x1 − 4x2 ≤ 4

x 1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :

 Z = −3x1 + 5x2
min
 −2x1 + 3x2 + x3 = 6
x1 − 4x2 + x4 = 4

xi ≥ 0, i = 1, · · · , 4
On remarque que I = {x3 , x4 } est une base réalisable évidente. En outre le programme est déjà sous
forme canonique par rapport à cette base. Les tableaux simplexes sont les suivants.
x1 x2 x4 x2
x3 -2 3 6 x3 2 -5 14
TS1 x4 1 -4 4 ← TS2 x1 1 -4 4
-3 5 0 3 -7 12
↑ ↑
On remarque que la colonne de la variable x2 est toute négative, il n y a donc pas de pivot. Le
programme linéaire est alors non borné ; c’est-à-dire que la valeur optimale est −∞.

Exemple 2.3.11 (Problème dégénéré)

max
 Z = 3x1 + 2x2

 4x1 + 3x2 ≤ 12

4x1 + x2 ≤ 8
 4x1 − x2 ≤ 8


x1 , x2 ≥ 0
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En outre le programme est déjà
sous forme canonique par rapport à cette base.
x1 x2 x4 x2
x3 4 3 12 x3 -1 2 4 ←
x4 4 1 8 ← x1 1/4 1/4 2
TS1 TS2
x5 4 -1 8 x5 -1 0 0
3 2 0 -3/4 5/4 -6
↑ ↑
x4 x3
x2 -1/2 1/2 2
x1 3/8 -1/8 3/2
TS3
x5 -2 1 4
-1/8 -5/8 -17/2

On est à l’optimum. Une solution optimale du problème initial est x∗ = ( 32 , 2)T et la valeur optimale
est Z ∗ = 17
2 .

19
2.3.7 Méthode du grand M
Pour résoudre le programme linéaire (P L) par la méthode du grand M , on considère l’hypothèse que
b ≥ 0 et on procède comme suit.
On considère le problème auxiliaire suivant.
∗ = min Z
∑m a
ZM
{ M = cx + M i=1 xi
a
Ax + Im x = b (PM )
x ≥ 0, xa ≥ 0

Comme dans la phase 1, les variables xai , i ∈ {1, · · · , m} sont des variables artificielles.
La constante M est une constante symbolique et elle est aussi grande que l’on veut (c’est-à-dire
supérieure à tout nombre auquel elle pourra être comparée lors de la résolution du problème).
On remarque comme précédemment dans la phase 1 que la matrice des vraies contraintes de (PM )
est Ā = (A, Im ). Donc, rangĀ = m < n + m. Par suite avec l’hypothèse que b ≥ 0, la matrice formée des
colonnes des variables artificielles est une base réalisable évidente pour (PM ). On peut donc le résoudre
à l’aide de la phase 2 du simplexe en partant de cette base.
On montre que

1) Si ZM∗ = −∞, il en est de même pour Z ∗ .

2) Si (PM ) possède une solution optimale, on a les cas suivants :

a) Si dans cette solution il reste encore des variables artificielles non nulles dans la base (elles sont
donc de base) alors le problème initial (P L) est impossible c’est-à-dire qu’il ne possède pas de solutions
réalisables.
b) Si dans cette solution toutes les variables artificielles sont nulles, la partie formée des variables
structurelles est une solution de base réalisable optimale de (P L).

Remarque 2.3.9 Pour un problème de maximisation, la fonction-objectif de (PM ) est ZM = cx −

∑
M m a
i=1 xi .

Comme dans la phase 1, on a les remarques suivantes :

Remarque 2.3.10 1) Etant donné que dans le programme auxiliaire l’introduction des variables artifi-
cielles sert à créer uniquement une base réalisable évidente, il n’est pas nécessaire d’en ajouter systématiqueme
à chaque équation. En effet, si une variable n’intervient que dans une seule équation et si le signe de
son coefficient est égal à celui du second membre de cette équation il n’est pas nécessaire d’ajouter une
variable artificielle à cette équation. Cette variable peut être considérée comme variable de base associée
associée à cette équation.
2) Dans la méthode des tableaux lorsqu’une variable artificielle sort de la base il est certain qu’elle ne
peut plus y revenir la colonne correspondante devient superflue et peut être supprimée.

Exemple 2.3.12

1) min Z = 8x1 + 7x2 + 3x3

 2x1 + x2 ≥ 1
x1 + 2x2 + x3 ≥ 1

xi ≥ 0, i = 1, · · · , 3
La forme standard de ce problème est
min
 Z = 8x1 + 7x2 + 3x3
 2x1 + x2 − x4 = 1
x1 + 2x2 + x3 − x5 = 1

xi ≥ 0, i = 1, · · · , 5

20
 On n’a pas de base réalisable évidente. Utilisons la méthode du grand M .
Considérons le programme auxiliaire :
min ZM = 8x1 + 7x2 + 3x3 + M x6

 2x1 + x2 − x4 + x6 = 1
x1 + 2x2 + x3 − x5 = 1

xi ≥ 0, i = 1, · · · , 5
I = {x6 , x3 } est une base réalisable évidente de ce problème.
La forme canonique par rapport à cette base est :

 ZM = (5 − 2M )x1 + (1 − M )x2 + M x4 + 3x5 + M + 3

min
 2x1 + x2 − x4 + x6 = 1
x1 + 2x2 + x3 − x5 = 1

xi ≥ 0, i = 1, · · · , 5
On a les tableaux simplexes suivants :
x1 x2 x4 x5
x6 2 ∗ 1 -1 0 1 ←
TS1 x3 1 2 0 -1 1
5-2M 1-M M 3 -3-M
↑
x6 x2 x4 x5
..
x1 . 1/2 -1/2 0 1/2
TS2 ..
x3 . 3/2 1/2 -1 1/2 ←
..
. -3/2 5/2 3 -11/2
↑

x3 x4 x5
x1 -1/3 -2/3 1/3 1/3
TS3 x2 2/3 1/3 -2/3 1/3
1 3 2 -5

On est à l’optimum pour PM et une solution optimale du problème initial est x∗ = ( 31 , 1

3, 0)T et la
valeur optimale est Z ∗ = 5.
2) min Z = x1 + x2 + x3


 x1 + 2x2 + 3x3 = 3


 −x1 + 2x2 + 6x3 = 2
4x2 + 9x3 = 5



 3x3 + x4 = 1

xi ≥ 0, i = 1, · · · , 4
On n’a pas de base réalisable évidente. On va utiliser la méthode du grand M .
Considérons le programme auxiliaire
min
 ZM = x1 + x2 + x3 + M (x5 + x6 + x7 )

 x1 + 2x2 + 3x3 + x5 = 3


 −x1 + 2x2 + 6x3 + x6 = 2
4x2 + 9x3 + x7 = 5



 3x 3 + x4 = 1

xi ≥ 0, i = 1, · · · , 7

21
 I = {x5 , x6 , x7 , x4 } est une base réalisable évidente pour ce problème. Déterminons la forme
canonique par rapport à cette base. Les variables de base sont déjà exprimées en fonction des variables
hors base. Il reste à exprimer la fonction-objectif en fonction des variables hors base.
On a : ZM = −10M + x1 + (1 − 8M )x2 + (1 − 18M )x3
Donc la forme canonique du programme par rapport à la base I est :

 ZM = −10M + x1 + (1 − 8M )x2 + (1 − 18M )x3

min

 x1 + 2x2 + 3x3 + x5 = 3


 −x1 + 2x2 + 6x3 + x6 = 2
4x2 + 9x3 + x7 = 5



 3x 3 + x4 = 1

xi ≥ 0, i = 1, · · · , 7
On a les tableaux simplexes suivants.
x1 x2 x3
x5 1 2 3 3
x6 -1 2 6 2
TS1 x7 0 4 9 5
x4 0 0 3∗ 1 ←
1 1-8M 1-18M -10M
↑

x1 x2 x4
x5 1 2 -1 2
x6 -1 2∗ -2 0 ←
TS2 x7 0 1 -3 2
x3 0 0 1/3 1/3
1 1-8M -1/3+6M -1/3-4M
↑

x1 x6 x4
..
x5 2 . 1 2 ←
..
x2 -1/2 . -1 0
TS3 ..
x7 2 . 1 2
..
x3 0 . 1/3 1/3
..
3/2-4M . 2/3-2M -1/3-4M
↑

x5 x4
.. x3
x1 . 1/2 1
.. x1 -3/2 1/2
x2 . -3/4 1/2 x2 9/4 5/4
TS4 .. TS5 x7 0 0
x7 . 0 0
.. x4 3 1
x3 . 1/3 1/3 ← 1/4 -7/4
..
. -1/12 -11/6
↑

On est à l’optimum pour PM et une solution optimale du problème initial est x∗ = ( 12 , 5

4, 0, 1)T et
la valeur optimale est Z ∗ = 47 .

22
 3) min Z = x1 − x2

 −2x1 + x2 ≤ 2

−x1 + 2x2 ≥ 8

 x + x2 ≤ 5
 1
xi ≥ 0, i = 1, · · · , 2
La forme standard de ce problème est

 Z = x1 − x2
min

 −2x1 + x2 + x3 = 2

−x1 + 2x2 + x3 − x4 = 8

 x + x2 + x5 = 5
 1
xi ≥ 0, i = 1, · · · , 5
On n’a pas de base réalisable évidente. Utilisons la méthode du grand M .
Considérons le programme auxiliaire :
min ZM = x1 − x2 + M x6


 −2x1 + x2 + x3 = 2

−x1 + 2x2 + x3 − x4 + x6 = 8

 x + x2 + x5 = 5
 1
xi ≥ 0, i = 1, · · · , 6
I = {x3 , x6 , x5 } est une base réalisable évidente de ce problème.
La forme canonique par rapport à cette base est :

 ZM = (1 + M )x1 + (−1 − 2M )x2 + M x4 + 8M

min

 −2x1 + x2 + x3 = 2

−x1 + 2x2 + x3 − x4 + x6 = 8
 x1 + x2 + x5 = 5


xi ≥ 0, i = 1, · · · , 6
On a les tableaux simplexes suivants :
x1 x2 x4
x3 −2 1 0 2 ←
x6 -1 2 -1 8
TS1
x5 1 1 0 5
1+M -1-2M M -8M
↑

x1 x3 x4
x2 −2 1 0 2
x6 3 -2 -1 4
TS2
x5 3 -1 0 3 ←
-1-3M 1+2M M 2-4M
↑

x5 x3 x4
x2 2/3 5/3 0 4
x6 -1 -3 -1 1
TS3
x1 1/3 -1/3 0 1
1/3+M 2/3+M M 3-M

On est à l’optimum pour PM ; mais il existe une variable artificielle non nulle à l’optimum. Alors le
problème initial est impossible.

23
Chapitre 3

Dualité en programmation linéaire

Etant donné un programme linéaire on peut toujours lui associer un autre programme linéaire appelé
programme dual du programme initial : dans ce cas le programme initial est appelé programme primal.
Ces deux programmes sont dits alors programmes duaux, ou duals, ou en dualité.

3.1 Définitions
On sait que par convention les contraintes d’inégalité pour un problème de minimisation sont du type
” ≥ ” et les contraintes d’inégalité pour un problème de maximisation sont du type ” ≤ ”.

Définition 3.1.1 Etant donné le programme linéaire sous la forme canonique (P ) ci-dessous
∑n
min
{ ∑Z(x) = j=1 cj xj
n
j=1 aij xj ≥ bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n
On appelle programme dual de (P ) le programme linéaire (D) ci-dessous
∑
m
max W = bi yi
 m i=1
 ∑ a y ≤ c j = 1, ..., n (D)
ij i j
i=1

yi ≥ 0 i = 1, ..., m

Cette définition est caractérisée par les règles suivantes :

1) A un problème primal de minimisation (de maximisation) correspond un problème dual de maxi-
misation (minimisation) ;
2) A toute vraie contrainte primale i correspond une variable duale yi ≥ 0 ;
3) A toute variable primale xj correspond une contrainte duale ;
4) Les coefficients de la fonction-objectif du primal deviennent les seconds membres des contraintes
duales. Les seconds membres des vraies contraintes primales deviennent les coefficients de la fonction-
objectif du dual ;
5) La matrice des vraies contraintes du dual est la transposée de la matrice des vraies contraintes du
primal.

Exemple 3.1.1

1) Soit à déterminer le dual du programme linéaire ci-dessous.

24
 min
 Z = 3x1 + 2x2 + x3

 2x1 + 5x2 + x3 ≥ 5

x1 − 3x2 − x3 ≥ 1

 4x1 + 2x2 + 6x3 ≥ 3

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
On considère les variables duales : y1 associée à la première contrainte, y2 à la deuxième et y3 à la
troisième. Le dual est alors :

max
 W = 5y1 + y2 + y3

 2y1 + 4y2 + y3 ≤ 3

5y1 − 3y2 + 2y3 ≤ 2

 y − y2 + 6y3 ≤ 1
 1
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

2) Soit à déterminer le dual du programme linéaire ci-dessous.

 Z = 8x1 − 4x2 + 2x3

max

 3x1 + 5x2 + 2x3 ≤ 4

x1 − 2x2 + 6x3 ≤ −7

 4x1 + 3x2 + x3 ≤ 3

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
On considère les variables duales : y1 associée à la première contrainte, y2 à la deuxième et y3 à la
troisième. Le dual est alors :

 W = 4y1 − 7y2 + 3y3

min

 5y1 + y2 + 4y3 ≥ 8

5y1 − 2y2 + 3y3 ≥ −4

 2y + 6y2 + y3 ≥ 2
 1
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.
On a la propriété suivante :

Proposition 3.1.1 L’opération de la dualité est involutive (i.e le dual du dual est le primal).

3.2 Propriétés de la dualité

Considérons le programme linéaire :
Z ∗ ={min Z = cx
Ax ≥ b (P )
x≥0

(où A ∈ Mm,n (R), c ∈ M1,n (R), b ∈ Mm,1 (R)) et son dual :

W∗ =
{ max W = bT u
AT u ≤ cT (D)
u≥0

Afin de gérer les mêmes données que dans le programme primal (car les deux programmes, primal et
dual sont deux aspects d’un même problème), on va considérer la notation matricielle suivante :

W∗ =
{ max W = yb
yA ≤ c (D)
y≥0

25
 Dans ce programme la variable y est une matrice ligne contrairement à la variable primale qui, elle,
est une matrice colonne.
On donne à présent quelques proipriétés de la dualité.

Proposition 3.2.1 (Propriété de la dualité faible)

Si x et y sont respectivement des solutions réalisables de (P ) et (D) alors on a : cx ≥ yb

Corollaire 3.2.1 On a : Z ∗ ≥ yb pour tout y : solution réalisable de (D).

W ∗ ≤ cx pour tout ∀x solution réalisable de (P ).

Corollaire 3.2.2 Si Z ∗ = −∞, le problème (D) n’admet pas de solution réalisable (i.e le dual (D) est
impossible si (P ) est non borné).
De même si W ∗ = +∞, le problème primal n’admet pas de solution réalisable, en d’autres termes, si le
dual (D) est non borné, le primal (P ) est impossible.

Corollaire 3.2.3 Si x∗ et y ∗ sont respectivement solution réalisable (P ) et (D) vérifiant cx∗ = y ∗ b,

alors, x∗ et y ∗ sont des solutions optimales de (P ) et (D) respectivement.
Preuve : Si x∗ n’est pas solution optimale de (P ) i.e ∃x solution réalisable de (P ) avec cx < cx∗ (car
problème de minimisation)
cx < cx∗ = y ∗ b, absurde !
On montre de même pour l’autre cas. 

Proposition 3.2.2 (Propriété de la dualité forte)

Si (P ) (respectivement (D)) possède une solution optimale finie alors il en de même pour (D) (respecti-
vement (P )) et de plus Z ∗ = W ∗
En d’autres termes étant donné deux problèmes en dualité si l’un possède une solution optimale finie,
alors il en est de même pour l’autre et de plus les valeurs optimales sont égales.

On a les corollaires suivants :

Corollaire 3.2.4 Soit x∗ et y ∗ respectivement des solutions réalisables de (P ) et (D).

{
∗ ∗ x∗ est solution optimale de(P )
cx = y b ⇐⇒
y ∗ est solution optimale de(D).
Corollaire 3.2.5 Etant donné une paire de problèmes en dualité, il n’existe que 4 situations possibles
parmi les 9 potentielles.
1) Les deux problèmes possèdent des solutions optimales finies
2) a) Le problème primal non borné, et le problème dual est impossible
b) le problème dual est non borné et le problème primal est impossible
3) Les deux problèmes sont impossibles.
On peut schématiser cela dans le tableau suivant
Solution optimale Problème Problème
Primal/ dual
finie non borné impossible
Solution optimale
1) non non
finie
Problème
non non 2) a)
non borné
Problème
non 2) b) 3)
impossible

26
 A partir du tableau optimal du primal, on peut déterminer une solution optimale du dual. A cet effet
on considère la correspondance suivante.
Etant donné deux programme en dualité sous forme canonique (P ) et (D), on a la correspondance
suivnate à l’optimum.
A la première variable d’écart du primal correspond la première variable structurelle du dual.
A la première variable structurelle du primal correspond la première variable d’écart du dual.
Cette correspondance permet de déterminer une solution optimale du dual à partir du tableau optimal
du primal pour deux programmes en dualité sous forme canonique. On procède de la façon suivante :
- les variables duales correspodant aux variables primales en base sont nulles ;
- les autres variables duales prennent les valeurs absolues des coûts réduits de leur correspondants
primales hors base.

3.3 Algorithme dual Simplexe

On considère le programme linéaire :

Z ∗ ={min Z = cx
Ax = b (P L)
x≥0

A ∈ Mm,n (R) ; c ∈ M1,n (R) et b ∈ Mm,1 (R)

On suppose que rg(A) = m < n.

On a la définition suivante :

c = c − cB B −1 A ≥ 0.
Définition 3.3.1 Soit B une base de (P L). Cette base est dite duale réalisable si b
Par opposition, B est primale réalisable si bb = B −1 b ≥ 0.

Remarque 3.3.1 1) Pour un problème de maximisation une base B est dite duale réalisable si b
c =
c − cB B A ≤ 0. Elle est primale réalisable si bb = B b ≥ 0.
−1 −1

2) Une base B qui est à la fois primale et duale réalisable est optimale.

L’algorithme dual simplexe contient deux phases :

Phase 1 : Procédure d’initialisation
On détermine une première base duale réalisable. Si cette procédure échoue, cela signifie qu’une telle
base n’existe pas. C’est-à-dire que le polyèdre de la solution réalisable du dual est, vide, et donc (P.L)
est impossible soit non borné Z ∗ = −∞.
Phase 2 : Procédure itérative
1) On considère B une base, on note I (resp. J) l’ensemble des indices des variables de base (resp.
hors-base). On écrit le programme linéaire sous forme canonique par rapport à B. On dispose donc
b = B −1 A, b
A c = c − cB B −1 A et bb = B −1 b.
On suppose que B est dual réalisable.
2) Tester bb = B −1 b.
a) Si bb ≥ 0, stop : (la solution courante est optimale).
b) Si ∃i ∈ I tel que bbi < 0 et baij ≥ 0 ∀j ∈ J, stop : (le problème (P L) est impossible).
c) Autrement, on effectue un changement de base.
3) Changement de base
a) Test de sortie : Soit l ∈ I telle que
bbl = min[bbi : i ∈ I, bbi < 0].
i

La variable correspondante xl sort de la base.

27
 b) Test d’entrée : Soit k ∈ J telle que
[ ]
ĉk ĉj
= min : j ∈ J, âlj < 0 .
âlk âlj

La variable xk rentre dans la base.

c) On pose I := I − l + k et J := J − k + l ; aller à 1).

Remarque 3.3.2 Dans le cas d’un problème de maximisation cet algorithme reste valable

Exemple 3.3.1

min
 Z = 8x1 + 6x2 + 2x3
 x1 − 2x2 + x3 ≥ 6
x1 + 3x2 − x3 ≥ 5

x1 , x2 , x3 ≥ 0.
La forme standard de (P1 ) est :

min
 Z = 8x1 + 6x2 + 2x3
 x1 − 2x2 + x3 − x4 = 6
x1 + 3x2 − x3 − x5 = 5

xi ≥ 0, i = 1, · · · , 5.

L’ensemble I = {4, 5} est une base évidente. La forme canonique par rapport à I est :

min
 Z = 8x1 + 6x2 + 2x3
 −x1 + 2x2 − x3 + x4 = −6
−x1 − 3x2 + x3 + x5 = −5

xi ≥ 0, i = 1, · · · , 5.

On a ĉ ≥ 0 donc I est une base duale réalisable.

On a les tableaux simplexes successifs suivants.
x1 x2 x3 x1 x2 x4
x4 -1 2 -1 -6 ← x3 1 -2 -1 6
TS1 x5 -1 -3 1 -5 TS2 x5 -2 -1 1 -11 ←
8 6 2 0 6 10 2 -12
↑ ↑
x5 x2 x4
x3 1/2 -5/2 -1/2 1/2
TS3
x1 -1/2 1/2 -1/2 11/2
3 7 5 -45

La condition d’arrêt de l’algorithme est vérifiée une solution optimale du problème est x∗ = ( 11 1 T
2 , 0, 2 )
∗
et la valeur optimale est Z = 45.

Exemple 3.3.2

 Z = −5x1 − 21x3
max
 x1 − x2 + 6x3 ≥ 2
x1 + x2 + 2x3 ≥ 1

x1 , x2 , x3 ≥ 0.

28
 La forme standard est :
 Z = −5x1 − 21x3
max
 x1 − x2 + 6x3 − x4 = 2
x1 + x2 + 2x3 − x5 = 1

xi ≥ 0, i = 1, · · · , 5.
L’ensemble I = {4, 5} est une base évidente. La forme canonique par rapport à I est :

 Z = −5x1 − 21x3
max
 −x1 + x2 − 6x3 + x4 = −2
−x1 − x2 − 2x3 + x5 = −1

xi ≥ 0, i = 1, · · · , 5.

On a ĉ ≤ 0 donc I est une base duale réalisable.

On a les tableaux simplexes successifs suivants.
x1 x2 x3 x1 x2 x4
x4 -1 1 -6 -2 ← x3 1/6 -1/6 -1/6 1/3
TS1 x5 -1 -1 -2 -1 TS2 x5 -2/3 -4/3 -1/3 -1/3 ←
-5 0 -21 0 -3/2 -21/6 -21/6 7
↑ ↑
x5 x2 x4
x3 1/2 -1/2 -1/4 1/4
TS3
x1 -3/2 2 1/2 1/2
-9/4 -1/2 -11/4 31/4

La condition d’arrêt de l’algorithme est vérifiée une solution optimale du problème est x∗ = ( 12 , 0, 14 )T
et la valeur optimale est Z ∗ = − 314 .

29
Bibliographie

[1] Bazaraa, Mokhtar S. and Shetty, C. M., 1979. Nonlinear Programming Theory and Algorithms,
John Wiley and Sons.
[2] Bazaraa, Mokhtar S. and Shetty, C. M., 1976. Foundations of Optimization, Lecture Notes in
Economic and Mathematical Systems, No 122, Springer-Verlag New-York.
[3] Bergounioux Maı̈tine, 2001. Optimisation et Contrôle des systèmes linéaires, Donod.
[4] Bertsimas, Dimitris and Tsitsiklis John N. 1997. Introduction to Linear Optmization, Athena
Scientific.
[5] Culioli, Jean-Christophe, 1994. Introduction à l’optimisation, Ellipses.
[6] Christelle Guéret, Christian Prins, Marc Sevaux, 2000. Programmation linéaire, Eyrolles.
[7] F. Droesbeke, M. Hallin, CL. Lefevre, 1986. Programmation linéaire par l’exemple, Ellipses.
[8] Hiriart-Urruty, Jean-Baptiste, 1998. Optimisation et Analyse Convexe, Presse Universitaire de
France.
[9] Hiriart-Urruty, Jean-Baptiste and Lemaréchal, Claude, 1993. Convex Analysis and Minimization
algorithms, Vol I et II Grundlehren der mathematichen Wissenschaften 305 and 306, Springer-
Verlag.
[10] Hiriart-Urruty, Jean-Baptiste, 1996. L’Optimisation, in collection ”Que sais-je ?”, Presse Universi-
taire de France.
[11] Michel Minoux, 1983. Programmation mathématique : Théorie et Algorithmes, Vol I, Dunod.
[12] Rockafellar, R. Tyrrel, 1970. Convex Analysis, Princeton University Press, Princeton N. J..
[13] Roseaux, 1985. T.3. Programmation linéaire et extensions ; problèmes classiques, Masson
[14] Michel Sakarovitch, 1984. Optimisation Combinatoire Graphes et Programmation linéaire, Hermann
[15] Jacques Teghem, 1996. Programmation linéaire, Editions Ellipses

30