OPTIMISATION NUMÉRIQUE

(OPTIMISATION LINÉAIRE
SOUS CONTRAINTE)

SEDDIK ILIAS INTTIC

 INTRODUCTION
• En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes
d'optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la
plupart des résultats présentés ici sont également vrais si l'objectif est une fonction monotone
croissante de chaque variable considérée.
• Le terme programmation linéaire suppose que les solutions à trouver doivent être représentées
en variables réelles. S'il est nécessaire d'utiliser des variables discrètes dans la modélisation du
problème, on parle alors de programmation linéaire en nombres entiers (PLNE). Il est
important de savoir que ces derniers sont nettement plus difficiles à résoudre que les PL à
variables continues.
 OPTIMISATION AVEC CONTRAINTES

Méthode de substitution:
 Définir les différentes variables , , …;

 Écrire l'objectif en fonction des variables ;

 Écrire toutes les contraintes ;

 Exprimer, en utilisant les contraintes, toutes les variables en termes d'une seule

 (par exemple(),(), ….);

 Substituer ces expressions dans l'objectif ;

 Optimiser.
 OPTIMISATION LINÉAIRE

Problème linéaire(exemple)
Une firme a le projet de construire deux produits nécessitant l'utilisation de 3 machines. la machine A ne
peut travailler que 150 heures par mois, la machine B, 210 heures, et la machine C, 180 heures. Le premier
produit P1 nécessite 1 heure de la machine A et 1 heure de la machine B et il est vendu 300$ à l'unité. Le
second produit P2 nécessite 1 heure de la machine A, 3 heures de la machine B et 3 heures de la machine C
et il est vendu 500$ à l'unité. La firme cherche à définir le programme de fabrication lui permettant de
rendre maximal son bénéfice.
 OPTIMISATION LINÉAIRE

Problème linéaire(exemple)

Produit P1 Produit P2 Disponibilité

(heure/mois)
Machine A 1 1 150
Machine B 1 3 210
Machine C 3 3 180
Prix de vente 300$ 500$
 OPTIMISATION LINÉAIRE

Problème linéaire(exemple)
Une modélisation mathématique conduit à appeler x le nombre de produits P1 à fabriquer et y le nombre de
produits P2 ; M sera le point de coordonnées (x, y). Les contraintes de fabrication s'expriment à l'aide des
inégalités suivantes :

Étant donné que l’objectif est de maximiser le chiffre d’affaire, notre fonction objectif sera:
max f(x,y) = 300x+500y
 OPTIMISATION LINÉAIRE

Problème linéaire(exemple)
La solution optimale de notre problème sera logiquement l’un
des sommet de notre polyèdre (qui est toujours convexe).
Une méthode intéressante est celle de la droite d’iso-valeur,
qui consiste à dessiner une série de droite définies par la
fonction objectif, celle qui donne la valeur la plus haute (en
cas de maximisation) dans la région des solutions admissibles,
touchera notre solution optimale.
Appliqué à notre problème, on trouvera:
x = 120, y = 30
 OPTIMISATION LINÉAIRE

Problème linéaire(exemple)
Une optimisation linéaire en dimension deux consiste en général à dessiner l'ensemble admissible (polygone
convexe borné ou non) et à chercher la meilleure position d'une droite de direction fixée pour rendre
maximale ou minimale une valeur donnée. Cette droite, si elle existe passe toujours par un sommet du
polygone. Dans une optimisation linéaire de dimension trois, l'ensemble admissible est un polyèdre et
l'optimisation consiste à trouver la meilleure position d'un plan de direction fixée.
 OPTIMISATION LINÉAIRE

Problème linéaire
• Le problème devient plus complexe en dimension supérieure où une résolution graphique est
inenvisageable et nécessite des outils demandant une formalisation sous forme matricielle.
• Une formalisation canonique est nécessaire

• Les contraintes se résument à . La fonction revenu net est qu’il faut maximiser. La formalisation
canonique s’écrit:
 OPTIMISATION LINÉAIRE

Problème linéaire
• II est parfois utile de remplacer l’inégalité définissant l’ensemble admissible par une égalité. Cela
peut se faire en augmentant la dimension d’étude du problème. Dans l’exemple ci-dessus, les
trois inégalités se traduisent par trois égalités et trois contraintes positives sous la forme suivante

• II suffit alors de poser

 OPTIMISATION LINÉAIRE

Méthode du Simplexe
 C’est une méthode de résolution en nombre fini d’étapes d'un
problème d'OL
L'algorithme a une interprétation géométrique simple. Les itérés
sont des sommets de l'ensemble admissible (un polyèdre convexe). En
un sommet, l'algorithme détermine une arête (face de dimension 1) de
l'ensemble admissible le long de laquelle la fonction-coût décroît et
prend comme nouvel itéré le sommet situé au bout de l'arête
sélectionnée.
 Il peut y avoir plusieurs arêtes permettant de faire décroître la
fonction-coût. L'algorithme choisit une arête le long de laquelle la
fonction-coût décroît le plus.
 OPTIMISATION LINÉAIRE
Algorithme du Simplexe
• Algorithme du simplexe révisé - On suppose au départ que l’on dispose d’un sommet de et
d’une base d’indices associée . Une itération calcule un nouveau sommet et une nouvelle base
d’indices , à moins qu’il ne soit observé que est solution ou que
le problème est non borné
1. On calcule le multiplicateur , solution du système linéaire

et on en déduit le cout réduit

2. Optimalité: Si , on s’arrête : est solution du problème

3. Direction de descente: Soit un indice tel que , respectant une règle d’anti-cyclage. On définit
la direction de descente du critère par

où est le j-ième vecteur de base de

 OPTIMISATION LINÉAIRE
Algorithme du Simplexe
• Algorithme du simplexe révisé –
4. Problème non borné. Si , on s’arrête car le problème n’est pas borné :
lorsque
5. Pas maximal. On calcule le pas maximal jusqu’à la frontière de l’ensemble admissible par

Ce pas peut être nul. On note un des indices donnant le minimum ci-dessus et respectant une
règle d’anti-cyclage
6. Nouveau sommet. .
7. Nouvelle base d’indices.
 OPTIMISATION LINÉAIRE
Algorithme du Simplexe
Convergence:
Si le problème d’optimisation PL est réalisable, (
𝑎𝑙𝑜𝑟𝑠 𝑙′𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚𝑒 𝑑𝑢 𝑠𝑖𝑚𝑝𝑙𝑒𝑥𝑒 𝑐𝑜𝑛𝑣𝑒𝑟𝑔𝑒𝑟𝑎 𝑒𝑛 𝑢𝑛 𝑛𝑜𝑚𝑏𝑟𝑒 𝑓𝑖𝑛𝑖 𝑑 ′é𝑡𝑎𝑝𝑒𝑠, soit en trouvant
une solution sur un sommet, soit en déterminant que la solution est non bornée.

Initialisation:
• Le point est un sommet de l’ensemble admissible du problème ci-dessus, lequel a toujours une
solution. Si ce problème est résolu par l’algorithme du simplexe en partant de ce point, il
obtient pour solution un point . Si , le problème n’est pas réalisable. Si est un sommet de
l’ensemble admissible de

– où est la matrice diagonale définie par si et sinon. On peut utiliser pour cela l’algorithme du
simplexe, démarrant en , qui est un sommet de son ensemble admissible
 OPTIMISATION LINÉAIRE
Algorithme du Simplexe
Étape 0 : On forme le tableau initial

1 0 0
0 1 0

. 0 0 1
0 0 0 0

• La base initiale de l'espace-colonne sera , , …, .

• Les autres variables seront égales à 0 ce qui correspond au point de départ x=(0,0,…,0)
 OPTIMISATION LINÉAIRE
Algorithme du Simplexe
Étape 1: On doit choisir la colonne de pivot.

• Pour cela, on choisit l'indice j tel quel.

• Si aucun choix n’est possible, on a atteint la solution optimale et l'algorithme se termine. Sinon, on passe à
l'étape suivante. Pour un problème de minimisation, on modifie le critère en choissisant l'indice tel que:

Étape 2: On doit choisir la ligne de pivot.

•
Pour cela, on choisit l'indice i en utilisant le critère du quotient:

• où est la colonne de pivot de l'étape 1 .

 OPTIMISATION LINÉAIRE
Algorithme du Simplexe
a) On applique la procédure d'élimination de Gauss-Jordan autour du pivot situé à l'intersection de la ligne
et de la colonne . Ensuite, on divise la ligne par le pivot pour le mettre égal à 1 .
b) On retourne à l'étape 1 et on recommence.
 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe

Ex: Ex:
s.c. s.c.

Variables de base: Variables hors base

si Alors:
 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe
Étape A: Le tableau initial se construit de la manière suivante:
 L'encadré bleu correspond aux coefficients des contraintes du (PL=).
 L'encadré vert correspond aux est-à-dire les coefficients dans .
Exemple pour la colonne de nommée :
• Les encadrés roses correspondent aux coefficients des variables dans la fonction objectif .
L'encadré gris correspond à la valeur des variables de base.
L'encadré orange correspond à la valeur de , donc la valeur de la fonction objectif qui se calcule de la façon
suivante :
 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe
Étape B: choix de la variable entrante (dans la base):
Maximum des pour des problèmes de max.
Minimum des pour des problèmes de .
Dans notre exemple : a le plus grand donc, il entre dans la base.

• Nb: Souvent, l’expression inverse qui est utilisée, il suffira de choisir inversement.
 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe
Étape C: Choix de la variable sortante:
Dans un problème de ou de max, la variable sortante sera le minimum des

Dans notre exemple, nous devons évaluer:

c est le minimum, donc est la variable qui sort de la base.

 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe
Étape D: pivotage

• La cellule bleue est nommée le pivot. Pour passer au tableau suivant et donc effectuer la première
itération, il est essentiel d'utiliser le pivot.
• Nous poursuivons avec la matrice identité pour les variables de base. Nous inscrivons 1 à
l’intersection de chaque variable et 0 ailleurs.
 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe
Étape D: pivotage
• Nous devons calculer les nouvelles valeurs pour les cases restantes à partir du tableau précédent

• Dans notre exemple, le 10 contenu dans l'encadré rouge provient de la formule suivante:

donc .
Faisons un autre exemple avec I'encadré vert. Nous obtenons de la façon suivante:
 OPTIMISATION LINÉAIRE
Exemple explicatif du Simplexe
Critères d’arrêt:
Nous arrêtons lorsque nous obtenons le critère d'optimalité. L'algorithme du simplexe s'arrête lorsque:
0 pour un problème de max
0 pour un problème de min
 OPTIMISATION LINÉAIRE
Exemple d’application du Simplexe
Max Z = 5 + +

sous les contraintes

2 X1 + 3 X2 + 1 X3 ≤ 5
2 X1 + 3 X2 + 1 X3 + 1 X4 = 5
4 X1 + 1 X2 + 2 X3 ≤ 11
4 X1 + 1 X2 + 2 X3 + 1 X5 = 11
3 X1 + 4 X2 + 2 X3 ≤ 8
3 X1 + 4 X2 + 2 X3 + 1 X6 = 8
0 X1 + 0 X2 + 0 X3 ≤ 0
0 X1 + 1 X7 = 0

X1, X2, X3 ≥ 0 X1, X2, X3, X4, X5, X6, X7 ≥ 0

 OPTIMISATION LINÉAIRE
Exemple d’application du Simplexe
Exemple avec
La variable qui sort de la base est P4, et celle qui entre est P1.
 OPTIMISATION LINÉAIRE
Exemple d’application du Simplexe
Exemple:
La variable qui sort de la base est P6, et celle qui entre est P3.
 OPTIMISATION LINÉAIRE
Exemple d’application du Simplexe
Exemple: Aucune variable de base ne peut être remplacée en augmentant la fonction

La solution optimale est Z = 13

X1 = 2
X2 = 0
X3 = 1
Exécutez l’exemple ici
 OPTIMISATION LINÉAIRE
Variantes de l’algorithme du Simplexe
Méthode des 2 phases: L’objectif est de trouver une solution de base admissible qui servira de
point de départ pour l’algorithme du simplexe. L’idée est de résoudre un problème intermédiaire
de minimisation dont la solution fournira le point de départ de la méthode du simplexe. Ce
problème intermédiaire porte le nom de Phase I du simplexe.
Elle peut-être très utile pour éviter les cas de solution de départ irréalisables sur l’algorithme du
simplexe basique.
 OPTIMISATION LINÉAIRE
Variantes de l’algorithme du Simplexe
Méthode du grand M: Cette technique combine les phases I et II de manière à ne devoir
résoudre qu'un seul problème d'optimisation linéaire, à savoir le problème

• où est pris comme dans la technique des deux phases et est une constante choisie «
suffisamment grande ». On ne connait pas a priori la valeur qu'il faut donner à pour que le
problème soit équivalent au problème , c'est-à-dire pour qu'en une solution du problème on ait
. Le raisonnement suivant montre pourquoi ils le seront si est « suffisamment grand».
Méthode du simplexe dual: Le concept de dualité des problèmes d’optimisation peut être très
utile à exploiter en collaboration avec l’algorithme du simplexe.
 OPTIMISATION LINÉAIRE
Dualité dans les problèmes linéaires
• Considérons à nouveau un problème d’optimisation linéaire sous forme canonique

où , et où les , les , et les

sont des constantes réelles.
A supposer que le problème possède au moins une solution optimale , la méthode du simplexe
permet, à chacune de ses étapes, d’obtenir (et d’améliorer) une borne inférieure sur la valeur
optimale de la fonction objectif.
• Une question naturelle, mais qui va dans la direction opposée, est celle de savoir s’il est
possible d’obtenir une borne supérieure sur la valeur , et cela sans être obligé de parcourir
l’algorithme du simplexe jusqu’à ce qu’il aboutisse à une solution optimale (approximation)
 OPTIMISATION LINÉAIRE
Dualité dans les problèmes linéaires
• Le problème dual du précédent est le problème:

On dit aussi que (10.1) est le problème primal de (10.3).

Remarquons que sous forme matricielle, les problèmes primal et dual s’écrivent donc

• Remarquons aussi que le problème dual est équivalent au problème d’optimisation linéaire sous
forme canonique
 OPTIMISATION LINÉAIRE
Algorithme du simplexe dual :

La méthode du simplexe dual (C.E. Lemke 1954, E.M.L. Beale 1954) consiste à appliquer la
méthode du simplexe au problème dual en travaillant avec des solutions de base qui ne sont
pas nécessairement positives (donc pas nécessairement réalisables)
 OPTIMISATION LINÉAIRE
Algorithme du simplexe dual :

Dans la méthode du simplexe dual, on ne travaille pas explicitement avec le problème dual
mais bien avec le problème primal.
A chaque itération, on détermine les indices :
i ∈ B vérifiant
et j ∈ H vérifiant

On choisit alors xj comme variable primale entrante et xi comme variable primale sortante.
 OPTIMISATION LINÉAIRE

Comparaison simplexe primal/dual :

Algorithme primal: On passe de solution de base primale réalisable en solution de base

primale réalisable Et on stoppe dès que l’on a atteint une base B qui est duale réalisable (coûts
réduits ≥ 0)

Algorithme dual: On passe de base duale réalisable en base duale réalisable Et on stoppe dès
que l’on a atteint une solution de base primale réalisable ( 𝐵 −1 𝑏 ≥ 0)
 OPTIMISATION LINÉAIRE
L'algorithme primal du simplexe :
• Phase 1 : on trouve une solution primal réalisable B B' et B adjacentes =
ne diffèrent que d'une
• Phase 2 :
colonne
1. si B est aussi dual réalisable alors stop. retourner B
2. sinon soit on a une preuve d'infinitude, soit on change de base : on trouve B'
adjacente à B, primal réalisable et meilleure que B
3. remplacer B par B' et retour en 1 .

L'algorithme dual du simplexe

• Phase 1 : on trouve une solution dual réalisable B
• Phase 2 :
1. si B est aussi primal réalisable alors stop. retourner B
2. sinon soit on a une preuve de non-réasibilité du primal (infinitude du dual), soit on
change de base : on trouve B' adjacente à B, dual réalisable et meilleure que B
3. remplacer B par B' et retour en 1 .
 OPTIMISATION LINÉAIRE
Exemple (Pb du pharmacien) :

de poudre laboratoire 1 laboratoire 2 II lui faut au moins

vitamine A 20 unités 5 unités 25 unités de vitamine A
vitamine B 30 unités 20 unités 60 unités de vitamine B
vitamine C 5 unités 10 unités 15 unités de vitamine C
coût 6 9

 Un 3ème laboratoire décide de commercialiser les vitamines A, B, C séparément. II lui faut trouver
le prix yA,yB,yC pour chaque unité de vitamine.
 Pour être concurrentiel avec le laboratoire 1 il faut : 20yA+30yB+5yC≤6 du laboratoire 1
 Pour être concurrentiel avec le laboratoire 2 il faut : 5yA+20yB+10yC≤9.
 Le laboratoire désire maximiser les gains en vendant ses vitamines au pharmacien
 OPTIMISATION LINÉAIRE
Exemple (Pb du pharmacien) :

du pharmacien : se fournissant auprès des laboratoires 1 et 2 préparer sa potion à un moindre coût

pb primal

Pb du concurrent des laboratoires 1 et 2 : trouver le juste prix des vitamines

pb dual s.c.
 OPTIMISATION LINÉAIRE
Exemple (Pb du pharmacien) :

Solutions: à exécuter ici

Pb primal: x1 = 1.5, x2 = 0.75 ; min f(x1,x2) = 15.75

Pb dual: y1 = 0, y2 = 0.075, y3 = 0.75; max f(y1,y2,y3) = 15.75

 OPTIMISATION LINÉAIRE
Méthodes de points intérieurs

Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre
des problèmes d’optimisation mathématique. Elles ont l'intérêt d'être polynomiales lorsqu'on les
applique aux problèmes d'optimisation linéaire, quadratique convexe, semi-définie positive.
Les méthodes de points intérieurs se répartissent en plusieurs familles :

 les méthodes « affine scaling » (optimisation sur des ellipsoïdes) ;

 les méthodes de réduction du potentiel (notion de barrière, chemin central, relaxation)

 OPTIMISATION LINÉAIRE
Méthodes de points intérieurs

Contrairement à l’algorithme du simplexe dont les sommets sont itération du polyèdre

convexe défini par des contraintes, donc appartenant à la limite de ce polyèdre, les méthodes
de point intérieur génère une itération à l’intérieur relative de tous admissibles. L’un des plus
Courrent en œuvre est l’algorithme prédicteur-correcteur.

Le succès des méthodes de points intérieurs pour la résolution des problèmes de

programmation linéaire entraina son extension aux problèmes de programmation non linéaires
et en particulier aux problèmes de programmation quadratique convexes, ainsi qu’aux
problèmes non linéaires convexe.
 OPTIMISATION LINÉAIRE
Méthodes de points intérieurs
Algorithme de Karmarkar(1984)
C’est le premier algorithme de points intérieurs réellement efficace pour traiter des problèmes
linéaires en un temps polynomial.
Soit le problème d’optimisation linéaire sous forme matricielle suivant
avec
 OPTIMISATION LINÉAIRE
Méthodes de points intérieurs
Algorithme de Karmarkar(1984)
 OPTIMISATION LINÉAIRE
Méthodes de points intérieurs
Algorithme de la barrière logarithmique
 SUPPORTS COMPLÉMENTAIRES
 Concept de contraintes
 Programmation linéaire
 Résolution graphique
 Méthode du Simplexe
 Méthode de points intérieurs
 Tester les méthodes étudiées online