Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
La programmation linéaire
Définition de la programmation linéaire :
La programmation linéaire est un des domaines les plus utilisés de la RO. Elle permet de
traiter un vaste ensemble de problèmes d’optimisation dans des contextes divers comme la
gestion de stocks, flux de transport, distribution de tâches à des personnels, recherche de
plans de fabrication etc. . . La modélisation de ces problèmes débouche sur des équations ou
inéquations linéaires (exprimant les différentes contraintes) dont on cherche les solutions
permettant d’optimiser une fonction économique elle-même linéaire. De plus on supposera
que les variables considérées sont astreintes à être positives (contraintes de positivité). On
appelle une telle formulation un programme linéaire (PL).
La programmation linéaire a été découverte en 1947 par G.B. Dantzig. Un an plus tard, le
même G.B. Dantzig inventait un algorithme (appelé l'algorithme du simplexe) permettant de
résoudre les programmes linéaires. Aujourd'hui encore, la programmation linéaire est très
largement utilisée.
Les conditions de formulation d’un PL :
On appelle programme linéaire un modèle d'optimisation vérifiant les quatre conditions
suivantes :
Tous les paramètres sont connus avec exactitude,
La fonction objectif et les membres de gauche des contraintes peuvent s'écrire comme une
somme de produits d'une variable par un paramètre,
Les contraintes sont des inégalités au sens large ou des égalités,
Le modèle comporte une fonction objectif qui doit être maximisée ou bien minimisée.
Modélisation d'un Problème de programmation linéaire :
La formalisation d’un programme est une tâche délicate mais essentielle car elle conditionne
la découverte ultérieure de la bonne solution. Elle comporte les mêmes phases quelles que
soient les techniques requises ultérieurement pour le traitement (programmation linéaire ou
programmation non linéaire) :
1. La détection du problème et l’identification des variables. Ces variables doivent
correspondre exactement aux préoccupations du responsable de la décision. En
programmation mathématique, les variables sont des variables décisionnelles.
1
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
2. La formulation de la fonction économique (ou fonction objectif) traduisant les
préférences du décideur exprimées sous la forme d’une fonction des variables
identifiées.
3. La formulation des contraintes. Il est bien rare qu’un responsable dispose de toute
liberté d’action. Le plus souvent il existe des limites à ne pas dépasser qui revêtent la
forme d’´equations ou d’inéquations mathématiques.
La forme générale d’un programma linéaire :
La forme générale d’un PL est comme suit :
𝑛
𝑜𝑝𝑡𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = ∑ 𝑐𝑖 𝑥𝑖
𝑖=1
𝑠. 𝑐:
≤
𝐴 (=) 𝑏𝑗
≥
{ 𝑥𝑖 ≥ 0
La forme matricielle :
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
𝑠 𝑐:
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
{ 𝑥𝑖 ≥ 0 𝑝𝑜𝑢𝑟 𝑖 = 1,2, … , 𝑛
𝑥1 , 𝑥2 , … , 𝑥𝑛 : sont les variables de décision (leurs valeurs respectives sont inconnues)
𝑐1 , 𝑐2 , … , 𝑐𝑛 : sont les coefficients des variables de la fonction économique (se sont par
exemple le profit unitaire pour un problème de maximisation ou le coût unitaire s’il s’agit
d’un problème de minimisation)
𝑏, 𝑏2 , … , 𝑏𝑚 : sont les quantités disponibles des m ressources
𝑎𝑖1 , 𝑎𝑖2 , … , 𝑎𝑖𝑛 : sont les coefficients technologiques de chaque variable de décision par
rapport à la ressource
Pour les problèmes à maximum de la fonction économique, les contraintes par rapport aux
seconds membres bj seront de type ≤ tandis que pour les problèmes à minimum elles seront
du type ≥. On obtient ainsi les deux formulations suivantes appelées formes canoniques :
2
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
𝑛 𝑛
𝑚𝑎𝑥 𝑍 = ∑ 𝑐𝑖 𝑥𝑖 𝑚𝑖𝑛 𝑍 = ∑ 𝑐𝑖 𝑥𝑖
𝑖=1 𝑖=1
𝑠. 𝑐: 𝑠. 𝑐:
𝑛 𝑛
∑ 𝑎𝑖𝑗 𝑥𝑖 ≤ 𝑏𝑗 𝑗 = 1,2, … , 𝑚 ∑ 𝑎𝑖𝑗 𝑥𝑖 ≥ 𝑏𝑗 𝑗 = 1,2, … , 𝑚
𝑖=1 𝑖=1
{ 𝑥𝑖 ≥ 0 𝑝𝑜𝑢𝑟 𝑖 ∈ {1, … , 𝑛} { 𝑥𝑖 ≥ 0 𝑝𝑜𝑢𝑟 𝑖 ∈ {1, … , 𝑛}
Exemple 1 :
Une entreprise de fabrication de châssis qui envisage la production de deux nouveaux
modèles au moyen des capacités résiduelles de ses trois ateliers. Il s’agit respectivement d’un
châssis en aluminium et d’un châssis en bois. Le premier produit nécessite le passage dans le
premier atelier pour fabriquer le cadre en aluminium et dans le troisième atelier où le verre
est monté sur le châssis. Tandis que le second produit nécessite le passage dans le deuxième
atelier pour fabriquer le cadre en bois et dans le troisième atelier où le verre est monté sur le
châssis. Les marges unitaires, les temps de fabrication de chacun des produits dans chacun
des ateliers ainsi que les capacités hebdomadaires résiduelles de ces ateliers sont données au
tableau suivant :
Produits
Produit 1 Produit 2 Capacité disponible
Ateliers
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Marge 3um 5um
La question qui se pose est la suivante : Combien faut-il produire de châssis de chaque type
par semaine pour maximiser le profit net ?
La formulation d’un problème d’optimisation comporte toujours les trois étapes suivantes :
1. choix des variables du modèle;
2. formulation de l’objectif;
3. formulation des contraintes.
3
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
La première étape consiste à choisir les variables du problème.
On appelle variable toute quantité utile à la résolution du problème dont le modèle doit
déterminer la valeur.
𝑥 : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑐ℎâ𝑠𝑠𝑖𝑠 𝑑𝑒 𝑡𝑦𝑝𝑒 1 𝑝𝑟𝑜𝑑𝑢𝑖𝑡𝑠 𝑝𝑎𝑟 𝑠𝑒𝑚𝑎𝑖𝑛𝑒
Notons donc : { 1
𝑥2 : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑐ℎâ𝑠𝑠𝑖𝑠 𝑑𝑒 𝑡𝑦𝑝𝑒 2 𝑝𝑟𝑜𝑑𝑢𝑖𝑡𝑠 𝑝𝑎𝑟 𝑠𝑒𝑚𝑎𝑖𝑛𝑒
La deuxième étape consiste à formuler mathématiquement l’objectif.
On appelle fonction objectif d’un problème d’optimisation le critère de choix entre les
diverses solutions possibles.
Ici l’entreprise désire maximiser son profit net. La marge étant de 3 pour le premier type de
châssis et de 5 pour le second, l’objectif s’exprime comme suit :
𝑴𝒂𝒙 𝒁 = 𝟑𝒙𝟏 + 𝟓𝒙𝟐
La troisième étape est la formulation les contraintes du problème.
On appelle contraintes du problème toutes les relations limitant le choix des valeurs
possibles des variables.
Atelier 1 : 𝑥1 ≤ 4
Atelier 2 : 2𝑥2 ≤ 12
Atelier 3 : 3𝑥1 + 2𝑥2 ≤ 18
Les quantités produites ne peuvent être négatives: 𝑥1 , 𝑥2 ≥ 0
La formulation de ce problème est comme suit :
𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2
𝑠𝑐:
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
{ 𝑥1 , 𝑥2 ≥ 0
La méthode graphique :
Lorsqu'il n'y a que deux variables de décision, un problème linéaire peut être résolu de
manière purement graphique.
4
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
A cause des contraintes de non-négativité des variables de décision, nous nous intéressons
seulement au cadran positif (voir figure suivante). Cette région s’appelle la région des
solutions possibles du problème.
La résolution graphique d'un problème linéaire consiste à tracer la droite qui sépare les
demi-plans pour chaque contrainte tout en conservant le demi-plan acceptable, c'est-à dire 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
Une représentation graphique des inégalités (des contraintes) va nous permettre de
déterminer l’ensemble des solutions réalisables.
Soit l’exemple suivant :
Exemple 1 :
Un fabricant produit 2 types de yaourts `a la fraise A et B `a partir de Fraise, de Lait et de
Sucre. Chaque yaourt doit respecter les proportions suivantes de matières premières.
Les matières premières sont en quantité limitée : 800 kilos de Fraises, 700 kilos de Lait et 300
kilos de sucre. La vente des yaourts A rapportent 4 um par kilo et les yaourts B 5um.
Yaourts A Yaourts B
Fraise 2 1
Lait 1 2
Sucre 0 1
a- Identification des variables de décision :
𝑥1 : la quantité de yaourts A à produire
𝑥2 : la quantité de yaourts B à produire
b- La fonction objectif :
𝑍 = 4𝑥1 + 5𝑥2
5
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
c- Les contraintes :
- La première contrainte : 2𝑥1 + 𝑥2 ≤ 800
- La deuxième contrainte : 𝑥1 + 2𝑥2 ≤ 700
- La troisième contrainte : 𝑥2 ≤ 300
Alors le modèle est comme suit :
𝑀𝑎𝑥 𝑍 = 4𝑥1 + 5𝑥2
𝑠𝑐:
2𝑥1 + 𝑥2 ≤ 800
𝑥1 + 2𝑥2 ≤ 700
𝑥2 ≤ 300
{ 𝑥1 𝑥2 ≥ 0
On prend la première contrainte du système et on remplace l'inégalité par une égalité.
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'équation résultante correspond à une droite (∆1 ). Pour tracer une droite, il faudrait
déterminer deux points, ce qui donne pour la première contrainte de notre exemple :
2𝑥1 + 𝑥2 = 800
𝑥1 = 0 ⇒ 𝑥2 = 800 ⇒ 𝑙𝑒 𝑝𝑟𝑒𝑚𝑖𝑒𝑟 𝑝𝑜𝑛𝑖𝑡 𝑒𝑠𝑡 (𝑥1 , 𝑥2 ) = (0 , 800)
{
𝑥2 = 0 ⇒ 𝑥1 = 400 ⇒ 𝑙𝑒 𝑑𝑒𝑢𝑥𝑖è𝑚𝑒 𝑝𝑜𝑖𝑛𝑡 𝑒𝑠𝑡 (𝑥1 , 𝑥2 ) = (400 , 0)
À partir de ces points on trace la première droite et on conserve ce qui est en dessus de la
droite. On élimine ensuite la partie supérieure puisque la contrainte est une contrainte
d'infériorité.
X2
800
X1
400
(∆1 )
2𝑥1 + 𝑥2 = 800
Représentation graphique de la première contrainte
6
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
On applique le même principe pour toutes les contraintes du système :
𝑙𝑎 𝑑𝑒𝑢𝑥𝑖è𝑚𝑒 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒: 𝑥1 + 2𝑥2 = 700
𝑥1 = 0 ⇒ 𝑥2 = 350 ⇒ 𝑙𝑒 𝑝𝑟𝑒𝑚𝑖𝑒𝑟 𝑝𝑜𝑛𝑖𝑡 𝑒𝑠𝑡 (𝑥1 , 𝑥2 ) = (0 , 350)
{
𝑥2 = 0 ⇒ 𝑥1 = 700 ⇒ 𝑙𝑒 𝑑𝑒𝑢𝑥𝑖è𝑚𝑒 𝑝𝑜𝑖𝑛𝑡 𝑒𝑠𝑡 (𝑥1 , 𝑥2 ) = (700 , 0)
La troisième contrainte : 𝑥2 = 300
L'intersection de toutes les contraintes forme le polygone de solutions tel qu'il est donné par
la représentation suivante :
X2
800
350
300 A B (∆3 ): 𝑥2 = 300
C
D
O X1
400 700
(∆1 ): 2𝑥1 + 𝑥2 = 800 (∆2 ): 𝑥1 + 2𝑥2 = 700
La représentation graphique indique dans sa partie hachurée l'ensemble des points qui
satisfont les contraintes du problème. Tous les couples de la partie hachurée satisfont les
contraintes. Mais en fait, la solution optimale sera toujours l'un des sommets du polyèdre
délimitant le domaine des solutions réalisables. Il s'agit dans ce cas des sommets suivants :
∗ 𝐿𝑒 𝑝𝑜𝑖𝑛𝑡 𝐴: 𝑖𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡𝑖𝑜𝑛 𝑑𝑒 (∆3 )𝑎𝑣𝑒𝑐 𝑙 ′ 𝑎𝑥𝑒 𝑂𝑋2 → 𝐴(0 , 300)
∗ 𝐿𝑒 𝑝𝑜𝑖𝑛𝑡 𝐵: 𝑖𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡𝑖𝑜𝑛 𝑑𝑒 (∆3 )𝑎𝑣𝑒𝑐 (∆2 ) → 𝐵(100 , 300)
∗ 𝐿𝑒 𝑝𝑜𝑖𝑛𝑡 𝐶: 𝑖𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡𝑖𝑜𝑛 𝑑𝑒 (∆1 )𝑎𝑣𝑒𝑐 (∆2 ) → 𝐶 (300 , 200)
∗ 𝐿𝑒 𝑝𝑜𝑖𝑛𝑡 𝐷: 𝑖𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡𝑖𝑜𝑛 𝑑𝑒 (∆1 )𝑎𝑣𝑒𝑐 𝑙 ′ 𝑎𝑥𝑒𝑂𝑋2 → 𝐷(400 , 0)
∗ 𝑙𝑒 𝑝𝑜𝑖𝑛𝑡 𝑑 ′ 𝑜𝑟𝑖𝑔𝑖𝑛𝑒 𝑂 (0 , 0)
Le vecteur normal de la droite définissant la fonction objectif indique le sens dans lequel on
4
doit la translater pour trouver le point optimal. Le vecteur normal ( ) de la droite
5
7
Module : Recherches Opérationnelles 1
Niveau : 1ère année second cycle
Dr : NAIM
4𝑥1 + 5𝑥2 = 0 indique un déplacement vers le haut, la fonction objectif doit alors couper
l'axe OX2 le plus haut possible, tout en touchant le domaine des solutions réalisables. On
s'aperçoit que celle qui conserve un point en commun avec la région réalisable est la droite
qui passe par le sommet (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 à
2200um.
