Optimisation :

Programmation Linéaire et non Linéaire

Dans ce document nous présentons une méthode de résolution pour les

programmes linéaire de facon très détaille et essayons de comprendre

son fonctionnement et son apui théorique.

La résolution des problèmes non linéaire est beaucoup plus compli-

quées, nous donnons un apercu assez succint.

Le plus important pour nous est beaucoup plus la methodologie et

l'approche de résolution que la résolution proprement dite

Abdelkader BELAHCENE

[email protected]

12 mars 2017
Table des matières
1 Programmation Linéaire 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Méthodes de Résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 La Méthode du Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Recherche d'une Solution de Base Réalisable . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Concepts Avancés de la PL 17
2.1 Modèles Particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 La Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Analyse Post Optimale et Sensitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Programmation non Linéaire sans Contrainte 34

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Fonction à une seule variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Optimisation de fonction à plusieurs variables . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Série d'exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1 Programmation Linéaire
1.1 Introduction

L'objectif principal de ce chapitre est d'initier le lecteur à la reconnaissance, la formulation et la

résolution d'une classe de problèmes en recherche opérationnelle dit de programmation linéaire. Ce
chapitre sera illustré par un exemple pédagogique que l'on désignera par P.L 1 (cf. Exemple 1.1.1). Il
est fortement recommandé au lecteur d'utiliser la méthodologie exposée au chapitre 1 pour formuler
et modéliser ce problème.
Exemple 1.1.1. Une usine fabrique deux produits P1 et P2 M1 M2 M3
sur 3 machines M1 , M2 et M3 . Le produit P1 est fabriqué par
les machines M1 et M2 alors que le produit P2 est fabriqué sur P1 0.25 0.4 0
les 3 machines. Le tableau suivant donne le temps de séjour
P2 0.5 0.2 0.8
des produits sur les machines.
Le temps de séjour est donné en heure/unité de produit. La disponibilité hebdomadaire de chaque
machine est de 40 h. Le produit P1 engendre un prot unitaire de 20 D.A et le produit P2 un prot
unitaire de 30 D.A. Le problème consiste à déterminer le planning de production qui maximise le prot
total.
Ce problème contient un objectif, à savoir la maximisation du prot total. Les contraintes représentent
la disponibilité hebdomadaire de chaque machine. Les variables de décisions (ou facteurs contrôlables)
représentent le volume de production de chaque produit que l'on désigne respectivement par x1 et x2 .
Les facteurs non-contrôlables sont les prots unitaires sur chaque produit et la disponibilité hebdo-
madaire de chaque machine. La formulation de ce problème se trouve à la section 1.1.2. La fonction
objective ainsi que les contraintes sont des fonctions linéaires par rapport aux variables de décision,
d'où le nom de programmation linéaire.

1.1.1 Dénition :
Un programme linéaire est un problème qui consiste à optimiser (maximiser ou minimiser) une fonction
linéaire à plusieurs variables soumise à un ensemble de contraintes linéaires. D'une manière générale,
un programme linéaire s'écrit sous la forme suivante :

max F = c1 x1 +...+ cn xn
a11 x1 ...........+ a1n xn R1 b1
a21 x1 ...........+ a1n xn R2 b2 (1.1)
....
am1 x1 ...........+ amn xn Rm bm
Les relations R1 , R2 , ..., Rm sont soient des égalités ou des inégalités. Les coecients c1 et cn dans
la fonction objective sont des nombres réels. De même que tous les coecients dans le système des
contraintes sont des réels. Ce programme général peut aussi être exprimé sous la forme matricielle
suivante :

max F = C x
Ax Rb
1.1.1. Introduction A.Belahcene

où A est la matrice m × n des coecients des variables dans le système des contraintes, i.e.,
 
 a11 ... a1n 
 
A =  . . . 

 am1 ... amn 

C est le vecteur des coecients dans la fonction objective C = (c , ..., cn ) , X est le vecteur re-
présentant les variables de décision ( x1 , x2 , ..., xn ) et b le vecteur second membre du système des
contraintes ( b1 , b2 , ..., bm ) = bt .
Dans le cas du programme de l'exemple1.1.1, le nombre de variables n est 2 et le nombre de contraintes
m est egal a 5 . Les éléments de la matrice A sont résumés comme suit :

a11 = 0.25 a21 = 0.4 a31 = 0 a41 = 1 a51 = 0

a12 = 0.5 a22 = 0.2 a32 = 0.8 a42 = 0 a52 = 1

Les vecteurs b et C sont : C = (2, 3) et bt = (40, 40, 40, 0, 0) . Les trois premières relations R1 , R2 , et R3
sont sous forme  ≤ . Par contre, les relations R4 et R5 sont sous la forme  ≥ . Ces deux dernières
contraintes assurent la non-négativité des variables.
Remarque 1.1.2. Comme tout programme linéaire peut se ramener à la forme standard d'un système
d'équations voir système, nous allons uniquement nous intéressé à la résolution de ce type de pro-
gramme.

1.1.2 Formulation d'un Programme Linéaire

La formulation d'un problème en programme linéaire peut se faire en 4 étapes :
Identication des variables elles sont souvent connues comme étant des activités et représentent
les facteurs (objets) que nous contrôlons. Par exemple, les activités de l'usine précédente étant
la production des produits P1 et P2 , d'où le choix des variables x1 et x2 . Il est important de
bien dénir les unités de chaque variable. Les variables sont indépendantes, si une variables
dépend d'autres elle est éliminée pour la taille du programme.
Identication des objets sous contraintes. Dans l'exemple 1.1.1, le temps de séjour de chaque
produit dans chacune des trois machines.
Traduction Objectif sous forme mathématique de la fonction objective en termes de variables.
Dans l'exemple 1.1.1 : max F (x1 , x2 ) = 2 x1 + 3 x2
Traduction Contraintes mise en forme des contraintes du problème qui ne sont rien d'autre que
les limites sur les objets. Dans l'exemple 1.1.1
Exemple 1.1.3. Le Probleme se formule comme suit
0.25 x1 +0.5 x2 ≤ 40
0.4 x1 +0.2 x2 ≤ 40
0.8 x2 ≤ 40

Il ne faut pas oublier les contraintes de non-négativités des variables : x1 ≥ 0 et x2 ≥ 0

En résumé le problème de l'exemple 1.1.1 se modélise comme :

max F = 2x1 + 3x2

0.25x1 +0.5x2 ≤ 40
0.4x1 +0.2x2 ≤ 40 (1.2)
0.8x2 ≤ 40
x1 ≥ 0 et x2 ≥ 0
1.1.1. Introduction A.Belahcene

1.1.3 La Forme Standard

Les méthodes de résolution d'un programme linéaire utilise souvent la forme standard. Nous allons
donner sa dénition ainsi que les transformations utiles pour ramener un programme linéaire donne
sous forme générale à une forme standard.
On appelle forme standard d'un programme linéaire, la forme suivante :

n
X
max F = cj xj
j=1
n
X
aij xj = bi i = 1, m
j=1
xj ≥ 0

Cette forme impose aussi que les seconds membres des contraintes soient des nombres réels positifs
ou nuls, c'est-à-dire, b1 ≥ 0 , i = 1, 2, ..., m . La traduction matricielle de la forme standard d'un
programme linéaire est :

max F = CX
AX = b X≥0

Lorsque le programme n'est pas donné sous la forme standard, il est utile d'utiliser les transformations
suivantes :
1. La fonction objective consiste à minimiser une fonction linéaire F . Ceci est équivalent à maxi-
miser G = −F et on a la relation suivante : min F = − max (G)
2. Lorsque une contrainte (par exemple la i ème ) n'est pas une égalité, deux cas peuvent se
produire :
a) ai1 x1 + .... + ain xn ≤ bi , on introduit une variable d'écart ei ≥ 0 pour avoir ai1 x1 + .... +
ain xn + ei = bi
b) ai1 x1 + .... + ain xn ≥ bi , on introduit une variable d'écart ei ≥ 0 pour avoir ai1 x1 + .... +
ain xn − ei = bi
3. Il arrive parfois qu'un ou plusieurs seconds membres des contraintes soit négatif. Pour mieux
xer les idées, supposons que la contrainte i possède un bi négatif, en d'autres termes : ai1 x1 +
.... + ain xn = bi avec bi < 0, Il sut, dans ce cas, de multiplier les deux termes de cette
contrainte par (−1) et on obtient :

−ai1 x1 − .... − ain xn = −bi avec − bi ≥ 0,

4. Supposons que la j eme variable soit quelconque. Il faut, dans ce cas, faire des changements de
variables et poser xj = x1j − x2j avec x1j ≥ 0, x2j ≥ 0 .
Écrivons la forme standard du programme linéaire associé à l'exemple précèdent. On introduit une
variable d'écart pour chacune des trois contraintes on obtient :

max F = 2x1 + 3x2

0.25x1 +0.5x2 +e1 = 40
0.4x1 +0.2x2 +e2 = 40
0.8x2 +e3 = 40
x1 x2 e1 e2 e3 ≥ 0
1.1.2. Méthodes de Résolution A.Belahcene

1.1.4 Espaces des Solutions

Une solution d'un programme linéaire est un vecteur (x1 , ..., xn ) de R satisfaisant aux contraintes du
système. Par exemple, (−1, −1) est solution du programme de l'exemple 1.1.1.
Un vecteur de valeurs (x1 , ..., xn ) est dit solution réalisable s'il vérie les contraintes du système . La
solution (−1, −1) n'est pas réalisable car elle ne vérie pas une containte. Par contre (0, 0) est solution
réalisable.
Une solution est dite de base si elle possède m variables de base et n − m variables hors-base. Les
variables hors-base doivent être nécessairement nulles. Une solution de base réalisable vérie en plus
toutes les contraintes. Par exemple (0, 0, 40, 40, 40) est une solution de base réalisable pour le P.L 1 .
Cette dernière est obtenue en annulant les variables de décision x1 et x2 . Elles sont donc des variables
hors-base et les variables d'écart sont de base. Évidemment cette solution de base réalisable n'est pas
unique et on peut trouver d'autres.
On montre que la solution optimale est nécessairement de base. Un ensemble est convexe si, tout
segment ayant ses extrémités dans l'ensemble, est dans cet ensemble.
L'ensemble de toutes les solutions réalisables forme un polyèdre convexe. Il peut être vide, borné ou
non-borné. Si ce polyèdre convexe est vide cela signie que le système des contraintes est incompatible,
dans ce cas une analyse détaillée doit être envisagée. Lorsque le polyèdre est borné alors le problème
possède au moins une solution optimale. Enn lorsque ce convexe n'est pas borné alors, soit nous avons
omis une ou plusieurs contraintes, ou que le problème ne possède pas de solution optimale nie. Nous
reviendrons en détail à ces problèmes particuliers dans le prochain chapitre.
Il est important de savoir (la théorie l'a montré) que les sommets du convexe correspondent à des
solutions de base réalisable et que si la solution optimale existe elle doit être forcément un de ces
sommets. En d'autres termes la solution optimale est atteinte en un sommet du convexe.

1.2 Méthodes de Résolution

Dans la littérature existante on distingue deux classes de méthodes de résolution d'un programme
linéaire à savoir la méthode graphique et la méthode du simplexe avec ses diérentes variantes.
Nous allons résoudre ce programme de 2 manières :
Méthode graphique nous servira simplement a comprendre la procédure et énumérer les concepts
de base importants, qui de toute façon est limitée a 2 variables.
Méthode algébrique qui est évidemment celle utilisée dans les algorithmes de résolution. Il faut
dire aussi que les méthodes implémentées dièrent quelque peu de celle présentée ici. Elle a été
simpliée pour l'ecacité de l'utilisation de l'outil informatique.

1.2.1 La Méthode Graphique

Cette méthode est simple mais malheureusement elle ne s'applique qu'aux programmes linéaires pos-
sédant au plus deux variables. Le principe de cette méthode est de représenter graphiquement l'espace
engendré par l'ensemble des contraintes, de parcourir tous les sommets du polyèdre et de choisir ensuite
celui qui optimise la fonction objective.
Reprenons la forme initiale de l'exemple, et donnons les droites correspondant aux inégalités voir
gure 1.1 page suivante. Chaque droite (prenons le cas par exemple de la droite D1) divise le plan en
3 parties :
1. la droite elle-même : ensemble des couples de points (x1 , x2 ) vériant l'équation : 0.25x1 +0.5x2 =
40.
2. le demi-plan  inférieur  ensemble des couples de points (x1 , x2 ) vériant l'inéquation : 0.25x1 +
0.5x2 < 40.
1.1.2. Méthodes de Résolution A.Belahcene

3. le demi-plan  supérieur  ensemble des couples de points (x1 , x2 ) vériant l'inequation : 0.25x1 +
0.5x2 > 40.
Les 2 premières parties sont solutions au problème, la troisième ne l'est pas. Par conséquent un point
(x1 , x2 ) est solution au problème si vérie toutes les contraintes, et donc appartient a l'intersection des
domaines. De façon pratique prendre un point et voir s'il est ou non dans le domaine. Par exemple le
point (0, 0) vérie toutes les contraintes.
La  droite  D0 est au fait un faisceau de droites parallèles. Le déplacement de cette droite fait changer
la valeur de la fonction objective, déterminer donc le sens de l'amélioration de la fonction objective.
Par exemple pour le point (0, 0) la valeur de la fonction est 0 pour (30, 20) la valeur est 120 donc le
déplacement de la droite vers la droite améliore la solution.
On voit donc facilement la solution optimale,  le dernier point du domaine réalisable en déplaçant D0
vers la droite , ici le point C. Voir le graphe 1.1.
D0 2x1 +3x2 =z
max F = 2x1 + 3x2
D1 0.25x1 +0.5x2 = 40
0.25x1 +0.5x2 ≤ 40
D2 0.4x1 +0.2x2 = 40
0.4x1 +0.2x2 ≤ 40
D3 +0.8x2 = 40
0.8x2 ≤ 40
x1 ≥ 0 et x2 ≥ 0 D4 x1 =0
D5 x2 =0

Table 1.1  Résolution Graphique d'un PL

Le domaine ainsi représenté est un polyèdre convexe, qui a des propriétés très intéressantes que nous
allons voir ci après.

Figure 1.1  Résolution graphique du P.L. 1

1.1.2. Méthodes de Résolution A.Belahcene

Dans le cas de l'exemple 1.1.1, le polyèdre convexe correspondant est représenté sur la gure 1.1. Ce
polyèdre possède 5 sommets O, A, B, C, D de coordonnées respectives (0,0), (0,50), (60,50), (80,40)
et (100,0). Les valeurs de la fonction objective en ces points sont respectivement 0, 150, 270, 280 et
270. Il est donc évident que le sommet C est la solution optimale, correspondant aux valeurs : x1 = 80,
x2 = 40 et F = 280.

1.2.2 Principes Fondamentaux

La Solution est un Sommet
La solution optimale d'un PL (Programme Linéaire) si elle existe, est un sommet : Dans notre cas un
sommet est l'intersection de 2 droites, dans l'espace a 3 dimensions, c'est l'intersection de 3 plans, en
général dans l'espace à n dimensions c'est l'intersection de n hyperplans.
Considérons le point B(60, 50) sur le graphe, il se trouve sur la droite D1 donc la variable d'écart
correspondante e1 = 0 et sur la droite D3, donc e3 = 0. Ceci est valable pour tous les sommets. Notons
que certains sommets ne sont par réalisables, comme pour le sommet S(75, 50) intersection D2 et D3.
Un sommet peut être l'intersection de plus de 2 droites, c'est alors un sommet  dégénéré .

La Signication Algébrique
Algébriquement, un sommet (toujours dans le plan) correspond une solution de base, c'est a dire, 2
variables (au moins) sont nulles. Si on revient a notre exemple, voir le système de la section 1.1.3 page 5.
La solution optimale est donc une solution de base, correspondant a 2 variables nulles et les autres
sont calculées par résolution du système d'équations 3X3. Par exemple le point O(0, 0) correspond aux
valeurs (x1 = 0 , x2 = 0, e1 = 40, e2 = 40 et e3 = 40). Le point A(0, 50) correspond a la solution
( x1 = 0, x2 = 50, e1 = 15, e2 = 30 et e3 = 0). On dira que la variable x2 est entrée dans la base,
devenue non nulle et la variable e3 est sortie de la base avec la valeur 0; De plus c'est deux sommets
sont adjacents.

Direction de Déplacement
La procédure d'optimisation est donc de se déplacer d'un sommet à un autre sommet adjacent en
s'assurant de l'amélioration de la solution.
Exercice 1.2.1. Donner pour notre exemple, le nombre de sommets, de sommets réalisables et com-
ment trouver leur coordonnées. Généraliser pour un PL avec N variables principales et M contraintes.
A deux sommets adjacents correspond deux solutions de base qui varient uniquement par une variable.
Les sommets O et A sont adjacents, leur solutions de base (e1 , e2 , e3 ) et ( e1 , e2 , x2 ) varient par les
variables e3 et x2 . C'est a dire e3 est sortie de la base et x2 est entrée.
Ici nous avons choisi de nous déplacer dans la direction x2 , c'est à dire on a choisi de faire rentrer cette
variable dans la base, car  on sait qu'elle améliore 1  la solution.

Limite des valeurs des variables

Pourquoi sommes nous arrêter au point A, au lieu d'aller au point T(0, 80) par exemple qui est aussi
un sommet ? La réponse est évidente au vue du graphe, sinon on sort du domaine de faisabilité, T
est un point non réalisable, il ne vérie par la troisième contrainte. Maintenant comment le traduire
algébriquement ? Nous verrons la justication détaillée plus tard, pour l'instant nous disons, que la
variable e3 est positive au dessous de la droite D3, elle devient nulle sur D3 et devient négative plus
haut. Puisque toutes les variables doivent être non-négative, T est donc refuse. La procédure de passage
d'un sommet a un autre doit prendre en charge la positivite des variables.
1. On verra plus tard pour la justication algébrique
1.1.3. La Méthode du Simplex A.Belahcene

Critère d'arrêt
Lorsqu'il n'y a plus d'amélioration possible, si la solution est réalisable alors elle est
optimale sinon elle n'existe pas.

1.3 La Méthode du Simplex

1.3.1 Les Concepts de Base

Cette section fait suite, à la section sur les  Principes Fondamentaux , dans laquelle nous allons
traduire algébriquement les règles déjà obtenues graphiquement.
Cette méthode a été mise au point par Dantzig en 1948. Elle permet de résoudre les problèmes de
la programmation linéaire. Son principe est de passer d'une solution de base réalisable à une autre
solution de base réalisable meilleure (amélioration de la valeur de la fonction objective). Dans le cas
où il n'est pas possible d'améliorer cette valeur alors la solution optimale est atteinte (si elle existe).
Néanmoins, l'utilisation de cette méthode nécessite une solution de base réalisable de départ. Cette
condition n'est pas un handicap puisque l'on verra à la section 1.4 comment obtenir une solution de
base réalisable de départ.
Les diérentes étapes de la résolution du P.L.1 par la méthode du simplexe sont décrites par la gure
1.2 suivante :

Etape 1 A B Etape 2

C Fin

Debut O D
Figure 1.2  Cheminement de la méthode du simplexe

Nous allons illustrer à travers l'exemple 1.1.1 le fonctionnement de la méthode du simplexe et déduire
par la suite l'algorithme de résolution d'une manière générale et donner les justication des règles
utilisées. Reprenons la forme standard vue a la section 1.1.3 et donnons le tableau du simplex associé :
XB CB P1 P2 P3 P4 P5 b
e1 0 0.25 0.5 1 0 0 40
e2 0 0.4 0.2 0 1 0 40
e3 0 0 0.8 0 0 1 40
Cj 2 3 0 0 0
Yj 0 0 0 0 0
∆j 2 3 0 0 0 Z=0

Figure 1.3  Tableau Initial de l'exemple

Cette solution de base (ce tableau) correspond sur le graphe à l'origine O = (0,0). Nous avons noté
par :
1.1.3. La Méthode du Simplex A.Belahcene

XB , XN Variables de base et hors base. Rappelons que les variables hors base sont toujours nulles
CB , CN Coecients de ces variables dans la fonction objective, respectivement des variables de
base et hors base.
AB , AN Matrice des coecients des contraintes scindée en colonnes des variables de base et hors
base.
Yj = CB .Pj est le produit scalaire des vecteurs colonnes Pj et CB . Il représente l'inuence des
variables de base dans la fonction objective.
∆j est le gain réduit causé par la variable hors base j si elle rentrait dans la base.
Z Valeur de la fonction objective.

1.3.2 Méthode Pratique par les Tableaux

Dans ce tableau ( 1.3 page précédente), La solution actuelle est (40, 40, 40), qui est le vecteur b,
correspondant aux variables de base e1 , e2 et e3 . La valeur de la fonction objective est nulle Z = 0.
Les variables hors base sont nulles.
Nous résumons les étapes a suivre, nous verrons plus loin les justications.
1. Une hors base peut rentrer si son coût réduit est positif. Dans notre cas x2 (ou d'ailleurs x1 ) peut
rentrer dans la base, car son delta est positif (∆2 = 3). On choisit donc la colonne  pivot .
2. Parmi les variables de base, prendre celle qui correspond au minimum du rapport de b et de la
colonne pivot. Dans notre cas, on choisit de sortir de la base la variable e3 qui correspond au
minimum :
b 40 40 40
min ( ) = min( , , ) = 50
P2 0.5 0.2 0.8
3. La case  pivot  ainsi obtenue, va permettre de transformer le tableau avec la méthode de
Gauss, et obtenir la nouvelle solution, de sorte que le vecteur entrant dans la base (ici P2 )
devient identité,  1  a la position  e3  et  0  ailleurs. Voyons comment la transformation
est faite sur l'exemple, la généralisation est immédiate.
Soit Lp=(e3 , 0, 0, 0.8, 0, 0, 1, 40), la nouvelle ligne pivot sera NLp=(x2 , 3, 0, 1, 0, 0, 1.25,
50), après division par le pivot 0.8, évidemment les 2 premiers éléments x2 et 3, ne sont pas
concernés par la division. La nouvelle ligne une : NL1 est obtenue à partir de L1 (ancienne ligne
une) et de NL1 comme suit : NL1= L1 - 0.5*NLp, ou 0.5 est la case colonne pivot ligne une.
Ainsi NL1= (e1 , 0.25, 0, 1, 0, 0, 0.625, 25). On fait de même pour la ligne 2. Notons l'ordre de
la soustraction, ne pas détruire l'identité
4. Compléter le tableau par calcul des autres éléments (Y , ∆ et Z ).
Les deuxième et troisième tableaux obtenus sont comme suit :
Xb Cb P1 P2 P3 P4 P5 b Xb Cb P1 P2 P3 P4 P5 b
1
e1 0 4 0 1 0 − 58 15 x1 2 1 0 4 0 − 52 60
4
e2 0 10 0 0 1 − 14 30 e2 0 0 0 − 85 1 3
4 6
5 5
x2 3 0 1 0 0 4 50 x2 3 0 1 0 0 4 50
Cj 2 3 0 0 0 Cj 2 3 0 0 0
15
Yj 0 3 0 0 4 150 Yj 2 3 8 0 − 54 270
∆j 2 0 0 0 − 15
4 ∆j 0 0 -8 0 5
4

Exercice 1.3.1. Donner le tableau suivant et vérie qu'il est optimal, et correspond au sommet C sur
le graphe 1.1 page 7. La variable d'écart e3 n'est pas nulle à l'optimum. En pratique, cela signie que
la troisième contrainte n'est pas serrée. Ceci veut dire que l'utilisation hebdomadaire de la troisième
machine n'a pas atteint la limite qui est de 40 heures.
1.1.3. La Méthode du Simplex A.Belahcene

1.3.3 Justication de la Méthode

Critère d'entrée

La variable candidate à entrer dans la base est celle qui possède un coecient réduit ∆j positif,
en général on choix le plus élevé dans l'espoir d'arriver plus vite, ce qui n'est pas toujours vrai. En
d'autres termes la nouvelle variable de base xr est telle que : ∆r = max{∆j , |∆j > 0} où ∆j représente
le coecient de la variable xj dans le vecteur F , son expression sera explicitée ultérieurement. Ainsi,
la variable x2 à la première étape de résolution du programme linéaire rentre en base car elle possède
le coecient le plus élevé dans ∇j .
Nous allons donner la justication de ce choix. A une étape quelconque, disons p, de notre algorithme,
nous pouvons éclater notre espace en variables de base XB , B ensemble de variables de base, et hors
base XN , N ensemble de variables hors base, ces dernières sont nulles. Regardons la condition sur une
variable hors base xk avec k ∈ N , notons N = N − {k}, les variables hors base qui restent donc nulles.
Nous donnons ici le debut de la démonstration, Le reste est laissé en exercice.

(1.3)
X X X
Z= ci xi + ci xi + ck xk = ci xi
i∈B i∈N i∈B

(1.4)
X X X
Z= ci x̄i + ci xi + ck x̄k = ci x̄i + ck x̄k
i∈B i∈N i∈B

Dans la pemiere equation 1.3 toutes les variables de i ∈ N , sont nulles, dans la seconde 1.4 la variable
xk prend une valeur, de meme les variables de base changent de valeur.

Démonstration. La variable xk améliore la solution si Z − Z > 0. Déterminons d'abord les nouvelles

valeurs des variables de base xi pour i ∈ B .

(1.5)
X
xi = bi − aik xk − aij xi = bi − aik xk
j∈N

Cette equation correspondant à la ligne xi du tableau du simplex est établie car variables j ∈ N restent
nulles. En d'autres termes la quantité aik xk est la modication de la valeur de la variable xi (elle était
bi ) lorsque xk devient positive. Pour l'ensemble du problème, faire la somme pour toutes les variables
de base. Ainsi l'équation 1.4 devient

(1.6)
X X X
Z = ci (bi − aik xk ) + ck xk = ci bi + ck xk − ci aik xk
i∈B i∈B i∈B

(1.7)
X
= Z + (ck − ci aik )xk = Z + (ck − CB Pk )xk = Z + ∆k xk
i∈B

L'amélioration est donc possible si ∆k = ck − Yk > 0, où Pk est la colonne correspondant à la variable

xk et Yk = CB Pk du tableau du simplexe .

Critère de sortie

Pour déduire la formule permettant de trouver la variable xs qui sort de la base, il serait utile de
reprendre l'illustration de la méthode du simplexe et de voir comment, par exemple, à la première
étape la variable e3 est sortie de la base :
e1 = 40 −0.5x2 ≥ 0
e2 = 40 −0.2x2 ≥ 0 (1.8)
e3 = 40 −0.8x2 ≥ 0
1.1.3. La Méthode du Simplex A.Belahcene

Ce système est équivalent à :

40 40 40
x2 ≤ = 80, x2 ≤ = 200, x2 ≤ = 50, (1.9)
0.5 0.2 0.8
Ceci implique que x2 = min{80, 200, 50} = 50 . Ensuite, on a posé que x2 = 50 . Il ne faut pas perdre
de vue que x2 représente la variable rentrante, c'est-à-dire xr . La variable xs doit donc satisfaire le
critère suivant : min{bi /air , air > 0} = bs /asr ou air est appelé le pivot. La variable xs est la première
variable de base qui s'annule quand on augmente la valeur de la variable hors base xr et toutes les autres
b b b
variables de base restent donc positives. A la première étape on a : 1 = 80 , 2 = 200 , 3 = 50
a12 a22 a32
b3 b1 b2 b3
Par suite la variable e3 sort de la base car elle vérie bien : = min { ; ; }. Formellement
a32 a12 a22 a32
on peut écrire les formules de passage d'une étape à une autre comme suit : Soient r et s les indices
des variables entrante et sortante, et akij l'élément de la ligne i, de la colonne j du kem tableau et aksj
l'élément pivot. Nous aurons alors :
aksj
ak+1
sj = j = 1, ..., m + n + 1
aksr (1.10)
ak+1
sj = asj − aksr ∗ akir
k i 6= s et j = 1, ..., m + n + 1

Rappelons que le tableau du simplexe a n + m colonnes correspondant aux variables initiales et d'écart
et une colonne correspondant au second membre.

Critère d'arrêt

Nous avons vu que la méthode du simplexe dans le cas d'un problème de maximisation se termine
lorsque les coecients des variables hors-base dans le vecteur F sont tous négatifs ou nuls. En d'autres
termes, on doit avoir : ∇j ≤ 0, ∀j ∈ N où N ) représente les indices des variables hors-base.

Résumé

Tous les mécanismes de calcul que nous venons d'eectuer peuvent être résumés dans un tableau,
appelé, tableau du simplexe. Reprenons le programme 1.1.3 page 5
max F = 2x1 +3x2
0.25x1 +0.5x2 +e1 = 40
0.4x1 +0.2x2 +e2 = 40
0.8x2 +e3 = 40
x1 , x2 , e1 , e2 , e3 ≥ 0

On remarque que tous les coecients ∆j sont négatifs ou nuls, la solution courante est donc optimale.
L'algorithme du simplexe s'énonce comme suit :
1. Mettre le programme linéaire sous sa forme standard.
2. Recherche d'une solution de base réalisable de départ.
3. Construire le premier tableau du simplexe.
Tester si : ∇j ≤ 0, ∀j ∈ {1, ..., n}
4. si oui ; terminer la solution est optimale
si non ; aller en (5)
5. Soit ∇r = max{∆j |∆j > 0} la variable xr entre en base
Tester si : air ≤ 0 ∀i ∈ {1, ..., m}
si oui ; terminer le problème ne possède pas de solution optimale nie.
si non ; aller en (6)
1.1.4. Recherche d'une Solution de Base Réalisable A.Belahcene

6. On détermine la variable sortante xs par :

bs bi
= min{ , air > 0} où asr est le pivot. Aller en (6)
asr air
7. Obtenir le nouveau tableau du simplexe en divisant la ligne-pivot par le pivot. Les autres
éléments du tableau sont obtenus par la règle précédente ( voir formule 1.10). Aller en (3).

1.4 Recherche d'une Solution de Base Réalisable

Il est impératif d'avoir une solution de base réalisable de départ pour pouvoir utiliser la méthode du
simplexe. Dans plusieurs situations, celle-ci n'est pas toujours facile à obtenir. La méthode des deux
phases que nous allons exposer dans ce paragraphe est une variante de la méthode du simplexe. La
première phase consiste à associer un problème auxiliaire au programme-standard pour déterminer
une solution de base réalisable. La deuxième phase utilise la méthode du simplexe pour optimiser cette
solution obtenue.
En général on utilise 2 méthodes :
 methode du BigM : consiste a ajouter des variables articielles pour obtenir une solution de
base , avec un cout  tres negatif  penalisant donc ces variables de sorte a les faire sortir de
la base. On fait sortir les variables articielles grace au cout tres negatif. On obtient une base
de depart, bien sur non realisable. On utilise l'algorithme de facon tout a fait ordinaire. Voir
exercice 1.4.2 page suivante.
 methode du programme auxiliaire. Nous la présentons ici en détail.
Considérons le problème linéaire sous sa forme standard :

max F = cx
(1.11)
Ax = b x≥0

Nous Associons 1.11 le programme auxiliaire suivant :

m
X
min ϕ= yi
i=1
Ax +y =b
x≥0 , y≥0
x désigne le vecteur variable du programme d'origine ainsi que les variables d'écarts et y le vecteur
représentant les variables articielles. Le programme auxiliaire 1.4 est obtenu a partir du programme
1.11 après ajout des variables yi appelées variables articielles. On rajoute les variables articielles
uniquement aux contraintes du programme 1.4 qui ne contiennent pas de variable de base. La solution
de base ne peut être réalisable que si les valeurs des Y sont nulles. Le principe de la méthode des deux
phases est :
Phase 1 : Résoudre le problème auxiliaire par la méthode du simplexe. Si ce problème possède une
solution optimale nie, alors cette solution est de base réalisable pour le problème initial.
Phase 2 : Résoudre le problème initial en utilisant comme solution de base réalisable de départ, celle
trouvée à la n de la phase 1.
Exemple 1.4.1. Donner la forme standard du programme lineaire suivant :
min f = x1 + 2x2 max f 0 = −x1 −2x2
2x1 + x2 ≤ 6 2x1 +x2 +e1 =6
x1 + x2 = 4 x1 +x2 =4 (1.12)
x1 + 3x2 ≥ 8 x1 +3x2 −e2 =8
x1 , x 2 ≥ 0 x1 , x2 , e1 , e2 ≥ 0
1.1.4. Recherche d'une Solution de Base Réalisable A.Belahcene

Exercice 1.4.2. Faire la résolution graphique, puis utiliser la méthode du BigM puis des deux
phases pour résoudre ce problème
Il n'est pas nécessaire de rajouter une variable articielle à la première contrainte. En eet, en écrivant
la forme standard du programme (P.L.2) on obtient :
La première contrainte contient la variable e1 comme variable de base. Par contre, on doit rajouter
une variable articielle à la deuxième et à la troisième contrainte. Le problème auxiliaire (P.L.A) du
problème (P.L 2) s'écrit comme :

min ϕ = y1 +y2
2x1 +x2 +e1 =6
x1 +x2 +y1 =4 (1.13)
x1 +3x2 −e2 + y2 = 8
x1 , x 2 , e 1 , e 2 , y1 , y2 ≥0

Avant d'utiliser la méthode du simplexe pour résoudre le programme 1.13. on se gardera de ne pas
oublier d'exprimer la fonction objective de ce programme en termes de variables hors-base.
A la n de la phase 1, s'il existe une solution optimale nie alors elle doit être nécessairement
nulle avec yi = 0 ∀ i ∈ I(A), où I(A) représente l'ensemble des indices des variables articielles. Nous
discuterons dans le prochain chapitre le cas où il n'existe pas de solution optimale nie.
Pour accroître la rapidité de résolution du problème, il est conseillé d'introduire dans le tableau du
simplexe, lors de la résolution de la phase 1 du programme 1.13, la fonction objective du programme
1.12. et lui faire subir les mêmes mécanismes de calcul que ceux eectués pour la fonction objective ϕ.
Utilisons la méthode des deux phases pour résoudre le problème 1.13. Pour cela, exprimons la fonction
objective du problème en terme de variable hors-base x1 , x2 et e2 . Ce problème est équivalent au
problème suivant 2 :

max (−ϕ) = 2x1 + 4x2 −e2

2x1 +x2 +e1 =6
x1 +x2 +y1 =4 (1.14)
x1 +3x2 −e2 + y2 = 8
x1 , x 2 , e 1 , e2 , y1 , y2 ≥0

Phase 1 : Le premier et deuxième tableau du simplexe ( pour le probleme modie) :

XB CB x1 x2 e1 e2 y1 b
b 5 1 10
XB CB x1 x2 e1 e2 y1 y2 e1 0 0 1 0
e1 0 2 1 1 0 0 0 6 3 3 3
2 1 4
y1 0 0 0 1
y1 0 1 1 0 0 1 0 4 3 3 3
1 1 8
y2 0 1 3 0 -1 0 1 8 x2 4 1 0 − 0
3 3 3
Cj 2 4 0 -1 0 0 Cj 2 4 0 -1 0
0 0 0 0 0 0 0 4 4 32
Yj Yj 4 0 − 0
3 3 3
∆j 2 4 0 -1 0 0 2 1
∆j 0 0 0
3 3

La variable x2 entre en base et la variable articielle y2 sort de cette base.

On remarque que la dernière colonne du tableau initial ne gure plus dans ce tableau cela est dû au
fait que lorsqu'une variable articielle quitte la base, elle ne la réintègre plus, il est donc inutile de
2. Nous négligeons la constante 12,
1.1.5. Exercices A.Belahcene

conserver la colonne correspondante. La variable x1 entre en base et remplace la variable articielle y2

. Remarquant que nous pouvons faire sortir aussi la variable e1 au lieu de y1 , mais la nouvelle valeur de
y1 sera nulle et donc nous l'eliminons de toute facon. On obtient donc le tableau de la seconde itération.
Le critère d'optimalité pour la fonction ϕ est vérié car ∀j , ∇j = 0 . D'où la solution de base réalisable
de départ : x1 = 2 , x2 = 2 , e1 = e2 = 0 . On integre la fonction objective max −f = f 0 = −x1 −2x2 ,
initiale dans le tableau realisable et on continue l'algorithme.
Phase 2 : Utilisons la méthode du simplexe avec comme solution de départ la solution de base
réalisable obtenue à la phase 1. Voir les tableaux suivants.

XB CB x1 x2 e1 e2 b XB CB x1 x2 e1 e2 b
1
e1 0 0 0 1 −
1
0 e1 0 0 0 1 − 0
2 2
1
x1 2 1 0 0
1
2 x1 -1 1 0 0 2
2 2
1
x2 4 0 1 0 −
1
2 x2 -2 0 1 0 − 2
2 2
Cj 2 4 0 -1 Cj -1 -2 0 0
1
Yj 2 4 0 -1 12 Yj -1 -2 0 -6
2
∆j 0 0 0 0 ∆j 0 0 0 -
1
2

Les coecients des variables dans la fonction objective étant tous négatifs ou nuls, la solution courante
(x∗1 = 2, x∗2 = 2, e∗1 = e∗2 = 0 et F ∗ = 6) est donc optimale.

1.5 Exercices

1. Déterminer la forme standard associée aux programmes linéaires suivants : et donner la forme
matricielle.
3x1 −3x2 +7x3 min 6x1 −3x2 +2x3 min
x1 +x2 +3x3 ≤ 40 x1 +3x2 +x3 ≥ 40
x1 +9x2 −7x3 ≥ 50 2x1 +3x2 +3x3 ≤ 50
5x1 +3x2 = 20 4x1 +2x2 +x3 ≤ 20
5x2 +8x3 ≤ −100
x1 ≥ 0 x2 ≥ 0 x3 ∈ R x1 ≤ 0 x2 ≥ 0 x3 ≥ 0

2. Reprendre le texte de
a) Résoudre graphiquement ce problème.
b) Résoudre ce problème par la méthode du simplexe.
3. Reprendre le Texte de
a) Écrire la forme standard associée.
b) Résoudre graphiquement ce problème. Conclure.
c) Résoudre ce programme linéaire en utilisant la méthode des deux phases.
d) Resoudre ce programme avec la methode du BigM.
e) reprendre le meme probleme (meme contraintes), en remplacant l'objectif minimisation des
couts par maximisation des prots.
4. .
min W = 3u1 + u2
Résoudre graphiquement puis avec la methode
u1 −u2 ≥2
du BigM, et enn avec la methode des 2 phases
u1 +u2 ≥1
le programme
u1 , u2 ≥ 0
1.1.5. Exercices A.Belahcene

5. Résoudre le programme avec la methode du BigM

min W = 40u1 +40u2 40u3
0.25u1 +0.4u2 ≥2
0.5u1 +0.2u2 +0.8u3 ≥ 3
u1 u2 u3 ≥0
6. Reprendre le texte du
a) Écrire sa forme standard.
b) Résoudre graphiquement ce problème.
c) Résoudre ce problème par l'algorithme du simplexe.
7. Démontrer que le choix de la variable entrant est correct, voir section 1.3.3 page 11
8. Soient les programmes linéaires suivants :
max Z = −x1 +2x2 −3x3 max Z = −x3 −2x4 −x5 +11
x1 +x2 +x3 =6 x1 +x3 −x4 +2x5 = 2
−x1 +x2 +2x3 =4 x2 −x3 +2x4 −x5 ≤ 50
+2x2 +3x3 =0 4x1 +2x2 +x3 ≤ 20
x3 ≤2
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 xj ≥ 0 j = 1..5
Résoudre ces programmes linéaires en utilisant la méthode la plus appropriée.
9. Une entreprise de conserve de tomates utilise 2 ateliers pour l'emballage et 3 dépôts pour le
stockage du produit ni.
Dépot D1 D2 D3
Elle organise le transport des ateliers aux dépôts
Atelier
de sorte a satisfaire la demande aux moindres coûts.
A1 25 17 18
Les coûts de transport sont résumés dans le tableau.
A2 25 18 14
L'atelier 1 peut produire jusqu'à 850 cartons en une semaine, l'atelier 2 son niveau de production
maximal atteint 650 cartons en une semaine. La demande au niveau de chaque dépôt est estimée
respectivement à 300, 400 et 500 cartons.
a) Structurer, formuler et modéliser ce problème.
b) Résoudre ce problème en utilisant une méthode appropriée.
10. Montrer, en utilisant la méthode graphique, que ce programme linéaire possède une innité de
solutions.
x2

Le domaine convexe de ce programme li-

néaire est donné par la gure ci-contre. (0.6) (2.6)
Les sommets B = (2.6) et C = (4.3) sont
solutions optimales. Donc toute combi-
naison convexe de ces deux solutions op- (4.3)
timales est aussi optimale.

x1

droite de F
L'ensemble des solutions optimales est O = { (x1 , x2 ) | 3 x1 + 2 x2 = 18. Le lecteur est invité
à montrer algébriquement ce résultat.
2 Concepts Avancés de la PL
Nous allons exposer quelques modèles particuliers de programmation linéaire et nous donnons les
méthodes adéquates de résolution. Ensuite nous abordons l'analyse sensitive et post-optimale qui est
d'un intérêt capital dans la vie pratique. Une autre partie sera consacrée à la notion de dualité en
programmation linéaire. L'accent sera mis sur l'intérêt pratique de la dualité surtout en analyse sensitive
et post-optimale.

2.1 Modèles Particuliers

2.1.1 Modèle irréalisable

Un programme linéaire est dit irréalisable si certaines de ses contraintes se contredisent. Prenons à
titre d'exemple un programme linéaire ayant les contraintes suivantes :

x1 + x2 ≥ 7 et x1 + x2 ≤ 2.

max Z = 2x1 + 3x2

Ce programme est irréalisable, puisque il n'a pas de solution. Lorsqu'un tel cas se présente la formulation
du problème doit être revue. On peut reconnaître un tel cas par la présence d'une variable articielle
dans la base à la n de la phase 1.

2.1.2 Modèle Dégénéré

Un modèle est dégénéré si une variable de base est nulle. Le cas de degenerescence est extremment
rare, malgre tout il faut le prendre en consideration. Dans ce cas, il est possible qu'une itération de la
méthode du simplexe n'améliore pas la valeur de la fonction objective. Pour illustrer ce cas, considérons
un programme linéaire dont l'ensemble des contraintes est délimité par les contraintes A, B et C. On
rappelle, qu'en général, la méthode du simplexe passe d'un sommet S1 où les contraintes A et B se
rencontrent au sommet S2 où les contraintes B et C se rencontrent tout en améliorant la valeur de la
fonction objective. La gure 2.1(a) donne un cas de situation normale et la gure 2.1(b) le cas d'un
modèle dégénéré.
Exemple 2.1.1. Considerons le cas suivant. Si on fait entrer la variable x2 et donc e5 sort en entre
dans le cycle de degenrescence, par contre si e1 entre et donc e2 on evite la degenerescence du moins
pour le moment.
2.2.1. Modèles Particuliers A.Belahcene

XB CB x1 x2 x3 e1 e2 e3 e4 e5 b
4
x3 0 2 1 -3 0 2 0 0 1
3
e2 0 0 -1 0 3 1 -1 0 0 4
11
x1 − 1 0 0 0 0 2 0 0 3
6
e4 0 0 0 0 1 0 -1 1 0 2
e5 0 0 1 0 -1 0 1 0 1 0
11 23 4
Cj − 0 0 0 0 0
6 3 3
11 8 4
Yj − -4 0 −1 0 0
6 3 3
∆j 0 5 0 4 0 1 0 0

A S2
S1 S1 = S2

B C A C
B
a) Situation normale b) Situation degeneree

Figure 2.1  Situation normale et situation dégénérée

Considérons la situation où, lors de la résolution d'un problème par la méthode du simplexe, on passe
du sommet S1 au sommet S2 , correspondant à deux solutions de bases diérentes.
Dans certains cas, voir l exemple de la gure 2.1 (b), S1 et S2 est le même sommet, on peut ainsi rester
au même point après plusieurs itérations.
Cette situation est aussi appelée cycle. Le cycle peut être inni. La convergence de l'algorithme du
simplexe n'est pas assurée dans ce type de problème. Pour éviter le cycle, on peut utiliser, par exemple,
la méthode de perturbation. Elle permet de passer d'une première solution de base réalisable à la
solution optimale, si elle existe, sans retourner à une solution antérieure. Dans cette méthode le vecteur
b est substitué par le vecteur b(ε), déni comme suit ( on l'appelle représentation lexicographique) :

n
X
j
b(ε) = b + ε Pj
j=1

où ε est un nombre très petit et Pj représente le vecteur-colonne de la variable xj dans la matrice du

système des contraintes. Cette façon de faire permet de séparer les cas ex-equo, c'est a dire 0 + εest
diérent de 0 + ε2 bien qu a la limite (ε = 0) la valeur sera la même. géometriquement cela signie
que l'on sépare légèrement les sommets S1 et S2 par exemple de la gure 2.1, et quand on quitte le
sommet S1 pour S2 on ne revient plus sur S1 , car S2 correspond à une meilleure solution que S1 . On
résout par la méthode du simplexe ce problème perturbé puis on revient, à la n de la résolution, au
problème initial en posant ε = 0.

2.1.3 Modèle non Borné

Un programme linéaire est dit non borné si son optimum est inni. On reconnaît un tel modèle lorsqu'à
une itération donnée, le vecteur-colonne de la variable xr qui entre dans la base est négatif ou nul. Le
programme linéaire ne possède pas de solution optimale nale car on peut augmenter indéniment la
valeur de la variable xr .
2.2.1. Modèles Particuliers A.Belahcene

Soit le programme linéaire 2.1 suivant :

x2

max F = x1 +x2
x1 −x2 ≤ 1 Domain
(2.1) (0.3)
−2 x1 +x2 ≤ 3
x1 , x2 ≥ 0

x1
(1.0)
Résoudre ce programme linéaire en utilisant la méthode du simplexe. Retrouver le resultat en vous
inspirant de la gure.
Base CB x1 x2 e1 e2 b
les variables d'écart e1 et e2 , en utilisant la x1 1 1 -1 1 0 1
méthode du simplexe et après une itération, e2 0 0 -1 2 1 5
on obtient le tableau suivant :
∆1 0 2 -1 0 -1
La variable x2 est candidate à entrer dans la base. Mais, le vecteur P2 est négatif. On ne peut sortir
une variable, car la variable x2 peut être augmentée indéniment sans que l'une des variables de base
devienne négative. En eet, la première ligne s'écrit :

x1 − x2 + e 1 = 1 ou encore, x1 = 1 + x2 − e1

En gardant e1 = 0 , on peut augmenter indéniment la variable x2 la variable x1 reste positive ou

nulle. On peut faire de même pour la seconde ligne de ce tableau. En pratique, cette situation peut
signier l'omission d'une contrainte vitale. Dans ce cas, une restructuration du problème s'impose.

2.1.4 Modèles à Innité de Solutions

Il existe en pratique des modèles qui possèdent une innité de solutions optimales. Ce type de modèle
apparaît lorsqu'à la n de la résolution du programme linéaire par la méthode du simplexe une variable
hors-base possède un coecient reduit nul ( ∆ = 0).
Dans ce cas, une itération supplémentaire donnera une seconde solution optimale. Toute combinaison
convexe (i.e combinaison linéaire dont la somme des coecients est égale à 1) de ces deux solutions est
une solution optimale.
Soit le programme linéaire 2.2 suivant :
x2

max F = 3 x1 + 2 x2
(0.6) (2.6)
3x1 +2 x2 ≤ 18
x1 ≤4 (2.2)
(4.3)
x2 ≤6
x1 , x2 ≥0
x1

droite de F
Montrer, en utilisant la méthode graphique, que ce programme linéaire possède une innité de solutions.
Le domaine convexe de ce programme linéaire est donné par la gure.
2.2.2. La Dualité A.Belahcene

Les sommets B = (2, 6) et C = (4, 3) sont solutions optimales. Donc toute combinaison convexe de
ces deux solutions optimales est aussi optimale.
L'ensemble des solutions optimales est O = { (x1 , x2 ) | 3 x1 + 2 x2 = 18 }. Le lecteur est invité à
montrer algébriquement ce résultat.

2.2 La Dualité

En pratique, il arrive que la résolution d'un programme linéaire par la méthode du simplexe soit
dicile en raison du nombre important de contraintes dans le programme linéaire. Le passage à la
forme duale réduit la taille des solutions de base, la résolution traitera des matrices réduites. La
dualité joue un rôle important en analyse post-optimale et sensitive, à cause surtout du théorème des
écarts complémentaires que nous verrons à la soussection 2.2.2
Considérons les programmes linéaire duaux : primal et dual suivants. A chaque contrainte i du primal
on associe une variable duale

c1 x1 +c2 x2 +... +cxnn M in z

a11 x1 +a12 x2 +... +ahn xn ≥ bl
... ... ... ... ...
ahl x1 +ah2 x2 +... +ahn xn ≥ bh
ui . a(h+1)1 x1 +... +a(h+n)n xn = b(h+1)
... ... ... ... ...
aml xl +am2 x2 +... +amn xn = bm
xj ≥ 0 xj ∈ R
j = 1, ..., K j = k − 1, ..., n

Associons a chaque contrainte i une variable duale uj . nous obtenons le programme dual :

b1 u1 +b2 u2 +... +bm un M axW

a11 u1 +a12 u2 +... +alm um ≤ cl
... ... ... ... ...
ak1 u1 +ak2 u2 +... +akm um ≤ ck
a(k−1)1 u1 +.. +a(k−l)m um = c(k+1)
... ... ... ... ...
an1 u1 +an2 u2 +... +amn un = cn
u1 ≥ 0 i = 1, ..., h
u1 ∈ R j = h + 1, ..., m

La façon la plus simple d'obtenir le programme dual à partir du primal est de le mettre sous l'une des
formes standards, on peut passer de l'un à l'autre et inversement.

max Z = C x min W = ub
(P ) Ax ≤b (D) uA ≥c
x≥ 0 u ≥0
Par exemple les 2 programmes suivant sont duaux :

max F = 2 x1 + 3 x2 min W =40u1 +40u2 +40u3

0.25 x1 + 3 x2 ≤ 40
0.4 x1 + 0.2 x2 ≤ 40 (2.3) 0, 25u1 +0, 4u2 ≥2
(2.4)
0.8 x2 ≤ 40 3u1 +0, 2u2 +0, 8u3 ≥ 3
x1 ≥ 0, x2 ≥ 0
u1 ≥ 0 u2 ≥ 0 u3 ≥ 0
De cette dénition, on tire les propriétés suivantes :
2.2.2. La Dualité A.Belahcene

1. Cette transformation est involutive (le dual du dual est primal). Vérier cela en Exercice.
2. Une variable primale non-négative correspond à une contrainte-inégalité dans le dual.
3. Une variable primale non astreinte correspond à une contrainte-égalité dans le dual.
4. La matrice des contraintes du dual est la transposée de la matrice du primal.
5. Les coecients de la fonction objective du primal sont le second membre du dual.
6. Un problème de maximisation primal devient un problème de minimisation dual.

2.2.1 Procédure de Transformation

Pour obtenir le dual il est utile de tenir compte des règles suivantes :
1. Ramener le programme sous forme 2.3 ou 2.4
2. Eclater une équation en 2 inéquations équivalentes
3. Remplacer une variable non astreinte en variables positives.
Exercice 2.2.1. En vous inspirant des regles précédantes, donner les programmes duaux des pro-
grammes linéaires suivants.
min f = x1 + 2 x2 max f = 2 x1 + 3 x2
5x1 +3x2 ≥ 12 x1 +2 x2 ≥5
(2.5) (2.6)
x1 −x2 =2 x1 +x2 =4
x1 ≥ 0 , x2 ∈ R x1 ≥ 0 , x2 ≥ 0

2.2.2 Théorème des Ecarts Complémentaires

Avant d'énoncer ce théorème nous donnons deux lemmes :
lemme 1 : Si la solution optimale du primal x∗ existe et est nie alors celle du dual u∗ existe aussi
et est nie. A l'optimum les valeurs des fonctions objectives sont égales, c'est-à-dire c x∗ = u∗ b
.

lemme 2 : Si la solution optimale du primal est innie positive, alors le dual n'a pas de solution.
La réciproque n'est pas vraie. (La démonstration de ce lemme est laissée en exercice).
On ne mettra pas l'exposant t pour la transposition de la matrice ou des vecteurs pour alléger l'écriture.
Il est évident que les opérations doivent être possibles, par exemple, c x = u b devrait être écrite.
ct x = ut b où c et u sont des vecteurs-colonnes.
Si la solution optimale du primal est innie positive, alors le dual n'a pas de solution. La réciproque
n'est pas vraie.
Démonstration :
Considérons les problèmes duaux :

min Z = C x max W = ub
(P1 ) Ax =b (D1 ) uA ≤c
x≥ 0 u ∈R
Si x∗ est solution réalisable du primal et u∗ solution du dual vériant : u∗ b = c x∗ , alors x∗ et u∗ sont
des solutions optimales.
En eet, posons :
P = { x | A x = b et x ≥ 0 }
D={u | uA ≤c}

Soit x ∈ P alors A x = b. Multiplions cette équation par u on obtient : u A x = u b (1)

2.2.2. La Dualité A.Belahcene

Soit u ∈ D alors u A ≤ c . Multiplions cette inéquation par x on trouve u A x ≤ c x (2)

En utilisant (1) et (2) on tire :u b ≤ c x, ∀ x ∈ P, ∀u ∈ D (3)
Soit u∗ ∈ D alors c x ≥ u∗ b, ∀x ∈ P. comme, c x∗ = u∗ b (par hypothèse), Il s'ensuit que :
c x ≥ c x∗ , ∀x ∈ P. Donc x∗ est solution optimale de (P1 ).
De la même façon on montre que u est solution optimale de (D1 ).
Théorème 2.2.2. (Ecarts Complementaires) Une condition nécessaire et susante pour que les solu-
tions réalisables x∗ et u∗ soient optimales est qu'elles vérient les conditions suivantes :
u∗ (A x∗ − b ) = 0
(2.7)
( c − u∗ A ) x∗ = 0

La traduction de la première condition est :

 Si la contrainte primale n'est pas serrée alors la variable duale correspondante est nulle.
 Si une variable duale est positive alors la contrainte primale est serrée.
La deuxième condition peut se traduire de la même façon. Montrons maintenant ce théorème. Soient
x∗ et u∗ solutions optimales. Par hypothèse on a :

Ax∗ − b = 0 , x∗ ≥ 0 (2.8)
et
c − u∗ A ≥ 0 (2.9)

En multipliant l'equation 2.8 par u∗ et l'equation 2.9 par x∗ on obtient :

ξ1 = u∗ (A x∗ − b) = 0 et ξ2 = (c − u∗ A) x∗ ≥ 0

Or, ξ1 + ξ2 = cx∗ − u∗ b = 0 car x∗ et u∗ sont optimales et le Lemme 1 donne u∗ b = c x∗ . Il s'ensuit que :

ξ1 = ξ2 = 0. D'où la condition nécessaire.
Supposons maintenant que x∗ et u∗ vérient le système 2.7 du théorème. Alors,
c∗ x = u∗ b. D'après le Lemme, 2 x∗ et u∗ sont optimales respectivement pour (P1 ) et (D1 ) . D'où la
condition susante.
La démonstration reste valable pour le cas d'un programme primal mis sous forme général car une
contrainte inégalité peut être transformée en une contrainte égalité.
Exercice 2.2.3. Soient le programme linéaire et son dual :
max F = x1 + 3 x2 +2 x3
max W = −8u1 +2u2 −2u3
x1 − 5 x2 +7 x3 ≤8
−u1 +2u2 −u3 ≤ −1
−2 x1 + 4 x2 −2 x3 ≤ −2
5u1 −4u2 +3u3 ≤ −3
x1 − 3 x2 +2 x3 ≤2
−7u1 +2u2 −2u3 ≤ −2
x1 , x 2 , x 3 ≥ 0
u1 , u1 , u3 ≥ 0
1. Vérier que chacun des programmes est dual de l'autre.
2. Vérier que les solutions suivantes respectivement du primal et dual sont optimales. xt =
(1, 0, 0) et u = (0, 0.5, 0)
3. Vérier le théorème des écarts complémentaires c est a dire les conditions 2.7,
a) u(Ax − b) = (0, 1/2, 0) ∗ (−7, 0, −1) = 0
b) (c − uA)x = (0, 1, 3) ∗ (1, 0, 0) = 0

Ces solutions sont donc optimales.

2.2.2. La Dualité A.Belahcene

2.2.3 Déduction du Dernier Tableau du Simplexe du Dual (D)

Dans ce paragraphe nous allons donner une démarche qui permet de reconstituer le dernier tableau
du simplexe du programme dual à partir du dernier tableau du simplexe du programme primal. On
établit d'abord la correspondance entre les variables primales avec celles du duales comme suit :

Variables
Programme Primal principales d'écarts
x1 xs e1 ep
⇓ ⇓ ⇑ ⇑
Programme Dual v1 vs u1 up
d'écarts principales

La solution du dual représente les coecients marginaux du primal à un signe près. On identie les
variables de base et hors-base du programme dual puis on exprime, en utilisant le tableau du simplexe,
les variables de base en fonction des variables hors-base en inversant le signe des coecients.
Soit le programme linéaire de l'exemple 2.3 page 20 et son programme dual voir les programmes 2.5
et 2.6.
Écrire le programme dual qui lui est associé, déduire le dernier tableau du simplexe de ce programme
dual puis donner sa solution optimale.
Les variables de base duale sont donc u1 et u2 . Par contre les variables u3 , v1 , v2 sont hors-base.
Exprimons les variables de base en fonction des variables hors base :
De façon pratique on procède comme suit :
 Placer la matrice identité après avoir déterminé les variables de bases, correspondant respec-
tivement ( variable d'ecart primale donne variable principale duale et inversement) donne aux
variables hors base du primal.
 Mettre les coecients en changeant le signe des lignes y compris le Delta et Second membre.
 Compléter la ligne des coecients de la fonction objective. Ne pas oublier que nous résolvons
toujours un problème de maximisation ;
 Vérier le calcul des delta en les recalculant à partir du tableau obtenu
D'où les derniers tableaux du simplexe du programme (D) et primal (P) sont : (on note P les vecteurs
colonnes)
Le programme dual de l'exemple 1.1.3 page 4est :

min W = 40u1 +40u2 40u3

0.25u1 +0.4u2 ≥2
0.5u1 +0.2u2 +0.8u3 ≥ 3
u1 u2 u3 ≥0

Xb Cb x1 x2 e1 e2 e3 b
Xb Cb u1 u2 u3 v1 v2 b
x1 2+a 1 0 −4/3 10/3 0 80
u1 -40 1 0 32/15 4/3 -8/3 16/3
e3 0 0 0 −32/15 4/3 1 8
u2 -40 0 1 -4/3 -10/3 5/3 5/3
x2 3 0 1 8/3 −5/3 0 40 .
C -40 -40 -40 0 0
C 2 3 0 0 0
Y -40 -40 -32 80 40
Y 2 3 16/3 5/3 0
∆j 0 0 -8 -80 -40
∆i 0 0 −16/3 -5/3 0
Exercice 2.2.4. En tirant les u1 et u2 du tableau Dual, et en les remplacant dans le programme initial,
vérier que le tableau correspond réellement au programme D, et qu'il est optimal.

Les variables v1 , v2 et v3 sont des variables d'écarts du programme dual .

2.2.2. La Dualité A.Belahcene

2.2.4 Interprétation Économique de la Dualité

La dualité joue un rôle particulièrement important en pratique. L'interprétation économique de la
dualité dépend évidement de la nature du programme primal.
Considérons le problème d'une entreprise qui met en oeuvre n diérentes activités en faisant intervenir
m ressources disponibles en quantités bi , i = 1, ..., m. A chaque activité on associe un coût dépendant
de son intensité. Ce problème se modélise comme suivant
max z = nj=1 cj xj
P
Pn
j=1 aij xj ≤ bi i = 1, ..., m
xj ≥ 0 j = 1, ..., n

cj est le prot unitaire de l'activité j,

xj est l'intensité de l'activité j,
bi représente la quantité de la ressource i consommée par les activités du problème
aij la quantité de la ressource i consommée par une unité de l'activité j .
Le programme dual correspondant est :
min w = m
P
i=1 bi ui
Pm
i=1 aij ui ≥ cj j = 1, ..., n
ui ≥ 0 j = 1, ..., m

Les variables duales représentent les contributions unitaires des ressources au prot (voir Exercice ).
Autrement dit, la variable duale ui représente la variation de la fonction objective en fonction de la
disponibilité de la ressource i (bi ). Elle est souvent appelée coût marginal et représente la somme que
nous sommes prêts à payer pour augmenter la disponibilité de la ressource i.
En d'autres termes, si une personne tierce nous propose le service d'augmenter notre disponible bi ,
dans quelle mesure ( à quel cout ? ) sommes nous pret a accepter son ore ? quel est le cout unitaire
du service est acceptable ?.
Ce qui explique la minimisation de la fonction objective du dual qui représente le plus faible prix à payer
pour augmenter la disponibilité des ressources et par conséquent augmenter le prot. La contrainte j
du dual signie que la contribution au prot des ressources consommées par une unité de l'activité j
doit être au moins égale au prot unitaire de cette activité.
En particulier si une variable duale ui est nulle, le coût à payer pour l'augmentation du disponible
bi est nul ; ce qui est évident puisque le disponible n'est pas entièrement consommé car la contrainte
primale correspondante est inactive

max W = −V = −3y1 −5y2

Yb Cb b y1 y2 e1 e2
−y1 − 2y2 ≤ −3 e01 0 -3 -1 -2 1 0
−y1 − 1.25y2 ≤ −2.5 (2.10) e02 0 -2.5 -1 -1.25 0 1
y1 ≥ 0 et y2 ≥ 0 4j 0 -3 -5 0 0
Tableaux Optimums non réalisables correspondent successivement aux points ( O' sur GD et A' sur
GD )

Yb Cb b y1 y2 e01 e02 Yb Cb b y1 y2 e01 e02

y20 -5 1.5 0.5 1 -0.5 0 y10 -5 2/3 0 1 -4/3 4/3
e02 0 -5/8 -3/8 0 -5/8 1 y20 -3 5/3 1 0 5/3 -8/3
4' j -7.5 -0.5 0 -2.5 0 4j -25/3 0 0 -5/3 -4/3
2.2.2. La Dualité A.Belahcene

Le dernier Tableau Optimal non réalisable correspond a B' sur GD.

Les graphes représentant les solutions du primal (P) et du dual (D)
Le domaine réalisable est noté par DR pour les deux graphes.2.2
x2 y2

C
A’
B B’
DR
DR
x1 y1
O A O’

GP : Graphe du Primal GD : Graphe du Dual

Figure 2.2  Tableau du Primal et Dual

A Chaque tableau du Primal (P) correspond un tableau du dual (D)

Par changement de ligne en colonne, de colonne en ligne et par changement de signe , la variable
principale devient d'écart et la variable d'écart devient principale.
Notons que le changement de signe vient du fait que nous avons résolu le programme Dual avec la
maximisation. Par exemple Le tableau optimale réalisable de (D) correspondant à B' s'obtient du
tableau optimal de (P) correspondant à B.
2 2 5 5
y2 = correspond ∆2 = − et y1 = correspond ∆1 = −
3 3 3 3
4 4 5 5
x2 = correspond ∆02 = − et x1 = correspond ∆01 = −
3 3 3 3
Interprétation des variables duales :
La valeur de la variable duale correspond à l'importance accordée à la contrainte associée du primale.
Si cette valeur est nulle par exemple, cela signie que cette contrainte  n'est pas bloquante , non
saturée, en d'autres termes l'augmentation du second membre de cette contrainte n'est intéressante.
Considérons la solution optimale, et la variabley1 = 35 . La valeur 5000/3 DA (rappelons que l'unité
est le Millier de DA) correspond au coût (l'importance) que l'on peut payer l'augmentation dune unité
( 1m3 ) la capacité du camion. C'est à dire si le coût d'amortissement de la transformation de notre
camion ( par exemple atteler une remorque) est inférieur à 5000/3 DA par m3 il est alors intéressant
de faire cette transformation.
Importante : ce coût marginal est une variation unitaire, c'est a dire pas forcément valable pour une
augmentation de plusieurs m3 par exemple. La solution optimale peut alors changer (Voir la partie :
programme linéaire paramétré).
Une autre façon de voir
un entrepreneur de construction de bâtiment pour un projet important doit-il acheter un camion pour
faire son propre transport ? ou louer un camion à chaque fois qu'il en a besoin ?
Dans quelles limites de prix, il serait plus intéressant d'acheter un camion, par forcement de même
tonnage et capacité volume ?
2.2.3. Analyse Post Optimale et Sensitive A.Belahcene

2.3 Analyse Post Optimale et Sensitive

Les variables duales permettent donc d'établir un ordre de paramétrisation du second membre des
contraintes du primal. Autrement dit, en analyse post-optimale et sensitive la priorité est donnée aux
contraintes du primal dont les variables duales correspondantes ont une valeur importante.
Dans les précédents paragraphes notre souci majeur était la recherche de solution optimale lorsqu'elle
existe. En réalité, certaines valeurs utilisées lors de la formulation du problème ne sont pas exactes. Il est
d'un grand intérêt de savoir si la solution trouvée reste optimale pour une variation de certaines valeurs
du programme et de déterminer un intervalle pour lequel cette solution reste optimale. Ces problèmes
sont appelés "Analyse sensitive" ou programmation paramètre. Un cas de problème intéressant en
pratique est l'étude de l'eet du changement des coecients de la fonction objective sur la solution.
Ce problème est aussi appelé "Analyse post-optimale".
Dans ce paragraphe, nous nous limitons aux changements dans le second membre des contraintes et
des coecients de la fonction objective. L'exemple 2.3 suivant illustrera ce paragraphe :
Reprendre le programme linéaire (P.L. 1) :

max F = (2 + a)x1 + 3x2

0.25x1 + 0.5x2 ≤ 40
x ≥ 0 et x2 ≥ 0
0.4x1 + 0.2x2 ≤ 40 1
0.8x2 ≤ 40

Discuter l'eet sur la solution optimale et sur l'optimum, dun changement du problème sur :
 prot unitaire du produit P1 de 2 à (2 + a).
 second membre de la deuxième contrainte : 0.4x1 + 0.2x2 ≤ 40 + b

2.3.1 Changement dans la fonction objective

Supposons que l'on change le coecient de la variable principale de base x de 2 à (2 + a). La fonction
objective s'écrit : F = (2 + a) x1 + 3 x2
A partir du système (3.5) les variables de base x1 et x2 s'écrivent en fonction des variables hors
base :x1 = 80 + 1.33e1 − 3.33e2
x2 = 40 − 2.67e1 − 1.67e2
Le remplacement de ces variables dans la fonction objective f donne :

F = (280 + 80a) + (−5.33 + 1.33a)e1 +(−1.67 − 3.33)e2

Le tableau du simplexe correspondant est :

Base CB x1 x2 e1 e2 e3 b
x1 2+a 1 0 -4/3 10/3 0 80
e3 0 0 0 -7/3 4/3 1 8
x2 3 0 1 2.67 -5/3 0 40
4j 0 0 -16/3+4/3a -5/3-10/3a 0 -280-80a

Base CB x1 x2 e1 e2 e3 b
x1 2 1 0 -4/3 10/3 0 80
e3 0 0 0 -7/3 4/3 1 8
x2 3 0 1 8/3 -5/3 0 40
4j 0 0 -16/3 -5/3 0 280
2.2.3. Analyse Post Optimale et Sensitive A.Belahcene

Cette solution reste optimale si et seulement si :

-5.33 + 1.33a≤0
-1.67 - 3.33a≤0

C'est la condition d'optima lité du tableau du simplexe, autrement dit, l'augmentation de e1 ou de e2

fera diminuer la valeur de la fonction objective.
La résolution de ce système d'inéquations donne a ∈ [−0.5, 4]. Pour a dans cet intervalle la solution
optimale reste la même (x1 = 80, x2 = 40) mais la valeur de la fonction objective (l'optimum) change
et devient égale à 280 + 80 a.
Notons d'abord que pour a = 0, le tableau est optimal. Suivant les valeurs de a, la variable e1 ou e2
rentre dans la base et la solution présente ne sera plus optimale. Nous avons les résultats suivants :
 −0.5 ≤ a ≤ 4 la solution actuelle est optimale et correspond au point C (cf. g 2.2).
 a > 4 la variable e1 rentre dans la base et correspond au point D.
 a ≤ −0.5 la variable e2 rentre dans la base mais la solution est optimale uniquement pour
a ≥ −2 ; il faut faire une autre itération pour le cas a < −2.
Nous donnons uniquement pour ce dernier cas le tableau obtenu, pour les autres le lecteur est invité à
faire les calculs et vérier nos résultats.
Base b x1 x2 e1 e2 e3
x1 60 1 0 4 0 -2.5
Pour a < −0.5 e2 6 0 0 -1.6 1 0.75
x2 50 0 1 0 0 1.25
4j -270-60a 0 0 -8-4a 0 1.25+2.5a
Le tableau n'est pas optimal si a < −2 , puisque le coecient de e1 est positif.
La variablee1 rentre dans la base et x1 en sort, on obtient le tableau suivant :
Base b x1 x2 e1 e2 e3
x1 150 0.25 0 1 0 -5/8
pour a < −2 e2 6 0.2 0 0 1 -0.25
x2 50 0 1 0 0 1.25
4j -150 2+a 0 0 0 -15
Ce tableau est optimal pour a < −2.
Récapitulatif :

Valeur de a −∞ -2 -0.5 4 +∞
Variable entrant e2 e2 aucune e1
Variables de base e1 , e2 ,x2 x1 ,x2 , e2 x1 , x2 , e3 x1 , e1 , e3
Solution ( 0,50 ) ( 60,50 ) (80,40 ) ( 100,0 )
Valeur de Z 150 270 + 60 a 280+80a 200 + 100 a

2.3.2 Changement dans le second membre

Dans certains cas, on désire savoir comment change la solution optimale (valeur des variables et de
la fonction objective) quand le second membre du programme change. Ce problème se ramène au cas
précédent, lorsqu'on utilise le programme dual.
On sait, de la section précédente, que le second membre du primal devient la fonction objective du
dual. Au fait, ce n'est pas un deuxième cas que l'on étudie mais simplement un autre problème pour
le même cas. Le dernier tableau du simplexe du programme dual est :
2.2.3. Analyse Post Optimale et Sensitive A.Belahcene

CB Base b u1 u2 u3 v1 v2
-40 u1 5.33 1 0 2.13 1.33 -2.67
-40 u2 1.67 0 1 -1.13 -3.33 1.67
4j -280 0 0 -8 -80 -40

Faisons la paramétrisation de la 2eme contrainte du problème initial primal :

0.4x1 + 0.2x2 ≤40 + b

Le coecient de u2 (variable associée a cette contrainte dans le dual) est donc −40 − b (le signe est
négatif à cause du problème de minimisation ramené à la maximisation).
Rappelons que les coûts réduits ∆j sont obtenus à partir des coecients de la fonction objective par la
transformation suivante ∆j = cj − CB Pj dans laquelle CB représente les coecients des variables
de base et Pj le vecteur colonne du tableau.
La dernière ligne du tableau peut être alors obtenue directement du tableau précédent :

−CB Base b u1 u2 u3 v1 v2
-40 u1 5.33 1 0 2.13 1.33 -2.67
-40-b u2 1.67 0 1 -1.13 -3.33 1.67
4j -280-5/3b 0 0 -8-1.33b -80-3.33b -40+1.67b

La solution initiale reste optimale pour ∆j négatif, c'est-à-dire,

8 − 1.33b ≤ 0 ; − 80 − 3.33b ≤ 0 et − 40 + 1.67b ≤ 0 ,

Ce qui donne : −6 ≤ b ≤ 24 .
b ∈ [−6, 24] la solution précédente reste optimale, en d'autres termes pour la contrainte 2 variant de :
0.4x1 + 0.2x2 ≤ 34 à 0.4x1 + 0.2x2 ≤ 64.En dehors de ces valeurs le tableau doit être changé.
b < −6 : La variable u3 rentre dans la base et la variable u1 en sort.
b > 24 : La variable v2 rentre et u2 sort.
De la même façon que pour le cas du primal, nous faisons les changements de tableau. Regardons ce
que devient le tableau précédant pour le cas b > 24, les autres cas sont laissés au soin du lecteur, nous
donnons cependant le tableau récapitulatif.
b > 24, ce cas correspond au second membre supérieur à 64, de la deuxième contrainte. Après avoir
fait entrer la variable v2 et sortir u2 on obtient le tableau optimal suivant :

CB Base b u1 u2 u3 v1 v2
-40 u1 8 1 8/5 0 1.33 0
0 u2 1 0 3/5 -4/5 -2 1
4j -320 0 24-b -40 -160 0
2.2.3. Analyse Post Optimale et Sensitive A.Belahcene

La solution primale correspondante est : x1 = 160 et x2 = 0 puisque ∆v1 = −x1 = −160

∆v2 = −2 x2 = 0
Récapitulatif :

Valeur de b −40 −30 −6 24 −→ ∞

Base du dual v1 , u2 u3 , u2 u1 , u2 u1 , v2
Sol. Primal x1 = 0 x1 = 2.5(30 + b) x1 = 80 + 10
3 b x1 = 160
x2 = 5(40 + b) x2 = 50 x2 = 40 − 53 b x2 = 0
5
Valeur de Z 600 + 15b 300 + 5b 280 + b 320
3

2.3.3 Interprétation graphique

Dans le cas de l'exemple 2.3, nous pouvons donner une interprétation géométrique à la signication des
variations du paramètre. La variation du coecient dans la fonction objective revient à faire changer
la pente de cette droite. La pente dans notre problème est l'opposé du rapport des coecients de
x1 et de x2 . Autrement dit
2+a
P =−
3
Quand cette pente est positive, l'optimum est le point A, ( donc pour a ≤ −2 ). Dans le cas où elle
est comprise entre les pentes de AB et BC, l'optimum est le point B, etc... Notons que, lorsqu'elle est
parallèle à une droite- contrainte, tous les points du segment réalisable sont optimums.
La variation dans le second membre revient à déplacer parallèlement la droite contrainte. Dans le cas
de l'exemple , on déplacera parallèlement la droite contenant le segment CD. Si on éloigne cette droite
de l'origine, la contrainte devient inutile et redondante, les points C et D sont alors confondus et loin
de la contrainte. En d'autres termes, le point optimum C glisse vers D. Ceci revient à augmenter la
valeur du paramètre b, à partir b = 24.
Inversement si b < 0 le point optimal C glisse vers B, puisque la droite contenant le segment DC se
déplace parallèlement vers l'origine, jusqu'à atteindre le point B avec la valeur b = - 6.
Si b < -6 les point B et C (confondus) glissent vers A. Ce point est atteint pour b= -30, si la valeur
de b continue à diminuer, le point optimal se rapprochera de O.
Notons cependant que pour un problème économique, un coût négatif na pas de sens, donc doit être
supérieur ou égal à -2. De même, b doit être supérieur ou égal à - 40 car la contrainte, qui dans la
pratique, représente une capacité, ne peut être négative.
x2

A B

C
Fonct. Objective
2 ieme contrainte
D x1

Figure 2.3  Variation de la seconde contrainte de l'exemple2.3

2.2.4. Exercices A.Belahcene

2.4 Exercices

1. Donner les programmes duaux des programmes linéaires suivants :

3x1 −3x2 +7x3 Max 6x1 −3x2 +2x3 min
x1 +x2 +3x3 ≤ 40 x1 +3x2 +x3 ≥ 40
x1 +9x2 −7x3 ≥ 50 2x1 +3x2 +3x3 = 50
5x1 +3x2 = 20 4x1 +2x2 +x3 ≤ 20
5x2 +8x3 ≤ 100
x1 ≤ 0 x2 ≥ 0 x3 ∈ R x1 ∈ R x2 ≥ 0 x3 ≥ 0

−3y1 −3x2 +7(y2 − y3 ) Max

−y1 +x2 +3(y2 − y3 ) ≤ 40
y1 −9x2 +7(y2 − y3 ) ≤ −50
5y1 −3x2 ≤ −20
−5y1 +3x2 ≤ 20
5x2 +8(y2 − y3 ) ≤ 100
y1 ≥ 0 x2 ≥ 0 (y2 ≥, y3 ≥ 0
1. Résoudre ces programmes linéaires suivants :
−x1 +2x2 −3x3 max max −x3 −2x4 −x5 +11
x1 +x2 +x3 =6 x1 +x3 −x4 +2x5 = 2
−x1 +x2 +2x3 = 4 x2 −x3 +2x4 −x5 ≤ 50
+2x2 +3x3 = 10 4x1 +2x2 +x3 ≤ 20
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 xj ≥ 0 j = 1..5
2. Montrer, avec l'algorithme du simplexe,
max F = x1 +x2
que le programme suivant n'a pas de solution x1 −x2 ≤ 1
nie. Interpréter le coecient négatif dans la −2 x1 +x2 ≤ 3
colonne de la variable entrant dans la base. x1 , x2 ≥ 0
3. Montrer, en utilisant la méthode graphique, que ce programme linéaire possède une innité de
solutions.
x2

Le domaine convexe de ce programme

linéaire est donné par la gure. (2.6)
(0.6)
Les sommets B = (2.6) et C = (4.3) sont
solutions optimales. Donc toute combinaison
convexe de ces deux solutions optimales est (4.3)
aussi optimale.

x1

droite de F
L'ensemble des solutions optimales est O = { (x1 , x2 ) | 3 x1 + 2 x2 = 18 . Le lecteur est invité
à montrer algébriquement ce résultat.
4. Soit le programme linéaire suivant :
max F = x1 + x2 + x3 + x4
a) Faire une analyse graphique x1 + x2 ≤2
b) Utiliser le Simplex. Que Conclure ? x3 + x4 ≤5
x1 , x2 , x3 ,x4 ≥0
2.2.4. Exercices A.Belahcene

a) Résoudre graphiquement ce programme linéaire. Que peut-on conclure ?

b) Résoudre par l'algorithme du simplexe ce programme. On donnera toutes les solutions opti-
males de ce problème.
5. Soit le graphique suivant, donner le programme lineaire correspondant, son dual, le tableau nal
du primal et determiner le tableau optimal dual a partir du primal
6. Montrer par le simplex que le problème suivant est non-borné :
6x1 +2x2 +10x3 + 8x4 max
3x1 −3x2 2x3 + 8x4 ≤ 25
−5x1 +6x2 −4x3 − 4x4 ≤ 20
4x1 −2x2 +x3 + 3x4 ≤ 10
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
7. Etudier la nature des tableaux (optimalité, degenerescence, faisabilité, possibilité d'amélioration
etc ..., a1 variable articielle et M  0).

Base x1 x2 x3 e1 e2 e3 b Base x1 x2 x3 e 1 e 2 a1 b
x1 1 0 1.5 4 1 0 10 x1 1 0 3 2 -1 0 1
x2 0 1 2 1 -3 0 5 x2 0 1 2 1 -3 0 5
e3 0 0 3 0 2 1 7 a1 0 0 -1 0 0 1 4
∆ 0 0 -4.5 -13 0 0 ∆ 0 0 M-9 0 6 0
8. Etudier graphiquement le changement du coecient dans la fonction objective de la variable
X1 puis de la contrainte Une dans le programme suivant :

max X1 + X2
0 ≤ X1 ≤ 1
0 ≤ X2 ≤ 1

9. Soit le programme linéaire (P) avec son dernier tableau du simplexe :

XB CB x1 x2 x3 e1 e2 e3 b
max F = 3x1 + x2 − x3 x1 3 1 0.75 0 0.5 0.25 0 6.5
x1 + x2 +2 x3 ≤10 x3 -1 0 1/8 1 0.25 -1/8 0 1.75
2x1 +x2 −4x3 ≤6 e3 0 0 0.12 0 -0.75 -1/8 1 3.75
x1 +x2 + x3 ≤12 C 3 1+α -1 0 0 0
x1 , x 2 , x 3 ≥ 0 Y 3 17/8 -1 1.25 7/8 0
71
∆ 0 α − 9/8 0 -1.25 -7/8 0 F =
4

a) Donner le dual (D) de (P).

b) Donner le tableau optimal de (D)
c) Discuter l'eet d'un changement du coecient de la variable x2 dans la fonction objective
de 1 à 1 + α .
d) Nous remplacons la capacité de la contrainte 3 par 12 + β , dans quelle limite la solution
actuelle reste optimale, et quelle est la valeur de la fonction objective optimale.
10. Une entreprise fabrique 4 types de bureau. Chaque bureau est fabriqué dans l'atelier 1 de
menuiserie puis envoyé à l'atelier 2 pour les travaux de nition (peinture, vernissage...). Le
nombre d'heures de main-d'oeuvre dans chaque atelier et les prots unitaires sont donnés dans
le tableau :
Bureau 1 2 3 4
La disponibilité en heures de main-d'oeuvre
Atelier 1 4 9 7 10
pour l'atelier 1 est de 6000 h. Elle est de 4000
Atelier 2 1 1 3 40
h pour l'atelier 2.
Prot 12 20 18 40
2.2.4. Exercices A.Belahcene

a) Formuler ce problème comme un programme linéaire P.

b) Soit xi le nombre de bureaux du type i que l'on doit fabriquer. Soit le tableau du simplexe :
Base x1 x2 x3 x4 e1 e2 b
4000
x1 1 2.3 1.6 0 4
15
−1
15 3
200
x4 0 1
− 30 1
30 1 1
− 150 2
75 3
20 10 44 4 56000
∆ 0 − − 0 − − f=
3 3 15 15 3
où e1 et e2 sont des variables d'écarts.
Donner le plan de production optimale pour cette entreprise.
c) Écrire le programme dual associé au programme primal P. En déduire son dernier tableau
du simplexe ainsi que la solution optimale du dual. Donner une interprétation économique
du dual.
d) Le directeur de cette entreprise décide d'augmenter la capacité maximale de l'atelier 1 d'une
quantité α. Pour quelles valeurs de α la solution optimale trouvée reste-t-elle optimale ?
e) Le directeur envisage la possibilité d'augmenter son prot de 400 unités. Quelles sont les
changements à opérer sur les capacités des deux ateliers pour atteindre cet objectif ?
Le plan de production optimal trouvé Bureau 1 2 3 4
f) serait-il aecté pour les prots unitaires prot 10 22 20 38
suivants :
Problème 2.4.1. Soit le domaine denie par le triangle (OAB) sur la gure.
1. Donner le programme linéaire correspondant.
2. Donner la solution optimale par le simplexe et préciser le point sur le graphe.
3. Donner le programme dual et son graphe.
4. Donner la solution optimale duale a partir de l'optimal dual.
5. On fait deplacer la contrainte droite OB, Donner les solutions correspondantes.
2.2.4. Exercices A.Belahcene
3 Programmation non Linéaire sans Contrainte
3.1 Introduction

La programmation linéaire même si elle couvre un vaste domaine d'applications, est loin de répondre
aux exigences de beaucoup de situations dont la formulation donne les programmes non linéaires ou
encore des programmes en nombres entiers. Nous donnons ci-après un exemple de problème se formulant
en programme non-linéaire
Exemple 3.1.1. Une entreprise de commercialisation possède m magasins de vente, d'un certain
produit, répartis à travers le pays. Ses magasins doivent être réapprovisionnés à partir des dépôts de
stockage. Elle veut déterminer l'emplacement de ses dépôts de sorte à minimiser les coûts de transport
du produit des dépôts vers les magasins. Un magasin peut être alimenté par n'importe quel dépôt.
Ce probleme se formule comme un programme Non lineaire à plusieurs Variables avec Contraintes.
Nous ne verrons pas de résolution pour ce genre de problemes, nous nous limitons ici aux programmes
non lineaires sans contraintes.

Notons d'abord que l'optimisation doit porter sur le coût global de transport, lequel dépend des quanti-
tés transportées de chaque dépôt à chaque magasin et de la distance séparant les dépôts des magasins.
Soient
n : le nombre de dépôts
m : le nombre de magasins.
xi , yi les coordonnées du dépôt i
aj , bj les coordonnées du magasin j.
ci la capacité du dépôt i
rj la demande du magasin j.
dij la distance du dépôt i au magasin j.
qij la quantité transporté du dépôt i au magasin j
Le problème se formule alors comme suit :

n X
X m
qij dij
i=1 j=1
Xm
qij <= ci i = 1, .., m
j=1
Xn
qij ≥ rj j = 1, ..., n
i=1
qij ≥ 0et dij ≥ 0 ∀i ∈ (1, n) ∀j ∈ (1, m)

En utilisant la norme Euclidienne alors on a :

q
dij = (xi − ai )2 +(yj −bj )2
3.3.2. Fonction à une seule variable A.Belahcene

Après remplacement de dij par son expression, la fonction objective devient non linéaire par rapport
aux variables indépendantes xi , yj . C'est donc un programme non-linéaire avec contraintes.
De plus, si la quantité à transporter est le nombre d'unités, le problème devient encore plus dicile à
résoudre, puisqu'il devient un programme en nombres entiers. La résolution d'un tel problème ne peut
se faire avec le simplexe (voir chapitre 2). Il faut développer d'autres techniques de programmation
non linéaire en nombres entiers.
Un programme non linéaire se présente sous la forme :

Optimiser f (x) tel que h(x) = 0 g(x) ≤ 0 avec x ∈ F

Où n est le nombre de variables, m et p sont les nombres de contraintes égalités et inégalités. F est
un sous ensemble de Rn . Les fonctions vectorielles h et g sont dénies par les fonctions f, gi et hi de
Rn dans R.

h(x) = (h1 (x), .......hn (x)) et g(x) = (g1 (x).........gp (x))

Si les fonctions f, gi et hi sont linéaires, le programme est alors linéaire. Les résultats de la program-
mation non linéaire sont aussi valables pour un programme linéaire.
Si E ⊆ Zn le programme est alors en nombres entiers.
Nous étudions uniquement les problèmes de minimisation ; un problème de maximisation se ramène à
un problème de minimisation en changeant le signe de la fonction objective.

3.2 Fonction à une seule variable

3.2.1 Dénitions
Dénition 3.2.1. Un programme non linéaire à une variable réelle se présente sous la forme : Optimiser
f (x)tel que x ∈ [a, b]. Ce problème est dit avec contrainte, il sera sans contrainte pour x ∈ R.
Dénition 3.2.2. Une fonction f admet un minimum local en x0 , s'il existe un voisinage de x0 (noté
V( x0 ) ) tel que : f (x0 ) ≤ f (x)∀x ∈ V (x0 ). Un minimum global sur un intervalle correspond au plus
petit des minimums locaux.
Dénition 3.2.3. Une fonction f est convexe sur l'intervalle I si ∀x, y ∈ I et α ∈]0, 1[ alors f (αx +
(1 − α)y) ≤ αf (x) + (1 − α)f (y). Si l'inégalité est stricte, f est strictement convexe. Si f (x) est convexe
alors −f (x) est concave.

3.2.2 Théorèmes
Théorème 3.2.4. Si f est continue sur un intervalle fermé et borné, alors elle admet sur cet intervalle
un minimum et un maximum.
Théorème 3.2.5. Soit f ∈ C 1 (I), c'est à dire que sa dérivée première f 0 est continue sur I ouvert. Si
f (y) est un optimum local alors f 0 (y) = 0. C'est une condition nécessaire d'optimalité (non susante).
Théorème 3.2.6. Soient f ∈ C n (I) et y ∈ I vériant : f 0 (y) = f 00 (y) = ...... = f k−1 (y) = 0 et
f k (y) 6= 0
si k est impaire f (y) n'est pas un extremum ( ni maximum, ni minimum) ;
si k est pair et f k (y) > 0 , f (y) est un minimum local
si k est pair et f k (y) < 0 , f (y) est un maximum local.
3.3.2. Fonction à une seule variable A.Belahcene

Théorème 3.2.7. Soit f ∈ C 2 (I) alors f est convexe sur I si et seulement si f 00 (x) ≥ 0 ∀x ∈ I . Si
f00 (x) > 0 ∀x ∈ I alors f est strictement convexe, la réciproque n'est pas vraie, (par exemple f (x) = x4
est strictement convexe dans R mais f 00 (0) = 0.
Théorème 3.2.8. Si f est convexe sur I alors la condition nécessaire est susante, c'est à dire que le
minimum local est global sur I. Si en plus I est fermé et borné, le maximum de f est à l'une des bornes
de I.
Théorème 3.2.9. Sur un intervalle fermé et borné une fonction peut atteindre son optimum :
soit au point où la fonction n'est pas dérivable.
soit au point où la dérivée est nulle,
soit aux bornes de l'intervalle.

Pour la démonstration de ces théorèmes voir la section des exercices.

3.2.3 Résolution analytique

Soit à résoudre le problème : Optimiser f (x) tel que x ∈ [a, b]
La méthode consiste à prendre en compte le lemme de la section précédente, c'est à dire, comparer les
valeurs f (a), f (b) et f (x) telles que :
 f 0 (x) = 0 sur l'intervalle où f est dérivable.
 ou bien f 0 (x) n 'existe pas.
Attention, La meilleure valeur cherchée est l'optimum global.
La méthode analytique est inecace lorsque la recherche des racines de f 0 (x) = 0 est dicile, ce qui
est le plus souvent le cas. Il faut alors chercher numériquement les racines de f 0 (x) = 0.
Soient les fonctions suivantes : f (x) = x4 , g(x) = x2 et h(x) = x sin(4x). Déterminer le minimum de
f sur R, les optimums de g sur [−1, 3]. Que dire des optima de h sur [2, 10] ?
f est une fonction dérivable sur R. Les seuls points à considérer sont les racines de f 0 (x) = 0 (condition
nécessaire ). On a f 0 (0) = f 00 (0) = f 000 (0) = 0 et f iv (0) = 24 donc f (0) est un minimum local.
De plus f est convexe sur R puisque f 00 (x) > 0 ∀x∈ R (théorème (3.2.6) ), le minimum est donc global
(théorème (3.2.8)). Ainsi la fonction f atteint sa plus petite valeur sur R au point x = 0 avec f (0) = 0.
La fonction g est dérivable sur ]-1 ,3[, sa fonction dérivée est g 0 (x) = 2x. Comme à l'exemple précédent
on montre que g(0)= 0 est un minimum global. Comme g est convexe, g(3) = 9 et g(−1) = 1 sont des
maximum locaux et g(3)= 9 est un maximum global.
La recherche des optimums pour h(x) = x sin 4x sur [2, 10] est dicile à cause de la complexité de
résolution de l'équation sin 4x + 4x cos 4x = 0. Il faut recourir aux méthodes itératives.

3.2.4 Résolution itérative

Soit à chercher le minimum d'une fonction f (x) donnée sur l'intervalle [a, b] de longueur L et  l'erreur
d'approximation.
Le principe de la méthode consiste à trouver une suite d'intervalles imbriqués qui contiennent la solution
recherchée. L'intervalle [a, b] de départ peut être R lui-même.
Pour éviter que les méthodes de recherche ne convergent vers des optimums locaux, on suppose que la
fonction est unimodale c'est à dire qu'elle possède un seul minimum (respectivement maximum ) pour
la recherche de minimum (respectivement maximum) sur l'intervalle.
Les fonctions convexes (respectivement concaves) sont unimodales pour la recherche de minimum
(respectivement maximum).
3.3.2. Fonction à une seule variable A.Belahcene

Les résolutions itératives permettent simplement la resolution de l'équation f ' (x) = 0, c'est a dire
la recherche d'un point condidat (vériant la condition nécessaire). C'est la raison pour laquelle nous
supposons l'unimodularité de la fonction.
Nous présentons dans ce qui suit deux des méthodes les plus utilisées : La méthode des 3 points et la
méthode de Fibonacci. Ces méthodes seront illustrées par l'exemple 3.2.10.
Exemple 3.2.10. Résoudre le problème suivant : g(x) = x2 tel que x ∈ [−1, 3] en utilisant :
 La méthode des trois points avec une erreur inférieure à ε = 0.01.
 La méthode de Fibonacci avec ε = 0.1

La méthode des trois points

Initialisation : Plaçons trois points x, y, t à l'intérieur de [a,b] de sorte que les intervalles [a,x], [x,y],
[y,t], [t,b] soient de même longueur L/4.

Procédure courante : Le nouvel intervalle de recherche est de longueur L/2 et centré sur z tel que :
Pour se xer les idées on suppose que le minimum de f soit en x ,f (x) = min f (x) = min(f (x), f (y), f (t)).
Le nouvel intervalle de recherche sera [x, t], on reprend la procédure avec cet intevalle. Voir le schema

a x y t b x y t

Critère d'arrêt : Soit zN la valeur approchée, à l'étape n, de la vraie valeur z* pour laquelle f(z*) est
L
minimum. L'algorithme s'arrête si l'erreur |zn −z ∗| ≤ ε. L'erreur commise est alors |zn −z ∗| ≤ .
2n + 1
log(L) − log(e)
Le nombre d'itérations est la partie entière de y = log 2
.
Utilisons la méthode des trois points pour résoudre le problème de l'exemple 3.2.10. Soit l'intervalle
I = [-1, 3] de longueur L= 4. On place les points x=0, y=1 et t=2. Ce qui donne f(x)=0, f(y)=1 et
f(t)=4. Le nouvel intervalle centre en 0 est I1 = [-1, 1] de longueur 2.
On reprend la procédure avec les nouveaux points x = −0.5 , y = 0 , t = 0.5. Le minimum est obtenu
pour y =0 donc nouvel intervalle est I2 = [0.5, 0.5].
A la 8ieme itération nous obtenons une erreur inférieure à L/29 = 0.008.
La fonction atteint son minimum au milieu de l'intervalle I, c'est à dire, au point 0.

Méthode de Fibonacci

La suite de Fibonacci est dénie par : Fn = Fn−1 + Fn−2

Les premiers éléments de la suite sont {1, 1, 2, 3, 5, 8, .......}. Notons par IN l'intervalle [aN , bN ] de
l'itération N et par LN sa longueur.

Initialisation : On détermine le plus petit N vériant FN .ε≥ b − a. Soit β = (b − a)/FN . On place

x1 et x2 à égale distance de a et b, soit : x1 = a + FN −1 β et x2 = b − FN −1 β

Procédure courante : Placer xj à une distance FN −j+1 β du dernier point extrémité placé de l'inter-
valle obtenu. Garder de l' intercalle Ij = [aj , bj ], l'intervalle contenant les meilleurs points. Le nouvel
intervalle est renommé Ij = [aj , bj ] pour la prochaine itération.
3.3.2. Fonction à une seule variable A.Belahcene

Critère d'arrêt : La procédure est arrêtée quand LN ≤ 2ε Ln ≤ 2 e , ce qui est le cas quand j = N −1.
Le nombre d'itérations est donc N − 1.
Utilisons la méthode de Fibonnaci avec ε = 0.1 pour résoudre le problème de l'Exemple précédant.
On a : a = −1, b = 3 et L1 = 4 F9 = 55 ≥ 4/0.1 . Il s'ensuit que N = 9 et β = 0.073.
On place : x1 = a + F8 β , c'est à dire, : x1 = 1.47 et x2 = b − F8 β , donc x2 = 0.28.
Or f(-1)=1, f(0.53) =0.28, f(1.47)= 2.16 et f(3) = 9. On garde donc l'intervalle contenant x = 0.53. Le
nouvel intervalle est [-1, 1.47].
On place x3 à F7 β = 1.53 de 1.47, (dernière extrémité de l'intervalle) c'est à dire x3 = 0.06. Nous
avons f(-1)=1, f(-0.06)=0.0036, f(0.53)=0.28 et f(1.47)=2.16. On retient l'intervalle contenant -0.006.
Le nouvel intervalle est [-1, 0.53].
A l'itération 8 on retient I8 = [−0.127, 0.019] de longueur L8 = 20 , la valeur approchée de x* est x9
=-0.054 milieu de I8 (placé à 0 de chacune des bornes ). L' erreur est inférieure à 0.073, on arrête la
procédure..
La méthode de Fibonacci nécessite plus d'itérations que la méthode des 3 points, puisque LN =
0.6LN − 1 au lieu de LN = 0.5 LN − 1 pour l'autre méthode. Cependant, dans une itération de la
méthode de Fibonacci on calcule un seul nouveau point alors que pour l'autre méthode on calcule
2 nouveaux points. La longueur de l'intervalle est divisée par 2 à chaque itération dans le cas de la
méthode des trois points. Par contre dans la méthode de Fibonacci LN et LN -1 sont telles que :

F
Ln = Ln−1 F N−n avec lim FFn = 0, 618, n→ ∞
N−n+1 n+1

la relationLN = L1 FNF−n+ permet de donner l'erreur à l'étape N connaissant l'intervalle initial L1 .

N

Ordre de convergence

Soit une suite {rn } convergente vers r* . L'ordre de convergence de {rn } est déni par p≥0 tel que :

| RK+1 − R∗ |
0 ≤ lim <∞
| RK − R∗ |P

La séquence rK = aK pour 0 < a < 1 est convergente vers 0 avec l'ordre 1. En eet :

| (αK−1 − 0 |
lim = α Dans ce cas p = 1.
| αK − 0 |1

Cette limite est le taux de réduction de l'erreur d'une itération à une autre. Notons qu 'en général la
limite n'est pas connue aussi on utilise alors les majorant de cette erreur.
Soit par exemple a = 0.02 alors r3 = 8 10−6 , r4 = 1.6 10−7 et r5 = 3.2 10−9
K
La séquence RK = a2 0 < a < 1 est convergente vers 0 avec l'ordre 2. En eet :
| RK+1 − 0 |
lim = 1 Dans ce cas p = 2.
| RK − 0 |2
Soit par exemple a = 0.5 alors r3 = 3.9 10−3 , r4 = 1.5 10−5 et r5 = 2.3 10−10
Il est clair que l'erreur dans ce cas tend plus vite vers 0 que dans le premier exemple bien que la valeur
de a est beaucoup plus grande que dans l'exemple 1.
La convergence linéaire est dite de taux t si la limite du rapport est égal à t. Dans l'exemple 1 le taux
est t = 0.02.
3.3.3. Optimisation de fonction à plusieurs variables A.Belahcene

3.3 Optimisation de fonction à plusieurs variables

Nous nous intéressons dans ce chapitre à la résolution des problèmes suivants : min f (x) où x est un
vecteur de Rn et f une fonction de Rn −→ R. Rappelons que maximiser f revient à minimiser −f .
Commençons par donner un exemple de problème se formulant en programme non-linéaire.
Exemple 3.3.1. Une entreprise achète trois produits qu'elle utilise dans un processus de fabrication.
Ses besoins annuels sont connus et constants D = {d1 , d2 , d3 }. Les prix d'achat unitaires des produits
sont U = {u1 , u2 , u3 }. Le coût d'un approvisionnement est supposé indépendant de la quantité com-
mandée et vaut A = {a1 , a2 , a3 }. L'entretien des produits engendre un coût de stockage estimé à 20%
de la valeur des produits en stock. L'entreprise veut connaître les volumes à commander pour chaque
produit à chaque réapprovisionnement. Formuler ce problème comme un programme sans contraintes.
Application numérique : D = {480, 500, 300}; U = {24, 10, 10}; A = {50, 40, 27}
Le réapprovisionnement est fait périodiquement. La période est supposée constante, mais reste à dé-
terminer. La quantité à commander est aussi à déterminer à chaque période. Notons :
qi : la quantité du produit i à commander.
di : le nombre de réapprovisionnement par an.
qi
Ci : le coût d'entretien du stock par unité de temps et par unité de produit.
K(q) : Le coût global formé des coûts de réapprovisionnement et des coûts de stockage.
La consommation étant supposée constante, la quantité moyenne en stock pour le produit i est 0.5 qi .
Pour une année et pour un produit i nous obtenons : coût de stockage égal à 0.5 qi Ci avec Ci = 20%Ui
, le coût d'approvisionnement égal à ai dqii . En résumé, le problème revient à minimiser la fonction non
linéaire K donnée par :
3
X di
K(q1 , q2 , q3 ) = (ai , + 0.5 q, ci )
qi
i=1

Notons que le coût d'achat n'a pas été inclu dans la fonction objective K puisque le coût total d'achat
est une constante et n'inue donc pas sur la solution.
Nous donnons ci-après un ensemble de dénitions et de théorèmes qui nous permettent de mieux
comprendre les développements des méthodes de recherche d'optimums.
Les démonstrations des théorèmes ne sont pas présentées pour éviter d'alourdir le texte, certains
sont donnés en exercice pour d'autres, le lecteur intéressé peut consulter les livres de mathématiques
avancées comme [WYL75], [HUR80], [BAZ79] ou [LUE89].

3.3.1 Dénitions
Dénition 3.3.2. On appelle un ε-voisinage de x0 , V (x0 ), les vecteurs x vériant : (x−x0 )t (x−x0 ) ≤ ε.
La fonction f admet un minimum au point x0 s'il existe un V (x0 ) tel que f (x0 ) ≤ f (x) pour tout x
dans V (x). Dans le cas où ε est inni alors le minimum est global.
∂f
Dénition 3.3.3. On appelle gradient de f le vecteur ∇f ∂f ∂f
=( ,
∂x1 ∂x2
, ... ). La matrice Hessienne
∂xn
∂2f
de f est la matrice Hf dénie comme suit : Hf = (hij ) où hij =
∂xi ∂xj
Dénition 3.3.4. Une matrice A est dénie positive (respectivement semi-dénie) dans un sous en-
semble E de Rn si la forme quadratique X t AX est positive (respectivement positive ou nulle ) pour
tout X 6= 0 et X ∈ E .
Dénition 3.3.5. La fonction f est dite convexe sur un domaine convexe D, si elle vérie la condition
suivante :
∀X, Y ∈ D et λ ∈ [0, 1] f (λX + (1 − λ)Y ≤ λf (X) + (1 − λ)f (Y )
3.3.3. Optimisation de fonction à plusieurs variables A.Belahcene

3.3.2 Théorèmes
Théorème 3.3.6. Une matrice est dénie positive (respectivement semi-positive) si ses valeurs propres
sont positives (respectivement positives ou nulles)
Théorème 3.3.7. Une matrice symétrique A est dénie positive si et seulement si, les déterminants
| Ai | sont positifs, elle est dénie négative si −1i | Ai | sont positifs. Ai est une sous matrice de A
formée de ses i premières lignes et i premières colonnes.
Les théorèmes qui suivent sont la généralisation des théorèmes de la section 3.2.2 , des fonctions à une
seule variable.
Théorème 3.3.8. Si f est continue dans une région fermée et bornée, alors elle admet un maximum
et un minimum dans cette région.
Théorème 3.3.9. Si f (x0 ) est un minimum et si Of existe sur un O(x0 ) alors Of (x0 ) = 0. ( condition
nécessaire d'ordre 1 ).
Théorème 3.3.10. Soient f ∈ C2 (I) et x ∈, Of (x) = 0. Si f (x) est un minimum alors Hf (x) est
semi-dénie positive (condition nécessaire d'ordre 2). Cette condition est susante si Hf (x) est dénie
positive.
Théorème 3.3.11. Soit f ∈ C2 (D) , f est convexe sur un domaine convexe D si et seulement si sa
matrice Hf est semi dénie positive en tout point de D. Si Hf est dénie positive, f est strictement
convexe, la réciproque n'est pas vraie.
Théorème 3.3.12. Si f est convexe sur un domaine convexe D, alors les conditions nécessaires
d'optimalité sont aussi susantes, de plus l'optimum est global sur D.

3.3.3 Résolution directe

La méthode consiste à chercher tous les points critiques (verier les conditions nécessaires voire théo-
rème (3.3.9)) puis à vérier pour chacun d'eux si les conditions d'optimalité locale (théorème (3.3.10)
) ou globale (théorèmes 3.3.11 et (3.3.12)) sont vériées. Or la recherche des points critiques est dif-
cile puisqu'il faut résoudre des systèmes d'équations non linéaires qui font le plus souvent appel à
des méthodes numériques d'approximation. De plus cette méthode suppose l'existence des dérivées
partielles.
Soit les problèmes suivants :
1. Minimiser f (x, y) = x2 + y 2 − xy + y − x
2. Minimiser g(x, y, z) = x(y − 1) + z 3 − 3z
3. Reprendre l'énoncé de l'Exemple 3.3.1
Résolution par la méthode exacte.
1. Le gradient de f est Of (x, y) = (2x − y − 1, 2y − x + 1) 
Comme Of (31 , − 13 ) = (0, 0). Ce point
2 −1
est donc stationnaire. De plus la matrice hessienne Hf = , est dénie positive car
−1 2
les déteminants des mineurs principaux ( | A1 |= 2 et | A2 |= 3), sont positifs dans R2 voir
3.3.6, donc en particulier au point ( 31 , − 13 ) voir théoreme (3.3.10). La fonction f étant convexe
il s'ensuit que f ( 13 , − 31 ) = − 31 est un minimum global voir théorème (3.3.11).
2. Les points X = (0, 1, 1) etY = (0, 1, −1)  sont des points critiques. On vérie que Og(x) =Og(y) =
0 1 0
0, mais la matrice Hf =  1 0 0  n'est semi-dénie positive en aucun point de R3 , le dé-
0 0 6z
terminant du mineur d'ordre 2 (| A2 |= 3) est négatif, en particulier aux points X = (0, 1, 1)
et Y = (0, 1, −1). Par conséquent f (X) et f (Y ) ne sont pas des minimums (voir théorème
(3.3.10)). En eet la valeur de f peut être innie négative pour des valeurs xées de x et y , et
pour z inni négatif.
3.3.3. Optimisation de fonction à plusieurs variables A.Belahcene

3. La fonction objective du problème de l'Exemple 3.3.1 est :

minK = 24000 q1−1 + 20000 q2−1 + 8100q3−1 + 2.4 q1 + q2 + q3 avec q1 , q2 , q3 ≥ 0

Cherchons les points stationnaires (points vériant) : 5K = (2.4 − 24000

2 ,1 −
20000 , 1 − 8100 ).
2 2
q1 q2 q3
Le gradient 5K s'annule pour les valeurs q1 = 100, q2 = 141.4 et q3 = 90 (on rejette les valeurs
négatives de qi ).
La matrice Hessienne HK est diagonale et admet des valeurs propres positives suivantes : λ1 =
48000 q1−3 , λ2 = 40000 q2−3 et λ3 = 16200 q3−3 donc HK (X) est dénie positive. De plus K est convexe
dans R+ 3 , par suite K(q , q , q ) est un minimum global. Notons que nous pouvons résoudre ce pro-
1 2 3
blème, en le considérant comme un programme avec contraintes (non négativité des variables) et en
utilisant les méthodes développées dans le chapitre suivant.

3.3.4 Résolution itérative

L'algorithme général de recherche de
minimum d'une fonction f par les mé- Xk dk Xk+1
thodes itératives est la recherche de d
k+1
suite de points intermediares avant de Xk+2
de chisoire nal : ( voir gure suivante
(3.1) , il )
1. Choisir un point initial (Xk , k =
0);
2. Déterminer la direction de dé-
placement dk qui assure l'amé-
lioration de la solution présente
(si elle n'est pas optimale) ;
3. Déterminer le point Xk+1 , qui
est le meilleur sur la direction
choisie dk ;
4. L'algorithme s'arrête lorsque | d
f (Xk ) − f (Xk+1 ) | ≤ , ou en-
core ||Xk − Xk+1 || ≤  et  ≥ 0. Figure 3.1  Déplacement retenu

Le choix du point minimum initial reste

un problème en lui-même. En outre si
la fonction n'est pas convexe et que le point initial est loin de l'optimum, la convergence peut se faire
vers un point qui est un optimum local ou un point uniquement stationnaire.
En général, si on n'a pas de connaissance susante sur la fonction, on prend un ensemble de points au
hasard et on choisit le meilleur comme point initial.
Le critère le plus utilisé est | f (Xk ) − f (Xk+1 ) |≤  pour sa simplicité. D'autres critères d'arrêt
peuvent être choisis , par exemple la norme du vecteur d'amélioration, k X − Xk+1 k≤  , ou encore
k 5f (Xk ) k≤ 
Notons que |f (X∗) − f (Xk )| ne peut être utilisé comme critère d'arrêt puisque f (X∗) n'est pas connu
( f (X∗) désigne la valeur optimale de f ). Il en est de même pour la distance entre X∗ et X .
Ces méthodes remplacent uniquement la résolution du système d'équations non linéaires 5f (Xk ) = 0
de la résolution algébrique et par conséquent l'optimalité locale (à fortiori globale) n'est pas assurée.
3.3.3. Optimisation de fonction à plusieurs variables A.Belahcene

Méthode de la plus forte descente

C'est la méthode la plus ancienne et la plus largement utilisée. Soit X0 une solution réalisable initiale.
On choisit la direction d'amélioration dk telle que dk = − 5f (Xk ). La plus grande pente est donnée par
la direction du gradient. Le point Xk+1 , solution à l'étape k + 1, est obtenu par l'algorithme suivant :
Xk+1 = Xk − α 5f (Xk ). Le paramétre α, est un réel positif, il est déterminé de sorte que f (Xk+1 )
soit minimum. La marge d'erreur  étant choisie, l'algorithme s'arrête lorsque | f (Xk ) − f (Xk+1 ) |≤  .
Soit le problème min f (x, y) = x2 + y 2 − xy + y − x Utiliser la méthode de la plus forte descente pour
résoudre ce problème. Prendre X0 = (1, 2) comme solution réalisable initiale et  = 0.001.
On note Xk la solution à l'étape k, f (Xk ) la valeur de la fonction objective à l'étape k, Ek = f (Xk ) −
f (Xk+1 ) l'erreur pour critère d'arrêt et dk direction de déplacement à partir du point Xk .
g(α) = f (Xk + αdk ) avec g(αk ) = min g(α) telque α ≥ 0
Nous avons f (X0 ) = 4 et 5f (1, 2) = (−1, 4). Donc la meilleure direction de recherche à partir de X0
est d1 = − 5 f (1, 2) = (1, −4).
Soit X1 le meilleur point sur cette direction. On a X1 = X0 + α1 d1 , où α1 minimise f (X1 ) =
f (α + 1, 2 − α) = g(α) donc g(α) = 21α2 − 17α + 4. Notons que g est convexe sur R puisque
g 0 (α) = 42α − 17 et g 00 (α) = 42. Par conséquent g(0.4) est un minimum global puisque g 0 (α) = 0 et
g 00 (α) > 0. On retient α1 = 0.4
Ce qui donne X1 = (1.4, 0.38), f (X1 ) = 0.56 et E0 = f (X0 ) − f (X1 ) = 3.44 > . On cherche alors
X2 . La direction de recherche est d2 = −∇f (X1 ) = (−1.1, −0.36) et X2 = X1 + α2 d2 où α2 minimise
g(α2 ) = f (X2 ).
La Table 3.1 résume les résultats obtenus. Voir
Si la fonction g(α) possède plusieurs minima sur la direction dk , on choisit le plus petit d'entre eux.
K XK f (XK ) EK dK αk

0 (1, 2) 4 - ( 1 , -4 ) 0.4
1 (1.4, 0.38) 0.56 3.44 ( -1.1 , -0.36 ) 0.8
2 (0.5 , 0.1) -0.19 0.75 ( 0.1 , -0.7 ) 0.5
3 (0.55 , -0.25) -0.3 0.1 ( -0.35 , -0.05 ) 0.44
4 (0.39 , -0.23) -0.325 0.025 ( -0.01 , -0.15 ) 0.51
5 (0.38 , -0.31) -0.332 0.007 ( -0.11 , 0 ) 0.34
6 (0.34 , -0.31) -0.333 0.001  

Table 3.1  Méthode du Gradient pour l'exemple

Méthode de la direction cyclique

Cette méthode dière de la précédente quant au choix de la direction de déplacement. Au lieu de

prendre la direction opposée au gradient, on choisit la direction du premier axe de coordonnées, puis
la direction du deuxième axe et ainsi de suite.
Cette méthode est plus facile à mettre en oeuvre et à programmer puisque il n 'y a pas de recherche
de gradient, qui peut être dicilement déterminé de façon automatique. De plus il y a moins de calcul
à faire à chaque itération, cependant le nombre d'itérations est plus important.
Soient X0 le point initial et Xk le point courant à l'étape k. On détermine une suite de n points
y1 , y2 . . . yn de la façon suivante : Y0 = Xk ; Yi+1 = Yi + αi di et Yn = Xk+1 où di est la direction selon
3.3.3. Optimisation de fonction à plusieurs variables A.Belahcene

X0

X0(1, 2)
X1(1.4, 0.38)
X2(0.5, 0.1)
X3(0.55, −0.25)
X*(0.33, −0.33)

X1
X2

11
00 X3
00
11
00
11
X*

Figure 3.2  Chemin suivi par la Résolution (Gradient)

le i eme axe à partir du point Yi . Autrement dit, di = (0, 0, · · · 0, 1, · · · 0). Le nombre 1 est à la ieme
position. αi est la valeur de α minimisant l'expression f (Yi + αdi ).
On n'a pas besoin d'ajouter un indice k (correspondant au point Xk ) au vecteur di car celui ci est
toujours le même pour toutes les itérations de Xk . On garde le même critère d'arrêt que la méthode
précédente.
Ainsi, dans le cas d'une fonction f à 2 variables on obtient :

X0 = Y0 → Y1 → Y2 = X1

X1 = Y0 → Y1 → Y2 = X2

...

Xk = Y0 → Y1 → Y2 = Xk+1

Cette procédure se répète jusqu'à ce que l'amélioration d'une étape à une autre soit jugée susamment
petite.
Utiliser la méthode des directions cycliques pour résoudre le problème min f (x, y) = x2 +y 2 −xy+y−x.
Prendra pour solution réalisable initiale X0 = (1, 2) et une erreur  = 0.001
Nous partons du même point que pour la méthode précédente, et on utilise le même critère d'arrêt de
manière à faire une comparaison entre les 2 méthodes. Voir la gure
Soit X0 = (1, 2), les directions de déplacement sont d1 = (1, 0) puis d2 = (0, 1) à partir de n'importe
quel point Xk .
On initialise Y0 par Xk . On détermine Y1 et Y2 en utilisant les directions d1 et d2 ,Y2 prendra la valeur
de Xk+1 .
On a Y0 = X0 = (1, 2) et Y1 = Y0 + α1 d1 . Le minimum global de g(α) = f (1 + α, 2) = α2 − α + 4 est
donné par α = 0.5 d' où Y1 = (1.5, 2).
3.3.4. Série d'exercices A.Belahcene

k Xk f (Xk ) Ek dk Y
0 (1,2) 4 - 1, 0 1.5 , 2
0, 1 1.5 , 0.25
1 ( 1.5 , 0.25 ) 0.69 3.31 1, 0 0.62 , 0.25
0, 1 0.62 , -0.19
2 ( 0.62 , -0.19 ) -0.27 0.96 1, 0 0.4 , -0.19
0, 1 0.4 , -0.3
3 ( 0.4 , -0.3 ) -0.31 0.04 1, 0 0.35 , -0.3
0, 1 0.35 , -0.32
4 ( 0.35 , -0.32 ) -0.33 0.02 1, 0 0.33 , -0.33
0, 1 0.33 , -0.33
5 ( 0.33 , -0.33) -0.333 0.00

Table 3.2  Méthode cyclique de l'exemple

X0
X0(1, 2) Y

Y(1.5, 2)
X1(1.5,0.25)
Y(0.62, 0.25)
X2(0.62, −0.19)

Y X1

X2
X*

Figure 3.3  Chemin suivi par la Résolution (Cyclique)

De même, de Y1 on se déplace selon la direction d2 = (0, 1). On obtient Y2 = (1.5, 0.25) = X1 ,

f (X1 ) = 0.69 et E0 = f (X0 ) − f (X1 ) = 3.31.
Les résultats des diérentes étapes sont regroupés dans le Table 3.2
La deuxième méthode nécessite, certes, plus d'étapes que la précédente, pour une précision donnée.
Mais les calculs faits à chaque étape restent plus simples puisqu'il n' y a pas de calcul de gradient. Par
conséquent, la deuxième méthode est, en général, plus rapide et aussi plus facile à mettre en oeuvre.

3.4 Série d'exercices

1. Résoudre analytiquement les problèmes suivants :

2. max Z = x(5 − πx) sur l'intervalle [0, 20] puis sur l'intervalle [0,5]
a) max Z =| x2 − 8 | sur [-4, 4] min Z = −x − exp(x2 )
3. Donner la nature des optimas def (x) = x3 − 6x2 + 9x + 6 sur les intervalles suivants : [0, 3], [1,
4] et [-1, 5].
3.3.4. Série d'exercices A.Belahcene

4. Démontrer les théorèmes du cours concernant l'optimalié locale et globale des fonctions à une
variable n fois dérivables.
5. Utiliser la méthode des trois points pour résoudre les problèmes : max Z = x(5π − x) sur[0, 20]
avec une erreur sur la variable inférieure à 1. min Z = x5 −5x sur [1, 2] puis sur [−1, 2] avece = 0.5
. Que peut on conclure ? Donner le nombre d'itérations susantes dans chaque cas.
6. Reprendre les exercices 1 et 2 en utilisant la méthode de Fibonacci, e = 0.5.
7. Chercher le minimum de f (x) = x3 − 6x2 + 9x + 6 sur [−3, 7]et [−1.5, 6.5] avec les méthodes
des 3 points et de Fibonacci. Expliquer les résultats.
√ √
8. Montrer que le terme général de la suite de Fibonacci peut s'ecrire : Fn = √1 ([ 1+ 5 ]N +1 -[ 1− 5 ])
5 2 2
√
En déduire que lim FFn−1
n
= [ 1+2 5 ]= 0.618
9. Donner l'ordre et le taux de convergence de la méthode des trois points et de Fibonacci. En
supposant la convergence de la suite {xn } avec a > 0 , quelle est son ordre de convergence de
1
la suite Xn−1 = (Xn + Xa )
2 n
10. Etudier la convexité et la concavité des fonctions données dans les exercices 1 et 2. Les optimums
sont-ils globaux ?
11. Montrer que l'intersection de 2 ensembles convexes est convexe. Montrer que tout demi-espace
AX ≤ b est convexe. (A est une matrice n ∗ n, x et b des n-vecteurs). Montrer que le polyèdre,
domaine de réalisation d'un programme linéaire, est convexe.
12. Utiliser la dénition pour montrer la convexité de f(x) = x2 , ∀ x∈ R. Montrer que f(x) = x4
est strictement convexe dans R bien que f(0)= 0.
13. Soit fi pour i ∈ I , un ensemble de fonctions convexes sur un domaine convexe D. Montrer que
la fonction g dénie par g(x) = sup fi (x) est convexe sur D.
14. Soient g une fonction à une variable, monotone non décroissante, convexe et f une fonction
convexe, dénie sur une région D. Montrer que g(f ) dénie par g(f (X)) pour X ∈ D est
convexe.
15. Donner, si possible le domaine de convexité ou de concavité des fonctions suivantes, et utiliser
la méthode algébrique pour trouver les minimums, s'ils existent, des fonctions de l'exercice
précédent.
x + y2
sin(xy) − cos(x − y)
x2 + y
(2x − 5)2 − (y − 3)2 − (5z − 2)2
10 − 2(y − x2 )2
x2 (y − 1) + z 3 − 3z
(x − 2)2 + (y − π) + 10
16. Résoudre graphiquement le problème :

Sachant que la solution sature la contrainte (1), max Z = (250 − x)x + (250 − y)y
rendre le problème sans contrainte, puis le résoudre.
x + y ≤ 100
Reprendre le problème avec la fonction max Z =
(300 − x)x + (100 − y)y . 8x + 3y ≤ 600
(x, y) ∈ R2
17. Soit le problème max Z = −6x + y 2 tel que x2 + y 2 = 4. Trouver le problème à une variable
équivalent, puis le résoudre.
18. Utiliser la méthode de la plus forte descente pour trouver les minima s'ils existent, des fonctions
suivantes. Les valeurs initiales sont données par x0 . On prend ε = 0.05. Faire d'abord une
résolution algebrique si possible. Donner d'autres directions améliorantes. (x − 2)4 − (x − 2y)2
pour x0 = (0, 3), (x − 2)2 − (y − π)2 + 10 pour x0 = (1, 1) et sin(xy) + cos(x − y) pour
x0 = (0.5, −0.4)
19. Reprendre l'exercice précédent en utilisant la méthode des directions cycliques.
3.3.4. Série d'exercices A.Belahcene

20. Résoudre algebriquement le problème : min Z = xy + t2 . Résoudre avec la méthode de la

plus forte descente avec les points initiaux : (1, −1, 0) , (−1, −1, 0) et (−1, −1, 1). Justier les
diérences entre les solutions trouvées.
21. Soit le problème min x2 − xy + 2y 2 − 2x + ex+y . Donner les points vériant les conditions
nécessaires d'optimalité. Ces points sont ils des solutions locales ou globales ? x = (0, 0) est il
une solution optimale ? Dans le cas contraire trouver une direction d qui améliore la solution .
Trouver itérativement la solution, prendre pour critère d'arrêt k 5 f (X) ≤ 0.5k. Utiliser la
méthode du gradient et la méthode des coordonnées cycliques.
22. Pour approximer une fonction g sur l'intervalle [0, 1]R par un polynome Pn (degré≤n) on minimise
l'erreur (méthodes des moindres carrés) f (a) = 01 [g(x) − p(x)]2 dx. Donner les équations à
résoudre pour trouver le vecteur optimal a. Vérier que la solution est optimale globale a =
n
(a0 , a1 ......an ) et p(x) = aj xj . Faire une application avec n = 2 et g(x) = sin(πx).
X

0
23. Soit la fonction f (x, y) = 5x2 + 5y 2 − xy − 11x + 11y + 11. Mettre f (X) sous forme matricielle, Q
1
est symétrique, f (X) = XQX + AX + C . Soit t = E(Xk+1 )/E(Xk ) la vitesse de convergence
2
de la méthode du gradient. Pour un problème quadratique on montre que t ≤ (A − a)2 /(A + a)2 .
Trouver t pour ce problème où A et a sont la plus grande et la plus petite valeur propre de Q.
si X∗ est la solution optimale et E(Xk ) est l'erreur f (X∗) − f (Xk ).
Soit X0 = (0, 1) le point initial. Combien d'étapes sont elles susantes pour amener la valeur
de f à 10−10 ? Que se passe-t-il dans le cas où Q admet les mêmes valeurs propres ? Trouver
Xk telle que f (Xk ) ≤ 10−5 avec la méthode du gradient puis avec la méthode des coordonnées
cycliques. Comparer vos résultats. Donner la solution algébriquement.