Résumé de la Programmation Linéaire
16 mars 2025
Table des matières
1 Introduction à la Programmation Linéaire 1
1.1 Exemple simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Vocabulaire et Concepts de Base 2
2.1 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Résolution Graphique d’un Programme Linéaire 2
3.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 Méthode des Points Extrêmes 3
5 Méthode Algébrique des Sommets 3
5.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
6 Conclusion 3
1 Introduction à la Programmation Linéaire
La Programmation Linéaire est une méthode mathématique utilisée pour
résoudre des problèmes d’optimisation. L’objectif est de maximiser ou mini-
miser une fonction (appelée fonction objectif ) tout en respectant certaines
contraintes. Ces contraintes sont généralement des inégalités ou des égalités
linéaires.
1.1 Exemple simple
Imaginez que vous gérez une entreprise qui produit deux types de produits,
A et B. Vous voulez maximiser votre profit, mais vous avez des limites sur les
ressources disponibles (comme la main-d’œuvre, les matières premières, etc.).
La programmation linéaire vous aide à déterminer combien de produits A et B
vous devez produire pour maximiser votre profit tout en respectant ces limites.
1
2 Vocabulaire et Concepts de Base
2.1 Vocabulaire
— Variables de décision : Ce sont les inconnues que vous devez déterminer.
Par exemple, x1 et x2 pourraient représenter les quantités de produits A
et B à produire.
— Fonction objectif : C’est la fonction que vous voulez optimiser (maxi-
miser ou minimiser). Par exemple, Z = 100x1 +150x2 pourrait représenter
le profit total, où 100 et 150 sont les profits unitaires des produits A et
B.
— Contraintes : Ce sont les limites que vous devez respecter. Par exemple,
si vous avez une limite de 100 heures de travail, une contrainte pourrait
être 2x1 + x2 ≤ 100, où 2x1 représente le temps nécessaire pour produire
x1 unités de A, et x2 le temps pour x2 unités de B.
— Non-négativité : Les variables de décision ne peuvent pas être négatives.
Par exemple, x1 ≥ 0 et x2 ≥ 0, car vous ne pouvez pas produire une
quantité négative de produits.
— Solution réalisable : Une solution qui respecte toutes les contraintes.
Par exemple, x1 = 10 et x2 = 20 est une solution réalisable si elle respecte
toutes les contraintes.
— Solution optimale : La solution réalisable qui maximise ou minimise la
fonction objectif.
3 Résolution Graphique d’un Programme Linéaire
La résolution graphique est une méthode simple pour résoudre des problèmes
de programmation linéaire à deux variables. Voici les étapes :
1. Représenter les contraintes : Chaque contrainte est représentée par
une droite sur un graphique. Par exemple, la contrainte 2x1 + x2 ≤ 100
est représentée par la droite 2x1 + x2 = 100.
2. Déterminer la région admissible : La région admissible est l’ensemble
des points qui satisfont toutes les contraintes. C’est généralement une
zone délimitée par les droites des contraintes.
3. Tracer les lignes de niveau de la fonction objectif : Les lignes de
niveau sont des droites parallèles qui représentent différentes valeurs de
la fonction objectif. Par exemple, pour Z = 100x1 + 150x2 , vous tracez
des droites pour différentes valeurs de Z.
4. Trouver la solution optimale : La solution optimale est le point de la
région admissible qui touche la ligne de niveau la plus élevée (pour une
maximisation) ou la plus basse (pour une minimisation).
2
3.1 Exemple
Si vous avez deux contraintes 2x1 + x2 ≤ 100 et x1 + 2x2 ≤ 80, vous tracez
ces deux droites sur un graphique. La région admissible est l’intersection des
zones sous ces droites. Ensuite, vous tracez des lignes de niveau pour la fonction
objectif Z = 100x1 + 150x2 et trouvez le point où Z est maximisé.
4 Méthode des Points Extrêmes
— Points extrêmes : Ce sont les sommets de la région admissible. Selon le
théorème fondamental de la programmation linéaire, la solution
optimale se trouve toujours à l’un de ces points extrêmes.
— Solution de base : Une solution où certaines variables sont égales à zéro
(variables hors base) et les autres sont déterminées par les contraintes
(variables de base).
— Solution de base réalisable : Une solution de base où toutes les va-
riables sont non négatives.
5 Méthode Algébrique des Sommets
Cette méthode consiste à :
1. Convertir les inégalités en égalités.
2. Résoudre le système d’équations pour trouver les points d’intersection
(sommets).
3. Vérifier quels sommets sont dans la région admissible.
4. Évaluer la fonction objectif à chaque sommet admissible pour trouver la
solution optimale.
5.1 Exemple
Si vous avez les contraintes 2x1 + x2 ≤ 100 et x1 + 2x2 ≤ 80, vous les conver-
tissez en égalités et résolvez le système pour trouver les points d’intersection.
Ensuite, vous vérifiez quels points sont admissibles et évaluez Z = 100x1 +150x2
à chaque point pour trouver le maximum.
6 Conclusion
La Programmation Linéaire est un outil puissant pour résoudre des
problèmes d’optimisation dans divers domaines comme la gestion des ressources,
la production, la logistique, etc. Elle permet de prendre des décisions opti-
males en maximisant ou minimisant une fonction objectif tout en respectant
des contraintes données.
— Résolution graphique : Utilisée pour des problèmes simples à deux
variables.
3
— Résolution algébrique : Utilisée pour des problèmes plus complexes
avec plusieurs variables et contraintes.
