Master Recherche en IEAI

Option : Tronc commun

Cours de Recherche Opérationnelle

Par

A
Bertuel TANGUE NDAWA
AW
ND
UE

2024/2025
NG
TA
el
tu
r
Be
 Dedication

A mes très chers amis ;

A
AW
particulièrement à
NGOUNOU BAKAM Yves Ismaël
ND
TIODJO NOUTCHIEU Viviane
UE

MBAKOP YONKEU Raoul.

NG

Je vous dédie ce document comme symbole de témoignage de mon affection

TA

et ma gratitude en vers vous ; certains pour plus de 20 ans d’amitié et d’autre

el

moins ; l’essentiel : se sont ces bons et agréables moments de loin ou de près que
tu

vous et moi avons partagé, partageons et partagerons. Je veux donc vous célébrer
r
Be

(célébrer ces précieux moments couverts de gestes grandioses) à travers ce que

j’apprends à faire (je n’en manquerai pas de le faire avec ce dont je possède) ; ce,
pendant que vous et moi sommes encore sur terre.
Chers Amis, que le Ciel nous prête longue vie et consolide notre amitié pour
en construire d’autres ; mais aussi et surtout, pour œuvrer pour sa gloire ; de telles
œuvres, nous en avons fait et nous en ferons encore ; Dieu nous soutiendra.

2 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
 Table des matières

Dedication 2

Table des matières 4

A
1 Introduction : Problème de recherche opérationnelle 5

AW
1.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ND 5
1.2 Problème de recherche opérationnelle et Vocabulaire . . . . . . . 5
1.3 Exercice introductif . . . . . . . . . . . . . . . . . . . . . . . . . . 6
UE

2 Fonction d’une variable réelle 8

NG

2.1 Généralités : Domaine de définition - ensemble image . . . . . . . 8

TA

2.2 Fonction numérique à variable réelle . . . . . . . . . . . . . . . . . 9

2.2.1 Sens de variation et extrema . . . . . . . . . . . . . . . . 9
el
tu

[Link] Sens de variation . . . . . . . . . . . . . . . . . . 9

r
Be

[Link] Extrema : optimisation des fonctions numériques

à variable réelle . . . . . . . . . . . . . . . . . . . 10
2.2.2 Dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
[Link] Fonction convexe et Fonction concave . . . . . . 13
[Link] Extrema et dérivée . . . . . . . . . . . . . . . . . 14
2.3 Fonction numérique à plusieurs (deux ou trois) variables . . . . . 14
2.3.1 Extrema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Dérivée partielle . . . . . . . . . . . . . . . . . . . . . . . . 15
[Link] Dérivée partielle d’ordre un et différentielles . . . 15
[Link] Dérivée partielle d’ordre supérieur . . . . . . . . 18

3 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
TABLE DES MATIÈRES 4

3 Optimisation non linéaire - Programmation linéaire 19

3.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Bornes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Optimisation d’une fonction à plusieurs variables sans contraintes 22
3.2.1 Existence d’un extremum : Condition suffisante . . . . . . 22
3.2.2 Existence d’un extremum : Condition nécessaire . . . . . . 23
3.2.3 Nature d’un extremum . . . . . . . . . . . . . . . . . . . . 23
3.2.4 Extremum global . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Optimisation sous contraintes . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Contrainte d’égalité . . . . . . . . . . . . . . . . . . . . . . 25

A
AW
3.3.2 Contrainte d’inégalité . . . . . . . . . . . . . . . . . . . . . 28
[Link] Contrainte pavé . . . . . . . . . . . . . . . . . . . 29
ND
3.3.3 Problème linéaire (affine) . . . . . . . . . . . . . . . . . . . 30
UE

[Link] Préliminaire . . . . . . . . . . . . . . . . . . . . . 30
[Link] Résolution . . . . . . . . . . . . . . . . . . . . . . 30
NG

[Link].1 Résolution graphique . . . . . . . . . . . 30

TA

[Link].2 Algorithme du simplexe . . . . . . . . . 31

el

4 Problème de Recherche Opérationnelle 35

r tu
Be

5 Travaux Dirigés 39
5.1 Fonction numérique . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 Problème de Recherche Opérationnelle . . . . . . . . . . . . . . . 45

Bibliographie 48

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
Chapitre One

Introduction : Problème de recherche

opérationnelle

1.1 Historique
La Recherche Opérationnelle (R.O) encore appelée Science Décisionnelle

A
AW
(S.D) est définie comme l’ensemble des méthodes et techniques rationnelles orienté
vers la recherche du meilleur choix dans la façon d’opérer en vu d’aboutir au
ND
résultat visé ou meilleur résultat possible. Cette science a vu le jour au lende-
main de la deuxième guerre mondiale en 1940 ; Patrick Blackett est appelé par
UE

l’état-major anglais afin de résoudre certains problèmes tels que l’implantation

NG

optimale des radars de surveillance ou la gestion des convois d’approvisionnement

TA

([Wikipédia(2019)]).
el
tu

1.2 Problème de recherche opérationnelle et Vo-

r
Be

cabulaire
La décision à prendre d’un problème de R.O découle de l’optimisation de
l’objectif (i.e, de sa minimisation lorsqu’il s’agit des “sorties” ; des dépenses ou de
sa maximisation lorsqu’il s’agit des “entrées” ; des gains). Un problème type de
R.O est décrit par :

- un domaine S : ensemble des valeurs possibles (réelles, entières etc.) ; qui

peut-être linéaire (un espace vectoriel), non linéaire, convexe, etc.,

- des contraintes C : ensemble des restrictions par rapport aux possibilités ;

qui peut-être linéaire (un espace vectoriel), non linéaire, concave, convexe,

5 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
1.3. EXERCICE INTRODUCTIF 6

sous forme d’égalité ou d’inégalités etc.

- de la fonction objectif f : S −→ R ; qui peut-être linéaire, non linéaire,

concave, convexe, etc.,

Symboliquement, un problème de R.O est sous la forme : inf f (x) (min f (x)) ou
x∈C x∈C
sup f (x) (max f (x)).
x∈C x∈C

Definitions 1.2.1. Soit inf f (x) un problème de R.O.

x∈C
- Une solution admissible est une valeur donnée qui satisfait toutes les contraintes,
et appartient au domaine de définition de la fonction objectif.

Exercice 1. Considérons les problèmes de recherche opérationnelle sui-

√ x
vants : min y x − 1 et min 2 . Pour chacun des problèmes de R.O

A
x≥0 y −1

AW
y≥0 x≤0
y≥0
ci-dessus,
ND
(a) déterminer la fonction objectif ainsi que son domaine de définition (le
UE

représenter repère orthonormé (O, I, J)) ;

NG

(b) Déterminer et représenter la contrainte dans le même repère que ci-

dessus ;
TA

(c) Déduire graphiquement et analytiquement l’ensemble des solutions ad-

el

missibles.
r tu

- Une solution optimale est une solution admissible qui optimise la fonction
Be

objectif.

- Modèle de recherche opérationnelle : minimiser la fonction objectif sous la

contrainte C.

1.3 Exercice introductif

L’exemple qui suit est tiré de [Fortz(2013), Site].

Exercice 2. Un homme d’affaires doit effectuer 5 voyages entre Douala (D) et

Yaoundé (Y), en partant le lundi à D et revenant le mercredi de Y à D.

1. Billet aller-retour : 12000 FCFA.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
1.3. EXERCICE INTRODUCTIF 7

2. Réduction de 20% si un weekend est inclus.

3. Aller simple : 75% du prix aller-retour.

- Quelle est la fonction objectif ?

- Quelle(s) la ou les variable(s) ?

- Y a t-il une contrainte ? Si oui la décrire ?

- Dénombrer les alternatives et conclure.

Avant d’aborder vivement le sujet qui nous intéresse (la Recherche Opéra-
tionnelle), nous consacrons le premier chapitre l’étude des fonctions numériques.
L’étudiant est appelé à traiter les exercices intermédiaires qui lui per-

A
mettront de vérifier la compréhension de la partie abordée ; ces exercices seront

AW
corrigés lors des séances de cours. ND
UE
NG
TA
el
r tu
Be

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
Chapitre Two

Fonction d’une variable réelle

Contents
2.1 Généralités : Domaine de définition - ensemble image 8

2.2 Fonction numérique à variable réelle . . . . . . . . . . 9

2.3 Fonction numérique à plusieurs (deux ou trois) va-

A
AW
riables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Cette partie les notions essentielles sur des fonctions à une variable en
ND
générale ; un accent est mis sur des fonctions numériques à variable réelle.
UE
NG

2.1 Généralités : Domaine de définition - ensemble

TA

image
el

Nous présentons la définition de fonction donnée par Dirichlet en 1837.

r tu
Be

1
Definitions 2.1.1. Une fonction f : E −→ F est la donnée de deux ensembles
E et F non vides et d’un procédé qui à tout point x dans E (ensemble de départ)
associe au plus un point y de F (ensemble d’arrivé). On écrit : y = f (x) ou x 7−→
f (x). L’ensemble des points x de E tels f (x) existe est appelé domaine de défini-
tion de f , et noté Df . Dans l’écriture y = f (x), x est appelé un antécédent de y,
et y l’image de x par f ; aussi f (x) est l’expression de f . L’ensemble des points
images de f est noté Im(f ), et donc définie par : Im(f ) = {f (x), x ∈ Df }. Si
E est égal au domaine de définition (Df ) de f , alors f est appelé application.
1. Une fonction de E vers F est une correspondance entre les éléments de E et ceux de
F telle qu’à un éléments de E on associe au plus un élément de F .

8 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
2.2. FONCTION NUMÉRIQUE À VARIABLE RÉELLE 9

Remark Definition 2.1.2. Soit f : E −→ F . Un point y ∈ F peut avoir

plusieurs antécédents par f . Dans ce cas, l’ensemble des antécédents de y par f
est noté f −1 ({y}) et défini par : f −1 ({y}) = {x ∈ E, tel que f (x) = y}.
2x √
Example 2.1.3. f (x) = , g(x) = x2 + 1 et h(x) = x2 − 2,, F (x, y) =
3x − 2
2x + 1
x + y, G(x, y) =
x − y2
Exercice 1.

1. Déterminer les ensembles de départ, et d’arrivée, le domaine de définition,

et l’ensemble image des fonctions définies dans l’Exemple 2.1.3.

2. Dire si f est une application ou simplement une fonction.

3. Déterminer lorsqu’il est possible les images et antécédents de : -1, 0, 2/3,

A
AW
(0,1), et (1,1) par des fonctions définies dans l’Exemple 2.1.3.
ND
2.2 Fonction numérique à variable réelle
UE

Dans cette section sauf mention différente, les fonctions consi-

NG

dérées sont des fonctions numériques d’une variable réelle ; i.e, des
TA

fonctions de R vers R.
el
tu

2.2.1 Sens de variation et extrema

r
Be

[Link] Sens de variation

Definitions 2.2.1. Soit f : R −→ R. Soit I ⊂ Df .

1. f est dite croissante resp (strictement croissante) sur I, si pour tout x, y ∈

I, x < y =⇒ f (x) ≤ f (y) resp (f (x) < f (y)).

2. f est dite décroissante resp (strictement croissante) sur I, si pour tout x, y ∈

I, x < y =⇒ f (x) ≥ f (y) resp (f (x) < f (y)).

3. f est dite constante sur I, si pour tout x, y ∈ I, f (x) = f (y).

4. f est dite monotone resp (strictement monotone) si elle est soit croissante
soit décroissante resp (soit strictement croissante soit strictement décrois-
sante).

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.2. FONCTION NUMÉRIQUE À VARIABLE RÉELLE 10

Exercice 2. Étudier le sens de variation des fonctions suivantes sur R : f1 (x) =

2x + 1, f2 (x) = −5x + 8, f( x) = 4, f( x) = x2 .

[Link] Extrema : optimisation des fonctions numériques à variable

réelle

Definitions 2.2.2. Soit f une fonction numérique à variable réelle définie sur R
et a ∈ R

1. f admet un minimum local (relatif ) en a, s’il existe un intervalle ouvert I

contenant a tel que, pour tout x ∈ I, f (x) ≥ f (a) ; i.e, f (a) est un minorant
de f sur I. f admet un minimum (global) en a si f (a) est minorant sur
Df .

A
AW
2. f admet un maximum local (relatif ) en a, s’il existe un intervalle ouvert I
ND
contenant a tel que, pour tout x ∈ I, f (x) ≤ f (a) ; i.e, f (a) est un majorant
de f sur I. f admet un maximum (global) en a si f (a) est majorant sur
UE

Df .
NG

3. f admet un extremum local respectivement global en a, si f admet un mi-

TA

nimum ou maximum local respectivement global en a.

el

Exercice 3. Pour chacune des courbes suivantes définies sur R, noter celles qui
tu

admettent un extremum local ou global ; les spécifier.

r
Be

2.2.2 Dérivée

Definitions 2.2.3. Soit f : R −→ R une fonction. Soit x0 ∈ R. Si la quantité

f (x) − f (x0 )
lim
x→x0 x − x0

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.2. FONCTION NUMÉRIQUE À VARIABLE RÉELLE 11

existe, il est noté f 0 (x0 ) et appelé dérivé (nombre dérivé) de f en x0 et dans ce

cas, on dit que f est dérivable en x0 . f est dérivable sur un sous ensemble A de
R si f est dérivable en tout point de A. La fonction dérivée de f est noté f 0 .

Remark Definition 2.2.4. Soit f : R −→ R une fonction. Soit x0 ∈ R.

1. Si la quantité
f (x) − f (x0 )
lim
x→x0 x − x−
0

existe, il est noté fg0 (x0 ) et appelé dérivé à gauche (nombre dérivé à gauche)
de f en x0 .

2. Si la quantité
f (x) − f (x0 )
lim

A
x→x0 x − x+
0

AW
existe, il est noté fd0 (x0 ) et appelé dérivé à droite (nombre dérivé à droite)
ND
de f en x0

3. Si f est dérivable en x0 alors fg0 (x0 ) = f 0 (x0 ) = fd0 (x0 )

UE

Proposition 2.2.5. 1. Soit f et g deux fonctions définies sur un intervalle I.

NG

Soit x0 un point de I. Si f et g sont dérivables en x0 , alors, les fonctions :

TA

f + g : x 7−→ f (x) + g(x), f g : x 7−→ f (x)g(x)

el
tu

sont dérivables en x0 et on a :
r
Be

(f + g)0 (x0 ) = f 0 (x0 ) + g 0 (x0 ) et (f g)0 (x0 ) = f 0 (x0 )g(x0 ) + f (x0 )g 0 (x0 )

. Si de plus, g(x0 ) 6= 0, alors la fonction

 
1 1
x 7−→ (x) =
g g(x)

est aussi dérivable en x0 et on a :

 0
1 g 0 (x0 )
(x0 ) = −
g (g(x0 ))2

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.2. FONCTION NUMÉRIQUE À VARIABLE RÉELLE 12

2. Si f est une fonctions dérivable en un point x0 , alors pour tout α > 0, la

fonction
x 7−→ (f (x))α

est dérivable en x0 et on a :

((f )α )0 (x0 ) = αf 0 (x0 ) (f (x0 ))α−1

3. Soit f et g deux fonctions définies respectivement sur deux intervalles I et

J. Soit x0 un point de I tel que f (x0 ) ∈ J. Si f est dérivable en x0 et g en
f (x0 ), alors, la fonction

x 7−→ (g ◦ f )(x) = g(f (x))

A
AW
est dérivable en x0 et on a : ND
(g ◦ f )0 (x0 ) = (g 0 (f (x0 )))f 0 (x0 ).
UE

4. Si f est une fonctions bijective et dérivable en un point x0 de dérivée non

NG

nulle, alors sa fonction réciproque f −1 est dérivable en y0 = f (x0 ) et on a :

TA

1
(f −1 )0 (y0 ) = .
f 0 (x 0)
el
tu

5. Toutes ses règles sur la dérivée sont également vraies pour la différentielle.
r
Be

Dérivée : f 0 Fonction : f Domaine Commentaire

αxα−1 xα R α∈R
1 zx
ezx e R z ∈ C∗
z
1 x
ax := ex ln a a R a ∈ R∗+ {1}
ln a
eix + e−ix
cos x = sin x R
2
e − e−ix
ix
sin x = − cos x R
2
1 π π
= 1 + tan2 x tan x ]− + kπ, + kπ[ k∈Z
cos2 x 2 2

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.2. FONCTION NUMÉRIQUE À VARIABLE RÉELLE 13

1
= 1 + cot2 x − cot x ]kπ, (k + 1)π[ k∈Z
sin2 x
1 x π 
ln tan + ]kπ, (k + 1)π[ k∈Z
cos x 2 2
1 x π π
ln tan ]− + kπ, + kπ[ k∈Z
sin x 2 2 2
x −x
e +e
cosh = sinh R
2
ex − e−x
sinh = cosh R
2
1
2 = 1 − tanh2 x tanh x R
cosh x
1
= −1 + coth2 x − coth x R∗
sinh2 x

A
1 x
√ ] − a, a[

AW
arcsin a>0
a2 − x 2 a
1 1  x
ND
√ arctan R a 6= 0
a2 + x 2 a a
UE

Exercice 4. Déterminer la dérivée et la différentielle des fonctions définies dans

NG

l’Exemple 2.1.3.
TA

[Link] Fonction convexe et Fonction concave

el

Definition 2.2.6. Une fonction f : R −→ R deux fois dérivables sur un intervalle

tu

I est
r
Be

- convexe respectivement strictement convexe sur I, si seulement si f 00 (x) >

0; ∀x ∈ I respectivement f 00 (x) > 0; ∀x ∈ I.

- concave respectivement strictement concave sur I, si seulement si f 00 (x) ≤

0; ∀x ∈ I respectivement f 00 (x) < 0; ∀x ∈ I.

- concave et convexe sur I, si seulement si f 00 (x) = 0; ∀x ∈ I.

Exercice 5. Étudier la concavité d’une application affine sur R (f (x) = ax +

b, a, b ∈ R).

Exercice 6. Soit a, b, c, d ∈ R. Étudier la concavité de l’application f (x) = ax4 +

bx2 + cx + d. On discutera éventuellement la concavité en fonction de la valeur
des paramètres a, b, c et d.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.3. FONCTION NUMÉRIQUE À PLUSIEURS (DEUX OU
TROIS) VARIABLES 14

[Link] Extrema et dérivée

Proposition 2.2.7. Soit c un élément d’un intervalle non vide ]a, b[. Soit f une
fonction numérique à variable réelle f tel que f 0 (c) = 0

- si f est décroissante sur ]a, c[ et croissante sur ]c, b[, alors f (c) est un mi-
nimum local de f .

- si f est croissante sur ]a, c[ et décroissante sur ]c, b[, alors f (c) est un maxi-
mum local de f .,

Proposition 2.2.8. Soient f : R −→ R dérivable sur Df , et a ∈ R. Si f (a)

est un extremum et a est point intérieur de Df (i.e, il existe  > 0, tel que
]a − , a + [⊂ Df ) alors, a est point stationnaire ou critique de f ; i.e, f 0 (a) = 0.

A
AW
Exercice 7. ND
1. Étudier les points extremum des fonctions définies dans l’Exercice 6.
UE

2. Étudier la concavité et les points extremum des fonctions à une variable

définies dans l’Exemple 2.1.3
NG
TA

2.3 Fonction numérique à plusieurs (deux ou trois)

el
tu

variables
r
Be

2.3.1 Extrema

Dans cette section, nous reprenons des définitions et propositions qui ont
été faite dans la sous section 2.2.1 ; s’y référer pourrait rendre la partie plus
digeste ; mieux, les définitions change seulement sur l’ensemble de départ et le
reste est un copié-collé.

Definitions 2.3.1. Soit f une fonction numérique définie sur Rn et a ∈ Rn

1. f admet un minimum local (relatif ) en a, s’il existe un pavé ouvert I conte-

nant a tel que, pour tout x ∈ I, f (x) ≥ f (a) ; i.e, f (a) est un minorant de
f sur I. f admet un minimum (global) en a si f (a) est minorant sur Df .

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.3. FONCTION NUMÉRIQUE À PLUSIEURS (DEUX OU
TROIS) VARIABLES 15

2. f admet un maximum local (relatif ) en a, s’il existe un pavé ouvert I conte-

nant a tel que, pour tout x ∈ I, f (x) ≤ f (a) ; i.e, f (a) est un majorant de
f sur I. f admet un maximum (global) en a si f (a) est majorant sur Df .

3. f admet un extremum local respectivement global en a, si f admet un mi-

nimum ou maximum local respectivement global en a.

Exercice 8. Pour chacune des surfaces suivantes définies sur R2 , noter celles
qui admettent un extremum local ou global ; les spécifier.

A
AW
ND
UE

2.3.2 Dérivée partielle

NG

[Link] Dérivée partielle d’ordre un et différentielles

TA

Cette notion de dérivée partielle est intiment liée à celle de dérivée. Le fait
est qu’ici, on a une fonction à plusieurs variable et comme les règles grammaticales
el
tu

nous l’enseignement, dans une telle circonstance on change de terminologie “la

r
Be

variable” en “une variable”. Ainsi, pour une variable fixé (i.e, on considère les
autres variables comme des paramètres ou des constantes), on a une fonction
numérique réelle (si la fonction de départ était numérique). Par conséquent on
peut reprendre le calcul de dérivée comme dans le chapitre 4 (Sous-Section 2.2.2) ;
c’est d’ailleurs dans cette logique que nous abordons cette partie.

Definition 2.3.2. Soient k ∈ [n]. La k ième dérivée d’une fonction f : Rn −→

R existe en un point (a1 , a2 , . . . , ak−1 , ak , ak+1 , . . . , an ) ∈ Rn , si la fonction dite
k ième fonction partielle

f(a1 ,a2 ,...,ak−1 ,ak+1 ,...,an ) : t ∈ R 7−→ f (a1 , a2 , . . . , ak−1 , t, ak+1 , . . . , an )

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.3. FONCTION NUMÉRIQUE À PLUSIEURS (DEUX OU
TROIS) VARIABLES 16
∂f
est dérivable en ak . On note (a) ou ∂xk f (a) ou encore ∂kf (a)la k ième dérivée
∂xk
de f en a. La k ième dérivée de f existe sur un domaine D ⊂ Rn , si elle existe
en tout point de D.

Recall 2.3.3. Soit (a1 , a2 , . . . , an ) ∈ Rn .

   t
a1 a1
   
   
t
 a2   a2 
(a1 , a2 , . . . , an ) = 
 ..   ..  = (a1 , a2 , . . . , an ).
 et  
 .   . 
   
an an
   t
1 1
Par exemple : (1, 2)t = 

A
 et   = (1, 2).

AW
2 2

Les définitions suivantes sont une généralisation des définitions dans la

ND
Définition 2.2.3.
UE

Definition 2.3.4. Soient k ∈ [n] et f = (f1 , . . . , fm ) une fonction .

NG

1. La k ième dérivée partielle de f existe en un point a ∈ Rn , si la k ième

TA

dérivée partielle de chacune des fonctions fj ; j ∈ [m] existe au point a et

on a :
el

 t
∂f ∂f1 ∂fm
tu

(a) = (a), . . . , (a) .

∂xk ∂xk ∂xk
r
Be

2. Si pour i ∈ [n], la iième dérivée partielle de chacune des fonctions fj ; j ∈

[m] existe au point a, alors on définit la matrice Jacobienne notée Ja (f ) ou
J(a, f ) (ou la différentielle de f en a notée Da f ) de f en a comme suit :
 
∂f ∂f ∂f
Ja (f ) = Da f := (a), (a), . . . , (a) ;
∂x1 ∂x2 ∂xn

qui est une matrice m × n. La Jacobienne de f en a est le déterminant de

Ja (f ) lorsque celui-ci est une matrice carré ; lorsque n = m.

Definition 2.3.5. Soient f une fonction numérique sur Rn et a un point de Rn .

La différentielle Da f de f en a est aussi appelée gradiant de f en a et notée ∇a f

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.3. FONCTION NUMÉRIQUE À PLUSIEURS (DEUX OU
TROIS) VARIABLES 17

et la différentielle da f de f en a est définie par :

−
→ −
→
da f = Da f dx = ∇a f dx

= Da f (dx1 , dx2 , . . . , dxn )t

∂f ∂f ∂f
= (a)dx1 + (a)dx2 + · · · + (a)dxn ;
∂x1 ∂x2 ∂xn

qui est une application n-linéaires de Rn vers R ; qui à un n-uplets

∂f ∂f ∂f
(h1 , h2 , . . . , hn ) , associe (a)h1 + (a)h2 + · · · + (a)hn .
∂x1 ∂x2 ∂xn
Remark Definition 2.3.6. Soient f une fonction numérique sur Rn et a un
point de Rn . Observons que

A
AW
da f = 0 ⇐⇒ Da f = 0 ⇐⇒ ∇a f = 0.
ND
Dans ce cas a est appelé un point critique (ou point stationnaire ; ce vocabulaire
UE

se justifie en la différentielle oo le gradiant comme la vitesse) de f .

NG

Definition 2.3.7. Soit k ∈ N∗ . Une fonction f de Rk vers Rm est différentiable

en un point a de Rk si sa différentielle existe et, elle différentiable sur un ensemble
TA

A si elle l’est en tout point de A.

el

1. Déterminer les 1er et 2ième dérivées partielles des fonctions

tu

Exercice 9.
r

à deux variables définies dans l’Exemple 2.1.3 en (0, 1) et (1, 1).

Be

2. En déduire leur matrice Jacobienne dans chacun des deux cas.

3. Calculer la jacobienne des fonctions à deux variables définies dans l’Exemple 2.1.3
en un point quelconque et les comparer à zéro.

4. En déduire les équations des plans tangents aux Γ(fi ); i ∈ [3] aux points
(0, 1) et (1, 1).

Definition Proposition 2.3.8. Soient f une fonction une fonction numérique

sur Rn et a un point de Rn . L’équation
∂f ∂f ∂f
xn+1 = (a)(x1 − a1 ) + (a)(x2 − a2 ) + · · · + (a)(xn − an ) + f (a)
∂x1 ∂x2 ∂xn
est celle du plan tangent à Γ(f ) au point (x1 , x2 , . . . , xn+1 )

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
2.3. FONCTION NUMÉRIQUE À PLUSIEURS (DEUX OU
TROIS) VARIABLES 18

[Link] Dérivée partielle d’ordre supérieur

Definition 2.3.9. Soient p = p1 + · · · + · · · pn ∈ N, a ∈ R et f = (f1 , . . . , fm )

une fonction. La dérivée partielle d’ordre p de f en a est notée

∂ pf
(a)
∂ p 1 x1 ∂ p 2 x2 · · · ∂ p n xn

et est définie par :

∂ pf ∂ p1 f ∂ p f ∂ p2 f ∂ pn f
   
(a) = ··· (a)
∂ p1 x1 ∂ p2 x2 · · · ∂ pn xn ∂ p1 x1 ∂ p 1 x1 ∂ p 2 x2 ∂ pn xn

lorsqu’elle existe ; où,

∂ pk f (p )
(a) = f(a1k,a2 ,...,ak−1 ,ak+1 ,...,an ) (ak ); ∀k ∈ [n].

A
p
∂ xk
k

AW
Exercice 10. Calculer les dérivées d’ordre 2 + 0, 0 + 2 et 1 + 1 des fonctions
ND
définies dans l’Exercice ?? en (0, 1) et (1, 1).
UE

Definition 2.3.10. Soit k ∈ N. Une fonction f = (f1 , . . . , fm ) est de classe C k si

toutes les dérivées partielles d’ordre inférieur ou égal k existent et sont continuent.
NG

On dit que la fonction f est k fois continument dérivable. Une fonction 0 fois
TA

continument dérivable est une fonction continue.

el

Remark 2.3.11. Soit k ∈ N. Notons que, la dérivée partielle d’ordre k existe est
r tu

continue si et seulement si toutes les dérivées partielles d’ordre inférieur ou égal

Be

k existent et sont continuent. Donc la définition peut se reformuler comme suit :

Une fonction f = (f1 , . . . , fm ) est de classe C k si la dérivée partielle d’ordre k
existe et est continue.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
Chapitre Tree

Optimisation non linéaire - Programmation

linéaire

Contents
3.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Optimisation d’une fonction à plusieurs variables sans

A
AW
contraintes . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 Optimisation sous contraintes . . . . . . . . . . . . . . 25

ND
Les étapes énumérées pour résoudre un problème de recherche opéra-
UE

tionnelle ressort celui de l’optimisation comme une très importante qui suit la
NG

modélisation. L’optimisation d’une fonction f est la recherche des extrema (le

minimum (plus généralement la borne inférieure) ou le maximum (plus générale-
TA

ment la borne supérieure)) de f . Dans certains cas (les plus pratiques d’ailleurs),
el

on restreint le domaine de définition de f par des contraintes. Cela correspond

tu

aux situations vitales comme par exemple, lorsque l’on décide de s’offrir un objet
r
Be

X avec des préférences. Précisément, lorsque suscite un envie, on peut : se fixer

un prix maximum, définir la marque, la couleur, etc. (selon l’objet) ; se sont en
fait des restrictions qui se posent sur l’achat. Mais face aux réalités (les prix,
l’existentiel, etc.) du marché, on cherche à satisfait au mieux ces préférences ; on
est en fait confronté à décider sur ce qu’on trouve (le prix, la marque, la cou-
leur etc.) et ses préférences : c’est de la recherche opérationnelle ou la science
décisionnelle. Cette scène est un vécu quasi-quotidien pour chacun de nous. En
entreprise, le exercice est encore plus complexe et les spécialistes du domaine
cherchent un modèle (définissent une fonction dite objectif avec en général des
contraintes (restrictions)) pouvant le mieux décrire le problème. Une fois fait, il
revient de chercher des solutions du modèle et revenir à une décision sur le pro-

19 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
3.1. PRÉLIMINAIRES 20

blème initiale. Dans ce cours, le modèle est supposé connu dans un premier temps
et la tâche principale est de présenter des méthodes de résolutions qui existent ;
symboliquement, il est question de présenter la résolution des problèmes du type :
inf f (x) (min f (x)) ou sup f (x) (max f (x)) ; avec f fonctions numérique Rn et C
x∈C x∈C x∈C x∈C
un sous ensemble Rn (définie par un pavé, l’égalité ou l’inégalité d’une fonction) ;
pour n = 2, 3, 4. Nous allons par suite traiter quelques problèmes concrets (de la
modélisation à l’optimisation).

3.1 Préliminaires

3.1.1 Bornes

A
AW
Remark 3.1.1. Soient f une fonction numérique (à valeur dans R), et C un
ND
ensemble. On a :

inf f (x) = −sup −f (x) et donc min f (x) = −max −f (x).

UE

x∈C x∈C x∈C x∈C

NG

Ainsi, on peut bien dire sans abus de langage que : Optimiser c’est minimiser ;
c’est maximiser.
TA

Definitions 3.1.2. Soient f une fonction numérique définie sur Rn et C ⊂ Rn .

el

1. arg min f := {a ∈ Rn tel que, f (x) ≥ f (a); ∀x ∈ I}.

tu

C
r

2. arg max f := {a ∈ Rn tel que, f (x) ≤ f (a); ∀x ∈ I}.

Be

C
3. Lorsque C est le domaine de définition, il peut-être omis.

Definition Proposition 3.1.3. Soient A un sous ensemble de R, m et M deux

réels.

1. m est un minorant de A, si ∀x ∈ A, m ≤ x. Si de plus, m est le plus grand

minorant ; i.e,
∀ > 0, ∃a ∈ A tel que a < m +  1 ,

on l’appelle borne inférieure (ou infimum) de A et on écrit m = inf A. Et,

on écrit m = min A, lorsque m = inf A et m ∈ A.
1. m est un majorant, mais si on lui ajoute une valeur aussi petite soit elle, il perd le
fait d’être minorant

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.1. PRÉLIMINAIRES 21

2. A est dit minoré s’il admet un minorant.

3. M est un majorant de A, si ∀x ∈ A, x ≤ M . Si de plus, M est le plus petit

majorant ; i.e,
∀ > 0, ∃a ∈ A tel que a > M −  2 ,

on l’appelle borne supérieure (ou supremum)de A et on écrit M = sup A.

Et, on écrit M = max A, lorsque M = sup A et M ∈ A.
x∈A
4. A est dit majoré s’il admet un majorant.

5. A est dit borné s’il est majoré et minoré.

Proposition 3.1.4. Soit A un sous ensemble de R.

1. Si A admet un minorant respectivement un majorant, alors il admet une

A
AW
infinité de minorants respectivement de majorants.

2. Si A n’admet pas de minorants respectivement de majorants, alors la borne

ND
inférieure de A est égal à −∞ respectivement la borne supérieure de A est
UE

égal à +∞ ; comme pour signaler que, les bornes inférieure et supérieure

NG

d’un sous ensemble de R existent toujours et sont uniques.

TA

Exercice 11.

1. Déterminer : deux minorants, deux majorants (s’ils existent), les bornes

el
tu

inférieure et supérieure (préciser si sont des minimum ou maximum)

 des
1
r

ensembles suivants : N, Z, [0, 1], ]1, 2], [−6, 0[ et ; n ∈ N∗ .

Be

n
2. Étudier la convexité des ensembles ci-dessous.

3. Déterminer : deux minorants, deux majorants (s’ils existent), les bornes

inférieure et supérieure (préciser s’ils sont minimum ou maximum) de l’en-
semble vide.

Proposition 3.1.5. Soit A et B deux sous ensembles de R tel que A ⊂ B.

1. Tout minorant respectivement majorant de B est un minorant respective-

ment majorant de A.

2. inf B ≤ inf A, et sup A ≤ sup B.

2. M est un majorant, mais si on lui enlève une valeur aussi petite soit elle, il perd le
fait d’être majorant

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.2. OPTIMISATION D’UNE FONCTION À PLUSIEURS
VARIABLES SANS CONTRAINTES 22

3.1.2 Ensemble convexe

Definition 3.1.6. Soit n un entier naturel non nul.

1. On dit qu’un sous ensemble A de Rn est convexe si ∀x, y ∈ A, le segment

[x, y] défini par : [x, y] := {βx + (1 − β)y; β ∈ [0, 1]} est contenu dans A ;
autrement, le plus court chemin qui quitte le x pour le point y reste dans A.

2. Tout sous-ensemble A de Rn admet un plus petit (au sens de l’inclusion)

ensemble convexe contenant A ; appelé enveloppe convexe de A.

Example 3.1.7.

1. Les seuls convexes de R sont des segments.

A
2. Tout espace vectoriel est convexe.

AW
Exercice 12. Dans chacun des cas ci-dessus, étudier la convexité de l’ensemble,
ND
et dans le cas non-échéant, représenter l’enveloppe convexe de celui-ci.
UE
NG
TA
el
tu

3.2 Optimisation d’une fonction à plusieurs va-

r
Be

riables sans contraintes

3.2.1 Existence d’un extremum : Condition suffisante

Proposition 3.2.1 (Condition suffisante). Soit n un entier naturel non nul. Si

f est une fonction numérique sur Rn continue vérifiant : lim = +∞ (cette
|x|→+∞
égalité fait de f une fonction coercive) alors f admet un minimum local en un
point x0 ∈ Rn ; i.e, il existe r > 0 tel que,

∀x ∈ Rn , |x − x0 | < r =⇒ f (x) ≤ f (xO ).

Exercice 13.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.2. OPTIMISATION D’UNE FONCTION À PLUSIEURS
VARIABLES SANS CONTRAINTES 23

1. A partir de la Proposition 3.2.1, donnez une condition suffisante pour

qu’une fonctions admette un maximum.

2. Étudier l’existence des extrema des fonctions : f (x, y) = x2 + y 2 , g(x, y) =

p
x + y et h(x, y) = − |x| + |y|

3.2.2 Existence d’un extremum : Condition nécessaire

Proposition 3.2.2 (Condition nécessaire). Soit n un entier naturel non nul. Une
fonction numérique différentiable f sur Rn admet un extremum local en un point
x0 ∈ Rn , alors ∇f (x0 ) = 0.

Exercice 14.

A
AW
1. Déterminer des potentielles antécédents des extrema locaux des fonctions
f (x, y) = x2 + y 2 et k(x, y) = xy.
ND
2. Prouver que la fonction g(x, y) = x + y n’admet pas d’extremum.
UE

Exercice 15. Pour chacune des fonctions f (x, y) = 2x3 + 6xy − 3y 2 + 2,

NG

2 +y 2 )
g(x, y) = x2 y 2 , h(x, y) = (2x2 +3y 2 )e−(x , i(x, y) = xy, j(x, y) = xy 2 +2x2 +y 2
TA

et k(x, y) = x2 + y 2 − 2xy − y déterminer les points critiques

el
tu

3.2.3 Nature d’un extremum

r
Be

Proposition Definition 3.2.3. Soient f fonction numérique deux fois conti-

nument différentiable (i.e, de classe C 2 ) sur un ouvert de Rn et (x0 , y0 ) ∈ Rn .
Soient
r0 = ∂x2 f (x0 , y0 ), s0 = ∂x ∂y f (x0 , y0 ) et t0 = ∂y2 f (x0 , y0 )

et r0 t0 − s20 le déterminant de
 
r0 s 0
Hessf (x0 , y0 ) =  
s0 t 0

la matrice Hessienne de f . Si x0 est un point critique de f , alors On a :

1. Si r0 t0 − s20 > 0 et r0 > 0, alors f admet un minimum en (x0 , y0 ).

2. Si r0 t0 − s20 > 0 et r0 < 0, f admet un maximum en (x0 , y0 ).

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.2. OPTIMISATION D’UNE FONCTION À PLUSIEURS
VARIABLES SANS CONTRAINTES 24

3. Si r0 t0 − s20 < 0 et r0 t0 6= 0, f n’admet ni un minimum, ni un maximum en

(x0 , y0 ) ; (x0 , y0 ) est un point selle ou col.

4. Autrement, on ne peut pas conclure.

Exercice 16. Déterminer lorsqu’il est possible la nature des extrema, arg min f
et arg max f des fonctions f (x, y) = x2 + y 2 et k(x, y) = xy.

Exercice 17. Déterminer les points critiques ainsi que leur nature de la fonction
suivante l(x, y) = x3 + 3xy 2 + 15x + 12y.

3.2.4 Extremum global

A
Proposition 3.2.4. Soit n un entier naturel non nul. Soit f une fonction nu-

AW
mérique définie sur un ensemble convexe de Rn . ND
1. Si f est convexe, tout minimum local de f est global.
UE

2. Si f est concave, tout maximum local de f est global.

3. Si f est strictement convexe respectivement concave, alors f a au plus un

NG

minimum respectivement maximum.

TA

Proposition 3.2.5. Soit f fonction numérique de classe C 2 définie sur un en-

el

semble convexe de R2 .
r tu

1. f est convexe si seulement si det(Hessf (x, y)) ≥ 0 et T r(Hessf (x, y)) > 0 ;
Be

∀(x, y) ∈ R2 .

2. f est concave si seulement si det(Hessf (x, y)) ≥ 0 et T r(Hessf (x, y)) < 0 ;
∀(x, y) ∈ R2 .

Exercice 18.

1. Étudier la globalité des extrema des fonctions f (x, y) = x2 + y 2 , et g(x, y) =

−2x2 − 3y 2 + 2xy.

2. Déterminer arg min f et arg max f .

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 25

3.3 Optimisation sous contraintes

3.3.1 Contrainte d’égalité

Definition 3.3.1. Soit max f (x, y) un problème d’optimisation. La contrainte est

(x,y)∈C
dite d’égalité s’il existe g une fonction numérique sur R2 telle que :

C = {(x, y) ∈ R2 , tel que g(x, y) = 0}.

Donc,
max f (x, y) s’écrire : max f (x, y)
(x,y)∈C g(x,y)=0

Remark Definition 3.3.2. Nous pouvons donc observer de par la Défini-

A
tion 3.3.1 que, deux situations peuvent arriver : la première où de l’équation

AW
g(x, y) = 0 on peut définir y comme une fonction de h(x) (vice-versa) et dans ce
ND
cas, on dit que les variables sont liées (ou que la contrainte est liée) et le problème
initial devient alors max f (x, h(x)). Ce qui reviens à chercher le maximum de la
UE

y=h(x)
fonction numérique à variable réelle : x 7−→ f (x, h(x) . lorsque la fonction h a
NG

de bonnes propriétés (continument différentiable ou linéaire), on peut se référer

TA

à la sous section Sous section [Link].

el

Exercice 19.
tu

1. Trouver le minimum de la fonction f : (x, y) 7−→ x2 + y 2 sous la contrainte

r
Be

x − y = 1. Déterminer arg min f

x−y=1
2. Quel est l’aire maximal d’un rectangle sachant le demi-périmètre est égal à
9cm ? Déterminer arg max f ; où, C est la contrainte.
C
3. S’il vous est demandé de fabriquer des gâteaux rectangulaires de pourtour
connu, que feriez vous pour optimiser votre gain ?

4. Deux bols rectangulaires de même périmètre diffèrent par l’égalité des côtés
ou non. Que choisirez vous pour acheter votre farine ?

Exercice 20. 1. Résoudre : max 5x2 + 6xy − 3y 2

x+2y=10

2. Discuter en fonction des réels a, b et c le problème d’optimisation de ax2 +

bxy + cy 2 sous la contrainte x + y = 10.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 26

Exercice 21. Soit le problème d’optimisation de xy sous la contrainte 4x2 + y 2 =

4

1. Représenter le domaine.

2. Déterminer les extrema de la fonction et leur nature sur le domaine.

Proposition Definition 3.3.3. Soit max f (x, y) un problème d’optimisation dif-

g(x,y)=0
férentiable (i.e, f l’est) avec une contrainte d’égalité et différentiable (i.e, g l’est).
Si f possède un extremum en (x0 , y0 ) vérifiant ∇g(x0 , y0 ) 6= 0, alors il existe un
réel λ0 appelé multiplicateur de Lagrange tel que (x0 , y0 , λ0 ) soit un point critique
du Lagrangien L ; i.e, 



 ∂x L(x0 , y0 , λ0 ) = 0

A


(3.3.1)

AW
 ∂y L(x0 , y0 , λ0 ) = 0



∂λ L(x0 , y0 , λ0 ) = 0;
 ND
où,
UE

L : (x, y, λ) 7−→ f (x, y) + λg(x, y).

NG

Donc,
(3.3.1) ⇐⇒ ∇f (x0 , y0 ) = −λ0 ∇g(x0 , y0 ).
TA

Remark 3.3.4.
el
tu

1. La Proposition Définition 3.3.3 permet de trouver (x0 , y0 ) antécédent

r
Be

d’un point extremum de f sans toute fois expliciter sa nature (maximum ou

minimum) ; donc on reste sur sa soif pour conclure sur le problème posé.
D’où l’importance de faire appel à celle qui suit ; qui donne des précisions
sur la nature de l’extremum dans certains cas.

2. Afin de simplifier la proposition qui suivra, remarquons que, L admet un

minimum en (x0 , y0 , λ0 ) (sans contrainte) si seulement si f admet un mi-
nimum en (x0 , y0 ) sous contrainte g = 0 (i.e, g(x, y) = 0; ∀(x, y) ∈ Dg ).
Ce qui laisse voir que lambda joue plus un rôle de paramètre (qu’on dira
même neutre) par rapport au problème de départ ; donnons lui cette place
de paramètre en définissant la fonction Lλ pour λ fixé comme suit :

Lλ : (x, y) 7−→ Lλ (x, y) = L(x, y, λ).

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 27

La différence entre deux fonctions est que, Lλ est défini pour une valeur fixé
de λ ; ce qui n’est pas le cas pour L.

Definition Proposition 3.3.5. Soit max f (x, y) un problème d’optimisation dif-

g(x,y)=0
férentiable avec une contrainte d’égalité et différentiable. Soit (x0 , y0 , λ0 ) un point
critique du Lagrangien. Posons :

r0 = ∂x2 Lλ0 (x0 , y0 ), s0 = ∂x ∂y Lλ0 (x0 , y0 ) et t0 = ∂y2 Lλ0 (x0 , y0 ).

Soit r0 t0 − s20 le déterminant de Lλ0

 
r0 s0
HessLλ0 (x0 , y0 ) =  
s0 t0

A
la matrice Hessienne de Lλ0 en (x0 , y0 ). On a (les mêmes conclusions dans la

AW
Proposition 3.2.3) : ND
1. Si r0 t0 − s20 > 0 et r0 > 0, alors Lλ0 donc f sous la contrainte g = 0 admet
UE

un minimum local en (x0 , y0 ).

2. Si r0 t0 − s20 > 0 et r0 < 0, alors Lλ0 donc f sous la contrainte g = 0 admet

NG

un maximum local en (x0 , y0 ).

TA

3. Si r0 t0 − s20 < 0 et r0 t0 6= 0, alors Lλ0 donc f sous la contrainte g = 0

el

n’admet ni un minimum ni un maximum en (x0 , y0 ) ; (x0 , y0 ) est un point

tu

selle ou col.
r
Be

4. Autrement, on ne peut pas conclure.

Exercice 22.

1. Déterminer les points extrema de la fonction f (x, y) = x2 + y 2 sous la

contrainte xy = 1. Donner si possible la nature des ces extrema.

2. Déterminer arg max f ; où, C est la contrainte.

C

Remark 3.3.6. La méthode du lagrangien donne condition nécessaire pour qu’une

fonction atteigne son extremum en un point. Dans certains cas, elle donne la
nature de l’extremum. Pour prolonger cette méthode, on peut faire recourt au
théorème Weierstrass qui affirme dans certains cas l’existence d’un minimum et
maximum

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 28

Theorem 3.3.7 (Weierstrass). Si f est une fonction continue, et que la contrainte

définit un ensemble compact 3 , alors f atteint son minimum et son maximum.

Exercice 23. Soient f (x, y) = x2 + y 2 et g(x, y) = 4x2 + y 2 − 1

1. Représenter l’ensemble g = 0.

2. Justifier que les fonctions f et g sont continument différentiables (et même

plus une infinité de fois continument différentiables).

3. Déterminer le Lagrangien associé au problème d’optimisation de f sous la

contrainte g = 0.

4. Déterminer les points critiques ainsi que leur nature.

A
5. Déterminer arg min f et arg max f ; où, C est la contrainte définie par g =

AW
C C
0. ND
3.3.2 Contrainte d’inégalité
UE

Definition 3.3.8. Soit max f (x, y) un problème d’optimisation. La contrainte

NG

(x,y)∈C
est dite d’inégalité s’il existe g = (g1 , . . . , gk ) et h = (h1 , . . . , hm ) ; pour certains
TA

k, m ∈ N∗ tels que
el

C = {(x, y) ∈ R2 , tel que gi (x, y) ≤ 0; i ∈ [k] et hj (x, y) = 0; j ∈ [m]}.

r tu
Be

Donc,
max f (x, y) s’écrire : max f (x, y) .
(x,y)∈C gi (x,y)≤0; i∈[k]
hj (x,y)=0; j∈[m]

La résolution des problèmes d’optimisation des fonctions à plusieurs va-

riables sous contraintes d’inégalité font généralement appelle à la méthode de
Karush-Kuhn-Tucker (KKT) ; qui necessite des études approfondies. Pour des
raisons pédagogiques, nous allons nous intéresser seulement à quelque cas parti-
culiers de ces problèmes.
3. fermé et borné ; pour une contrainte d’égalité, il suffit que l’ensemble soit borné

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 29

[Link] Contrainte pavé

Remark Proposition 3.3.9. Une contrainte C en pavé (ouvert) ; i.e, C =

]a1 , a2 [×]b1 , b2 [ est une contrainte d’inégalité. En effet,

C = {(x, y) ∈ R2 , tel que gi (x, y) < 0; i ∈ [4]};

avec, gi (x, y) = (−1)i x − ai , i = 1, 2 et gi (x, y) = (−1)i y − bi , i = 3, 4.

Proposition 3.3.10. Soient f une fonction numérique de classe C 1 définie sur

un pavé ouvert C. Si f atteint son extremum en un point x0 ∈ C sous la contrainte
C, alors ∇f (x0 ) = 0 (i.e, x0 est un point critique de f ). De plus (cas particulier
de la Proposition 3.2.4 ; car un pavé est un ensemble convexe),

A
AW
1. si f est convexe respectivement strictement convexe, tout minimum local de
f est global respectivement f a au plus un minimum ;
ND
2. si f est concave respectivement strictement concave, tout maximum local de
UE

f est global respectivement f a au plus un maximum.

NG

Cette proposition prend la forme plus générale et précise suivante.

TA

Proposition 3.3.11. Soient f une fonction numérique de classe C 1 sur un en-

el

semble convexe C ⊂ R2 .
tu

1. si f est convexe, f atteint son minimum global en x0 ∈ C sous la contrainte

r
Be

C, si seulement si ∇f (x0 ) = 0 ;

2. si f est concave, f atteint son maximum en x0 ∈ C sous la contrainte C,

si seulement si ∇f (x0 ) = 0.

Exercice 24. Soit le problèmes suivant : max −x2 − 6y 2 − xy + 2x + 3y

−3<x<0
1<y<2

1. Représenter le domaine.

2. Montrer que la fonction objectif nommée f est concave.

3. Déterminer le point critique de f ainsi que sa nature.

4. Déterminer arg min f et arg max f ; où, C est la contrainte tel que présentée
C C
ci-haut.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 30

3.3.3 Problème linéaire (affine)

[Link] Préliminaire

Definition 3.3.12. Un problème d’optimisation est dit linéaire (P OL) lorsque les
applications g et h de la Définition 3.3.8 sont affines. De tels problèmes peuvent-
être traités graphiquement (en dimension 2 uniquement), ou par la méthode de
simplexe.

Definition 3.3.13. Soient n, m ∈ N, A ∈ Mm,n (R), C, X ∈ Mn,1 (R) et B, Y ∈

Mm,1 (R). Les problèmes suivantes

max Z = C t X et max Zt = B t Y
AX≥B A Y ≥C

A
X≥0 Y ≥0

AW
sont dits duaux.
ND
Exercice 25. Déterminer le problème duale à celui suivant :
UE

max z = 5x + 4y
3x+2y≤12
NG

y−x≤1
x+2y≤6
y≤2
TA

x, y≥0

Remark 3.3.14. Pour des problèmes d’optimisations linéaires (fonction objectif

el

linéaire (affine) et contrainte d’inégalité définie par des fonctions linéaires (af-
r tu

fines) ; i.e, un polyèdre), les extrema se trouvent aux sommets du polyèdre. Un

Be

problème qui se pose peut-être le nombre relativement élevé de sommets. Nous

présentons dans la suite deux méthodes permettant de ne pas évaluer tous les
sommets.

[Link] Résolution

[Link].1 Résolution graphique

Exercice 26. Soit le problème de l’Exercice 25.

1. Représenter la contrainte

2. Représenter dans le même repère une courbe de niveau de la fonction objectif

passant par l’intérieur de la contrainte.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 31

3. Rechercher une direction dans laquelle la fonction objectif croit (décroit) et

déduire les solutions

4. Déterminer arg min f et arg max f ; où, C est la contrainte.

C C
5. Déduire le minimum et le maximum de la fonction objectif sous la contrainte.

[Link].2 Algorithme du simplexe

Exercice 27. Résoudre les problèmes suivants :

max T = −x − y − 3z et min T = x + y + 3z
2x+y+z≤5 2x+y+z≤5
4x+y+z≤11 4x+y+z≤11
x+y+2z≤8 x+y+2z≤8
x,y,z≥0 x,y,z≥0

A
Déduire les solutions de :

AW
max xn+1 = c + ni=1 −|ai |xi
P Pn
et min xn+1 = c + i=1 |ai |xi ;
ND
Ax≤b AX≤b
xi ≥0 xi ≥0

où, n ≥ 2, x = (x1 , . . . , xn )t , ai ∈ R, 0 ≤ b ∈ Mm,1 , et A ∈ Mm,n ; avec m ≥ 2.

UE
NG

1. Préliminaire :

(a) Variables d’écart et d’excédent : Le principe est basé sur le

TA

fait que, pour deux nombres réels a et b fixés, il existe c tel que a+c = b.
el

Alors pour être plus précis dans les terminologies, considérons g une
tu

fonction numérique à n ∈ N∗ variable(s) x1 , . . . , xn tel g(x1 , . . . , xn ) 6=

r
Be

b ; pour un certain b ∈ R. On suppose que g dépend d’au moins deux

variables ou que b est non nul. Un réel positif e est une variable d’écart
resp d’excédent de l’inéquation g(x1 , . . . , xn ) 6= b si g(x1 , . . . , xn ) + e =
b resp g(x1 , . . . , xn ) − e = b. Un P OL sera noté P OL= lorsque toutes
les fonctions de contraintes seront sous forme d’égalité.
Exercice 28. Déterminer le P OL= des P OL suivants :

max z = 3x + 4y et min z = 3x + 4y
3x+2y≤2 3x+2y≤2 (3.3.2)
y+3x≤1 y+3x≤1
x,y≥0 x,y≥0

(b) Variables de base : Soit (S) un système de m ∈ N∗ équation(s)

à n ∈ N∗ inconnu(s) x1 , . . . , xn avec m < n. Si on suppose n − m

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 32

xi1 , . . . , xin−m variables nulles, alors le système obtenu est défini par
des variables dites de bases et une solution obtenue du système ini-
tiale sous l’hypothèse ci-haut (n − m variables nulles) est dite de base
{x1 , . . . , xn } \ {xi1 , . . . , xin−m }.
Exercice 29. Déterminer trois solutions de base (la méthode de Gauss
est recommandée) de la contrainte des P OL= issu des POL (3.3.2).

(c) Classe : Les problèmes considérés ici sont ceux qui peuvent prendre
la forme :

min xn+1 = at x ou max xn+1 = at x

Ax≤b Ax≤b (C − P OL)
x≥0 x≥0

où, a ∈ Mn,1 , A ∈ Mm,n , 0 ≤ b ∈ Mm,1 et x = (x1 , . . . , xn )t . Et, en

A
AW
additionnant les variables d’écart on obtient la forme :
ND
min xn+1 = at x ou max xn+1 = at x
A0 x0 =b A0 x0 =b
(C − P OL= )
x0 ≥0 x0 ≥0
UE

où, A0 = (A, Im ) et x0 = (x, e) = (x1 , . . . , xn , e1 , . . . , em )t ; m.

NG

Ainsi, une solution de base de (C − P OL= ) sera dite admissible si

toutes les composantes sont positives ou nulles. La condition imposée
TA

sur b (b ≥ 0) fait de 0 = 0Rn complété avec les valeurs des variables

el

d’écart une solution admissible. Il initialise ainsi donc l’algorithme du

tu

simplex. Deux solutions sont dites adjacentes si les variables de base

r
Be

ne diffèrent que d’un seul élément.

Exercice 30. Déterminer deux solutions adjacentes du POL (3.3.2).

2. Algorithme du simplex
Rendu à cette étape, nous sommes assez outillés pour aborder avec aisance
les différentes étapes de l’algorithme. Le système sera écrit sous la forme

 A0 x0 = b

(3.3.3)
 xn+1 = at x


avec pour objectif de chercher la valeur maximale ou minimale de xn+1 . Le

traitement est mieux sous forme matricielle. Dans ce qui suit nous décrivons
l’algorithme.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 33

(a) Une solution initiale triviale est sous la forme (0, . . . , 0, e1 , . . . , em ) ;

| {z }
nf ois
clairement, on pose (x1 , . . . , xn ) = (0, . . . , 0) dans A0 x0 = b, et déduit
(e1 , . . . , em ).
Exercice 31.

i. Déterminer une solution initiale de (3.3.2).

ii. En déduire une forme matricielle (un seul bloc sans inconnu) de
(3.3.2).

Si tous les coefficients de xn+1 sont négatifs resp positifs selon que
le problème est de maximiser resp minimiser, le processus s’arrête et
la solution initiale (0, . . . , 0, e1 , . . . , em ) maximise resp minimise xn+1 .

A
| {z }
nf ois

AW
Sinon,
ND
(b) on cherche la solution adjacente à (0, . . . , 0, e1 , . . . , em ) dans A0 x0 = b ;
| {z }
nf ois
faisant entrer xi dans la base ; où l’indice i est choisi tel que ai =
UE

max{ak ; k ∈ [n]}. Et naturellement, un ej sortira de la comme ; c’est

NG

celui qui en prenant la valeur 0 dans A0 x0 = b (modulo xk = 0, k ∈

TA

[n] \ {i}) minimise xi . Et le processus recommence, jusqu’à ce que tous

les coefficients de xn+1 sont négatifs resp positifs selon que le problème
el
tu

est de maximiser resp minimiser.

r
Be

Exercice 32.

1. Résoudre les problèmes suivants par la méthode de simplexe

max z = 5x + 2y et min z = −x − 9y
3x+2y≤2 3x+2y≤2
y+3x≤1 y+3x≤1
x,y≥0 x,y≥0

2. Traiter les problèmes en (3.3.2).

Exercice 33. Soit

  
x + 2y + z ≤ 430

 
 


 
 


 
 

D1 = (x, y, z) ∈ R3+ , 3x + 2z ≤ 460 , T1 = 3x + 2y + 5z,

 
 


 
 


 x + 4z ≤ 420
 


TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
3.3. OPTIMISATION SOUS CONTRAINTES 34

  
x + 2y + z ≤ 4

 
 


 
 


 
 

D2 = (x, y, z) ∈ R3+ , 2x + 5y + z ≤ 8 , T2 = x + 7y + 8z.

 
 


 
 


 x + y + z ≤ 4
 


Résoudre par la méthode de simplexe les problèmes suivants :

min T1 , max T1 , min T2 , max T2 .
D1 D1 D2 D2

A
AW
ND
UE
NG
TA
el
r tu
Be

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
Chapitre Four

Problème de Recherche Opérationnelle

Cette partie est consacrée à la résolution de quelques problèmes de

recherche opérationnelle. De tels problèmes, nous en avons déjà présenter à l’in-
troduction (Exemple 2), et dans Exercice 19 ; leur résolution consiste à :

1. l’identification des variables ;

A
AW
2. la mathématisation (modélisation) du problème ; il s’agit de trouver un
modelé mathématique qui décrit le problème posé ; autrement dit, il s’agit
ND
de trouver une fonction qui détermine les différentes valeurs possibles de
UE

l’objectif (fonction objectif) relativement aux variables, et de formaliser les

NG

contraintes ;

3. la résolution du problème d’optimisation ;

TA

4. et le retour au problème posé.

el
tu

Exercice 34 (PAF-1010 UQTR, S4). Une compagnie fabrique deux types d’acier :
r
Be

Acier trempé (T) et l’acier détrempé (D). Le profit pour une tonne d’acier est de
6k et 4k pour l’acier T et D respectivement. Il faut 2 et 3 tonnes de matières
premières pour les aciers T et D respectivement tandis que le temps de produc-
tion est respectivement de 6 et 4 unités. La compagnie dispose de 120 tonnes de
matières premières et de 100 unités de temps

1. Identifier les variables.

2. Déterminer la fonction objectif ; puis donner son expression analytique.

3. Formaliser le problème.

4. Résoudre le problème modéliser graphiquement, et par méthode de simplexe.

5. Répondre au problème initial.

35 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
 36

Exercice 35 (PAF-1010 UQTR, S4). Un constructeur automobile doit livrer son

modèle AA à 4 concessionnaires à partir de trois usines de production. Les dis-
ponibilités aux usines sont respectivement de 80, 40 et 100 unités tandis que les
démandes des vendeurs sont de 40, 75, 25 et 60 pour les concessionnaires I, II, III
et IV respectivement. Les coûts de livraison des automobiles, en centaine d’unités
(u), sont donnés par le tableau suivant :

Concessionnaire
I II III IV
1 4 2 6 4

A
Usines 2 8 6 10 8

AW
3 6 4 8 6 ND
1. Interpréter chaque élément du tableau.

2. Identifier les variables.

UE

3. Déterminer la fonction objectif ; puis donner son expression analytique.

NG

4. Formaliser le problème.
TA

5. Résoudre le problème modéliser par méthode de simplexe.

el

6. Déterminer le plan de livraison optimal.

r tu

Exercice 36 (R.0 - L3 G- M. MEGHRAOUI, CAS MPM DANS LE PO...). L’en-

Be

treprise DURALUMIN fabrique pour des entreprises de quincaillerie des pièces

en inox. Ces pièces sont de trois types : A, B, C, Elles sont fabriquées par lots de
50 dans un atelier où sont rassemblées deux machines pour la découpe de l’inox,
une machine pour l’emboutissage, deux machines pour le polissage et la finition.
Chaque machine fonctionne 120 heures par mois. Les charges variables de fabri-
cation sont rassemblées dans le tableau suivant :

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
 37

Coût de l’heure Lot A Lot B Lot C

Découpe 20u 1h 1.5h 1.5h
Emboutissage 20u 1h 1.5h 1.5h
Polissage et finition 20u 1h 1.5h 1.5h
Inox 20u 1h 1.5h 1.5h
Prix de vente (H.T) 200u 200u 210u
1. Identifier les variables.

2. Déterminer l’objectif

3. Donner l’expression analytique de l’objectif.

4. Formaliser le problème.

A
5. Résoudre le problème formalisé.

AW
6. Revenir proposer une solution au chef de l’entreprise.
ND
Exercice 37. Le responsable de l’usine de VANNES de la société Pro-Mer sou-
UE

haite lancer la production de combinaisons de plongée ; le modèle « Shorty », forme

NG

short et manches courtes, noté « S » et le modèle « Long John », combinaison

longue, noté « L ». Il désire mettre au point un programme optimal de production
TA

afin de maximiser la rentabilité de ce projet. La fabrication d’une combinaison de

el

plongée occuperait trois ateliers A, B, C pendant une durée exprimée en minutes

tu

et notée dans le tableau ci-dessous.

r
Be

Atelier modèle S Modèle L temps mensuel atelier

A 20 minutes 25 minutes 36000 minutes
B 20 minutes 30 minutes 45000 minutes
C 15 minutes 15 minutes 24000 minutes

La compatibilité analytique prévisionnelle indique les chiffres :

élément unitaires modèle S Modèle L

Marché potentiel 1000 unités 700 unités
Prix de vente 500 u 700 u
Charge variables 350 u 500 u

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
 38

Résoudre le problème par les méthodes graphique et de simplexe.

A
AW
ND
UE
NG
TA
el
r tu
Be

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
Chapitre Five

Travaux Dirigés

5.1 Fonction numérique

Exercice 1.

1. Déterminer les ensembles de départ, et d’arrivée, le domaine de définition,

A
AW
et l’ensemble image des fonctions définies dans l’Exemple 2.1.3.

2. Dire si f est une application ou simplement une fonction.

ND
3. Déterminer lorsqu’il est possible les images et antécédents de : -1, 0, 2/3,
UE

(0,1), et (1,1) par des fonctions définies dans l’Exemple 2.1.3.

NG

Exercice 2. Étudier le sens de variation des fonctions suivantes sur R : f1 (x) =

TA

2x + 1, f2 (x) = −5x + 8, f( x) = 4, f( x) = x2 .
el

Exercice 3. Pour chacune des courbes suivantes définies sur R, noter celles qui
tu

admettent un extremum local ou global ; les spécifier.

r
Be

Exercice 4. Déterminer la dérivée et la différentielle des fonctions définies dans

l’Exemple 2.1.3.

Exercice 5. Étudier la concavité d’une application affine sur R (f (x) = ax +

b, a, b ∈ R).

39 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]
5.2. OPTIMISATION 40

Exercice 6. Soit a, b, c, d ∈ R. Étudier la concavité de l’application f (x) = ax4 +

bx2 + cx + d. On discutera éventuellement la concavité en fonction de la valeur
des paramètres a, b, c et d.

Exercice 7.

1. Étudier les points extremum des fonctions définies dans l’Exercice 6.

2. Étudier la concavité et les points extremum des fonctions à une variable

définies dans l’Exemple 2.1.3

Exercice 8. Pour chacune des surfaces suivantes définies sur R2 , noter celles
qui admettent un extremum local ou global ; les spécifier.

A
AW
ND
UE
NG

Exercice 9. 1. Déterminer les 1er et 2ième dérivées partielles des fonctions

TA

à deux variables définies dans l’Exemple 2.1.3 en (0, 1) et (1, 1).

el

2. En déduire leur matrice Jacobienne dans chacun des deux cas.

r tu

3. Calculer la jacobienne des fonctions à deux variables définies dans l’Exemple 2.1.3
Be

en un point quelconque et les comparer à zéro.

4. En déduire les équations des plans tangents aux Γ(fi ); i ∈ [3] aux points
(0, 1) et (1, 1).

Exercice 10. Calculer les dérivées d’ordre 2 + 0, 0 + 2 et 1 + 1 des fonctions

définies dans l’Exercice ?? en (0, 1) et (1, 1).

5.2 Optimisation
Exercice 11.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.2. OPTIMISATION 41

1. Déterminer : deux minorants, deux majorants (s’ils existent), les bornes

inférieure et supérieure (préciser si sont des minimum ou maximum)
 des
1
ensembles suivants : N, Z, [0, 1], ]1, 2], [−6, 0[ et ; n ∈ N∗ .
n
2. Étudier la convexité des ensembles ci-dessous.

3. Déterminer : deux minorants, deux majorants (s’ils existent), les bornes

inférieure et supérieure (préciser s’ils sont minimum ou maximum) de l’en-
semble vide.

Exercice 12. Dans chacun des cas ci-dessus, étudier la convexité de l’ensemble,
et dans le cas non-échéant, représenter l’enveloppe convexe de celui-ci.

A
AW
ND
UE

Exercice 13.
NG

1. A partir de la Proposition 3.2.1, donnez une condition suffisante pour

TA

qu’une fonctions admette un maximum.

2. Étudier l’existence des extrema des fonctions : f (x, y) = x2 + y 2 , g(x, y) =

el
tu

p
x + y et h(x, y) = − |x| + |y|
r
Be

Exercice 14.

1. Déterminer des potentielles antécédents des extrema locaux des fonctions

f (x, y) = x2 + y 2 et k(x, y) = xy.

2. Prouver que la fonction g(x, y) = x + y n’admet pas d’extremum.

Exercice 15. Pour chacune des fonctions f (x, y) = 2x3 + 6xy − 3y 2 + 2,

2 +y 2 )
g(x, y) = x2 y 2 , h(x, y) = (2x2 +3y 2 )e−(x , i(x, y) = xy, j(x, y) = xy 2 +2x2 +y 2
et k(x, y) = x2 + y 2 − 2xy − y déterminer les points critiques

Exercice 16. Déterminer lorsqu’il est possible la nature des extrema, arg min f
et arg max f des fonctions f (x, y) = x2 + y 2 et k(x, y) = xy.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.2. OPTIMISATION 42

Exercice 17. Déterminer les points critiques ainsi que leur nature de la fonction
suivante l(x, y) = x3 + 3xy 2 + 15x + 12y.

Exercice 18.

1. Étudier la globalité des extrema des fonctions f (x, y) = x2 + y 2 , et g(x, y) =

−2x2 − 3y 2 + 2xy.

2. Déterminer arg min f et arg max f .

Exercice 19.

1. Trouver le minimum de la fonction f : (x, y) 7−→ x2 + y 2 sous la contrainte

x − y = 1. Déterminer arg min f
x−y=1

A
2. Quel est l’aire maximal d’un rectangle sachant le demi-périmètre est égal à

AW
9cm ? Déterminer arg max f ; où, C est la contrainte.
C
ND
3. S’il vous est demandé de fabriquer des gâteaux rectangulaires de pourtour
connu, que feriez vous pour optimiser votre gain ?
UE

4. Deux bols rectangulaires de même périmètre diffèrent par l’égalité des côtés
NG

ou non. Que choisirez vous pour acheter votre farine ?

TA

Exercice 20. 1. Résoudre : max 5x2 + 6xy − 3y 2

x+2y=10
el

2. Discuter en fonction des réels a, b et c le problème d’optimisation de ax2 +

tu

bxy + cy 2 sous la contrainte x + y = 10.

r
Be

Exercice 21. Soit le problème d’optimisation de xy sous la contrainte 4x2 + y 2 =

4

1. Représenter le domaine.

2. Déterminer les extrema de la fonction et leur nature sur le domaine.

Exercice 22.

1. Déterminer les points extrema de la fonction f (x, y) = x2 + y 2 sous la

contrainte xy = 1. Donner si possible la nature des ces extrema.

2. Déterminer arg max f ; où, C est la contrainte.

C

Exercice 23. Soient f (x, y) = x2 + y 2 et g(x, y) = 4x2 + y 2 − 1

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.2. OPTIMISATION 43

1. Représenter l’ensemble g = 0.

2. Justifier que les fonctions f et g sont continument différentiables (et même

plus une infinité de fois continument différentiables).

3. Déterminer le Lagrangien associé au problème d’optimisation de f sous la

contrainte g = 0.

4. Déterminer les points critiques ainsi que leur nature.

5. Déterminer arg min f et arg max f ; où, C est la contrainte définie par g =
C C
0.

Exercice 24. Soit le problèmes suivant : max −x2 − 6y 2 − xy + 2x + 3y

−3<x<0
1<y<2

A
AW
1. Représenter le domaine.

2. Montrer que la fonction objectif nommée f est concave.

ND
3. Déterminer le point critique de f ainsi que sa nature.
UE

4. Déterminer arg min f et arg max f ; où, C est la contrainte tel que présentée
C C
NG

ci-haut.
TA

Exercice 25. Déterminer le problème duale à celui suivant :

el

max z = 5x + 4y
tu

3x+2y≤12
r

y−x≤1
Be

x+2y≤6
y≤2
x, y≥0

Exercice 26. Soit le problème de l’Exercice 25.

1. Représenter la contrainte

2. Représenter dans le même repère une courbe de niveau de la fonction objectif

passant par l’intérieur de la contrainte.

3. Rechercher une direction dans laquelle la fonction objectif croit (décroit) et

déduire les solutions

4. Déterminer arg min f et arg max f ; où, C est la contrainte.

C C

5. Déduire le minimum et le maximum de la fonction objectif sous la contrainte.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.2. OPTIMISATION 44

Exercice 27. Résoudre les problèmes suivants :

max T = −x − y − 3z et min T = x + y + 3z
2x+y+z≤5 2x+y+z≤5
4x+y+z≤11 4x+y+z≤11
x+y+2z≤8 x+y+2z≤8
x,y,z≥0 x,y,z≥0

Déduire les solutions de :

max xn+1 = c + ni=1 −|ai |xi

P Pn
et min xn+1 = c + i=1 |ai |xi ;
Ax≤b AX≤b
xi ≥0 xi ≥0

où, n ≥ 2, x = (x1 , . . . , xn )t , ai ∈ R, 0 ≤ b ∈ Mm,1 , et A ∈ Mm,n ; avec m ≥ 2.

Exercice 28. Déterminer le P OL= des P OL suivants :

max z = 3x + 4y et min z = 3x + 4y

A
3x+2y≤2 3x+2y≤2 (5.2.1)

AW
y+3x≤1 y+3x≤1
x,y≥0 ND x,y≥0

Exercice 29. Déterminer trois solutions de base (la méthode de Gauss est re-
commandée) de la contrainte des P OL= issu des POL (3.3.2).
UE

Exercice 30. Déterminer deux solutions adjacentes du POL (3.3.2).

NG

Exercice 31.
TA

1. Déterminer une solution initiale de (3.3.2).

el
tu

2. En déduire une forme matricielle (un seul bloc sans inconnu) de (3.3.2).
r
Be

Exercice 32.

1. Résoudre les problèmes suivants par la méthode de simplexe

max z = 5x + 2y et min z = −x − 9y
3x+2y≤2 3x+2y≤2
y+3x≤1 y+3x≤1
x,y≥0 x,y≥0

2. Traiter les problèmes en (3.3.2).

Exercice 33. Soit

  
x + 2y + z ≤ 430

 
 


 
 


 
 

D1 = (x, y, z) ∈ R3+ , 3x + 2z ≤ 460 , T1 = 3x + 2y + 5z,

 
 


 
 


 x + 4z ≤ 420
 


TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.3. PROBLÈME DE RECHERCHE OPÉRATIONNELLE 45

  
x + 2y + z ≤ 4

 
 


 
 


 
 

D2 = (x, y, z) ∈ R3+ , 2x + 5y + z ≤ 8 , T2 = x + 7y + 8z.

 
 


 
 


 x + y + z ≤ 4
 


Résoudre par la méthode de simplexe les problèmes suivants :

min T1 , max T1 , min T2 , max T2 .
D1 D1 D2 D2

5.3 Problème de Recherche Opérationnelle

Exercice 34 (PAF-1010 UQTR, S4). Une compagnie fabrique deux types d’acier :
Acier trempé (T) et l’acier détrempé (D). Le profit pour une tonne d’acier est de

A
6k et 4k pour l’acier T et D respectivement. Il faut 2 et 3 tonnes de matières

AW
premières pour les aciers T et D respectivement tandis que le temps de produc-
ND
tion est respectivement de 6 et 4 unités. La compagnie dispose de 120 tonnes de
matières premières et de 100 unités de temps
UE

1. Identifier les variables.

NG

2. Déterminer la fonction objectif ; puis donner son expression analytique.

TA

3. Formaliser le problème.
el

4. Résoudre le problème modéliser graphiquement, et par méthode de simplexe.

r tu

5. Répondre au problème initial.

Be

Exercice 35 (PAF-1010 UQTR, S4). Un constructeur automobile doit livrer son

modèle AA à 4 concessionnaires à partir de trois usines de production. Les dis-
ponibilités aux usines sont respectivement de 80, 40 et 100 unités tandis que les
démandes des vendeurs sont de 40, 75, 25 et 60 pour les concessionnaires I, II, III
et IV respectivement. Les coûts de livraison des automobiles, en centaine d’unités
(u), sont donnés par le tableau suivant :

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.3. PROBLÈME DE RECHERCHE OPÉRATIONNELLE 46

Concessionnaire
I II III IV
1 4 2 6 4
Usines 2 8 6 10 8
3 6 4 8 6
1. Interpréter chaque élément du tableau.

2. Identifier les variables.

3. Déterminer la fonction objectif ; puis donner son expression analytique.

4. Formaliser le problème.

5. Résoudre le problème modéliser par méthode de simplexe.

A
AW
6. Déterminer le plan de livraison optimal.
ND
Exercice 36 (R.0 - L3 G- M. MEGHRAOUI, CAS MPM DANS LE PO...). L’en-
treprise DURALUMIN fabrique pour des entreprises de quincaillerie des pièces
UE

en inox. Ces pièces sont de trois types : A, B, C, Elles sont fabriquées par lots de
NG

50 dans un atelier où sont rassemblées deux machines pour la découpe de l’inox,

une machine pour l’emboutissage, deux machines pour le polissage et la finition.
TA

Chaque machine fonctionne 120 heures par mois. Les charges variables de fabri-
el

cation sont rassemblées dans le tableau suivant :

r tu

Coût de l’heure Lot A Lot B Lot C

Be

Découpe 20u 1h 1.5h 1.5h

Emboutissage 20u 1h 1.5h 1.5h
Polissage et finition 20u 1h 1.5h 1.5h
Inox 20u 1h 1.5h 1.5h
Prix de vente (H.T) 200u 200u 210u
1. Identifier les variables.

2. Déterminer l’objectif

3. Donner l’expression analytique de l’objectif.

4. Formaliser le problème.

5. Résoudre le problème formalisé.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
5.3. PROBLÈME DE RECHERCHE OPÉRATIONNELLE 47

6. Revenir proposer une solution au chef de l’entreprise.

Exercice 37. Le responsable de l’usine de VANNES de la société Pro-Mer sou-

haite lancer la production de combinaisons de plongée ; le modèle « Shorty », forme
short et manches courtes, noté « S » et le modèle « Long John », combinaison
longue, noté « L ». Il désire mettre au point un programme optimal de production
afin de maximiser la rentabilité de ce projet. La fabrication d’une combinaison de
plongée occuperait trois ateliers A, B, C pendant une durée exprimée en minutes
et notée dans le tableau ci-dessous.

Atelier modèle S Modèle L temps mensuel atelier

A 20 minutes 25 minutes 36000 minutes

A
AW
B 20 minutes 30 minutes 45000 minutes
C 15 minutes 15 minutes 24000 minutes
ND
UE

La compatibilité analytique prévisionnelle indique les chiffres :

NG

élément unitaires modèle S Modèle L

Marché potentiel 1000 unités 700 unités
TA

Prix de vente 500 u 700 u

el

Charge variables 350 u 500 u

r tu
Be

Résoudre le problème par les méthodes graphique et de simplexe.

TANGUE NDAWA Bertuel © UN Recherche Opérationnelle

bertuelt@[Link]
 Bibliographie

[Fortz(2013)] B. Fortz (2013). ‘Recherche opérationelle et application’.

[Wikipédia(2019)] Wikipédia (2019). ‘Recherche opérationelle’. Wikipédia.

A
AW
ND
UE
NG
TA
el
r tu
Be

48 TANGUE NDAWA Bertuel © UN

bertuelt@[Link]