Chapitre 1 :
Programmation Linéaire
Génie informatique
2023-2024
1
Plan
1. Introduction à la recherche opérationnelle
2. Introduction à la programmation linéaire
3. Modélisation d’un programme linéaire
4. Résolution graphique d’un programme linéaire
5. Analyse de sensibilité
2
Définition
La recherche opérationnelle (RO) est au confluent de l'informatique, des mathématiques
appliquées, de la gestion et du génie industriel. L'objet de cette discipline est d’élaborer de
meilleures décisions et de fournir des bases rationnelles à la prise de décisions, habituellement
dans un but de contrôle ou d'optimisation (améliorer l'efficacité, diminuer les coûts, etc.).
La R.O est une discipline récente (environ 60-70 ans) qui est à la frontière entre Informatique,
Economie et Mathématiques appliquées.
Origines militaire de la RO :
Objectif : optimisation de la logistique militaire et du réapprovisionnement des troupes. A l'origine,
le mot opérationnel signifie donc en vue de programmer des opérations militaires.
Après, le domaine de la RO s'est étendu à des applications civiles.
R de RO = recherche de solutions concrètes
3
Domaines d’application
On utilisera par exemple des techniques de RO pour :
● Gérer les soins de santé dans les hôpitaux
● Organiser les services policiers ou ambulanciers
● Planifier l'utilisation et gérer la production d'énergie
● Planifier des systèmes de livraison ou de transport en commun
● Gérer la production, les stocks et la distribution de produits usinés
● Concevoir des systèmes de communication et des systèmes informatiques
● Établir des horaires de travail, de cours ou des calendriers sportifs
● Choisir des politiques économiques et financières
● Production
● Problèmes de transport
● Problèmes de télécoms
● Planification de projets
● Gestion financière (banques)
4
Plan
1. Introduction à la recherche opérationnelle
2. Introduction à la programmation linéaire
3. Modélisation d’un programme linéaire
4. Résolution graphique d’un programme linéaire
5. Analyse de sensibilité
5
Programmation Linéaire:
La programmation linéaire est un outil très puissant de la recherche opérationnelle. Les problèmes
de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources
limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le
terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui
réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d’un
problème mathématique
Problème Linéaire:
Bien que la réalité soit souvent loin d’être linéaire, un grand nombre de problèmes peuvent s’écrire
sous forme linéaire, soit directement, soit en première simplification. D’autre part, un très grand
nombre de modèles constituent des extensions de programmes linéaires. Sa compréhension est
essentielle à la compréhension de modèles plus sophistiqués.
Définition : Programme linéaire: Modèle mathématique dans lequel la fonction objectif et les
contraintes sont linéaires en les variables
6
(1): fonction Objectif « F.O »
(2): m contraintes linéaires.
(3): contraintes de positivités.
𝑥𝑗 : variables de décision
𝑏𝑗 : second terme
7
Forme Générale d’un PL:
8
Plan
1. Introduction à la recherche opérationnelle
2. Introduction à la programmation linéaire
3. Modélisation d’un programme linéaire
4. Résolution graphique d’un programme linéaire
5. Analyse de sensibilité
9
Éléments d’un PL:
Un modèle mathématique est donc constitué de:
1. une fonction objectif
2. des variables de décision
3. des contraintes qui sont de type:contraintes de ressources et contraintes de signe
Étapes 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 principales, les variables de décision du problème (non connues), 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.
10
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.
11
Exemple 1:
Problème : Achat de billets d’avion.
● Un homme d’affaires doit effectuer 5 voyages (sur 5 semaines) entre Fayetteville (FYV) à Denver
(DEN), en partant le lundi de FYV et revenant le mercredi de DEN à FYV.
● Billet aller-retour : $400.
● Réduction de 20 % si un weekend est inclus.
● Aller ou retour simple : 75 % du prix aller-retour.
Question: Comment acheter les billets pour les 5 semaines (à prix minimum) ?
Aide à la décision
1. Quelles sont les alternatives possibles ?
2. Quelles sont les restrictions à cette décision ?
3. Quel est l’objectif utilisé pour évaluer les alternatives ?
Restrictions
FYV-DEN le lundi et DEN-FYV le mercredi de la même semaine.
1 voyage : FYV-DEN-FYV
12
Exemple 1:
Evaluation des alternatives Alternatives
● Acheter 5 FYV-DEN-FYV normaux:
5 x $400 = $2000
● Acheter un FYV-DEN, 4 DEN-FYV-DEN comprenant un weekend et un DEN-FYV:
0.75 x $400 + 4 x 0.8 x $400 + 0.75 x $400 = $1880
● Acheter un FYV-DEN-FYV pour le lundi de la première semaine et le mercredi de la dernière
semaine, et 4 DEN-FYV-DEN comprenant un weekend pour les autres voyages:
5 x 0.8 x 400 =1600.
⇒ La troisième alternative est la meilleure.
13
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éfice net de 100 dinars. Un hectare de piments demande 4 heures de main
d’œuvre, 2 m3 d’eau et donne un bénéfice 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 afin d’optimiser le profit?
14
Exemple 2:
𝑥1 ≤ 90
𝑥1 , 𝑥2 ≥ 0 15
Exemple 3:
16
17
Exemple 4 :
18
Exemple 5:
19
Propriétés
La programmation linéaire permet de modéliser de nombreux problèmes réels en exprimant leur fonction objectif
et leurs contraintes sous forme de fonctions linéaires des variables de décision. Cependant, elle impose un
certain nombre de restrictions réduisant ainsi son champ d’application. Ces restrictions sont :
• La proportionnalité : les termes mesurant les coûts et les quantités de ressources utilisées doivent être
proportionnels au niveau de chaque activité.
• L’additivité : les coûts et les ressources engagés par l’utilisation conjointe de deux activités doivent être égaux
aux termes correspondants des activités utilisées séparément.
• La continuité ou encore la divisibilité : les variables utilisées doivent être continues.
• Le problème déterministe : tous les coefficients du modèle doivent être des constantes connues et non des
variables sujettes à variations.
20
Propriétés
• Un problème de maximisation est transformé en un problème équivalent de minimisation en remplaçant
uniquement Max 𝑐 𝑡 x = - Min 𝑐 𝑡 x.
• On a 𝑀𝑎𝑥𝑥 f(x) + c équivaut 𝑀𝑎𝑥𝑥 f(x).
𝑀𝑎𝑥𝑥 d*f(x) équivaut à 𝑑 ∗ 𝑀𝑎𝑥𝑥 f(x) si d positive.
• Une variable de décision 𝑥𝑗 négative peut être remplacée dans la formulation par l’opposé d’une autre variable
positive : 𝑥𝑗 = −𝑦𝑗 , 𝑦𝑗 ≥ 0.
• Le sens d’une inégalité peut être inversé en multipliant des deux côtés par –1.
• Une égalité peut être remplacée par deux contraintes : l’une est supérieure ou égale et l’autre est inférieure ou
égale au second membre.
• Certaines variables peuvent ne pas être forcés à être supérieures à 0. Par exemple, considérons la contrainte
x ≥ −4, qui équivaut à x + 4 ≥ 0. Nous pouvons alors définir y = x + 4, de sorte que la contrainte devient y ≥ 0.
De même, considérons −10 ≤ x ≤ −2. En définissons y = x + 10, nous avons la contrainte y ≥ 0.
21
Formes d’un PL
La forme canonique avec des contraintes ≤ s’utilise dans la représentation graphique, et la forme standard avec
des contraintes égalité s’utilise dans la résolution algébrique.
22
