Cours de mathématiques pour ingénieurs

Première année cycle ingénieur

K. Oufaska

Ecole Supérieure d’Informatique et du Numérique

Université Internationale de Rabat

A.U., 2025/2026

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 1 / 190

Enseignants

Kenza Oufaska et OUDANI Mustapha

E-mail : [email protected]
Bureau : 308 Bâtiment 2
Office houres : Jeudi de 16h30 -17h30
Mustapha Oudani, Phd (TD, TP)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 2 / 190

Descriptif

1 Chapitre 1 : Modélisation et programmation mathématique

2 Chapitre 2 : Programmation linéaire
3 Chapitre 3 : Programmation linéaire en nombres entiers
4 Chapitre 4 : Problèmes de transport et d’affectation
5 Chapitre 5 : Programmation non linéaire

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 3 / 190

Compétences Escomptées

1 CO1 : Model a problem as a linear program

2 CO2 : Solve graphically and analytically a linear program
3 CO3 : Solve linear programs using various CPLEX interfaces
4 CO4 : Implement Simplex and gradient algorithms using Python

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 4 / 190

Bibliographie I

Bazaraa, M. S., Jarvis, J. J., & Sherali, H. D. (2011).

Linear programming and network flows.
John Wiley & Sons.

Luenberger, D. G., & Ye, Y. (1984).

Linear and nonlinear programming (Vol. 2).
Reading, MA : Addison-wesley.
,

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 5 / 190

Evaluation

Moyenne de contrôle continu : 50%

Examen final : 50 %
Pénalité pour retard :
Tout travail remis en retard sans motif valable sera pénalisé de 10 % par
jour de retard.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 6 / 190

Modélisation mathématique
Problème de fleuriste

Un fleuriste dispose de 45 roses, 36 tulipes et 27 marguerites. Il veut offrir

à ses clients deux types de bouquets de fleurs :
Type 1 : bouquet à 80 Dhs, composé de 10 roses, 4 tulipes et 2
marguerites
Type 2 : bouquet à 60 Dhs, composé de 6 roses, 6 tulipes et 6
marguerites.
Le souci du fleuriste est de déterminer le nombre de bouquets de chaque
type afin de maximiser son revenu total.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 7 / 190

Modélisation mathématique
Problème de fleuriste

Notons par : x1 : le nombre de bouquet à préparer de type 1.

Notons par : x2 : le nombre de bouquet à préparer de type 2.
Un bouquet de type 1 rapporte 80 Dhs, donc pour un nombre x1 de
bouquet de même type, le gain est 80x1 . Un bouquet de type 2 est vendu
à 60 Dhs, donc pour un nombre x2 de même bouquet le gain sera de 60x2 .
Ainsi, le revenu total de la vente de tous les bouquets est :

80x1 + 60x2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 8 / 190

Modélisation mathématique
Problème de fleuriste

Il faut que le nombre de fleurs utilisées de chaque catégorie ne dépasse pas

leur disponibilité :
Rose : le fleuriste dispose de 45 roses, ainsi :

10x1 + 6x2 ≤ 45

Tulipes : le fleuriste dispose de 36 tulipes, ainsi :

4x1 + 6x2 ≤ 36

Marguerites : le fleuriste dispose de 27 marguerites, ainsi :

2x1 + 6x2 ≤ 27

Il faut également que le nombre de bouquets préparés soint non nul, ainsi :

x1 , x2 ≥ 0
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 9 / 190
Modélisation mathématique
Problème de fleuriste

Le modèle mathématique du problème de fleuriste est donné donc par :




 Max z = 80x1 + 60x2

sujet à




10x + 6x ≤ 45
1 2


 4x1 + 6x2 ≤ 36




 2x1 + 6x2 ≤ 27

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 10 / 190

Modélisation mathématique
Problème de fleuriste

Le modèle mathématique du problème de fleuriste est donné donc par :




 Max z = 80x1 + 60x2 fonction objectif

sujet à




10x + 6x ≤ 45 contrainte 1
1 2


 4x1 + 6x2 ≤ 36 contrainte 2




 2x1 + 6x2 ≤ 27 contrainte 3

x , x ≥ 0 contrainte de signe
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 11 / 190

Modélisation mathématique
Problème de production

Une usine fabrique 2 sortes de produits P1 et P2 à l’aide de deux machines

M1 et M2 . Le tableau ci-dessous représente les durées de fabrication de
chaque produit sur chacune des deux machines :

P1 P2
M1 30 min 20 min
M2 40 min 10 min

La machine M1 est disponible 6000 min/mois

La machine M2 est disponible 4000 min/mois
Un article P1 fabriqué rapporte 400 dh et un article P2 rapporte 200 dhs

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 12 / 190

Modélisation mathématique
Problème de production

Variables de décision :
x1 : le nombre d’unités produit de P1
x2 : le nombre d’unités produit de P2
Modèle mathématique :



 Max z = 400x1 + 200x2

Sous contraintes :


 30x1 + 20x2 ≤ 6000

40x + 10x ≤ 4000
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 13 / 190

Modélisation mathématique
Problème de sac à dos

Considérons le problème du chargement d’un sous-ensemble parmi n objets

dans un sac à dos. Chaque objet i a une valeur vi et un poids pi . Le
chargement devra être fait de manière à maximiser la valeur totale des
objets sélectionnés sans dépasser le poids maximal W .
(
1 si l’objet i est choisi
xi =
0 sinon

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 14 / 190

Modélisation mathématique
Problème de sac à dos

Le problème de sac à dos peut être modélisé comme suit :

n

 X



 Max vi xi


 i=1

 Sujet à
X n




 pi xi ≤ W

 i=1


x ∈ {0, 1}, i ∈ {1, ..., n}
i

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 15 / 190

Modélisation mathématique
Problème de voyageur de commerce

Le problème du voyageur de commerce (Travelling Salesman Problem,

TSP) consiste en la détermination de l’itinéraire, de coût minimal (temps,
distance,. . .), d’un voyageur partant d’un point, visitant (n − 1) autres
points (villes, entrepôts, usines, supermarchés, . . .) et revenant au même
point de départ.
Ce problème classique est une généralisation du problème, plus simple, qui
consiste à trouver le plus court chemin entre deux points donnés. Il a
beaucoup d’applications directes, notamment dans les transports, les
réseaux et la logistique. Par exemple, trouver le chemin le plus court pour
les véhicules de ramassage des ordures ou, dans l’industrie, pour trouver la
plus courte distance que devra parcourir le bras mécanique d’une machine
pour percer les trous d’un circuit donné.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 16 / 190

Modélisation mathématique
Problème de voyageur de commerce

Soit la variable de décision :

(
1 si le voyageur passe du point i au point j
xij =
0 sinon
Le TSP se modélise comme suit :
n X
X n
Min cij xij
i=1 j=1
n
X
xij = 1, ∀ 1 ≤ i ≤ n
j=1
Xn
xij = 1, ∀ 1 ≤ j ≤ n
i=1
XX
xij ≤ |S| − 1, ∀ S ⊂ {2, 3, ..., n − 2}
i∈S j∈S
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 17 / 190
Modélisation mathématique
Problème d’affectation

Le responsable d’une unité de production désire affecter n personnes à n

tâches. Chaque personne doit effectuer une et une seule tâche. Soit Cij le
coût de formation de la personne i à la tâche j. Le problème d’affectation
consiste à trouver la meilleure affectation, c’est-à-dire affecter les
personnes aux tâches de sorte que la somme des coûts de formation soit
minimum. Le problème d’affectation est résumé par un tableau de la
forme :
T1 T2 ... Tj ... Tn
P1 C11 C12 ... C1j ... C1n
P2 C21 C22 ... C2j ... C2n
... ... ... ... ... ...
Pi Ci1 Ci2 ... Cij ... Cin
... ... ... ... ... ...
Pn Cn1 Cn2 ... Cnj ... Cnn

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 18 / 190

Modélisation mathématique
Problème d’affectation

Exercice
Proposer une modélisation du problème d’affectation

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 19 / 190

Modélisation mathématique
Problème d’affectation

Le problème d’affectation peut être modélisé comme suit :


X n X n



 Min Cij xij

i=1 j=1




Sous contraintes


n


X
xij = 1, ∀j ∈ {1, ..., n}

 i=1
n



 X



 xij = 1, ∀i ∈ {1, ..., n}

 j=1


xij ∈ {0, 1}


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 20 / 190

Programmation mathématique

Un programme mathématique est une traduction d’un problème

d’optimisation (maximisation ou minimisation) par des relations
mathématiques dans le but de lui appliquer les outils, les techniques et les
théories mathématiques pour résoudre le problème
La modélisation mathématique d’un problème consiste à identifier
certaines composantes relatives au problème :
L’ensemble des variables
Les contraintes
L’objectif

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 21 / 190

Programmation mathématique

Un programme mathématique est un problème d’optimisation de la

forme : 


Min f (x)

Sujet à
(P)
fi (x) ≤ 0, i ∈ {1, ..., m}



x ∈ C

Ou 


Max f (x)

Sujet à
(P ′ )


fi (x) ≤ 0, i ∈ {1, ..., m}

x ∈ C

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 22 / 190

Programmation mathématique

Remarque
Nous pouvons considérer seulement les problèmes de type (P) ; en
effet,
Max f (x) = − Min(−f (x))
Dans le problème (P), il n’y a pas de contraintes d’égalités, car une
contrainte de type h(x) = 0 peut être remplacée par deux contraintes
h(x) <= 0 et –h(x) <= 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 23 / 190

Programmation mathématique

Définition
On dit que x ∗ est un minimum local de (P) s’il existe un voisinage Vx de
x ∗ tel que x ∗ soit minimum du problème (P1 ) suivant :

Min f (x)



Sujet à
(P1 )


fi (x) ≤ 0, i ∈ {1, ..., m}

x ∈ C ∩ V
x

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 24 / 190

Programmation mathématique
Types de programmes

Selon la nature de la fonction objectif et de l’ensemble des contraintes , on

distingue :
La programmation linéaire : étudie les cas ou la fonction objectif
est linéaire et les contraintes sont des égalités ou inégalités linéaires.
La programmation linéaire en nombre entiers : étudie les
programmes linéaires dans lesquels les variables sont contraintes à
prendre des valeurs entières.
La programmation quadratique :
La fonction objectif peut contenir des termes quadratiques, tout en
conservent une description du domaine réalisable par des
égalités/inégalités linéaires.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 25 / 190

Programmation mathématique
Types de programmes

La programmation non linéaire : étudie le cas général ou la fonction

objectif et /ou les contraintes contiennent des parties non linéaires :
Programmation non-linéaire sans contraintes.
Programmation non linéaire avec contraintes.
La programmation stochastique : étudie le cas dans lequel
certaines contraintes dépendent de variables aléatoire (prise de
décision sous incertitude) Exemple : problèmes dépendants des
demandes qui ne sont pas connues à l’avance de clients problèmes liés
à la météo, cours de la bourse, du marché

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 26 / 190

Programmation mathématique
Types de programmes

La programmation convexe : si la fonction objectif et les

contraintes sont des fonctions convexes.
La programmation dynamique : Utilise la propriété qu’une solution
d’un problème dépend des solutions précédentes obtenues des
sous-problèmes en permettent aux sous-problèmes de se superposer.
Autrement dit , un sous –problèmes peut être utilise dans la solution
de deux sous-problèmes différents.
Exemples : problème de recherche du chemin optimal entre deux
points.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 27 / 190

Programmation linéaire

Fonction objectif et contraintes linéaires

Variables continues
Existence de plusieurs algorithmes de résolution exacte (Simplexe,
point intérieur, etc)
Problèmes non linéaires qui se ramènent aux problèmes linéaires

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 28 / 190

Programmation linéaire
Notions matricielles

Définition
Soient A = (aij )1≤i,j≤n et B = (bij )1≤i,j≤n deux matrices carrées, alors :
A + B = (aij + bij )1≤i,j≤n
n
X
AB = (cij )1≤i,j≤n avec cij = aik bkj
k=1

Définition
La matrice A est dite symétrique si aij = aji , ∀1 ≤ i, j ≤ n
La matrice A est dite antisymétrique si aij = −aji , ∀1 ≤ i, j ≤ n
La matrice A est dite diagonale si aii = λi , ∀ 1 ≤ i ≤ n et
aij = 0, ∀i ̸= j

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 29 / 190

Programmation linéaire
Notions matricielles

Définition
La matrice A est dite triangulaire supérieure si aij = 0, ∀ i > j
La matrice A est dite triangulaire inférieure si aij = 0, ∀ i < j
Si le déterminant d’une matrice est différent de 0, on dit que la
matrice est régulière ou inversible
Le rang d’une matrice est l’ordre de la plus grande matrice extraite
de A dont le déterminant est non nul
Soit A une matrice de rang m. On appelle base de A toute sous
matrice carrée régulière d’ordre m extraite de A.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 30 / 190

Programmation linéaire
Définitions

Définition
Solution réalisable : Solution qui satisfait toutes les contraintes du
problème.

Définition
Domaine réalisable : Ensembles de tous les jeux de valeurs des variables
de décision satisfaisant toutes les contraintes et restriction de signe du
programme linéaire (PL).

Définition
Solution optimale : Solution réalisable qui optimise (maximise ou
minimise) la fonction économique.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 31 / 190

Programmation linéaire
Définitions

Définition
Un problème de programmation linéaire peut être écrit sous la forme
suivante (forme matricielle) :



Min c t x

Sujet à
(PL)
Ax = b



x ≥ 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 32 / 190

Programmation linéaire
Définitions

Définition
Il peut s’écrire également sous la forme suivante, dite forme standard :

Min c1 x1 + c2 x2 + ... + cn xn


Sujet à





a11 x1 + a12 x2 + ... + a1n xn = b1



(PL) a21 x1 + a22 x2 + ... + a2n xn = b2

...





am1 x1 + am2 x2 + ... + amn xn = bm





xi ≥ 0, ∀i ∈ {1, ..., n}


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 33 / 190

Programmation linéaire
Définitions

Définition
Un problème avec des contraintes d’inégalités de la forme suivante :


 Min c1 x1 + c2 x2 + ... + cn xn

Sujet à





a11 x1 + a12 x2 + ... + a1n xn ≤ b1



(PL) a21 x1 + a22 x2 + ... + a2n xn ≤ b2

...





am1 x1 + am2 x2 + ... + amn xn ≤ bm





xi ≥ 0, ∀i ∈ {1, ..., n}


Peut être converti en forme standard en ajoutant des variables positifs

(appelés variables d’écarts ou slacks en anglais)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 34 / 190

Programmation linéaire
Définitions

Définition
Avec les variables d’écarts :


 Min c1 x1 + c2 x2 + ... + cn xn

Sujet à




a11 x1 + a12 x2 + ... + a1n xn + y1 = b1



(PL) a21 x1 + a22 x2 + ... + a2n xn + y2 = b2

...





am1 x1 + am2 x2 + ... + amn xn + yn = bm





xi , yi ≥ 0, ∀i ∈ {1, ..., n}


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 35 / 190

Programmation linéaire
Définitions

Définition
Un problème avec des contraintes d’inégalités de la forme suivante :


 Min c1 x1 + c2 x2 + ... + cn xn

Sujet à





a11 x1 + a12 x2 + ... + a1n xn ≥ b1



(PL) a21 x1 + a22 x2 + ... + a2n xn ≥ b2

...





am1 x1 + am2 x2 + ... + amn xn ≥ bm





xi ≥ 0, ∀i ∈ {1, ..., n}


Peut être converti en forme standard en retranchant des variables positifs

(appelés variables de surplus)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 36 / 190

Programmation linéaire
Définitions

Définition
Avec les variables de surplus :

Min c1 x1 + c2 x2 + ... + cn xn


Sujet à





a11 x1 + a12 x2 + ... + a1n xn − y1 = b1



(PL) a21 x1 + a22 x2 + ... + a2n xn − y2 = b2

...





am1 x1 + am2 x2 + ... + amn xn − yn = bm





xi , yi ≥ 0, ∀i ∈ {1, ..., n}


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 37 / 190

Programmation linéaire

Remarque
Sans perte de généralité, nous pouvons supposer que x1 , x2 , ..., xn sont
positifs. En effet, s’il existe j tel que xj < 0, on pose xj = xj+ − xj− , avec
xj+ = max(xj , 0) et xj− = max(−xj , 0)

Exercice
Ecrire sous forme standard le programme linéaire suivant :



 Min z = 5x1 − 3x2

Sujet à




x − x ≥ 2
1 2
(P)


 2x 1 + 3x2 ≤ 4




 −x1 + 6x2 = 10

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 38 / 190

Programmation linéaire

Exercice
Ecrire sous forme standard le programme linéaire suivant :


 Min z = x1 + 2x2 + x3

Sujet à





x1 − x2 + x3 = 1



(P) x1 + x2 − x3 ≤ 2

x1 + x2 + x3 ≥ 3




x1 , x2 ≥ 0




x3 ∈ R


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 39 / 190

Programmation linéaire
Résolution graphique

La méthode de résolution graphique concerne les programmes à deux

variables :
1 On reporte sur un graphique chacune des contraintes du problème et
on détermine la région commune à l’ensemble de ces contraintes. La
région commune, si elle existe, constitue la région des solutions
réalisables.
2 On détermine les coordonnées des points extrêmes ou sommets de la
région des solutions réalisables en les localisant directement sur le
graphique ou plus exactement en résolvant simultanément les
équations des droites qui se coupent à chacun des points extrêmes.
3 On substitue les coordonnées de chaque point extrême dans
l’expression de la fonction économique. Le point extrême qui optimise
la fonction économique correspond à la solution optimale.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 40 / 190

Programmation linéaire
Résolution graphique

Il existe quatre cas de figure :

1 Problème borné inférieurement
2 Problème avec infinité de solutions optimales
3 Problème non borné inférieurement
4 Problème avec domaine réalisable non borné et solution optimale finie

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 41 / 190

Programmation linéaire
Résolution graphique

Exemple
Soit à résoudre graphiquement le programme :



Min − 10x1 − 20x2




s.c :

x + 3x ≤ 12
1 2
(P)


x1 + x2 ≤ 6




8x1 + 5x2 ≤ 39

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 42 / 190

Résolution graphique

Figure – Résolution graphique

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 43 / 190

Résolution graphique

Exercice
Résoudre graphiquement le programme linéaire suivant :



 Min x1 + x2




 s.c :

2x + x ≥ 12
1 2


 5x1 + 8x2 ≥ 74

x1 + 6x2 ≥ 24




x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 44 / 190

Résolution graphique

Exercice
Résoudre graphiquement le programme linéaire suivant :



 Min 2x1 + x2




 s.c :

x − x ≤ 6
1 2


 2x1 + x2 ≤ 24

x2 ≤ 20




x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 45 / 190

Rappels
Pivot de Gauss

Exercice
Appliquer le pivot de Gauss sur la matrice suivante :
 
2 1 3 4
3 −1 0 6
 
1 0 −1 4
4 1 −1 3

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 46 / 190

Rappels
Pivot de Gauss

Exercice
Appliquer le pivot de Gauss sur la matrice suivante :
 
6 0 −3 1
2 3 4 16 
 
8 5 −1 0 
1 3 −1 −3

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 47 / 190

programmation linéaire
Algorithme de Simplexe

Soit à résoudre le programme suivant :




Min z = −80x − 60y

S.c :




10x + 6y ≤ 45
(P)


4x + 6y ≤ 36




2x + 6y ≤ 27

x, y ≥ 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 48 / 190

programmation linéaire
Algorithme de Simplexe

La forme standard de ce problème est :




 Min z = −80x − 60y




 S.c :

10x + 6y + u = 45
(PS)


 4x + 6y + v = 36




 2x + 6y + h = 27

x, y , u, v , h ≥ 0

La solution de base correspondante est (x, y , u, v , h) = (0, 0, 45, 36, 27).

C’est une solution de base réalisable puisque toutes les valeurs de variables
sont positives. La valeur de la fonction objectif est z = 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 49 / 190

Programmation linéaire
Algorithme de Simplexe

La solution de base (x, y , u, v , h) = (0, 0, 45, 36, 27) n’est pas optimale
puisque les coefficients dans la fonction objectif des variables hors-base x
et y sont négatifs.Puisque nous cherchons à minimiser z = −80x − 60y
alors c’est la variable x qui influence plus la diminution de z.
L’augmentation de x est limitée par la contrainte de positivité. En effet,

45
u = 45 − 10x ≥ 0 ⇐⇒ x ≤ 10

v = 36 − 4x ≥ 0 ⇐⇒ x ≤ 36 4
 27
h = 27 − 2x ≥ 0 ⇐⇒ x ≤ 2


Donc pour que la solution demeure réalisable, il faut que :

45 36 27
x ≤ min{ , , }
10 4 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 50 / 190

Programmation linéaire
Algorithme de Simplexe

Considérons le tableau initial du Simplexe, obtenu à partir de la forme

standard, suivant
Variables de base x y u v h -z Termes de droite
u 10 6 1 0 0 0 45
v 4 6 0 1 0 0 36
h 2 6 0 0 1 0 27
-z -80 -60 0 0 0 1 0

Les coefficients des variables de la dernière ligne du tableau du simplexe

sont appelés coûts relatifs, coûts réduits ou coûts marginaux.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 51 / 190

Programmation linéaire
Algorithme de Simplexe

La variable de sortie u va quitter la base pour être remplacée par la variable

x qui va alors jouer le rôle de la variable de base dans la prochaine base.

Variables de base x y u v h -z Termes de droite

x 1 3/5 1/10 0 0 0 9/2
v 4 6 0 1 0 0 36
h 2 6 0 0 1 0 27
-z -80 -60 0 0 0 1 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 52 / 190

Programmation linéaire
Algorithme de Simplexe

Variables de base x y u v h -z Termes de droite

x 1 3/5 1/10 0 0 0 9/2
v 0 18/5 -2/5 1 0 0 18
h 2 6 0 0 1 0 27
-z -80 -60 0 0 0 1 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 53 / 190

Programmation linéaire
Algorithme de Simplexe

Variables de base x y u v h -z Termes de droite

x 1 3/5 1/10 0 0 0 9/2
v 0 18/5 -2/5 1 0 0 18
h 0 24/5 -1/5 0 1 0 18
-z 0 -12 8 0 0 1 360

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 54 / 190

Programmation linéaire
Algorithme de Simplexe

Variables de base x y u v h -z Termes de droite

x 1 3/5 1/10 0 0 0 9/2
v 0 18/5 -2/5 1 0 0 18
y 0 1 -1/24 0 5/24 0 15/4
-z 0 0 15/2 0 5/2 1 405

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 55 / 190

Programmation linéaire
Algorithme de Simplexe

L’algorithme de Simplexe peut être résumé comme suit :

1 Ecrire le problème sous forme standard
2 Identifier une solution de base initiale et donner le tableau initial du
Simplexe
3 Si tous les coefficients de la dernière ligne sont positifs ou nuls, alors
la solution actuelle est optimale. Sinon sélectionner la variable
hors-base ayant le plus petit coefficient négatif pour entrer en base :
c’est la variable d’entrée
4 Appliquer la règle du plus petit rapport pour identifier la variable qui
quitte la base : c’est la variable de sortie.
5 Exécuter le pivot sur l’élément à l’intersection de la colonne de la
variable d’entrée et de la ligne de la variable de sortie. Retourner à
l’étape 3.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 56 / 190

Programmation linéaire
Algorithme de Simplexe

Exercice
Appliquer la méthode de Simplexe tabulaire pour résoudre le programme
linéaire suivant : 


Min z = −x1 − 2x2




S.c :

−3x + 2x ≤ 2
1 2
(P)


−x1 + 2x2 ≤ 4




x1 + x2 ≤ 5

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 57 / 190

Programmation linéaire
Algorithme de Simplexe

Exercice
Appliquer la méthode de Simplexe tabulaire pour résoudre le programme
linéaire suivant : 


Min z = −x1 − 2x2




S.c :

−3x + 2x ≤ 2
1 2
(P)
−x1 + 2x2 ≤ 4






x1 + x2 ≤ 5

x , x ≥ 0
1 2

La solution est : x1 = 2, x2 = 3 et son coût est -8.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 58 / 190

Programmation linéaire
Algorithme de Simplexe

Remarque
Pour résoudre un problème de maximisation il faut le transformer en
problème de minimisation ou bien adapter le critère d’optimalité. Ainsi,
dans ce cas, il faut que les coûts marginaux de toutes les variables
hors-base soient négatifs ou nuls

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 59 / 190

Programmation linéaire
Algorithme de Simplexe

Exercice
Résoudre le programme suivant par la méthode tabulaire de Simplexe



 Max z = x1 + 2x2




 sujet à

−3x + 2x + x = 2
1 2 3


 −x1 + 2x2 + x4 = 4




 x1 + x2 + x5 = 5

x , x , x , x , x ≥ 0
1 2 3 4 5

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 60 / 190

Programmation linéaire
Algorithme de Simplexe

Exercice
Résoudre le programme suivant par la méthode tabulaire de Simplexe



 Max z = x1 + 2x2

sujet à




−3x + 2x + x = 2
1 2 3


 −x1 + 2x2 + x4 = 4




 x1 + x2 + x5 = 5

x , x , x , x , x ≥ 0
1 2 3 4 5

La solution est x1 = 2, x2 = 3, x3 = 2 et son coût est 8.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 61 / 190

Programmation linéaire
Algorithme de Simplexe

Théorème
Considérons le polytope X = {x ∈ Rn : Ax = b, x ≥ 0} où A est de rang
m. Alors, x ∈ X est un point extrême de X si et seulement si x est une
solution de base de X .

Remarque
L’augmentation de la valeur d’une variable hors-base et l’ajustement des
valeurs des variables de base pour effectuer un changement de base
correspond géométriquement à se déplacer sur une arête du polytope X .
Aurement dit, cela consiste à se déplacer d’un point extrême à un autre
point extrême adjacent.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 62 / 190

Programmation linéaire
Algorithme de Simplexe

Dans l’étape 3 de l’algorithme de Simplexe lorsque les coûts marginaux de

toutes les variables sont positifs ou nuls, alors la solution actuelle est
optimale. Mais s’ils sont tous non nuls, alors la solution optimale est
unique. Si par contre, l’un de ces coûts des variables hors-base est nul,
alors on peut avoir deux ou plusieurs solutions optimales. On dit qu’on a
dégénérescence de première espèce .

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 63 / 190

Programmation linéaire
Algorithme de Simplexe

Pour illuster cette dégénérescence, on considère l’exemple suivant :




 Min z = −50x1 − 30x2

 sujet à




10x + 6x ≤ 45
1 2
(P)


 4x1 + 6x2 ≤ 36




 2x1 + 6x2 ≤ 27

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 64 / 190

Programmation linéaire
Algorithme de Simplexe

Variables de base x y u v h -z Termes de droite

u 10 6 1 0 0 0 45
v 4 6 0 1 0 0 36
h 2 6 0 0 1 0 27
-z -50 -30 0 0 0 1 0

La variable x entre dans la base pour remplacer la variable u qui la quitte.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 65 / 190

Programmation linéaire
Algorithme de Simplexe

Variables de base x y u v h -z Termes de droite

x 1 3/5 1/10 0 0 0 9/2
v 0 18/5 -2/5 1 0 0 18
h 0 24/5 -1/5 0 1 0 18
-z 0 0 5 0 0 1 225

Nous obtenons une solution optimale dont les variables de bases sont
x, v , h. Mais le coût marginal de y est nul. Faisons entrer cette variable y

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 66 / 190

Programmation linéaire
Algorithme de Simplexe

Variables de base x y u v h -z Termes de droite

x 1 0 1/8 0 -1/8 0 9/4
v 0 0 -1/4 1 -3/4 0 9/2
y 0 1 -1/24 0 5/24 0 15/4
-z 0 0 5 0 0 1 225

Nous obtenons donc une autre solution de base optimale dont les variables
de base sont x, v , y

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 67 / 190

Programmation linéaire
Algorithme de Simplexe

En appliquant la règle du plus petit rapport pour désigner la variable de

sortie, il est possible que le plus petit rapport soit atteint pour deux
contraintes. En effectuant le changement de base, nous obtenons alors une
solution de base avec l’une des composantes nulle. Nous disons qu’on a
une dégénérescence de deuxième espèce. Nous pouvons même retrouver
une base déjà rencontrée à une itération précédente. On dit alors qu’on a
un phénomène de cyclage.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 68 / 190

Programmation linéaire
Algorithme de Simplexe

Afin d’illuster ce type de dégénérescence, considérons l’exemple suivant :




 Min z = −4x1 − 3x3




 sujet à

x − x ≤ 2
1 2
(P)


 2x 1 + x2 ≤ 4




 x1 + x2 + x3 ≤ 3

x , x , x ≥ 0
1 2 3

Introduisons les variables d’écarts et écrivons le premier tableau de

Simplexe

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 69 / 190

Programmation linéaire
Algorithme de Simplexe

V. B x1 x2 x3 x4 x5 x6 -z b
x4 1 -1 0 1 0 0 0 2
x5 2 0 1 0 1 0 0 4
x6 1 1 1 0 0 1 0 3
-z -4 0 -3 0 0 0 1 0

La variable x1 entre en base. Mais en appliquant la règle du plus petit

rapport, nous constatons que le minimum est atteint pour les deux
premières contraintes. Choisissons x4 comme variable de sortie, nous
obtenons le tableau suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 70 / 190

Programmation linéaire
Algorithme de Simplexe

V. B x1 x2 x3 x4 x5 x6 -z b
x1 1 -1 0 1 0 0 0 2
x5 0 2 1 -2 1 0 0 0
x6 0 2 1 -1 0 1 0 1
-z 0 -4 -1 0 2 0 1 4

Cette nouvelle solution n’est pas optimale. Cette solution est dite
dégénérée puisque l’une des variables de base est nulle (x5 = 0). En
appliquant la méthode de plus rapport, nous constatons que la variable x5
quitte la base et nous obtenons le tableau suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 71 / 190

Programmation linéaire
Algorithme de Simplexe

V. B x1 x2 x3 x4 x5 x6 -z b
x1 1 0 1/2 0 1/2 0 0 2
x2 0 1 1/2 -1 1/2 0 0 0
x6 0 0 0 1 -1 1 0 1
-z 0 0 -3 4 0 0 1 4

La solution obtenue n’est pas optimale et elle dénénérée (x2 = 0). La

valeur de la fonction objectif n’a pas changé. A l’itération suivante, x2
quitte la base et sera remplacée par x3

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 72 / 190

Programmation linéaire
Algorithme de Simplexe

V. B x1 x2 x3 x4 x5 x6 -z b
x1 1 -1 0 1 0 0 0 2
x3 0 2 1 -2 1 0 0 0
x6 0 0 0 1 -1 1 0 1
-z 0 6 0 -2 3 0 1 4

Encore une fois, le changement de base n’a pas modifiée la valeur de la

fonction objectif. En plus la nouvelle solution n’est pas optimale. Ce
phénomène de dégénérescence s’arrête à l’itération suivante où nous
obtenons une solution de base non dégénérée.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 73 / 190

Programmation linéaire
Algorithme de Simplexe

V. B x1 x2 x3 x4 x5 x6 -z b
x1 1 -1 0 0 1 -1 0 1
x3 0 2 1 0 -1 2 0 2
x4 0 0 0 1 -1 1 0 1
-z 0 6 0 0 1 2 1 6

Nous obtenons une solution de base optimale non dégénérée.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 74 / 190

Programmation linéaire
Algorithme de Simplexe

Remarque
Dans certains cas de problèmes dégénérés, nous pouvons avoir un
phénomène de cyclage où nous retrouvons une même solution de base
après un certain nombre d’itérations sans aucune amélioration de la valeur
de la fonction objectif.

Remarque
Dans le cas où on a plusieurs variables candidates à enter en base nous
pouvons utiliser la règle de Bland qui consiste à choisir systématiquement
comme variable entrante, parmi les variables candidates, celle ayant le plus
petit indice et comme variable sortante celle ayant le plus petit indice.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 75 / 190

Programmation linéaire
Algorithme de Simplexe

Dans tous les exemples que nous avons étudié, une solution de base
réalisable initiale est facile à identifier puisque la forme standard est aussi
une forme canonique. Ceci n’est pas toujours le cas. Soit l’exemple
suivant : 
 Min z = −80x − 60y


sujet à





10x + 6y = 45



4x + 6y ≤ 36

2x + 6y ≤ 27





x ≥2





x, y ≥ 0


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 76 / 190

Programmation linéaire
Algorithme de Simplexe

Soit le PL :



Min z = c1 x1 + c2 x2 + ... + cn xn

sujet à




a x + a x + ... + a x = b
11 1 12 2 1n n 1
(P)


a21 x1 + a22 x2 + ... + a2n xn = b2




am1 x1 + am2 x2 + ... + amn xn = bm

x , x , ..., x ≥ 0
1 2 n

Le programe (P) est dit sous forme canonique si :

La fonction objectif est exprimée en fonction en variables hors-base
La colonne de la matrice des contraintes correspondant à chaque
variable de base forme un vecteur unité
Toutes les bi sont non négatifs
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 77 / 190
Programmation linéaire
Algorithme de Simplexe

La phase 1 de la méthode des deux phases consiste à écrire le problème à

résoudre sous forme canonique en identifiant une solution de base initiale.
Ceci peut se faire en appliquant, soit la méthode des variables artificielles
ou la méthode du grand M. Par contre la phase 2 consiste à appliquer
l’algorithme du Simplexe au problème sous forme canonique obtenue à la
phase 1.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 78 / 190

Programmation linéaire
Algorithme de Simplexe

Considérons le problème linéaire sous forme la forme standard :



 Min z = c1 x1 + c2 x2 + ... + cn xn

sujet à





a11 x1 + a12 x2 + ... + a1n xn = b1





a21 x1 + a22 x2 + ... + a2n xn = b2



(P) .

.





.





am1 x1 + am2 x2 + ... + amn xn = bm





x1 , x2 , ..., xn ≥ 0


Nous allons ajouter à chaque contrainte d’égalité une variable dite

variable artificielle, qui jouera le rôle de variable de base
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 79 / 190
Programmation linéaire
Algorithme de Simplexe



Min z = c1 x1 + c2 x2 + ... + cn xn

sujet à





a11 x1 + a12 x2 + ... + a1n xn = t1 = b1





a21 x1 + a22 x2 + ... + a2n xn + t2 = b2



(P+) .

.




.




am1 x1 + am2 x2 + ... + amn xn + tm = bm





x1 , x2 , ..., xn , t1 , t2 , ..., tm ≥ 0


t1 , t2 , ...tm étant les variables artificielles.Les problèmes (P) et (P+) ne

sont équivalents que si les variables artificielles sont toutes nulles.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 80 / 190

Programmation linéaire
Algorithme de Simplexe

Il faudra donc ajouter à (P+) la contrainte supplémentaire :

t1 + t2 + ... + tm = 0

Ce qui nous obligera à ajouter une autre variable artificielle. L’idée consiste
à ne pas introduire une nouvelle contrainte dans le modèle (P+), mais de
considérer un nouveau modèle ayant les mêmes contraintes que (P+) et
qui pénalise le fait que t1 , t2 , ..., tm prennent des valeurs strictement
positives. Donc au lieu de résoudre (P+) on peut résoudre le programme
suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 81 / 190

Programmation linéaire
Algorithme de Simplexe



Min w = t1 + t2 + ... + tm

sujet à





a11 x1 + a12 x2 + ... + a1n xn = t1 = b1





a21 x1 + a22 x2 + ... + a2n xn + t2 = b2



(Pa ) .

.





.




am1 x1 + am2 x2 + ... + amn xn + tm = bm




x1 , x2 , ..., xn , t1 , t2 , ..., tm ≥ 0


Si le problème (Pa ) a une solution optimale égale à 0, alors nous obtenons

une solution initiale réalisable pour (P), sinon le problème (P) est non
réalisable.
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 82 / 190
Programmation linéaire
Algorithme de Simplexe

Exemple
Soit le programme linéaire


 Min z = −80x − 60y

sujet à





10x + 6y = 45



(P1 ) 4x + 6y ≤ 36

2x + 6y ≤ 27





x ≥ 2




x, y ≥ 0


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 83 / 190

Programmation linéaire
Algorithme de Simplexe

Après transformation du programme en forme standard puis introduction

des variables artificielles, le nouveau modèle prend la forme :


 Min z = −80x − 60y

sujet à





10x + 6y + t1 = 45



(P1 +) 4x + 6y + e1 = 36

2x + 6y + e2 = 27





x − e3 + t2 = 2





x, y , e1 , e2 , e3 , t1 , t2 ≥ 0


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 84 / 190

Programmation linéaire
Algorithme de Simplexe

Modifions la fonction objectif :



 Min za = t1 + t2

sujet à





10x + 6y + t1 = 45



(Pa ) 4x + 6y + e1 = 36

2x + 6y + e2 = 27





x − e3 + t2 = 2





x, y , e1 , e2 , e3 , t1 , t2 ≥ 0


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 85 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T.D
t1 10 6 0 0 0 1 0 45
e1 4 6 1 0 0 0 0 36
e2 2 6 0 1 0 0 0 27
t2 1 0 0 0 -1 0 1 2
−za 0 0 0 0 0 1 1 0

Pour que t1 et t2 jouent le rôle de variables de base, il faut transformer ce

tableau en soustrayant la première et la quatrième ligne de la dernière
ligne. Nous obtenons le tableau suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 86 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T.D
t1 10 6 0 0 0 1 0 45
e1 4 6 1 0 0 0 0 36
e2 2 6 0 1 0 0 0 27
t2 1 0 0 0 -1 0 1 2
−za − za0 -11 -6 0 0 1 0 0 -47

Cette solution n’est pas optimale. La variable x entre en base et t2 sort de

la base. Nous obteneons le tablea suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 87 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T.D
t1 0 6 0 0 10 1 -10 25
e1 0 6 1 0 4 0 -4 28
e2 0 6 0 1 2 0 -2 23
x 1 0 0 0 -1 0 1 2
−za − za0 0 -6 0 0 -10 0 11 -25

Cette solution n’est pas optimale. La variable t1 sera remplacée par la

variable d’entrée e3 . Nous obteneons le tableau suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 88 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T.D
e3 0 3/5 0 0 1 1/10 -1 5/2
e1 0 18/5 1 0 0 -2/5 0 18
e2 0 24/5 0 1 0 -1/5 0 18
x 1 3/5 0 0 0 1/10 0 9/2
−za − za0 0 0 0 0 0 1 1 0

La solution (9/2, 0, 18, 18, 5/2, 0, 0) est une solution de base optimale de
(Pa ) avec une valeur optimale égale à 0. Donc (9/2, 0, 18, 18, 5/2)
constitue une solution de base initiale du problème (P1 ). Ceci termine la
phase 1 et va nous permettre de construire un tableau initial du Simplexe
de (P1 ) pour démarrer la phase 2.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 89 / 190

Programmation linéaire
Algorithme de Simplexe

Phase 2 :
Pour commencer la phase 2, il suffit de supprimer les colonnes associées
aux variables artificielles et remplacer les coefficients de la fonction objectif
za par ceux de la fonction objectif z.

V.B x y e1 e2 e3 T.D
e3 0 3/5 0 0 1 5/2
e1 0 18/5 1 0 0 18
e2 0 24/5 0 1 0 18
x 1 3/5 0 0 0 9/2
−z -80 -60 0 0 0 0

x étant une variable de base, nous devons donc remplacer -80 par 0. Nous
multiplions la quatirème par -80 et nous l’ajoutons à la dernière ligne.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 90 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 T.D
e3 0 3/5 0 0 1 5/2
e1 0 18/5 1 0 0 18
e2 0 24/5 0 1 0 18
x 1 3/5 0 0 0 9/2
−z 0 -12 0 0 0 360

Cette solution n’est pas optimale. La variable y entre en base et la variable

e2 sort de la base.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 91 / 190

Programmation linéaire
Algorithme de

V.B x y e1 e2 e3 T.D
e3 0 0 0 -3/5 1 1/4
e1 0 0 1 -18/5 0 9/2
y 0 1 0 5/24 0 15/4
x 1 0 0 -1/8 0 9/4
−z 0 0 0 5/4 0 405

Cette solution est optimale. La solution optimale de (P1 +) est

(9/4, 15/4, 9/2, 0, 1/4) et donc la solution optimale de (P1 ) est
(9/4, 15/4) avec comme valeur optimale z = −405

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 92 / 190

Programmation linéaire
Algorithme de Simplexe

Méthode de grand M
Contrairement à la méthode des variables artificielles, la méthode du grand
M utilise à la fois les variables initiales du problème et les variables
artificielles. On pénalise les variables artificielles en leur affectant un
coefficient de valeur très élevée dans la fonction objectif (+M pour un
problème de minimisation, −M pour un problème de maximisation). Les
pénalités ont pour objet de forcer, au fil des itérations, les variables
artificielles à quitter la base. A l’optimum (s’il existe) les variables
artificielles sont hors base. Si à l’optimum, certaines variables artificielles
sont dans la base, avec une valeur non nulle, alors le programme n’a pas
de solution réalisable.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 93 / 190

Programmation linéaire
Algorithme de Simplexe

Appliquons l’algorithme de Simplexe au problème



 Min zm = −80x − 60y + Mt1 + Mt2

sujet à





10x + 6y + t1 = 45



4x + 6y + e1 = 36

2x + 6y + e2 = 27





x − e3 + t2 = 2





x, y , e1 , e2 , e3 , t1 , t2 ≥ 0


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 94 / 190

Programmation linéaire
Algorithme de Simplexe

Le tableau initial du Simplexe est donné par :

V.B x y e1 e2 e3 t1 t2 T. droite
t1 10 6 0 0 0 1 0 45
e1 4 6 1 0 0 0 0 36
e2 2 6 0 1 0 0 0 27
t2 1 0 0 0 -1 0 1 2
−zm -80 -60 0 0 0 M M 0

Pour que t1 et t2 jouent le rôle de variables de base, il faut transformer ce

tableau en soustrayant M fois la première et M fois la quatrième ligne de
la dernière ligne

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 95 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T. droite
t1 10 6 0 0 0 1 0 45
e1 4 6 1 0 0 0 0 36
e2 2 6 0 1 0 0 0 27
t2 1 0 0 0 -1 0 1 2
0
−zm − zm -80-11M -60-6M 0 0 M 0 0 -47M

Cette solution de base n’étant pas optimale, nous appliquons alors le

critère d’entrée et le critère de sortie pour remplacer la variable de sortie t2
par la variable d’entrée x. Nous obteneons le tableau suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 96 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T. droite
t1 0 6 0 0 10 1 -10 25
e1 0 6 1 0 4 0 -4 28
e2 0 6 0 1 2 0 -2 23
x 1 0 0 0 -1 0 1 2
0
−zm − zm 0 -60-6M 0 0 -80-10M 0 80+11M 160-25M

Cette solution de base n’est pas optimale. La variable de sortie t1 sera

remplacée par la variable d’entrée e3 .

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 97 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 t1 t2 T. droite
e3 0 3/5 0 0 1 1/10 -1 5/2
e1 0 18/5 1 0 0 -2/5 0 18
e2 0 24/5 0 1 0 -1/5 0 18
x 1 3/5 0 0 0 1/10 0 9/2
0
−zm − zm 0 -12 0 0 0 8+M M 360

Toutes les variables artificelles sont hors base avec un fort coefficient positif
et ne pourront plus y entrer. La phase 1 s’achève en éliminant les variables
artificielles du tableau précédent et la phase 2 du simplexe démarre.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 98 / 190

Programmation linéaire
Algorithme de Simplexe

V.B x y e1 e2 e3 T. droite
e3 0 3/5 0 0 1 5/2
e1 0 18/5 1 0 0 18
e2 0 24/5 0 1 0 18
x 1 3/5 0 0 0 9/2
−z 0 -12 0 0 0 360

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 99 / 190

Programmation linéaire
Dualité en programmation linéaire

Reprenons l’exemple du fleuriste :


Max z = 80x + 60y






 sujet à

10x + 6y ≤ 45
(P)


 4x + 6y ≤ 36




 2x + 6y ≤ 27

x, y ≥ 0

Supposons qu’un client fait une proposition au fleuriste pour acheter

toutes ses fleurs (ressources) : son problème est de déterminer les prix
unitaires u1 (pour 1 rose), u2 (pour 1 tulipe) et u3 (pour 1 marguerite)
dans le but de minimiser le coût total d’achat. Mais, pour que le fleuriste
accepte son offre , le prix payé pour les fleurs requises pour préparer un
bouquet de type 1 doit être d’au moins 80 Dhs et pour un bouquet de
type 2 doit être d’au moins 60 Dhs.
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 100 / 190
Programmation linéaire
Dualité en programmation linéaire

Le client doit alors résoudre le problème suivant :



 Min w = 45u1 + 36u2 + 27u3

sujet à



(D) 10u1 + 4u2 + 2u3 ≥ 80

6u1 + 6u2 + 6u3 ≥ 60





u1 , u2 , u3 ≥ 0


Le programme (P) est appelé le problème primal et (D) le problème dual.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 101 / 190
Programmation linéaire
Dualité en programmation linéaire

A chaque problème primal est associé un problème dual

A chaque variable du primal est associée une contrainte du dual
A chaque contrainte du primal est associée une variable de dual
Si l’objectif du primal est à maximiser, alors l’objectif du dual est à
minimiser et inversement
Le dual du dual est le primal

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 102 / 190
Programmation linéaire
Dualité en programmation linéaire

Les propriétés de correspondance primal-dual peuvent être résumées dans

le tabelau suivant :
Primal (Min) Dual (Max)
X
xj ≥ 0 aij uj ≤ cj
1≤j≤m
X
xj ≤ 0 aij uj ≥ cj
1≤j≤m
X
xj ∈ R aij uj = cj
X 1≤j≤m
aij xj ≥ bi ui ≥ 0
1≤j≤m
X
aij uj ≤ bi ui ≤ 0
1≤j≤m
X
aij xj = bi ui ∈ R
1≤j≤m

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 103 / 190
Programmation linéaire
Dualité en programmation linéaire

Nous avons les correspondances primales duales suivantes :


t
Min c x



sujet à
(P)


 Ax ≥ b

x ≥ 0

↔ 


Max b t u

sujet à
(D)


At u ≤ c

u ≥ 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 104 / 190
Programmation linéaire
Dualité en programmation linéaire

Nous avons les correspondances primales duales suivantes :


t
Min c x



sujet à
(P)


 Ax = b

x ≥ 0

↔ 


Max b t u

sujet à
(D)


At u ≤ c

u ∈ R

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 105 / 190
Programmation linéaire
Dualité en programmation linéaire

Exercice
Donner le dual du programe suivant :



Min z = 2x1 + 3x2




sujet à

x ≥ 3
1
(P)


x2 ≥ 6




2x1 + 3x2 ≥ 9

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 106 / 190
Programmation linéaire
Dualité en programmation linéaire

Exercice
Donner le dual du programme suivant :



Min z = x1 − 3x2




sujet à

x ≤ 5
1
(P)


x2 ≤ 3




2x1 + x2 ≤ 10

x , x ≥ 0
1 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 107 / 190
Programmation linéaire
Dualité en programmation linéaire

Théorème
Pour toute solution x réalisable du problème primal et toute solution u
réalisable du dual, on a :
bt u ≤ c t x

Preuve
On a
c t x = x t c ≥ x t (At u) = (Ax)t u ≥ b t u

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 108 / 190
Programmation linéaire
Dualité en programmation linéaire

Théorème
Si le problème primal admet une solution réalisable x et si son dual admet
une solution réalisable u telles que b t u = c t x alors x et u sont des
solutions optimales respectivement du primal et du dual.

Preuve
c t x ≥ bt u = c t x

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 109 / 190
Programmation linéaire
Dualité en programmation linéaire

Théorème
Considérons le programme linéaire (P) et son dual (D)
Si l’un des problèmes duaux admet une solution optimale finie, alors il
en est de même pour l’autre et les valeurs des fonctions objectifs à
l’optimum sont égales
Si l’un des problèmes duaux n’est pas borné, alors l’autre n’est pas
réalisable

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 110 / 190
Programmation linéaire
Dualité en programmation linéaire

Théorème
Étant donné un programme linéaire (P) et le programme dual (D) associé.
Si (P) et (D) ont des solutions, alors chacun d’eux a une solution optimale
et Min(P) = Max(D). Ce théorème est dit ”Théorème fondamental de la
dualité”.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 111 / 190
Programmation linéaire
Dualité en programmation linéaire

Théorème
Soient x et u des solutions réalisables respectivement pour les problèmes
primal et dual. Alors x et u sont des solutions optimales pour ces
problèmes si et seulement si :

(u t a.j − cj )xj = 0, pour j = 1, 2, ..., n

Ce théorème est dit ”théorème des écarts complémentaires”

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 112 / 190
Programmation linéaire
Dualité en programmation linéaire

Algorithme dual de Simplexe

Considérons le problème primal :


 Max z = x1 − 3x2

sujet à



(P) x1 − 2x2 ≤ 2

−2x1 − x2 ≤ 3




x1 , x2 ≥ 0


Au lieu de résoudre le problème (P) directement par l’algorithme du

Simplexe, nous allons passer par la résolution de son dual

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 113 / 190
Programmation linéaire
Dualité en programmation linéaire



Min z = 2u1 + 3u2

sujet à



(D) u1 − 2u2 ≥ 1

−2u1 − u2 ≥ −3





u1 , u2 ≥ 0


La forme standard de (D) est :



 Min z = 2u1 + 3u2

sujet à



(DS) −u1 + 2u2 + u3 = −1

2u1 + u2 + u4 = 3





u1 , u2 , u3 , u4 ≥ 0


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 114 / 190
Programmation linéaire
Dualité en programmation linéaire

La forme tabulaire associée à (DS) est :

Variables de base u1 u2 u3 u4 Termes de droite

u3 -1 2 1 0 -1
u4 2 1 0 1 3
−z 2 3 0 0 0

Nous constatons que la solution est optimale, mais elle n’est pas réalisable
puisque l’un des termes de droite est négatif. Donc u3 sort de la base
(variable associé à la ligne du terme négatif. Et la variable u1 entre en base
car c’est la variable correspondante au plus petit rapport positif. En
effectuant la règle de pivotage, nous obteneons le tableau :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 115 / 190
Programmation linéaire
Dualité en programmation linéaire

Variables de base u1 u2 u3 u4 Termes de droite

u1 1 -2 -1 0 1
u4 0 5 2 1 1
−z 0 7 2 0 -2

Tous les coûts relatifs associés aux variables hors-base sont positiifs et tous
les termes de droite sont positifs. Donc la solution de base actuelle est
optimale.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 116 / 190
Programmation linéaire
Dualité en programmation linéaire

Remarque
Dans l’algorithme primal de Simplexe, nous commençons par des solutions
réalisables et on cherche au courant des itérations une solution optimale
alors que pour l’algorithme dual de Simplexe, on part d’une solution
optimale (peut être non réalisable) et on cherche une solution réalisable.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 117 / 190
Programmation linéaire en nombres entiers

La plupart des problèmes issus du monde économique se présentent

ou peuvent être ramenés à des problèmes linéaires dont les variables
prennent des valeurs entières.
Plusieurs problèmes de gestion (affectation, sac à dos, TSP, VRP,
etc) sont des Problèmes Linéaires en Nombres Entiers PLNE

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 118 / 190
Programmation linéaire en nombres entiers

Définition
Un problème de PLNE est donné sous la forme générale :

X n
Min cj xj





j=1




S.c :
(PLNE ) X n




 aij xj ≥ bi , i = 1, 2, ..., m

 j=1


xj ≥ 0, xj ∈ N, j = 1, 2, ..., n


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 119 / 190
Programmation linéaire en nombres entiers

Considérons le problème de PLNE suivant :



 Min z = −x1 − x2

 sujet à



−2x1 + 2x2 ≤ 1

16x1 − 14x2 ≤ 7





x1 , x2 ≥ 0, x1 , x2 ∈ N


Ce problème admet une solution optimale continue x = (7, 7.5) avec

z = −14.5

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 120 / 190
Programmation linéaire en nombres entiers

Figure – Exemple PLNE

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 121 / 190
Programmation linéaire en nombres entiers

Remarque
La relaxation continue consiste à supprimer (ou relâcher) les
contraintes d’intégrité du problème
Un cas particulier est lorsque la solution optimale de la relaxation
continue du problème est une solution entière
Dans le cas général, la relaxation continue nous donne une borne
inférieure du problème PLNE (problème de minimisation)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 122 / 190
Programmation linéaire en nombres entiers
Méthode d’arrondi

Pour le problème précédent, les solutions arrondies sont x1 = (7, 7) avec

z = −14 et x2 = (7, 8) avec z = −15
Ces deux solutions arrondies ne sont pas réalisables et, en plus sont très
éloignées de la solution optimale entière x ∗ = (3, 3) du problème avec
z = −6

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 123 / 190
Programmation linéaire en nombres entiers
Méthode d’énumération

La méthode d’énumération consiste à tester toute les solutions entières du

domaine réalisable
Considérons un problème de PLNE et distinguons les deux cas suivants :
Cas 1 : 10 variables de l’ensemble {1, 2, ..., 9} ce qui donne 910 soit
plus de 3.109 cas à tester
Cas 2 : 50 variables binaires, soit 250 cas à tester

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 124 / 190
Programmation linéaire en nombres entiers

Il existe des méthodes efficaces de résolution de PLNE comme :

Méthode de séparation et d’évaluation (Branch and Bound) et ses
variantes
Méthode de coupes
Méthodes des groupes
Méthode de Benders

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 125 / 190
Programmation linéaire en nombres entiers
Partitionnement

Définition
On dit que le problème (P) de domaine réalisable F (P) est partitionné en
sous-problèmes (P1 ), (P2 ), ..., (Pq ) si F (P1 ), F (P2 ), ..., F (Pq ) constitue
une partition de F (P). Autrement dit, si :
1 Toute solution réalisable de (P) est réalisable pour exactement un
sous-problème (Pj )
2 Toute solution réalisable pour l’un des sous-problèmes (Pj ) est
réalisable pour (P)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 126 / 190
Programmation linéaire en nombres entiers
Partitionnement

Exemple
1 Le problème (P) dont le domaine réalisable
F (P) = {xj = 0 ou xj = 1} peut être partitionné en deux problèmes
(P1 ) et (P2 ) de même fonction objectif et ayant respectivement
comme domaine réalisable : F (P1 ) = {xj = 0} et F (P2 ) = {xj = 1}
2 Le problème (P) dont le domaine réalisable
F (P) = {0 ≤ xj ≤ 2 et xj ∈ N} peut être partitionné en trois
problèmes (P1 ), (P2 ), (P3 ) de même fonction objectif et ayant comme
DR respectivement :
F (P1 ) = {xj = 0}, F (P2 ) = {xj = 1} et F (P3 ) = {xj = 2}

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 127 / 190
Programmation linéaire en nombres entiers
Partitionnement

Exemple
Le problème (P) dont le domaine réalisable
F (P) = {0 ≤ xj ≤ 4 et xj ∈ N} peut être partitionné en deux problèmes
(P1 ) et (P2 ) de même fonction objectif et ayant respectivement comme
domaine réalisable : F (P1 ) = {0 ≤ xj ≤ 2 et xj ∈ N} et
F (P2 ) = {3 ≤ xj ≤ 4 et xj ∈ N}

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 128 / 190
Programmation linéaire en nombres entiers
Stratégie de la méthode de résolution

1 Etape 1 : Essayer de solutionner (P), si la solution obtenue par

relaxation continue n’est pas entière alors partitionner (P) en deux ou
plusieurs sous-problèmes et placer les dans la liste
2 Etape 2 : Sélectionner un problème dans la liste. C’est le problème
candidat noté (PC )
3 Etape 3 : Essayer de solutionner (PC ), si la résolution est réussie alors
choisir un autre problème candidat sinon, partitionner le problème
(PC ) en deux ou plusieurs sous-problèmes que l’on place dans la
liste.Le processus est répété tant que la liste est non vide

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 129 / 190
Programmation linéaire en nombres entiers
Stratégie de la méthode de résolution

Remarque
Chaque fois que la solution de (PC ) est faite avec succès, on identifie une
solution réalisable de (P) et on retient la meilleure solution de (P) retenue
jusqu’ici.
Si aucun candidat n’a pas été identifié, alors le problème n’aura pas de
solution optimale. Sinon, le dernier point candidat est considéré comme
solution optimale.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 130 / 190
Programmation linéaire en nombres entiers

Définition
Le problème (P) est dit relaxé si certaines contraintes sont relâchées,
c’est-à-dire ne sont pas prises en considération. Le problème relaxé sera
noté (PR)

Proposition
1 F (P) ⊂ F (PR)
2 F (PR) = ∅ =⇒ F (P) = ∅
3 V (PR) ≤ V (P) (pour un problème de minimisation )
4 Si une solution optimale de (PR) est dans F (P), alors c’est aussi une
solution optimale de (P)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 131 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

La méthode Branch and Bound (B&B) est appelée également méthode de

séparation et évaluation, elle est largement utilisée pour résoudre les
problèmes de PLNE. Nous présentons dans ce qui suit cette méthode
appliquée à un exemple en s’inspirant de la méthode générale de résolution.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 132 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Soit le PLNE suivant : 


 Min 4x − 6y

sujet à





−x + y ≤ 1



x + 3y ≤ 9

3x + y ≤ 15





x, y ≥ 0





x, y ∈ N


Etape 1 (initialisation) : La solution optimale continue est

(xr∗ , yr∗ ) = (1.5, 2.5) et la valeur optimale de l’objectif est z ∗ = −9

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 133 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Etape 2 (séparation) : La deuxième étape dite de séparation (branching)

consiste à séparer le domaine réalisable de (P0 ) en deux sous ensembles
dont aucun ne devra conteneir la solution optimale de (PR0 ). Cette
séparation va se faire par rapport à l’une des deux variables, dite variable
de séparation, qui ne respecte pas la contrainte d’intégrité qui lui est
associée dans le problème (P0 )

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 134 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Nous pouvons choisir une des deux variables pour la séparation, il existe
plusieurs critères de séparation
Choix arbitraire
Critère de la variable du plus petit indice
Critère de la variable la plus distante : choisir une variable ayant une
valeur non entière qui s’écarte le plus de l’entier le plus près
Critère du meilleur Cj
Lorsque plusieurs variables sont jugées intéressantes pour un critère on
peut adopter un autre critère, ainsi de suite. Dans notre exemple les deux
variables seront choisies selon le critère de la variable la plus distante, on
fait donc un choix arbitraire en préférant x

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 135 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Nous obtenons deux sous-ensembles :

{(x, y ) ∈ F (PR0 )/x ≤ 1} ou {(x, y ) ∈ F (PR0 )/x ≥ 2} Ces deux
ensembles candidats nous définissent les deux problèmes candidats :
 

 Min 4x − 6y 
 Min 4x − 6y
 
sujet à sujet à

 


 

 
−x + y ≤ 1 −x + y ≤ 1

 

 
(P1 ) x + 3y ≤ 9 (P2 ) x + 3y ≤ 9
 
3x + y ≤ 15 3x + y ≤ 15

 


 

 
x ≤ 1 x ≥ 2

 

 
 
x, y ∈ N x, y ∈ N
 

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 136 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Évaluation : en relaxons les contraintes du problème (P1 )




 Min 4x − 6y




 sujet à

−x + y ≤ 1
(P1 )


x + 3y ≤ 9




3x + y ≤ 15

x ≤ 1

Nous obtenons la solution optimale entière (x, y ) = (1, 2) avec z = −8,

cette solution constitue une solution réalisable pour le problème (P0 ) et la
valeur -8 constitue une borne supérieure de la valeur optimale de (P0 )

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 137 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Stérilisation : la solution optimale de (P2 )




 Min 4x − 6y




 sujet à

−x + y ≤ 1


 x + 3y ≤ 9

3x + y ≤ 15




x ≥ 2

est (x, y ) = (2, 37 ) et z = −6, elle est donc non entière, donc non
réalisable pour le problème (P). Inutile de séparer suivant la variable y du
fait que les solutions qui seront obtenus seront supérieure ou égale à -6
(> −8) déjà obtenue

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 138 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

1 Initialisation : Résoudre le (PLC ) associé : le Problème Linéaire

Continu.Si cette solution est réalisable pour le (PLE ) alors la solution
courante est optimale. Sinon, identifier une borne inférieure de (PLE )
2 Séparation : Choisir l’une des composantes non-entières xj∗ de (PC ).
Partitionner le sous-ensemble en ajoutant les contraintes :

xj ≤ E (xj∗ )

xi ≥ E (xj∗ ) + 1
3 Si une solution réalisable de (P) a été trouvée, c’est donc une
solution candidate à être optimale. Une borne supérieure est donc
trouvée. Sinon, faire une séparation.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 139 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

1 Evaluation : Déterminer une borne inférieure de la fonction objectif

(la valeur optimale du problème relaxé)
2 Stérilisation :
1 Si le problème relaxé n’est pas réalisable alors retourner en 2
2 Sinon, si la valeur de l’objectif est supérieure à la borne supérieure
retourner à l’étape 2
3 Sinon, si la valeur de l’objectif est inférieure strictement à la borne
supérieure. Retourner à l’étape 2.
3 Test : retourner en 1

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 140 / 190
Programmation linéaire en nombres entiers
Méthode de Branch and Bound

Exercice
Résoudre le PLNE suivant avec la méthode de Branch and Bound :


 Min 4x − 7y − 12z

s.c :




−3x + 6y + 8z ≤ 12



6x − 3y + 7z ≤ 8

−6x + 3y + 3z ≤ 5





x, y , z ≥ 0





x, y , z ∈ N


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 141 / 190
Programmation non linéaire
Rappels

Définition
Normes et distances (EVN, EM)
Normes classiques
Fonctions de plusieurs variables (Dérivées partielles, laplacien,
jacobienne, hessien)
Définitions de limites
Théorème de Weierstrass sur R
Optimum sur R

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 142 / 190
Programmation non linéaire
Rappels

Exercice
Calculer les dérivées partielles premières et secondes des fonctions
suivantes :
1

f (x, y ) = e x cos(y )
2

f (x, y ) = (x 2 + y 2 ) cos(xy )

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 143 / 190
Programmation non linéaire
Rappels

Exercice
Calculer le gradient des fonctions suivantes :
1 f (x, y ) = x 2 + y 2 − 2ax − 2by
2 f (x, y ) = x 4 + y 4 + 2(x − y )2
3 f (x, y ) = 4xy − x 4 − y 4

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 144 / 190
Programmation non linéaire
Introduction

Problème d’ajustement de moindres carrées

Soient X = (xi )i et Y = (yi )i deux séries. On note Mi les points du
plan de coordonnées (xi , yi ).
Soit D une droite quelconque, d’équation y = ax + b.
Soient Pi la projection de Mi sur D parallèlement à (Oy ). Donc les
′
coordonnées de Pi sont de la forme (xi , yi ).

′
Notez que Pi ∈ D, donc yi = axi + b.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 145 / 190
Programmation non linéaire
Introduction

Ajuster par la méthode des moindres carrés consiste à rechercher

parmi toutes les droites D, celle qui rend minimale la somme des
carrés des longueurs Pi Mi .
On notera ei = Pi Mi .

Formulation de (PO)
2 ′
− y i )2 = − axi − b)2
P P P
Minimiser i=1 (ei ) = i=1 (yi i=1 (yi
(a, b) ∈ R2 .
⇒ Problème d’Optimisation non-linéaire continue sans contraintes
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 146 / 190
Programmation non linéaire
Généralités

Définition
Soit f une fonction de Rn 7→ R qui à x 7→ f (x) où x = (x1 , x2 , ..., xn ).
Considérons le problème :

 Min f (x)

(P) s.c :

x ∈ U ⊂ Rn


En général la fonction f est appelée fonctionnelle

Résoudre (P) revient à chercher x ∗ ∈ U, tel que ∀x ∈ U, f (x ∗ ) ≤ f (x)
Le point x ∗ est appelé un minimum global de f sur U

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 147 / 190
Programmation non linéaire
Définitions

Définition
Lorsque U ̸= Rn , on dit que (P) est un problème avec contraintes
Lorsque U = Rn , on dit que (P) est un problème sans contraintes
Lorsque U = {x ∈ Rn , gi (x) ≤ 0, i = 1, ..., m}, on dit qu’on a des
contraintes d’inégalités
Si les fonctions gi et f sont convexes, on dit que le problème (P) est
convexe.
Si la fonction f et les fonctions gi peuvent s’écrire comme différence
de fonctions convexes, on dit que (P) est un problème d’optimisation
DC
Si f est une fonction quadratique et U est un polyèdre convexe, on
dit que (P) est un problème d’optimisation quadratique.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 148 / 190
Programmation non linéaire

Théorème
Soient U une partie fermée bornée (compacte) de Rn et f : Rn 7→ R une
fonction continue, alors le problème :

Min f (x)

(P) s.c :

x ∈ U ⊂ Rn


Admet au moins une solution

Définition
Soit f : Rn 7→ R une fonction. On dit que f est coercive si

lim f (x) = +∞
∥x∥→+∞

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 149 / 190
Programmation non linéaire

Théorème
Soient U une partie non vide fermée de Rn et f : Rn 7→ R une fonction
continue coercive. Si l’ensemble U est non borné, alors il existe au moins
un élement x ∗ ∈ U, tel que f (x ∗ ) = inf{f (x), x ∈ U}

Preuve
Soit x 0 ∈ U, comme f est coercive, alors : ∃r > 0 tel que
∥x∥ > r =⇒ f (x 0 ) < f (x) (prendre A = f (x 0 ) dans la définition de la
limite). Donc l’ensemble des solutions du problème (P) coincide avec
l’ensemble des solutions du problème (P0 ) suivant :

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 150 / 190
Programmation non linéaire

Preuve

 Min f (x)

(P0 ) s.c :

x ∈ U0 = U ∩ {x ∈ Rn , ∥x∥ ≤ r }


Or U0 est fermé et borné et donc d’après le théorème précédent, (P0 )

admet au moins une solution.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 151 / 190
Programmation non linéaire

Considérons le problème :

Min f (x)

(P) s.c :

x ∈ Rn


Dans la suite, nous supposons f continue et admet des dérivées partielles

∂f
premières ∂x i
, i = 1, ..., n et des dérivées partielles secondes
∂2f
∂xi ∂xj , i, j = 1, ..., n continues ∀x ∈ Rn

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 152 / 190
Programmation non linéaire

Définition
Soit A ∈ Mn (R),
On dit que la matrice A est semi-définie positive sur Rn si
∀x ∈ Rn , < Ax, x >≥ 0 ou x t Ax ≥ 0
On dit que la matrice A est définie positive sur Rn si elle est
semi-définie positive sur Rn et si ∀x ∈ Rn , x ̸= 0, < Ax, x >≥ 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 153 / 190
Programmation non linéaire
Conditions nécessaires d’optimalité

Théorème
Pour que x ∗ soit un minimum de f , il faut que les deux conditions
suivantes soient vérifiées :
1 Le gradient ∇f (x ∗ ) = 0
∂2f
2 La matrice hessienne ∇2 f (x ∗ ) = ∂xi ∂xj soit une matrice semi-définie
positive

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 154 / 190
Programmation non linéaire

Exercice
Déterminer les points critiques et calculer le Hessien des fonctions
suivantes :
1 f (x, y ) = −x 4 − y 4
2 f (x, y ) = x 2 − y 3
3 f (x, y ) = 4xy − x 4 − y 4

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 155 / 190
Programmation non linéaire

Remarque
Le contre exemple suivant montre que la réciproque du théorème
précédent n’est pas toujours vraie : Considérons la fonction à une variable
réelle f (x) = x 3 Le point x = 0 vérifie les conditions 1) et 2) du théorème
mais il n’est pas un optimum

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 156 / 190
Programmation non linéaire
Conditions suffisantes d’optimalité

Théorème
Soit f : Rn 7→ R de classe C 2 .Pour que x ∗ soit un minimum de f , il faut et
il suffit que les deux conditions suivantes soient vérifiées :
1 Le gradient ∇f (x ∗ ) = 0
∂2f
2 La matrice hessienne ∇2 f (x ∗ ) = ∂xi ∂xj soit une matrice définie
positive

Définition
On dit que f est strictement convexe sur U si :

∀x, y ∈ U, ∀α ∈]0, 1[, f (αx + (1 − α)y ) < αf (x) + (1 − α)f (y )

Interprétation géométrique : la condition 2) du théorème précédent est

équivalente à f est strictement convexe dans un voisinage de x ∗
K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 157 / 190
Programmation non linéaire

Définition
On dit que x ∗ est un point critique ou un point stationnaire de f si
∇f (x ∗ ) = 0

Remarque
Toutes les méthodes numériques d’optimisation sans contraintes dans Rn
consistent à chercher un point critique x ∗ , ce qui est équivalent à résoudre
le système d’équations :
∂f
(x) = 0, ∀i = 1, ..., n
∂xi

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 158 / 190
Programmation non linéaire

Exercice
Chercher les points critiques des fonctions suivantes :
1 f (x, y ) = x 3 y − y 3 x
2 f (x, y ) = x 4 + y 4 + 2(x − y )2
3 f (x, y ) = 4xy − y 4 − x 4

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 159 / 190
Programmation non linéaire
Méthode de gradient à pas fixe

La méthode du gradient à pas fixe est une méthode itérative qui consiste à
construire une suite x 0 , x 1 , x 2 , ..., x n telle que
f (x 0 ) ≥ f (x 1 ) ≥ ... ≥ f (x n−1 ≥ f (x n ). L’étape de l’algorithme sont :
1 On se donne un point x 0
2 On calcule le gradient ∇f (x 0 )
3 Pour k = 1, ..., n, on calcule x k+1 = x k − h∇f (x k ) avec h > 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 160 / 190
Programmation non linéaire
Méthode de gradient à pas prédéterminé

La méthode du gradient à pas prédéterminé est une méthode itérative qui

consiste à construire une suite x 0 , x 1 , x 2 , ..., x n telle que
f (x 0 ) ≥ f (x 1 ) ≥ ... ≥ f (x n−1 ≥ f (x n ). L’étape de l’algorithme sont :
1 On se donne un point x 0
2 On calcule le gradient ∇f (x 0 )
3 Pour k = 1, ..., n, on calcule x k+1 = x k − αk ∇f (x k ) avec αk > 0

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 161 / 190
Programmation non linéaire
Méthode de gradient normalisé à pas prédéterminé

La méthode du gradient à pas prédéterminé est une méthode itérative qui

consiste à construire une suite x 0 , x 1 , x 2 , ..., x n telle que
f (x 0 ) ≥ f (x 1 ) ≥ ... ≥ f (x n−1 ≥ f (x n ). L’étape de l’algorithme sont :
1 On se donne un point x 0
2 On calcule le gradient ∇f (x 0 )
∇f (x k )
3 Pour k = 1, ..., n, on calcule x k+1 = x k − αk avec αk > 0
∥∇f (x k )∥

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 162 / 190
Programmation non linéaire
Méthode de gradient à pas prédéterminé

Remarque
La méthode est dite à pas prédéterminée car αk est choisi à priori

Théorème
La méthode de gradient à pas prédéterminé est convergente

Remarque
1
En pratique on prend en général αk = k
L’inconvénient de cette procédure est que la convergence peut être
lente
L’avantage est qu’elle peut être généralisée au cas des fonctions non
partout différentiables

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 163 / 190
Programmation non linéaire
Méthode de la plus forte pente

Cette méthode consiste à choisir αk de façon à minimiser la fonction en

α : g (α) = f (x k − α∇f (x k )), ∀k = 1, ..., n
Algorithme de la plus forte pente :
1 Choisir un point de départ x 0
2 A l’itération k poser d k = −∇f (x k ) et chercher αk tel que

f (x k − αk ∇f (x k )) = Min {f (x k − α∇f (x k ))}

3 Poser x k+1 = x k − αk d k
4 Si le test d’arrêt est vérifié, stop, sinon faire k = k + 1 et retourner à
l’étape 2

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 164 / 190
Programmation non linéaire
Méthode de la plus forte pente

Remarque
Comme on ne sait pas d’avance l’optimum et comme on n’est pas sûr que
la convergence a lieu en nombre limité d’itérations, nous devons faire un
test d’arrêt
Les tests d’arrêts les plus utilisés sont :
∂f
max(| ∂x i
|) < ϵ
∥∇f ∥2 < ϵ
|f (x k+1 ) − f (x k )| < ϵ
Dans tous les cas, il est préférable de limiter le nombre d’itérations

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 165 / 190
Programmation non linéaire
Méthode de la plus forte pente

Théorème
Soit f : Rn 7→ R de classe C 1 et coercive alors pour tout point de départ
x 0 , la méthode de la plus forte pente converge vers un point stationnaire.

Remarque
La convergence de la méthode ne signifie pas que l’on trouve un
optimum de f
La convergence de la méthode de la plus forte pente peut être plus
lente

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 166 / 190
Programmation non linéaire
Méthode des directions conjuguées

Définition
On dit que la fonction f est quadratique si :
1
f (x) = < Ax, x > + < b, x > +c
2
Avec A ∈ Mn (R) est une matrice, b ∈ Rn et c ∈ R

Exemple
Exemple de fonction quadratique :

f (x, y ) = x 2 + y 2 + 2xy

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 167 / 190
Programmation non linéaire
Méthode des directions conjuguées

Définition
Soient d 0 , d 1 , ..., d n−1 , n vecteurs de Rn tels que
d i = 1, ∀i = 0, ..., n − 1. (d 0 , d 1 , ..., d n−1 ) sont appelés des directions
de Rn

Définition
On dit que les directions d 0 , d 1 , ..., d n−1 sont mutuellement conjuguées
par rapport à la forme quadratique q(x) si (d i )t Ad i = 0, ∀i ̸= j

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 168 / 190
Programmation non linéaire
Méthode des directions conjuguées

Les étapes de l’algorithme des directions conjuguées :

Définition
1 Initialisation : x 0 , g0 = ∇f (x0 ), d0 = −g0
2 Itération k :
gkt gk
αk = , x k+1 = x k + αk dk
dkt Adk
t g
gk+1 k+1
gk+1 = ∇f (x k+1 ), βk = , dk+1 = −gk+1 + βk dk
gkt gk
3 Si βk = 0 stop, sinon k ← k + 1

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 169 / 190
Programmation non linéaire avec contraintes

Dans ce qui suit nous nous intéressons au programme mathématique

suivant : 


 Min f (x)

sujet à :
(P1 )


 gi (x) ≤ 0, ∀i ∈ I
x ∈ Rn


Où I = {1, ..., m} et X = {x ∈ Rn /gi (x) ≤ 0, i ∈ I } On suppose que lesz

fonctions f et gi sont différentiables.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 170 / 190
Programmation non linéaire avec contraintes

Définition
On dit que x ∗ ∈ X est un optimum local de (P1 ) s’il existe un voisiange
Vx ∗ de x ∗ tel que : f (x ∗ ) ≤ f (x), ∀x ∈ Vx ∗ et gi (x ∗ ) ≤ 0, ∀i ∈ I

Théorème
On suppose que la fonction f et les fonctions gi , (i ∈ I ) sont de classe C 1 ,
alors une condition nécessaire pour que x 0 soit un optimum local du
problème (P1 ) est qu’il existe des nombres λi (i ∈ I ) tels que :
 X
∇f (x 0 ) + λi ∇gi (x0 ) = 0
i∈I
λi gi (x 0 ) = 0, ∀i ∈ I


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 171 / 190
Programmation non linéaire avec contraintes

Problèmes avec contraintes d’égalités et d’inégalités

Considérons le programme :


Min f (x)

sujet à :



(P2 ) gi (x) ≤ 0, ∀i ∈ I = {1, ..., m}

hj (x) = 0, j ∈ J = {1, ..., p}





x ∈ Rn


On suppose que f et gi , i ∈ I et hj , j ∈ J sont de classe C 1

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 172 / 190
Programmation non linéaire avec contraintes

Problèmes avec contraintes d’égalités et d’inégalités

Théorème
Supposons que les fonctions f et gi , i ∈ I et hj , j ∈ J sont de classe C 1 .
Alors une condition nécessaire pour que x 0 soit un optimum local de (P2 )
est qu’il existe des nombres λi , (i ∈ I ) et µj , (j ∈ J) (µj non contrainte en
signe), tels que :
 X X
∇f (x 0 ) +
 λi ∇gi (x 0 ) + µj ∇hj (x 0 ) = 0
i∈I j∈J
λ g (x 0 ) = 0,

∀i ∈ I
i i

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 173 / 190
Programmation non linéaire avec contraintes

Problèmes avec contraintes d’égalités

Dans le cas d’un problème avec des contraintes d’égalités seulement :



Min f (x)

sujet à :
(P3 )


hj (x) = 0, j ∈ J = {1, ..., p}
x ∈ Rn


Une condition nécessaire pour que x 0 soit un optimum local est qu’il existe
des µj (j ∈ J) non contraintes en signe tels que :
X
∇f (x 0 ) + µj ∇hj (x 0 ) = 0
j∈J

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 174 / 190
Programmation non linéaire avec contraintes

Conditions suffisantes d’optimalité

Considérons le programme :



Min f (x)

sujet à
(P)


gi (x) ≤ 0, i ∈ I
x ∈ S ⊂ Rn


Si S = Rn , on retrouve les programmes précédents.

Définition
On appelle fonction de Lagrange associée au programme (P), la fonction :
X
L(x, λ) = f (x) + λi gi (x)
i∈I

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 175 / 190
Programmation non linéaire avec contraintes

Conditions suffisantes d’optimalité

Définition
Soit x ∗ ∈ S et λ ≥ 0. On dit que (x ∗ , λ∗ ) est un point col de L si :
1 L(x ∗ , λ∗ ) ≤ L(x, λ∗ ), ∀x ∈ S
2 L(x ∗ , λ) ≤ L(x ∗ , λ∗ ), ∀λ ≥ 0
Autrement dit L(x ∗ , λ∗ ) est une borne inférieure de L(., λ∗ ) et une borne
supérieure de L(x ∗ , .)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 176 / 190
Programmation non linéaire avec contraintes

Conditions suffisantes d’optimalité

Théorème
Soit x ∗ ∈ S et λ∗ ≥ 0, (x ∗ , λ∗ ) est un point col pou L(x, λ) si et
seulement si :
1 L(x ∗ , λ∗ ) = min(L(x, λ∗ ), x ∈ S)
2 gi (x ∗ ) ≤ 0, ∀i ∈ I
3 λ∗i gi (x ∗ ) = 0, ∀i ∈ I

Théorème
Si (x ∗ , λ∗ ) est un point col de L(x, λ) alors x ∗ est un optimum global de
(P)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 177 / 190
Programmation non linéaire avec contraintes

Définition
Soit C un sous-ensemble de Rn , on définit la fonction ΨC associée à C
par : (
0 si x ∈ C
ΨC (x) =
+∞ sinon
On considère les problèmes :
(
Min f (x)
(P1 )
x ∈C

et (
Min f (x) + ΨC (x)
(P2 )
x ∈ Rn

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 178 / 190
Programmation non linéaire avec contraintes

Proposition
Les problèmes (P1 ) et (P2 ) sont équivalents

Remarque
Comme la fonction Ψc n’est pas continue et donc n’est pas dérivable, les
méthodes que nous avons vues ne sont pas appliquables. Pour remédier à
ce problème, des auteurs ont proposé d’autres méthodes de pénalités.
Considérons le problème :

 Min f (x)



 sujet à
(P)


gi (x) ≤ 0, i ∈ I
x ∈ Rn


K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 179 / 190
Programmation non linéaire avec contraintes
Méthode de pénalités extérieures
Fiacco et Mc Cormic ont proposé la méthode de pénalisation suivante :
On considère la fonction :
(
h(y ) = 0 pour y ≤ 0
h(y ) = y 2 pour y > 0

On pose
m
X m
X
H(x) = h(gi (x)) = (gi (x))2
i=1 i=1

Puis on considère le problème :

(
Min ϕ(x, r ) = f (x) + rH(x)
(P ′ )
x ∈ Rn

Où r > 0 est appelé coefficient de pénalité.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 180 / 190
Programmation non linéaire avec contraintes

Définition
La fonction H est appelée une fonction de pénalisation extérieure (où)
fonction de pénalité extérieure)

Remarque
Le nombre réel r doit être choisi suffisament grand pour que le point
x ∗ obtenu soit proche de l’ensemble des solutions de X .
Si r est choisi trop grand, la fonction ϕ peut être mal conditionnée ce
qui conduit à des difficultés numériques. Il faut donc un compromis
pour le choix de r .

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 181 / 190
Programmation non linéaire avec contraintes

Théorème
Soit H : Rn 7→ R une fonction de pénalisation extérieure vérifiant :
1 H(x) ≥ 0, ∀x ∈ Rn
2 H(x) = 0, ∀x ∈ X = {x ∈ Rn /gi (x) ≤ 0, i ∈ I }
3 H continue
Supposons aussi que f continue, que X est fermé et que l’une des deux
conditions suivantes est vérifiée :
f est coercive : lim f (x) = +∞
∥x∥→+∞
X est borné et lim H(x) = +∞
∥x∥→+∞
Alors, lorsque le coefficient de pénalité r → +∞, la suite x ∗ (r ) admet au
moins un point d’accumulation et tout point d’accumumlation de la suite
(x ∗ (rk ))k est une solution optimale du problème (P)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 182 / 190
Programmation non linéaire avec contraintes

Méthode de pénalités intérieures

Ces méthodes consistent à approcher l’optimum par l’intérieur. On
suppose que X est d’intérieur non vide et que tout de la frontière de X est
limite d’une suite de points appartenant à l’intérieur de X . Soit B la
m
X 1
fonction définie par B(x) = − , on a :
gi (x)
i=1
Dom(B) = int(X )
B(x) ≥ 0, ∀x ∈ int(X )
B(x) → +∞ lorsque x → x ∗ (x ∗ dans la frontière de X )
B est continue si gi , i ∈ I sont continues

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 183 / 190
Programmation non linéaire avec contraintes

Définition
La fonction B est appelée une fonction de pénalisation ou fonction barrière.

Considérons la fonction Ψ(x, t) = f (x) + tB(x), t est appelé le coefficient

de pénalité.
Si f est continue sur X et l’une des conditions suivantes est vérifiée :
f est coercive
X est bornée
Choisissons t1 > 0, on cherche un minimum de Ψ(x, t1 ), on obtient
x 1 = x ∗ (t1 ) ∈ int(X ). Si la quantité t1 B(x 1 ) est suffisament faible alors x 1
est une bonne approximation , stop. Sinon, on prend t2 < t1 et on cherche
x 2 = x ∗ (t2 ) comme minimum de Ψ(x, t2 ) et ainsi de suite on construit une
suite Ψ(x, tk )k

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 184 / 190
Programmation non linéaire avec contraintes

Théorème
Soit X = {x ∈ Rn /gi (x) ≤ 0, i ∈ I } l’ensemble des solutions de (P). On
suppose que X est fermé, que int(X ) ̸= ∅ et que :

∀x ∈ X il existe (xn )n ⊂ int(X ) tel que xn → x

Soit B : Rn 7→ R une fonction de pénalisation intérieure telle que :

B(x) ≥ 0, ∀x ∈ int(x)
B(x) 7→ +∞ lorsque x 7→ x ∗
B est continue et les fonctions gi , i ∈ I sont continues

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 185 / 190
Programmation non linéaire avec contraintes

Théorème
On suppose que f est continue et qu’elle vérifie l’une des conditions
suivantes :
f est coercive
X est bornée
Alors lorsque le coefficient de pénalité tk → 0, la suite (x ∗ (tk ))k admet au
moins un point d’accumulation et tout point d’accumulation de la suite
(x ∗ (tk ))k est un optimum de (P)

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 186 / 190
Programmation non linéaire avec contraintes
Dualité lagrangienne

Considérons le programme :



 Min f (x)

 sujet à
(P)


gi (x) ≤ 0, i ∈ I
x ∈ S ⊂ Rn


X
On a la fonction de Lagrange : L(x, λ) = f (x) + λi gi (x)
i∈I
Pour λ ≥ 0 posons W (λ) = inf{L(x, λ), x ∈ S}. Supposons qu’on a les
conditions sur f et gi et S pour que :

W (λ) = min{L(x, λ), x ∈ S}

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 187 / 190
Programmation non linéaire avec contraintes
Dualité lagrangienne

On a (x ∗ , λ∗ ) est point col de L si et seulement si (x ∗ , λ∗ ) est solution du

problème : 
max min L(x, λ)
(D) λ x∈S
λ ∈ Rn

(D) est appelé le problème dual de (P)

(P) est appelé le problème primal de (D)
W est appelée la fonction duale.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 188 / 190
Programmation non linéaire avec contraintes
Dualité lagrangienne

Théorème
Pour tout λ ∈ Rn+ on a :

W (λ) ≤ W (λ∗ ) ≤ f (x ∗ )

Où W (λ∗ ) est la valeur optimale du problème (D) et f (x ∗ ) est la valeur

optimale du problème (P)

Proposition
La fonction duale W est une fonction convexe de λ

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 189 / 190
Programmation non linéaire avec contraintes
Dualité lagrangienne

Théorème
Si le problème (P) admet un point col (x ∗ , λ∗ ) alors :

max(D) = W (λ∗ ) = f (x ∗ ) = min(P)

Réciproquement, s’il existe x ∗ solution de (P) et λ∗ ≥ 0 tels que :

W (λ∗ ) = f (x ∗ )

Alors (x ∗ , λ∗ ) est un point col.

K. Oufaska (UIR) Cours de mathématiques pour ingénieurs A.U., 2025/2026 190 / 190