Recherche Opérationnelle
Résolution d’un programme linéaire
La PL comme outil de modélisation mathématique d'un problème concret comporte
trois étape:
o Identification des variables
o Formulation des contraintes
o Définition de la fonction objectif
Une fois la modélisation est effectuée, on peut passer à la résolution du problème, donc
du PL. Différentes méthodes existent (méthodes de résolution directes, algorithme du
simplexe, méthode des deux phases, ...)
Recherche Opérationnelle
Résolution d’un programme linéaire
La méthode graphique est l’une des premières méthodes utilisées pour la résolution de problèmes de programmation
linéaire.
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.
Choix du 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 du système d’axes peut
compliquer la représentation et amener à des solutions imprécises.
Le plus simple est le repère orthogonal (pas nécessairement orthonormé)
A cause des contraintes de non-négativité des variables de décision, nous
nous intéressons seulement au cadran positif (voir figure). Cette région
s’appelle la région des solutions possibles du problème.
Recherche Opérationnelle
Résolution d’un programme linéaire
Prenons l’exemple 2 relatif au problème de médecine. Le programme linéaire est le suivant :
Pour la résolution graphique, un bon choix du système
d’axes à adopter se vase sur l’observation des paramètres du
programme. Pour l’exemple, on peut choisir le système
d’axes suivant :
Recherche Opérationnelle
Résolution d’un programme linéaire
Représentation graphique des contraintes
Dans les solutions du problème, on distingue:
o Ceux qui vont satisfaire toutes les contraintes du programme, appelés solutions réalisables
o Ceux qui vont satisfaire une partie ou aucune de ces contraintes, appelés solutions non réalisables.
Revenons à l’exemple 2 du problème de médecine.
Une des contraintes de ce problème est celle relative au grain d’aspirine :
L’ensemble des solutions qui vérifient cette inégalité est le même que celui qui vérifie
Recherche Opérationnelle
Résolution d’un programme linéaire
Représentation graphique des contraintes
L’ensemble des solutions qui correspond à l’équation est l’ensemble des points de la droite l définie par
Cette droite admet une valeur de la pente égale à –2 et intercepte l’axe des ordonnées en 12 (voir figure)
L’inégalité correspond à un demi-plan limité par la droite Or cette droite divise le
plan en deux demi-plans ouverts donc quel est le demi-plan à choisir ?
Pour ce faire, il suffit de prendre un point de l’un des demi-plans (c’est à dire
n’appartenant pas à la droite ) et voir s’il vérifie l’inégalité
Par exemple le point de coordonnées (0,0) ne vérifie pas l’inégalité
Donc le demi-plan 𝜋𝜋1 au-dessus de la droite est celui recherché (voir figure)
L’espace hachuré représente le demi-plan fermé des solutions qui vérifient la
contrainte .
Recherche Opérationnelle
Résolution d’un programme linéaire
Représentation graphique des contraintes
Si on fait de même pour les deux autres contraintes du problème (voir figures ci-dessous), on obtient les deux autres
demi-plans 𝜋𝜋2 et 𝜋𝜋3 relatifs aux solutions vérifiant respectivement les contraintes et
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 (voir figure).
Recherche Opérationnelle
Résolution d’un programme linéaire
Représentation de la fonction objectif
Recherche Opérationnelle
Résolution d’un programme linéaire
Représentation de la fonction objectif
Recherche Opérationnelle
Résolution d’un programme linéaire
Représentation de la fonction objectif
Recherche Opérationnelle
Résolution d’un programme linéaire
Recherche de la solution optimale par résolution graphique
Si nous retraçons l’ensemble des droites parallèles relatives à 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 petite valeur de z.
Dans notre exemple, la solution optimale est l’intersection des deux
contraintes et .
Une évaluation des coordonnées de ce point revient à résoudre le système
linéaire suivant :
Elle correspond d’après le graphique au point (2,8). Donc la prescription optimale est de 2 pilules de petite taille et 8
pilules de grande taille. Le nombre de pilules (la valeur de la fonction objectif) est égale à 10.
Recherche Opérationnelle
Résolution d’un programme linéaire
Exemples
Recherche Opérationnelle
Résolution d’un programme linéaire
Exemples
Recherche Opérationnelle
Résolution d’un programme linéaire
Exemples
Recherche Opérationnelle
Résolution d’un programme linéaire
Exemples
Recherche Opérationnelle
Résolution d’un programme linéaire
Exemples
Recherche Opérationnelle
Résolution d’un programme linéaire
Remarque:
1. À partir de ces exemples, on constate qu’un problème de programmation linéaire peut avoir:
o Aucune solution
o Une solution unique
o Une solution infinie
o Une infinité de solutions
2. On a constaté que lorsque une solution finie existe, elle se présente en un sommet du domaine de solutions
acceptable. Cette propriété forme la base de la méthode de simplexe.
3. La méthode graphique a été possible grâce au nombre réduit de variables et de contraintes.
Recherche Opérationnelle
Résolution d’un programme linéaire
Exercice 1 Exercice 2
Soit le programme linéaire maximisation Soit le programme linéaire maximisation
𝑀𝑀𝑀𝑀𝑀𝑀 2𝑥𝑥1 + 5𝑥𝑥2
𝑀𝑀𝑀𝑀𝑀𝑀 10𝑥𝑥1 + 20𝑥𝑥2
𝑠𝑠𝑠𝑠
𝑥𝑥1 + 3𝑥𝑥2 ≥ 3 𝑠𝑠𝑠𝑠
𝑥𝑥1 + 𝑥𝑥2 ≥ 4
5𝑥𝑥1 + 𝑥𝑥2 ≥ 5
5𝑥𝑥1 + 10𝑥𝑥2 ≤ 30
𝑥𝑥1 ≥ 0 , 𝑥𝑥2 ≥ 0
𝑥𝑥1 ≥ 0 , 𝑥𝑥2 ≥ 0
Recherche Opérationnelle
Résolution d’un programme linéaire
Exercice 3 Exercice 4
Soit le programme linéaire minimisation Soit le programme linéaire maximisation
𝑀𝑀𝑖𝑖𝑖𝑖 3𝑥𝑥1 + 4𝑥𝑥2
𝑠𝑠𝑠𝑠 𝑀𝑀𝑀𝑀𝑀𝑀 50𝑥𝑥1 + 100𝑥𝑥2
𝑥𝑥1 + 𝑥𝑥2 ≥ 5 𝑠𝑠𝑠𝑠
𝑥𝑥1 + 𝑥𝑥2 ≤ 300
2𝑥𝑥1 + 𝑥𝑥2 ≤ 4
2𝑥𝑥1 + 𝑥𝑥2 ≤ 400
𝑥𝑥1 ≥ 0 , 𝑥𝑥2 ≥ 0
𝑥𝑥2 ≤ 250
𝑥𝑥1 ≥ 0 , 𝑥𝑥2 ≥ 0
