1 / 28

Chapitre 1: Recherche opérationnelle

Démarche de Modélisation

Hamed Sidi Nounou

Institut Universitaire Professionel, Licence LgTr

23 Avril 2020
 2 / 28
Qu'est-ce que la Recherche Opérationnelle ?

 Il n'y a rien dans le monde qui ne se réalise sans la volonté de

minimiser ou maximiser quelque chose  Euler

Optimiser ( maximiser ou minimiser) quelque chose ⇒ prendre

meilleure décision.

Recherche opérationnelle
Technique d'aide à la décision.
Discipline des mathématiques appliquées qui traite des
questions d'utilisation optimale des ressources dans
l'industrie et dans le secteur public.
L'étude des opérations d'une organisation dans le but
d'accroître son ecacité.
 3 / 28
Champs d'applications de la recherche opérationnelle

Domaine militaire :
RO est née pendant la seconde guerre mondiale
fournir des techniques d'optimisation des ressources
militaires
prendre les meilleures décisions dans les batailles et
d'essayer acquérir la victoire
opérationnelle : opérations militaires.

Le champ d'application de la RO s'est élargi à des domaines

comme :
Planication de la production
Allocation optimale des ressources
Gestion des stocks
Ordonnancement des tâches
 4 / 28
Champs d'applications de la recherche opérationnelle
Gestion de la chaîne logistique

Problème du voyageur de commerce

 5 / 28
Champs d'applications de la recherche opérationnelle
Gestion de la chaîne logistique

Problème du transport
 6 / 28
Champs d'applications de la recherche opérationnelle
Gestion des ressources humaines

Problème d'aectation
 7 / 28
Champs d'applications de la recherche opérationnelle

Problème du sac à dos

 8 / 28
Problèmes d'agriculture

Exemple 1 :

Un agriculteur possède un certain nombre d'hectares, d'engrais

et d'insecticide. Il peut planter du maïs ou du blé, ces cultures
requièrent des quantités diérentes d'engrais et d'insecticide et
fournissent un revenu diérent.
Objectif : maximiser le revenu net

Le programme linéaire qui modélise ce problème ? !

 9 / 28
Problèmes d'agriculture

Exemple 2 :

Un agriculteur veut allouer 150 hectares de surface irrigable

entre culture de tomates et celles de piments. Il dispose de 480
heures de main d'÷uvre et de 440 m3 d'eau. Un hectare de
tomates demande 1 heure de main d'÷uvre, 4 m3 d'eau et
donne un bénéce net de 100 dinars. Un hectare de piments
demande 4 heures de main d'÷uvre, 2 m3 d'eau et donne un
bénéce net de 200 dinars.
Le bureau du périmètre irrigué veut protéger le prix des tomates
et ne lui permet pas de cultiver plus de 90 hectares de tomates.
Quelle est la meilleure allocation de ses ressources ?

Le programme linéaire qui modélise ce problème ? !

 10 / 28
Problèmes d'agriculture
Problème de la diète (Diet problem)

Un éleveur essaye de nourrir le bétail de sa ferme avec le régime plus

économique possible (minimiser les coûts d'alimentation de la
production animale).
Ce régime doit contenir quatre types de nutriments étant que A, B , C
et D. On trouve ces composants dans deux types de fourrage M et N .
La quantité, en grammes, de chaque composant par kilo de ces
fourrages se montre dans le tableau suivant :

Céréale \ nutriments A B C D
M 100 − 100 200
N − 100 200 100

Le régime par jour d'un animal doit être composé au moins de 0.4Kg
du composant A, 0.6Kg du composant B , 2Kg du composant C et
1.7Kg du composant D. Le composé M coût 0.2 euros /Kg et le
composé N 0.08 euros /Kg . Quelles quantités de fourrages M et N
l'éleveur doit acquérir pour dépenser le moins en nourriture ?

Formuler le problème comme un programme linéaire.

 11 / 28

Les ingrédients principaux d'un modèle de recherche

opérationnelle sont :
Variables : les inconnues du problème

Contraintes : les restrictions (les limites, la disponibilité)

Fonction-objectif : minimiser ou maximiser

Le problème d'optimisation peut être :

combinatoire ou discrète (le domaine X est un ensemble
discret (e.g., ensemble des vecteurs avec des composantes
entières N ou 0/1).
continue on se concentre sur X qui est un "continuum"
(e.g., X = {x ∈ Rn | a ≤ x ≤ b}).
linéaire, X ⊂ Rn et l'objectif et les contraintes sont des
fonctions linéaires de x.
 12 / 28

Dénition
Soit f : Rn −→ R. On dit que f est linéaire si et seulement si
∀(x, y) ∈ Rn × Rn , ∀λ ∈ R; f (x + λy) = f (x) + λf (y).

Les fonctions linéaires dénies sur Rn sont des fonctions de la

forme
f (x1 , x2 , · · · , xn ) = c1 x1 + c2 x2 + · · · + cn xn ⇔ f (x) = c> x

où c = (c1 , c2 , · · · , cn ) ∈ Rn .

Un modèle de programmation mathématique est linéaire si la

fonction-objectif et les contraintes sont linéaires en les variables.
 13 / 28
Modélisation

La modélisation est la conception d'un phénomène réel sous

forme d'un modèle mathématique, ce modèle permet d'analyser
ce phénomène et de prévoir des résultats à partir de
l'application des outils et théories mathématiques, et les
techniques de la recherche opérationnelle.

Face à un problème réel, il est tout à fait naturel qu'on pose les
questions suivantes :

Sur quelles quantités peut-on travailler ?

Que cherche-t-on à optimiser ?
Quelles sont les contraintes du problème ?
 14 / 28
Formulation d'un problème de RO et Processus d'optimisation

Modélisation
Etape 1 : Identication des variables de décision,
Etape 2 : Identication des contraintes,
Etape 3 : Identication de la fonction-objectif.
Résolution : Méthodes (algorithmes)
Interprétation
Mise en ÷uvre
 15 / 28
Rappel d'algèbre linéaire

On se place dans ce cours dans le R-espace vectoriel de

dimension n, Rn où n ∈ N∗ .
Un vecteur v de Rn est un n-uplet v = (x1 , x2 , · · · , xn ), v est dit
un vecteur
  ligne, un vecteur colonne est un vecteur de la forme
x1
x2
u =   et u> = v le transposé de u.
.
.
.
xn
x  y 
1 1
x2 y2
On considère les deux vecteurs x =   et y =   de Rn .
.
.
.
.
. .
xn yn
Le produit scalaire de x et y est déni par
n
X
hx, yi = x> y = x1 y1 + x2 y2 + · · · + xn yn = xi yi
i=1
Combinaison linéaire des vecteurs v1 , v2 , · · · , vn est
λ1 v1 + λ2 v2 + · · · + λn vn
où λ1 , λ2 , . . . , λn sont des scalaires.
 16 / 28
Rappel d'algèbre linéaire

Si chaque λi est compris entre 0 et 1, et λ1 + λ2 + · · · + λn = 1,

alors cette combinaison λ1 v1 + λ2 v2 + · · · + λn vn s'appelle
combinaison convexe des vecteurs v1 , v2 , · · · , vn .

Dénition
Soit C un sous-ensemble de l'espace vectoriel Rn . On dit que
l'ensemble C est convexe si et seulement si
∀(x, y) ∈ C 2 , ∀α ∈ [0, 1], αx + (1 − α)y ∈ C

Autrement dit, un ensemble est convexe s'il contient tout

segment passant par deux de ses points.
Point extrême (sommet) d'un ensemble convexe ne peut être
s'inscrit comme une combinaison convexe d'autres vecteurs.
 17 / 28
Rappel d'algèbre linéaire
Exemples d'ensembles convexes et non convexes

Figure  L'ensemble de gauche est convexe, de milieu n'est pas

convexe et celui de droite (polygone) est convexe.
 18 / 28
Rappel d'algèbre linéaire

Une matrice est un tableau bi-dimensionnel carré ou

rectangulaire d'éléments :
 
a11 a12 · · · a1n
 a21 a22 · · · a2n 
A= . .. . . ..  = (aij )
 ..
 
. . 
1≤i≤m
. 1≤j ≤n

am1 am2 · · · amn

A est une matrice de m lignes et n colonnes, et l'indice i fait

référence au numéro de ligne et l'indice j fait référence au
numéro de colonne.

Soit i ∈ {1, 2, · · · , m}, a

i1 ai2 · · · ain la i-ème ligne de A.



a1j
 a2j 
Soit j ∈ {1, 2, · · · , n}, 
 ..  la j-ème colonne de A.

 . 
amj
 19 / 28
Rappel d'algèbre linéaire
Produit de deux matrices

La matrice A de taille m × n multipliée par la matrice B de

taille n × p donne une matrice C de taille m × p.
a11 a12 ··· a1n b11 b12 ··· b1p c11 c12 ··· c1p
     
 a21 a22 ··· a2n   b21 b22 ··· b2p   c21 c22 ··· c2p 
. . . .  =  . . .
     
 . . . . . . .
 .. .
.
.
.
.   .
. .
.
.
.
.
. 
.
 .. .
.
.
.
. 
.

am1 am2 ··· amn bn1 bn2 ··· bnp cm1 cm2 ··· cmp

Les composantes cij de C sont données par

 
b1j

 b2j 

cij = Li (A).Cj (B) = ai1 ai2 · · · ajn .  . 
 .. 
bmj
= ai1 b1j + ai2 b2j + · · · + ain bnj

cij est le produit scalaire de i-ème ligne de A avec j -ème colonne

de B .
 20 / 28
Rappel d'algèbre linéaire
Produit d'une matrice par un veceteur

La matrice A de taille m × n multipliée par le vecteur X de

taille n × 1 (vecteur colonne) donne un vecteur C de taille m × 1
( vecteur colonne).
a11 a12 ··· a1n x1 a11 x1 + a12 x2 + · · · + a1n xn
     
 a21 a22 ··· a2n   x2   a21 x1 + a2 x2 + · · · + a2n xn 
. . .  =  .
     
 . . . .
 .. .
.
.
.
.   . 
. .
 .
.

am1 am2 ··· amn xn am1 x1 + am2 x2 + · · · + amn xn

Transposition d'une matrice

On appelle transposée d'une matrice A de taille m × n et de
terme général aij , la matrice de taille n × m notée A> obtenue
en échangeant les lignes avec les colonnes de A.
A> = (bij ) = (aji ) avec i ∈ {1, 2, · · · , n}, j ∈ {1, 2, · · · , m}
On note que (A> )> = A et (A.B)> = B > .A> .
 21 / 28
Rappel d'algèbre linéaire

Rang d'une matrice

Soit A une matrice à coecients réels et de taille m × n,

A ∈ Mm×n (R).
Dénition
le rang de la matrice A est le nombre maximal de lignes (ou
colonnes) linéairement indépendantes. Autrement dit le plus
grand des ordres des matrices carrées inversibles extraites de A.
On a
rg(A) ≤ min{m, n}.

Exemple :  
3 0 1 0 5
5 2 0 0 2
8 0 0 4 6
 22 / 28

Dénition : Polygone
Un polygone est une gure géométrique plane fermée dont les
côtés sont des segments. Les extrémités des segments sont
appelés sommets ou coins du polygone.

Figure  Exemples de polygones.

 23 / 28

Dénition : Polyèdre
Un polyèdre est une forme géométrique à trois dimensions (un solide ) dont
toutes les faces sont des polygones. Les côtés de ces polygones sont appelés
arêtes. Les extrémités des arêtes sont des points appelés sommets.

Figure  Exemples de polyèdres

Un polyèdre convexe fermé est un ensemble convexe fermé qui peut être
décrit comme :
P = {x ∈ Rn | Ax ≤ b}
où A une matrice de taille n × m et b un vecteur de Rm .
L'ensemble admissible d'un programme linéaire est un polyèdre convexe.
 24 / 28

Les polyèdres convexes compacts (c'est-à-dire fermés bornés) de

Rn , appelés aussi polytopes de Rn .
Dénition : Demi-espace et Hyperplan
Soient a un vecteur non nul de Rn et b un scalaire. Un
demi-espace est un ensemble de la forme
n o
x ∈ Rn | a> x ≤ b .

Un hyperplan est un ensemble décrit comme

n o
x ∈ Rn | a> x = b .

Note : Un hyperplan est la frontière du demi-espace

correspondant.
 25 / 28

Dénition : Point extrême (sommet)

Soit P un polyèdre. Un vecteur x ∈ P .
m x est un point extrême de P si on ne peut pas trouver deux
vecteurs y et z dans P , diérents de x, et un scalaire λ ∈]0, 1[
tels que
x = λy + (1 − λ)z.
Autrement dit, si on ne peut pas exprimer x comme
combinaison convexe de deux autres points de P .
En deux dimensions (R2 ), un sommet est la rencontre de deux
droites (ou plus) dénies par les frontières des contraintes.
 26 / 28

Soient X ⊂ Rn et f : X −→ R.
Dénition : Minimum local et global
Soit x∗ un point de l'ensemble X : x∗ ∈ X
On dit que x∗ est un minimum local de f s'il existe une
boule B(x∗ , r) avec r > 0 tel que
∀ x ∈ B(x∗ , r), f (x∗ ) ≤ f (x).

On dit que x∗ est un minimum global si

∀ x ∈ X, f (x∗ ) ≤ f (x).

Dans ce cas on dit f (x∗ ) = min f (x) est la valeur minimale

x∈X
de f sur le domaine X .
Note : f admet un maximum lorsque −f admet un minimum
sur X et on a max f (x) = − min{−f (x)}.
x∈X x∈X
27 / 28
 28 / 28

Existence d'un minimum

Théorème
Si X est compact (fermé et borné) et f est continue sur X , alors
f atteint ses bornes, c'est-à-dire f admet un minimum et un
maximum.

Théorème
Si le polyèdre formé par l'ensemble des solutions d'un PL est
borné, alors il existe au moins une solution optimale et l'une
d'elles est obtenue sur un point extrême.