RECHERCHE
OPÉRATIONNELLE
Chehabi Hamza
3ème année ITIRC
PROGRAMME
- Introduction
- Formulation d’un programme linéaire
- Résolution géométrique (graphique) d’un programme linéaire.
- Méthode algébrique de substitution
- Méthode de Simplexe.
- Programmation linéaire en nombres entiers.
Recherche opérationnelle 3
INTRODUCTION
Dans un monde en constante évolution, les
organisations sont confrontées à des défis
complexes et dynamiques. Que ce soit pour
minimiser les coûts, maximiser les bénéfices,
optimiser les ressources, ou prendre des décisions
stratégiques, la recherche opérationnelle se révèle
être un atout essentiel. Aujourd'hui, nous allons
plonger dans l'univers fascinant de l'optimisation
en recherche opérationnelle.
PROGRAMMATION
LINÉAIRE
Programmation linéaire 5
CONDITIONS DE FORMULATION
D’UN PL
• La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le
décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses sont :
1. Les variables de décision du problème sont positives
2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables, c’est à
dire, que la fonction ne peut pas contenir par exemple un produit croisé de deux de ces variables. La
fonction qui représente le critère de sélection est dite fonction objectif (ou fonction économique).
3. Les restrictions relatives aux variables de décision (exemple: limitations des ressources) peuvent être
exprimées par un ensemble d’équations linéaires. Ces équations forment l’ensemble des contraintes.
4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec certitude.
Programmation linéaire 6
ETAPES DE FORMULATION D’UN
PL
Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme linéaire :
1. Identifier les variables du problème à valeur non connues (variable de décision) et les représenter sous forme symbolique
(exp. x1, y1 ).
2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’équations linéaires.
3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction des variables de
décision. Spécifier si le critère de sélection est à maximiser ou à minimiser.
Programmation linéaire 7
PRÉSENTATION THÉORIQUE
Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite fonction
objectif en satisfaisant certaines équations et inégalités dites contraintes. En langage mathématique, on
décrira de tels modèles de la manière suivante :
Soient N variables de décision 𝑥1 , 𝑥2 , … , 𝑥𝑁
l’hypothèse que les variables de décision sont positives implique que 𝑥1 ≥ 0 , 𝑥2 ≥ 0 , , … . 𝑥𝑁 ≥ 0 .
La fonction objective est une forme linéaire en fonction des variables de décision de type
𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑁 𝑥𝑁
où les coefficients 𝑐1 , 𝑐2 , … , 𝑐𝑁 doivent avoir une valeur bien déterminée (avec certitude) et peuvent être
positifs, négatifs ou nuls. Par exemple le coefficient 𝑐𝑗 peut représenter un profit unitaire lié à la production
d’une unité supplémentaire du bien 𝑥𝑗 , ainsi la valeur de z est le profit total lié à la production des différents
biens en quantités égales à 𝑥1 , 𝑥2 , … , 𝑥𝑁
Programmation linéaire 8
Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis par M inégalités
où les coefficients 𝑎11 , ⋯ 𝑎𝑀𝑁 et 𝑏1 , … , 𝑏𝑀 doivent avoir une valeur bien déterminée (avec certitude) et peuvent
être positifs, négatifs ou nuls. Le paramètre 𝑏𝑖 représente la quantité de matière première disponible dont le bien
𝑥𝑗 utilise une quantité égale à 𝑎𝑖𝑗 𝑥𝑗 .
Programmation linéaire 9
En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :
(PL)
Programmation linéaire 10
Exemples de formulation :
Exemple 1 :
Un fabricant produit 2 types de yaourts à la fraise A et B à partir de Fraise, Lait et de Sucre.
Chaque yaourt doit respecter les proportions suivantes de matières premières
Yaourt A Yaourt B
Fraise 2 1
Lait 1 2
Sucre 0 1
Les matières premières sont en quantité limitée : 800 Kilos de Fraises, 700 litres de Lait et 300 Kilos de sucre.
La vente des Yaourts A rapportent 45 dh par kilo et les Yaourts B 55 dh.
Programmation linéaire 11
1-Identification des variables de décision :
𝑥1 : la quantité de Yaourts A à produire.
𝑥2 : la quantité de Yaourts B à produire.
2- La fonction objective:
3- Les contraintes structurelles :
Yaourt A Yaourt B Disponibilités
(𝑥1 ) (𝑥2 ) de matières
premières
Fraise 2 1 800 Première contrainte
Lait 1 2 700 Deuxième contrainte
Sucre 0 1 300 Troisième contrainte
Programmation linéaire 12
Première contrainte : 2𝑥1 + 𝑥2 ≤ 800
Deuxième contrainte : 𝑥1 +2𝑥2 ≤ 700
Troisième contrainte : 𝑥2 ≤ 300
4- Les contraintes de positivité:
𝑥1 ≥ 0, 𝑥2 ≥ 0
Alors, le programme linéaire peut s’écrire sous la forme mathématique suivante :
Programmation linéaire 13
Exemple 2:
Ebéniste fabrique des tables et des armoires, avec 3 sortes de bois : chêne, pin, et noyer.
Pour fabriquer une table, on a besoin de 2m² de chêne, de 2 m² de pin et de 1m² de
noyer. De même, pour fabriquer une armoire, on a besoin de 3m² de chêne, de 1 m² de
pin et de 3 m² de noyer. En outre, l'ébéniste dispose d'une quantité limitée de bois. Il a
180 m² de chêne, 120 m² de Pen et 150 de noyer.
Sachant que le prix de revient d’une table est 3 unités et que celui d’une armoire e
st de 4 unités.
Combien de tables et d’armoires faut-il fabriquer pour maximiser le profit?
Programmation linéaire 14
Exemple 3 :
Un agriculteur souhaite mélanger des engrais de façon à obtenir au minimum 15
unités de potasse, 20 unités de nitrates et 30 unités de phosphates. Il achète deux
types d’engrais.
• Le type 1 procure 3 unités de potasse, 1 unité de nitrates et 3 unités de
phosphates. Il coûte 1200 dh.
• Le type 2 procure 1 unités de potasse, 5 unité de nitrates et 2 unités de
phosphates. Il coûte 600 dh.
Exprimer à l’aide d’un programme linéaire la combinaison d’engrais qui
remplira les conditions exigées au moindre coût.
Programmation linéaire 15
1-Identification des variables de décision :
𝑥1 : La quantité de mélange de type 1 à acheter.
𝑥2 : La quantité de mélange de type 2 à acheter.
2-La fonction objective :
3-Les contraintes structurelles :
Mélange de type 1 Mélange de type 2 Les besoins
(𝑥1 ) (𝑥2 )
Potasse 3 1 15 Première contrainte
Nitrates 1 5 20 Deuxième contrainte
Phosphates 3 2 30 Troisième contrainte
Programmation linéaire 16
Première contrainte : 3𝑥1 + 𝑥2 ≥ 15
Deuxième contrainte : 𝑥1 + 5𝑥2 ≥ 20
Troisième contrainte : 3𝑥1 + 2𝑥2 ≥ 30
4-Les contraintes structurelles :
𝑥1 ≥ 0, 𝑥2 ≥ 0
Alors, le programme linéaire peut s’écrire sous la forme mathématique suivante :
Programmation linéaire 17
Exemple 4:
Une société de communication négocie des droits d’exploitation sur plusieurs années d’une chaîne de télévision à
couverture nationale. Un contrat l’oblige à diffuser pendant cette période au moins 1800 heures de fictions françaises,
1800 heures de fictions européennes et 1200 heures de reportages.
Pour acheter les programmes, elle se fournit auprès de deux entreprises de production télévisuelle qui vendent des
ensembles d’émissions « clé en main » appelés « lots ».
La société Damol propose des lots composés de la manière suivante :
• 90 heures de fictions françaises
• 120 heures de fictions européennes
• 40 heures de reportages
Chaque lot coûte 20 M€.
La société Martel propose des lots composés de la manière suivante :
• 90 heures de fictions françaises
• 60 heures de fictions européennes
• 100 heures de reportages
Chaque lot coûte 24 M€.
Modéliser ce problème par un programme linéaire.
RÉSOLUTION
GÉOMÉTRIQUE D’UN
PROGRAMME
LINÉAIRE (PL)
Résolution graphique 19
INTRODUCTION
Après avoir illustré par des exemples, comment un problème pratique peut être modélisé par un programme
linéaire, l’étape qui va suivre sera certainement celle de la résolution de ce problème mathématique. La
méthode graphique est l’une des premières méthodes utilisées à ce sujet.
Si on parle de résolution graphique alors on doit se limiter à une représentation à deux variables et au plus à
trois variables. Ceci indique que dans ce chapitre on examinera seulement les programmes linéaires à deux
variables de décision.
Résolution graphique 20
SYSTÈME D’AXES
Une des conditions de la réussite de notre représentation graphique est le choix d'un système d’axes. Un
mauvais choix peut rendre notre représentation non claire et imprécise.
A cause des contraintes de non-négativité des variables de décision, nous nous intéressons seulement au
cadran positif (voir figure ci-dessus). Cette région s’appelle la région des solutions possibles du problème.
Résolution graphique 21
Prenons l’exemple 1 relatif au problème de production des yaourts à base de la fraise. Le programme linéaire est le suivant :
Un bon choix se base sur une lecture des différents paramètres du programme linéaire. Dans notre cas, on ne
peut qualifier de bon, le choix de 200 comme unité dans les deux axes. Pour cet exemple, on peut choisir le
système d’axes suivant :
Résolution graphique 22
REPRÉSENTATION GRAPHIQUE DES
CONTRAINTES
Parmi les solutions possibles d’un problème, il y a ceux qui vont satisfaire toutes les contraintes du programme,
appelés solutions réalisables, et ceux qui vont satisfaire une partie ou aucune de ces contraintes, appelés
solutions non réalisables.
Une représentation graphique des inégalités (des contraintes) va nous permettre de déterminer l’ensemble
des solutions réalisables. Revenons à l’exemple 1 du problème de production des yaourts :
- Une des contraintes de ce problème est celle relative à la disponibilité de la fraise :
2𝑥1 + 𝑥2 ≤ 800
L’ensemble des solutions qui vérifient cette inégalité est le même que celui qui vérifie
2𝑥1 + 𝑥2 = 800 𝑒𝑡 2𝑥1 + 𝑥2 < 800
L’ensemble des solutions qui correspond à l’équation est l’ensemble des points de la droite Δ1 définie par
2𝑥1 + 𝑥2 = 800 .
L’inégalité 2𝑥1 + 𝑥2 < 800 correspond à un demi-plan limité par la droite 2𝑥1 + 𝑥2 = 800. Or cette droite
divise le plan en deux demi-plans ouverts donc quel est le demi-plan à choisir ?
Résolution graphique 23
Pour ce faire, il suffit de prendre un point de l’un des demi-plans (c’est à dire n’appartenant pas à la
droite 2𝑥1 + 𝑥2 = 800 ) et voir s’il vérifie l’inégalité 2𝑥1 + 𝑥2 < 800
Par exemple le point de coordonnées (0,0) vérifie l’inégalité 2𝑥1 + 𝑥2 < 800 donc le demi-plan 𝜋1 au-
dessous de la droite est celui recherché.
L’espace hachuré représente le demi-plan fermé des solutions qui ne vérifient pas la contrainte
2𝑥1 + 𝑥2 < 800 .
Si on fait de même pour les deux autres contraintes du problème , on obtient les deux autres demi-
plans 𝜋2 , 𝜋3 relatifs aux solutions vérifiant respectivement les contraintes
𝑥1 +2𝑥2 ≤ 700 et 𝑥2 ≤ 300
Une solution possible du problème est dite réalisable si et seulement si elle vérifie toutes les
contraintes, c’est à dire si elle appartient aux trois demi-plans relatifs à chaque contrainte du
programme linéaire, en d’autre terme à
𝜋1 ∩ 𝜋2 ∩ 𝜋3
Résolution graphique 24
Δ3
Δ2
Δ1
Résolution graphique 25
Δ3
Δ2
Δ1
Résolution graphique 26
Δ3
Δ2
Δ1
Résolution graphique 27
REPRÉSENTATION DE LA
FONCTION OBJECTIVE
Soit z la valeur de la fonction objectif du problème de yaourts :
Pour z=0, la fonction objectif est représentée de la manière suivante :
z=0
Résolution graphique 28
On peut tracer une infinité de droites qui représentent les différentes valeurs de la
fonction objective. Par suite elles sont parallèles entre elles. De plus on peut améliorer la
valeur de z indéfiniment dans le sens indiqué dans la figure ci-dessous.
Le problème est de connaître qu’elle est la droite qui correspond à la valeur maximale de
la fonction objectif ?
Résolution graphique 29
RECHERCHE DE LA SOLUTION
OPTIMALE
1- Résolution graphique :
Si nous retraçons l’ensemble des droites parallèles relatives aux différentes valeurs de la fonction
objectif sur la figure qui représente l’ensemble des solutions réalisables, on peut localiser la
solution optimale. Elle correspond à la solution réalisable qui intercepte la droite à la plus
grande valeur de z.
Dans notre exemple, la solution optimale est l’intersection des deux contraintes
2𝑥1 + 𝑥2 ≤ 800 et 𝑥2 ≤ 300
Une évaluation des coordonnées de ce point revient à résoudre le système linéaire suivant :
2𝑥1 + 𝑥2 ≤ 800
ቊ
𝑥2 ≤ 300
Elle correspond d’après le graphique au point (300,200). Donc la prescription optimale est de
300 unités des yaourts de type 1 et 200 unités des yaourts de type2. Le chiffre d’affaire rapporté
(la valeur de la fonction objectif) est égal à 24500 dh.
Titre de la présentation 30
2- Résolution par énumération:
On remarque que la solution optimale du problème de production des yaourts à la base de la fraise est un
point extrême qui se trouve sur le bord de l’ensemble des solutions. Une telle solution est dite solution
réalisable de base. On peut admettre le résultat suivant : « Si un programme linéaire admet une solution
optimale alors il existe une solution réalisable de base pour laquelle la fonction objectif atteint la valeur
optimale » Une méthode de résolution du programme linéaire consiste donc à déterminer les solutions
réalisables de base (les points d’intersection des droites qui forment les contraintes) et à calculer pour
chaque point la valeur de la fonction objectif. La solution du programme linéaire est la solution à qui on
associe la valeur optimale de la fonction objective.
Dans le problème de production des yaourts, l’ensemble des solutions réalisables de base présente 3
points extrêmes A(0,300), B(100,300) et C(300,200) et D(400,0). La valeur de la fonction objective associée
respectivement à A, B, C et D sont :16500 DH, 21000 DH , 24500 DH et 18000 DH. On vérifie bien que C
est la solution optimale du problème avec une valeur optimale égale à 24500 DH.
Résolution graphique 31
Exemple :
Reprenons l’exemple de la société de communication qui négocie des droits d’exploitation sur plusieurs
années d’une chaîne de télévision à couverture nationale. On avait trouver le programme linéaire suivant :
Et on peut le rendre comme suit :
RÉSUMÉ
Dans cette méthode, seules les variables d’activités ou variables réelles seront utilisées. Il n’y aura donc pas de variables
d’écarts ou artificielles.
Après traduction du problème posé en modèle mathématique, on se bornera simplement à :
1. Représenter graphiquement les droites-limites (équations provenant des inéquations de départ).
2. Délimiter la frontière de l’enveloppe polygonale c'est-à-dire à construire le domaine d’acceptabilités.
3. Remplacer successivement les coordonnées de chaque sommet du polygone dans la fonction économique afin
d’obtenir la combinaison optimale cherchée.
En général, pour chercher le minimum, on optera pour le point le plus voisin de l’origine, alors que pour le maximum
ce sera le point le plus éloigné.
On pourra utiliser, à la place de l’énumération de tous les points de polygone d’acceptabilité, le procédé qui consiste à
déplacer la droite de la fonction économique parallèlement à son inclinaison à l’origine et en chacun des sommets du
domaine d’acceptabilité. Pour le coût, on retiendra la droite la plus voisine de l’origine et pour le minimum la plus
éloignée.
