Cours de la 3ème année ENSAM-Meknès

Année universitaire : 2024/2025

Recherche Opérationnelle

Préparé par : Pr. Oulfa Labbi

Plan du cours

1- Programmation Linéaire
 Présentation de la recherche opérationnelle et des
problèmes de type programmation linéaire
 Résolution par la méthode graphique
 Résolution par la méthode du Simplex
 Dualité en programmation linéaire
1-Programmation linéaire
 Analyse de sensibilité 2- Théorie des graphes et
 Mise en œuvre sur un solveur Optimisation
 Programmation en nombre entiers
2- Théorie des graphes et optimisation
 Le graphe et ses diverses extensions
 Graphes Eulérien et Hamiltonien
 Arbre couvrant et algorithmes
 Recherche du plus court chemin et Flots
 Chapitre 1

Introduction à la recherche opérationnelle

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

  La RO est une discipline scientifique qui utilise des
1.Recherche Opérationnelle : Définition, modèles mathématiques, des algorithmes et des
Objectifs, Démarche et Outils techniques analytiques pour aider à la prise de
décision et à l'optimisation des systèmes
complexes.

 Elle vise à améliorer l'efficacité et la performance

La recherche opérationnelle (RO) est la dans divers domaines tels que l'industrie, la
discipline des mathématiques appliquées qui logistique, la finance et la gestion.
traite
des questions d'utilisation optimale des
 Elle repose sur l’analyse de problèmes réels en les
ressources dans l'industrie et dans le secteur formulant sous forme de modèles mathématiques,
public. C’est l’ensemble des méthodes et puis en utilisant des méthodes quantitatives
techniques rationnelles d’analyse et de comme la programmation linéaire, la théorie des
synthèse files d’attente, la simulation, les heuristiques.. pour
des phénomènes d’organisation utilisables pour trouver des solutions optimales ou quasi-optimales.
élaborer de meilleures décisions.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

  Quelques champs d’application:
1.Recherche Opérationnelle : Définition, Logistique et Transport : Optimisation des itinéraires.
Objectifs, Démarche et Outils
Gestion des Stocks : Minimisation des coûts
d’inventaire.
Planification de Production : Allocation optimale des
ressources.
Santé : Allocation des ressources médicales
(personnel, équipements).
La recherche opérationnelle (RO) est utilisée
dans les domaines ou la prise de décision fait ……..
appel à la résolution des problèmes
d’optimisation telle que les problèmes de :
Dimensionnement, localisation, gestion de
ressources, Ordonnancement, Prévisions….

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

  Période d'après-guerre (1945 - 1960)
 Extension de la RO aux domaines civils : industries,
Un peu d’histoire…… transport, santé, finance.
 Développement de la programmation linéaire
par George Dantzig (1947) et de l’algorithme du
simplexe.
 Formalisation de la théorie des files d’attente et
L'origine de la recherche opérationnelle remonte au des modèles stochastiques pour la gestion des
début du XXe siècle, mais elle s'est particulièrement services et de la production.
développée pendant la Seconde Guerre mondiale.
Voici les grandes étapes de son évolution :  Modernisation et informatisation (1960 - 2000)
 Débuts (1910 - 1939)  Apparition des premiers logiciels de RO et
 Premiers travaux sur l'optimisation dans simulation informatique.
l'industrie et l'économie (ex. modèles de  Intégration avec l’intelligence artificielle et les
production et de gestion des stocks). systèmes experts.
 Développement de la théorie des jeux par  Développement des métaheuristiques (ex.
John von Neumann et Oskar Morgenstern. algorithmes génétiques, recuit simulé).
 Seconde Guerre mondiale (1939 - 1945)  Depuis 2000 : RO et Big Data
 Utilisation intensive de la RO par les armées  Utilisation massive de la RO dans l’analyse des
alliées pour optimiser l'utilisation des ressources
militaires (ex. déploiement de radars, données, le machine learning et l’optimisation à
logistique, stratégies anti-sous-marins). grande échelle.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

1. Formulation du Problème :
Démarche de la
Comprendre le contexte, les objectifs et
les contraintes. RO
2. Modélisation Mathématique :
Traduire le problème réel en équations
ou modèles(Programmation linéaire par
ex)
3. Résolution du modèle:
Appliquer des algorithmes (Simplex par
ex) ou des outils pour trouver une
solution( logiciel spécialisé: Cplex,
Lindo,Gams,…) [

4. Validation du modèle :
Analyser les résultats pour s'assurer de
leur pertinence.
5. Prise de décision et Mise en Œuvre :
Implémenter les solutions dans la
pratique.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

1.Recherche Opérationnelle : Définition,
Objectifs, Démarche et Outils
 1-Modèles Mathématiques :
 Programmation linéaire (PL). Principaux outils
 Programmation non linéaire (PNL). de la RO

 Programmation dynamique.
 2-Algorithmes :
 Simplexe.
 Branch and Bound.  Nous traiterons principalement dans ce
cours la programmation linéaire
 3-Techniques :
 Théorie des graphes.
 Simulation (exemple : Monte Carlo).
 Théorie des files d’attente.
 4- Logiciels d’optimisation:
 Excel Solver.
 MATLAB.
 Solveurs:GAMS, LINGO, CPLEX, Gurobi, Xpress,
MINOS……
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2- Programmation linéaire: formulation

2.1.Définition :
La programmation linéaire consiste à maximiser ou minimiser une fonction objective linéaire, sous des
contraintes exprimées par des inégalités ou des égalités linéaires.

➢ Composantes principales :

 Une fonction objective.

 Des variables de décision.
 Des contraintes linéaires.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2- Programmation linéaire: formulation

➢ Les bonnes questions à se poser, face à un

problème du type recherche opérationnelle,
sont les suivantes :
 Quelles sont les variables de décision ? C'est-à-
dire quels sont les éléments de mon modèle
que j'ai le droit de faire varier pour proposer
d'autres solutions ?
 Quelles sont les contraintes ? Une fois
identifiées les variables de décision, quelles sont
les valeurs autorisées pour ces variables
 Quel est l'objectif ou le critère ? Quelle est la
quantité que l'on veut maximiser ou minimiser ?

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

2.2. Étapes de la Modélisation en PL:

o Identification des variables de décision :

On détermine les variables du Système qui représente les décisions à prendre (ex. : quantité à produire,
ressources à allouer). Les variables représentent les inconnues du système, ils sont représentés sous forme
symbolique x1,x2,…..
o Formulation de la fonction objective :

Représente l’objectif ou le but attendu du problème. il peut être une fonction de minimisation lorsqu'il
s'agit d'une dépense, d'un investissement ou une fonction de maximisation lorsqu'il s'agit d'un profit ou de
gain. Donc Déterminer ce qu’il faut maximiser ou minimiser (ex. : coût, profit).

o Établissement des contraintes :

Les objets mathématiques qui assurent l'interaction et la liaison des variables par rapport aux ressources
disponibles et aux données du problème sont appelées contraintes. On Traduit les limitations du
problème en équations ou inéquations linéaires.
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2-Programmation linéaire: formulation

2.2. Étapes de la Modélisation en PL:

o Exemple d’application 1:
Une petite menuiserie fabrique deux produits : des chaises et des tables. L’entreprise souhaite maximiser
son profit en utilisant efficacement ses ressources limitées.
 Chaque chaise rapporte 30 € de bénéfice.
 Chaque table rapporte 50 € de bénéfice.
 L’atelier dispose de 300 heures de travail disponibles par semaine.
 Chaque chaise nécessite 5 heures de travail.
 Chaque table nécessite 10 heures de travail.
 L’atelier ne peut produire plus de 40 chaises par semaine.
La question qui se pose est combien de chaises et de tables faudra t-on fabriquer pour maximiser le
profit, tout en respectant les contraintes?

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

1-Identification des variables de décision :

La première étape consiste à choisir les variables du problème.

Les quantités que le modèle doit déterminer sont les quantités de tables et de chaises à produire par
semaine. Posons donc:
x1​ : nombre de chaises fabriquées par semaine
x2 : nombre de tables fabriquées par semaine

2-Formulation de la fonction objective :

La deuxième étape consiste à formuler l’objectif. L’entreprise souhaite maximiser son profit. Le bénéfice
étant de 30 pour la chaise et de 50 pour la table, l’objectif(ou fonction économique) s’exprime comme
suit:
Maximiser le profit : Z=30 x1+50 x2

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

3-Expression des contraintes:

Contrainte de temps (charge horaire): le total d’heures utilisées ne doit pas dépasser 300 : 5 x1+10 x2≤300

Limite de production des chaises : L’atelier ne peut produire plus de 40 chaises par semaine: x1≤40

Contraintes de positivité :on ne peut pas produire un nombre négatif de chaises ou de tables: x1≥0, x2≥ 0

Finalement, le problème peut être formulé en programme linéaire:

max Z=30 x1+50 x2
5 x1+10 x2≤300
(P)
x1≤40
x1≥0, x2≥ 0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

2-Programmation linéaire:formulation

 Exemple 2:
Une entreprise doit transporter des marchandises depuis deux entrepôts vers deux magasins. L’objectif
est de minimiser le coût total du transport, sachant que chaque entrepôt a une capacité limitée et que
chaque magasin a une demande spécifique.

Capacité des entrepôts :

•Entrepôt E1 : 30 unités
•Entrepôt E2 : 50 unités

Demande des magasins :

•Magasin M1 : 40 unités
•Magasin M2 : 40 unités

•Coût du transport par unité : Magasin M1 Magasin M2

Entrepôt E1 4 €/unité 7 €/unité
Entrepôt E2 6 €/unité 5 €/unité

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

1-Identification des variables de décision :

x11​ : quantité transportée de E1 → M1

x12: quantité transportée de E1 → M2
x21 : quantité transportée de E2 → M1
x22: quantité transportée de E2 → M2

2-Formulation de la fonction objective :

Minimiser le coût total de transport:

Z= 4 x11+7 x12+6 x21+5 x22

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

3-Expression des contraintes:

Capacité des entrepôts :
x11+x12≤30
50x21+x22≤50
Demande des magasins :
x11+x21=40
x12+x22=40 Min Z= 4 x11+7 x12+6 x21+5 x22
x11+x12≤30
Contraintes de positivité : x11 ,x12 ,x21 x22 ≥0
(P2) 50x21+x22≤50
Le programme linéaire associé à notre problème est le suivant: x11+x21=40
x12+x22=40
x11 ,x12 ,x21 x22 ≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

 Exemple 3:

Une usine fabrique deux modèles de smartphones, Modèle X et Modèle Y, en utilisant trois ressources principales :
composants électroniques, main-d'œuvre, et temps d'assemblage.
Le tableau suivant indique les besoins en ressources pour chaque modèle ainsi que les quantités disponibles :

Ressources Modèle X Modèle Y Quantité disponible

Composants (unités) 5 8 200
Main-d'œuvre (h) 3 6 150
Temps d’assemblage
2 4 100
(h)

Chaque Modèle X vendu rapporte un bénéfice de 1200 Dhs, et chaque Modèle Y vendu rapporte un bénéfice
de 1800 Dhs.
Quelles quantités de Modèle X et de Modèle Y l’usine doit-elle produire pour maximiser son bénéfice total ?

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

1-Identification des variables de décision :

x1​ : nombre d’unités de smartphone X à produire

x2​ : nombre d’unités de smartphone Y à produire

2-Formulation de la fonction objective :

Maximiser le profit total:

Z= 1200 x1+ 1800 x2

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

3-Expression des contraintes:

Disponibilités des ressources:
5x1+ 8x2≤200
3x1+ 6x2≤150
2x1+ 4x2≤100
Contraintes de positivité : x1 ,x2 ≥0
Le programme linéaire associé à notre problème est le suivant:
Max Z= 1200 x1+ 1800 x2

(P3) 5x1+ 8x2≤200

3x1+ 6x2≤150
2x1+ 4x2≤100
x1 ,x2 ≥0
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2-Programmation linéaire: formulation

2.3. Formulation générale d’un PL

2.3.1.formulation générale:
 Fonction Objectif:
Max (ou min) z = c1 x1 +c2 x2+…+ cn xn
 Contraintes :
a11 x1+ a12 x2 + …+ a1n xn ≤ , = ,≥ b1
a21 x1+ a22 x2 + …+ a2n xn ≤ , = ,≥ b2
.

a11 x1+ a12 x2 + …+ amn xn ≤ , = ,≥ bm

 Contraintes de positivité( non négativité):
xj ≥ 0 ∀ 𝑗 = 1, … . . , 𝑛

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

2.3. Formulation générale d’un PL

2.3.1.formulation générale:

 La forme générale d’un PL est donc:

Max (ou min) z =σ𝑛𝐽=1 𝑐𝑗𝑥𝑗
Sous les Contraintes :
𝑛

෍ 𝑎𝑖𝑗𝑥𝑗 ≤= ≥𝑏𝑖 𝑝𝑜𝑢𝑟 𝑖 = 1, … . . , 𝑚

𝐽=1

xj ≥ 0 ∀ 𝑗 = 1, … . . , 𝑛
Avec
 xj: variables de décision du programme linéaire ( inconnues)
 aij , bi, cj : paramètres du programme linéaires (connus)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

2-Programmation linéaire: formulation

2.3.2.formulation matricielle:
 La forme canonique d'un programme linéaire peut être exprimée par un ensemble de vecteurs
comme suit :
X= (x1,x2,…….,xn) ϵ Rn où x1,x2,…….,xn sont les variables de décision.
C=(c1,c2,……..,cn ) ϵ Rn
b=(b1,b2,……..,bm ) ϵ Rm
Avec:
n = nombre de variables et m = nombre de contraintes,

𝑎11 𝑎12 … 𝑎1𝑛

𝑎.21 𝑎22 . … 𝑎2𝑛
.
Et la matrice A de taille m x n (matrice de contraintes) : A= . . .
. . .
𝑎𝑛1 𝑎𝑛2 𝑎𝑛𝑚
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
2-Programmation linéaire: formulation

2.3. Formulation générale d’un PL

2.3.2.formulation matricielle:
 le programme linéaire peut s’écrire donc sous la forme:

Min ou Max Z= cT x
(PL) A x ≤; =; ≥ b
x ≥0

 Un choix des valeurs des variables (x1, . . . , xn) est appelé solution du problème.
 Une solution est faisable ou réalisable si elle vérifie les contraintes.
 Une solution est optimale si elle est faisable et minimise ou maximise la fonction objective.
 L’Ensemble réalisable (région admissible) est l’ensemble formé par toutes les solutions réalisables
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 2-Programmation linéaire: formulation

2.3. Formulation générale d’un PL

2.3.2.formulation matricielle:
Reprenons l’exemple 3 :

Max Z= 1200 x1+ 1800 x2

200 5 8
150 3 6 (P3) 5x1+ 8x2≤200
1200
c= b= 100 A= 2 4 3x1+ 6x2≤150
1800 0 −1 0 2x1+ 4x2≤100
0 0 −1 x1 ,x2 ≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 2-Programmation linéaire: formulation

Exercice
Un atelier fabrique trois produits P1, P2 et P3 en quantités respectives x1,x2 et x3. Les marges
unitaires des trois produits sont de 3 dirhams, 4 dirhams et 12 dirhams respectivement.
Les contraintes de production et du marché sont les suivantes :
 Le produitP1 nécessite 1 heure de travail par unité produite, et le marché ne peut
absorber plus de 40 unités par jour.
 Le produit P2 nécessite 2 heures de travail par unité produite.
 Le produit P3 nécessite 3 heures de travail par unité produite, et le marché ne peut
absorber plus de 80 unités par jour.
 La capacité totale de travail disponible dans l'atelier est de 300 heures par jour.
TAF: Déterminer le programme linéaire permettant de maximiser le profit total généré par la
production des trois produits, en respectant les contraintes de temps et de capacité du
marché.
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 Chapitre 2

Résolution des programmes linéaires

Méthode graphique

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Il existe plusieurs techniques de résolution pour les programmes linéaires.

Nous présenterons dans ce chapitre: la résolution graphique et la résolution analytique par la méthode
du Simplexe.
1.1. Résolution par la méthode graphique
o La résolution graphique d’un PL consiste à tracer la droite
qui sépare les demi-plans pour chaque contrainte tout en conservant
le demi-plan des solutions réalisables pour la contrainte. L'intersection
des différents demi-plans de toutes les contraintes sans oublier les
contraintes de positivité forme le polygone des solutions,
appelé aussi "région des solutions admissibles".
o Un point optimal (une solution optimal) est un point de la région
admissible qui maximise ou minimise la fonction objectif

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1. Etapes de la Résolution par la méthode graphique

étape1 étape2 étape 3

Tracer les droites Identifier la Choisir la solution
des contraintes région admissible optimale

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1 Etapes de la Résolution par la méthode graphique

Illustrons la résolution par la méthode graphique à travers un exemple:

Max Z= 3 x1+ 5 x2
Considérons le PL suivant:

x1≤4
(P) 2x2≤12
3x1+ 2x2≤18
x1 ≥0
x2 ≥0

Étape 1 :Tracer les droites des contraintes

o graphiquement, une contrainte telle que 3x1+ 2x2≤18 correspond à un demi-plan limité par la droite
d’équation 3x1+ 2x2=18

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Étape 1 :Tracer les droites des contraintes Représentation graphique de la

 On trace la droite d’équation 3x1+ 2x2=18 : contrainte

Pour x1 ⇒ x2=9
Pour x2=0 ⇒ x1=6
La droite passe donc par les points (0,9) et (6,0).
 Cette droite divise le plan x1x2 en deux régions. Pour
déterminer quelle région satisfait la contrainte donnée,
on peut sélectionner n’importe quel point en dehors de la
droite pour tester si le point satisfait la contrainte donnée.
 Le point le plus simple à tester est l’origine. Il vérifie bien l’inégalité
3x1+ 2x2≤18. la région à garder est donc celle qui contient l’origine

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Étape 2 : identifier la région admissible

 De la même manière, On trace les droites des autres contraintes :
X1=4
X2=6
Sans oublier les contraintes de positivité
 la région des solutions admissibles ou région admissible est l’ensemble des points (x1,x2) qui satisfont les
Contraintes du PL.
 La région admissible (polygone des solutions) est donc formée par l’intersection des cinq demi-plans
correspondant aux cinq contraintes de ce PL.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1 Etapes de la Résolution par la méthode graphique

Représentation de la région des solutions admissibles
On appelle:

Solution de base: Points résultant de l’’intersection des

droites des contraintes

Solution de base réalisable: points résultant de

l’’intersection des droites des contraintes appartenant
À la région admissible

Solution de base non réalisable: points résultant de

l’’intersection des droites des contraintes en dehors de
La région admissible

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1 Etapes de la Résolution par la méthode graphique

Représentation de la région des

solutions admissibles

La question qui se pose maintenant est :

quel est le point qui donne la valeur optimale
pour ce problème ?

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Étape 3 : choix de la solution optimale

 Pour choisir la solution optimale, on peut procéder par deux méthodes:

Choix de la solution
optimale

Méthode des Recensement des

droites parallèles sommets de la région
(les iso-objectifs ou admissible
les isocoûts) (énumération)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1 Etapes de la Résolution par la méthode graphique

Étape 3 : choix de la solution optimale
1-Méthode des droites parallèles

Pour trouver la valeur maximale pour ce problème , la méthode des droites parallèles consiste à tracer
la droite qui correspond à la fonction objective.
o On considérera des valeurs successives de l’objectif z=k, ce qui correspond graphiquement à des
droites parallèles d’équation 3 x1+ 5 x2 = k (iso-objectifs ou droites d’isocoût ou d’iso-profit)
o On peut réarranger l’équation de la fonction objectif pour déterminer x2 :
X2= -3/5 x1 +k/5
o Donc pour tracer les iso-objectifs, il suffit de donner à k une valeur particulière.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1 Etapes de la Résolution par la méthode graphique

Étape 3 : choix de la solution optimale

1-Méthode des droites parallèles

o On commence tout d’abord à attribuer la valeur de zéro à l’équation de la fonction objectif(k=0).

Ce qui donne pour cet exemple : 3 x1+ 5 x2 = 0→ x2 =-3/5 x1 +0/5→ x2 =-3/5 x1 (droite passant par
l’origine (0,0) et le point (5,-3)
o Une fois la droite tracée on effectue une translation parallèle à la direction de la droite du bas vers
le haut jusqu’à rencontrer le dernier point du polygone satisfaisant les contraintes. (toutes ces droites
ont le même coefficient directeur (pente p=-3/5))

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1-Méthode des droites parallèles

Pour maximiser l’objectif, il faudra prendre la droite d’iso-profit qui s’éloigne le plus possible de l’origine
avec la valeur la plus élevée (donnant la plus grande à l’objectif) et qui touche aussi la région
admissible. Le point d’intersection est un point optimal.

Représentation graphique de la
solution optimale

La solution optimale est

donnée par le point (2,6)
qui donne la valeur
maximale z=36

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

1-Résolution d’un PL

les sommets du polygone ou

polyèdre des solutions sont
appelés les points extrémaux.

L’ensemble réalisable ou
région admissible définie par
un ensemble de contraintes
peut être borné ou non.

On dit qu’une région sur le

plan x1x2 est bornée si elle est
contenue dans un disque.
Sinon, on dit que la région est
non bornée.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Région admissible

Trois situations possibles peuvent résulter de l’intersection des demis plans( région
admissible):

1. L’intersection donne un domaine où la fonction objective est majorée sur cet

ensemble et par conséquent le Pl admet une solution optimale (qui est un sommet du
polyèdre) non nécessairement unique.

2. Un domaine non vide mais la fonction objective n’est pas majorée sur ce domaine et
le max de Z = +∞.

3. Le domaine est vide = ø et le PL n’a pas de solutions

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1-Méthode des droites parallèles

Remarque en cas de minimisation:
s’il s’agit d’un PL avec une fonction objective à minimiser , il faudra prendre la droite d’iso-profit qui se
rapproche le plus possible de l’origine avec la valeur la plus basse (donnant la plus petite valeur à
l’objectif).
Exemple de résolution par la méthode graphique en cas de minimisation:
Considérons le PL suivant:

Min Z=3x1 +2x2

x1 +x2 ≥4
x1 -x2 ≥2
(P)
x1 ≥0
x2 ≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Exemple de résolution par la méthode graphique en cas de minimisation:

o Comme expliqué auparavant, on commence à tracer graphiquement les droites des contraintes et
on passe à identifier la région admissible:
Représentation graphique des
contraintes et de la région admissible

La région admissible dans cet

exemple est non bornée

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Exemple de résolution par la méthode graphique en cas de minimisation:

o On applique ensuite la méthode des droites parallèles
Représentation graphique des
contraintes et de la région admissible

Le point optimal est celui qui

appartient à la droite
d’isocoût qui s’approche le
plus de l’origine (minimisant
l’objectif) et qui touche aussi
la région admissible. C’est le
sommet formé par
l’intersection des droites des
deux contraintes

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.1 Etapes de la Résolution par la méthode graphique

Étape 3 : choix de la solution optimale

2-recensement des sommets de la région admissible (énumération)

o Si un problème de programmation linéaire a une solution optimale, alors la solution se situe sur la
frontière (c’est-à-dire sur les arrêtes et les sommets). De plus, si une frontière contenant une solution
optimale a un sommet (ou des sommets), alors la solution se situe sur l’un des sommets.
o La méthode des sommets consiste donc à calculer la valeur de l’objectif qui correspond à chaque
sommet de la région admissible, la solution optimale à choisir est le sommet qui maximise( PL avec
une maximisation) ou minimise (PL avec une minimisation) la fonction objective.
o Reprenons l’exemple de maximisation: Max Z= 3 x1+ 5 x2
x1≤4
(P) 2x2≤12
3x1+ 2x2≤18
x1 ; x2 ≥0
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès
 1-Résolution d’un PL

2-recensement des sommets de la région admissible

o La région admissible trouvée est la suivante:

o La région admissible possède 4
sommets: A(0,6) ;B(2,6); C (4,3) et D( 4,0)
o on calcule la valeur de l’objectif Z pour
ces différents sommets:
pour A → Z= 30
pour B→ Z= 36
pour C→ Z= 27
pour D→ Z=12
(P) o l’objectif est donc maximal au sommet
B (2,6). C’est la même solution trouvée
par la méthode des droites parallèles

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.2.Quelques cas particuliers:

➢ On peut se retrouver avec des cas particuliers comme:

o région admissible bornée avec une infinité de solutions

o région admissible non bornée avec une solution infinie : aucune solution finie (z= ∞)

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.2.Quelques cas particuliers:

o Région admissible bornée avec une infinité de solutions (solution optimale multiple) :

Max Z= x1+ x2 Segment optimal

-2x1+ x2≤1 (1)
(P) x1≤2 (2)
x1 + x2≤3 (3)
x1 ; x2 ≥0

Tous les points situés sur le segment de droite BC correspondent à la valeur de la fonction objective : Z = 3

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

1.1.2.Quelques cas particuliers:

o Région admissible non bornée avec une solution infinie : aucune solution finie (z= ∞)

Max Z= 3x1+ 2x2

x1 - x2≤1 (1)
(P) x1 + x2≥3 (2)
x1 ; x2 ≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

En résumé:

L’ensemble réalisable-région admissible) d’un PL peut être:

o vide→ pas de solution
o non vide et borné :
→ solution optimale unique : sommet optimal unique du polyèdre
→ Solutions optimales multiples: côté optimal du polyèdre

o non vide et non borné:

→ solution optimale unique : sommet optimal unique du polyèdre
→ Solutions optimales multiples: côté optimal du polyèdre
→ Aucune solution optimale finie

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

➢ La méthode graphique pour la résolution d'un problème linéaire à deux variables est facile à
appliquer mais Sa difficulté augmente par l'augmentation des variables dans le système. Elle devient
difficile pour trois variables et, voire impossible, au delà de trois inconnus dans le système étudié.

➢ pour faire face à cette difficulté, on peut appliquer la méthode du simplexe pour résoudre un PL
avec plusieurs variables de décision: c’est l’objet des slides suivants.

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Exercices d’application:
➢ Résoudre graphiquement les programmes linéaires suivants:

Min Z= 2000x1+ 7000x2

Max Z= 2x1+ 3x2
Max Z= 50x1+ 60x2 Min Z= 400x1+ 600x2 2x1 + x2 ≥30
-x1 - x2≤-1 (P4)
(P1) x1 +2 x2≤8 x1 +1,5 x2 ≥300 (P3) x1 + 2x2 ≥30
(P2) x1 + 4x2 ≤ 2
2x1 + 2x2 ≤ 10 x1 ≥50 x1 + 4x2 ≥40
6x1 + x2 ≤ 2
x1 +4/9x2≤4 x2 ≥100 x1 ; x2 ≥0
x1 ; x2 ≥0
x1 ; x2 ≥0 x1 ; x2 ≥0

O.Labbi Cours de recherche opérationnelle ENSAM-Meknès

 1-Résolution d’un PL

Corrigé des exercices :Résoudre graphiquement les programmes linéaires suivants:

Solution pour P1 Solution pour P2 Solution pour P3 Solution pour P4

Solution Optimale au niveau Infinité de solutions au niveau Région admissible non bornée
La solution est l’ensemble
du sommet B(2,3)avec du segment AB avec avec une solution optimale
vide: contraintes
Zmax=280 Zmax=120000 au sommet c (20,5) avec
incompatibles
Zmin=75000
O.Labbi Cours de recherche opérationnelle ENSAM-Meknès