Revision sheet: Introduction à la Programmation Linéaire

📋 Plan du Cours

1. Modélisation PL
2. Système d’axes
3. Représentation contraintes
4. Solutions réalisables
5. Fonction objectif
6. Recherche solution optimale
7. Méthode graphique
8. Solutions extrêmes
9. Problèmes spécifiques
10. Exemples d’application

📖 1. Modélisation PL

🔑 Notions clés & Définitions

• Programme Linéaire (PL) : Modèle mathématique visant à optimiser (maximiser ou minimiser) une fonction objectif sous contraintes linéaires.
• Variables de décision : Quantités à déterminer pour atteindre l’objectif, généralement notées $X_1, X_2, \dots$.
• Fonction objectif : Fonction à optimiser, souvent de la forme $Z = c_1X_1 + c_2X_2 + \dots$.
• Contraintes : Inégalités ou égalités linéaires limitant la solution, par ex. $a_1X_1 + a_2X_2 \leq b$.
• Solution réalisable : Ensemble des points satisfaisant toutes les contraintes du PL.
• Solution optimale : Solution réalisable pour laquelle la fonction objectif atteint sa valeur maximale ou minimale.
• Demi-plan : Région du plan délimitée par une droite, correspondant à une contrainte.
• Points extrêmes : Sommets ou intersections des contraintes, souvent candidats à la solution optimale.

📝 Points essentiels

• La résolution graphique d’un PL à deux variables consiste à tracer les contraintes sous forme de demi-plans et à identifier leur intersection, qui représente l’ensemble des solutions réalisables.
• La région admissible est l’intersection de tous les demi-plans correspondant aux contraintes.
• La fonction objectif est représentée par une famille de droites parallèles ; la solution optimale se trouve à l’un des points extrêmes de la région admissible.
• La méthode graphique permet de déterminer la solution optimale en traçant la famille de droites de la fonction objectif et en repérant la dernière intersection dans la région admissible.
• La solution optimale est souvent un point extrême, c’est-à-dire l’intersection de deux contraintes.
• La résolution par énumération consiste à calculer la valeur de la fonction objectif en chaque point extrême pour choisir la meilleure.

💡 À retenir

La modélisation d’un programme linéaire repose sur la représentation graphique des contraintes et de la fonction objectif, où la solution optimale se situe généralement à un point extrême de la région admissible. La méthode graphique est efficace pour deux variables, permettant une visualisation claire du problème et de sa solution.

📖 2. Système d’axes

🔑 Notions clés & Définitions

• Système d’axes : Dispositif graphique permettant de représenter visuellement les contraintes et la région des solutions possibles d’un programme linéaire à deux variables.
• Région des solutions possibles : Zone du plan délimitée par les contraintes où toutes les solutions réalisables résident.
• Demi-plan : Partie du plan délimitée par une droite, correspondant à l’ensemble des points vérifiant une contrainte (inégalité).
• Solution réalisable : Point appartenant à l’intersection de tous les demi-plans correspondant aux contraintes du problème.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif.
• Points extrêmes (ou sommets) : Intersections de deux contraintes, souvent candidats à la solution optimale dans un problème linéaire.

📝 Points essentiels

• Le choix du système d’axes doit faciliter la lecture et la représentation graphique des contraintes.
• La région des solutions possibles est limitée au cadran positif (non-négativité des variables).
• La représentation graphique des contraintes se fait en traçant leurs droites d’égalité, puis en déterminant les demi-plans vérifiant les inégalités.
• La solution réalisable correspond à l’intersection de tous les demi-plans liés aux contraintes.
• La fonction objectif est représentée par une famille de droites parallèles ; la solution optimale est celle qui touche la dernière droite dans la direction d’optimisation.
• La résolution graphique consiste à repérer l’intersection des contraintes qui maximise ou minimise la fonction objectif.
• La recherche de la solution optimale peut aussi se faire par énumération des points extrêmes, souvent suffisant dans un problème à deux variables.
• La méthode graphique est limitée à deux variables, mais efficace pour visualiser et comprendre le problème.

💡 À retenir

Le système d’axes est un outil graphique essentiel pour visualiser et résoudre graphiquement un programme linéaire à deux variables, en identifiant la région réalisable et la solution optimale par intersection de contraintes et positionnement de la fonction objectif.

📖 3. Représentation contraintes

🔑 Notions clés & Définitions

• Solution réalisable : Point du plan qui satisfait toutes les contraintes du programme linéaire.
• Solution non réalisable : Point qui ne satisfait pas une ou plusieurs contraintes.
• Demi-plan : Région du plan délimitée par une droite, correspondant à l’ensemble des solutions vérifiant une contrainte.
• Représentation graphique des contraintes : Méthode consistant à tracer les demi-plans correspondant à chaque contrainte pour déterminer l’intersection, qui représente l’ensemble des solutions réalisables.
• Région des solutions possibles : Intersection de tous les demi-plans des contraintes, généralement limitée au cadran positif en cas de non-négativité.
• Solution de base : Point d’intersection de deux contraintes (droites) qui peut être candidate à la solution optimale.

📝 Points essentiels

• La représentation graphique des contraintes permet de visualiser l’ensemble des solutions réalisables en traçant chaque contrainte sous forme d’une droite ou demi-plan.
• La région des solutions possibles est l’intersection de tous ces demi-plans, limitée au cadran positif si les variables sont non négatives.
• La solution optimale se trouve généralement à un point extrême (intersection de contraintes) du polygone formé par la région réalisable.
• La vérification des contraintes se fait en choisissant un point test dans le demi-plan (ex : (0,0)) pour déterminer si ce demi-plan est celui qui satisfait la contrainte.
• La fonction objectif est représentée par des droites parallèles ; la valeur optimale correspond à la dernière droite tangentant la région réalisable dans le sens d’augmentation (maximisation) ou de diminution (minimisation).

💡 À retenir

La résolution graphique d’un programme linéaire consiste à tracer les contraintes pour délimiter la région réalisable, puis à identifier la solution optimale à un point extrême de cette région, en utilisant la représentation des droites de la fonction objectif.

📖 4. Solutions réalisables

🔑 Notions clés & Définitions

• Solution réalisable : Point du plan qui satisfait toutes les contraintes du programme linéaire, c’est-à-dire appartient à l’intersection de tous les demi-plans définis par ces contraintes.
• Solution non réalisable : Point qui ne vérifie pas au moins une contrainte, donc ne fait pas partie de l’ensemble des solutions possibles.
• Demi-plan : Région du plan délimitée par une droite correspondant à une contrainte, contenant tous les points vérifiant cette contrainte.
• Solution de base : Solution extrême du problème, généralement située à l’intersection de deux contraintes (droites) dans le plan.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif, située à l’intersection de la région réalisable avec la droite représentant la valeur optimale de la fonction objectif.

📝 Points essentiels

• La résolution graphique d’un programme linéaire à deux variables consiste à représenter graphiquement les contraintes sous forme de demi-plans.
• La région des solutions possibles (ou solutions réalisables) est l’intersection de tous ces demi-plans.
• La solution optimale se trouve généralement à un point extrême (intersection de contraintes), correspondant à une solution de base.
• La méthode graphique permet d’identifier la solution optimale en traçant la famille de droites parallèles à la fonction objectif et en repérant la plus grande valeur atteinte dans la région réalisable.
• La recherche de solutions de base consiste à examiner les points d’intersection des contraintes pour déterminer la meilleure valeur de la fonction objectif.

💡 À retenir

La résolution graphique d’un programme linéaire consiste à identifier la région des solutions réalisables, puis à localiser la solution optimale à l’intersection des contraintes, souvent un point extrême.

📖 5. Fonction objectif

🔑 Notions clés & Définitions

• Fonction objectif : Fonction mathématique à optimiser (maximiser ou minimiser) dans un programme linéaire, généralement notée Z ou f(x).
• Valeur optimale : La valeur maximale ou minimale que la fonction objectif peut atteindre en respectant toutes les contraintes.
• Droite de niveau : Ensemble des points du plan où la fonction objectif prend une valeur constante (par exemple, Z = c). Ces droites sont parallèles pour une fonction linéaire.
• Solution réalisable : Point ou ensemble de points dans l’espace de décision qui satisfont toutes les contraintes du problème.
• Solution optimale : Solution réalisable pour laquelle la valeur de la fonction objectif est la meilleure (maximale ou minimale).

📝 Points essentiels

• La fonction objectif est représentée graphiquement par une famille de droites parallèles, dont l’orientation dépend du type d’optimisation (maximisation ou minimisation).
• La recherche de la solution optimale consiste à déplacer ces droites dans le plan jusqu’à toucher la région faisable à la valeur la plus favorable.
• La solution optimale se trouve généralement à un point extrême (intersection de contraintes) dans le cas d’un programme linéaire.
• La méthode graphique permet de visualiser l’ensemble des solutions réalisables et d’identifier la solution optimale en traçant les droites de niveau.
• La solution optimale peut être unique, multiple (sur un segment) ou non bornée (illimitée).

💡 À retenir

La fonction objectif est une droite de niveau dont la position relative à la région faisable détermine la solution optimale, souvent située à un point extrême du polytope défini par les contraintes.

📖 6. Recherche solution optimale

🔑 Notions clés & Définitions

• Programme linéaire (PL) : Modèle mathématique d’optimisation où la fonction objectif et les contraintes sont linéaires.
• Solution réalisable : Point dans l’espace des variables qui satisfait toutes les contraintes du PL.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif.
• Demi-plan : Région du plan délimitée par une droite représentant une contrainte linéaire, contenant toutes les solutions vérifiant cette contrainte.
• Point extrême : Intersection de plusieurs contraintes, souvent candidate à la solution optimale dans un PL.
• Solution de base : Solution correspondant à l’intersection de contraintes (points extrêmes), souvent solution optimale dans la résolution graphique.

📝 Points essentiels

• La résolution graphique d’un PL à deux variables consiste à tracer l’ensemble des contraintes sous forme de demi-plans et à identifier leur intersection, qui constitue l’ensemble des solutions réalisables.
• La fonction objectif est représentée par une famille de droites parallèles ; la solution optimale se trouve à l’intersection de la famille de droites la plus éloignée dans le sens de maximisation ou minimisation.
• La recherche de la solution optimale se limite souvent aux points extrêmes, car dans un PL, la valeur optimale est atteinte en un point extrême ou sur un segment reliant deux points extrêmes.
• La méthode graphique permet d’identifier rapidement la solution optimale en traçant la famille des droites de la fonction objectif et en repérant la dernière à toucher l’ensemble réalisable.
• La solution optimale est souvent un point d’intersection de deux contraintes, appelé point extrême ou de base.

💡 À retenir

La solution optimale d’un programme linéaire à deux variables se trouve toujours à un point extrême de l’ensemble des solutions réalisables, ce qui permet de la déterminer par une analyse graphique simple et efficace.

📖 7. Méthode graphique

🔑 Notions clés & Définitions

• Programme linéaire (PL) : Modèle mathématique visant à optimiser (maximiser ou minimiser) une fonction objectif sous des contraintes linéaires.
• Solution réalisable : Point du plan qui satisfait toutes les contraintes du PL.
• Solution de base : Solution extrême correspondant à l’intersection de contraintes (droites ou plans).
• Région des solutions possibles : Zone du plan où toutes les contraintes sont respectées, généralement délimitée par des demi-plans.
• Représentation graphique : Méthode visuelle pour résoudre un PL à deux variables en traçant contraintes, solutions réalisables, et fonction objectif.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif, localisée à la frontière de la région réalisable.

📝 Points essentiels

• La méthode graphique est limitée aux PL à deux variables de décision, voire trois si représentées en 3D.
• La représentation commence par le choix d’un système d’axes adapté, en tenant compte de la non-négativité des variables.
• Les contraintes sont représentées par des droites (ou plans) ; l’ensemble des solutions réalisables est l’intersection des demi-plans correspondant à chaque contrainte.
• La fonction objectif est représentée par des droites parallèles ; la solution optimale se trouve au point d’intersection de la région réalisable avec la droite de valeur maximale ou minimale.
• La recherche de la solution optimale consiste à déplacer la droite de la fonction objectif jusqu’à toucher la dernière position dans la région réalisable.
• La méthode d’énumération consiste à examiner les points extrêmes (intersections) des contraintes pour déterminer la solution optimale.

💡 À retenir

La méthode graphique permet de visualiser et de résoudre efficacement un programme linéaire à deux variables en identifiant la région réalisable, puis en localisant la solution optimale sur la frontière de cette région.

📖 8. Solutions extrêmes

🔑 Notions clés & Définitions

• Solution extrême : Point d'intersection de deux ou plusieurs contraintes dans un problème de programmation linéaire, représentant une solution potentielle optimale.
• Solution réalisable : Point dans l'espace des solutions qui vérifie toutes les contraintes du problème.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif.
• Point d’intersection (ou sommet) : Point où deux contraintes se croisent, souvent point candidat pour la solution optimale.
• Solution dégénérée : Situation où plusieurs contraintes se rencontrent en un même point, pouvant compliquer la résolution.

📝 Points essentiels

• La résolution graphique d’un programme linéaire à deux variables consiste à représenter graphiquement la région des solutions possibles (intersection des demi-plans).
• La région des solutions possibles est limitée par les contraintes et doit respecter la non-négativité des variables.
• La solution optimale se trouve généralement à un point extrême (sommet) de la région admissible, où la fonction objectif atteint sa valeur maximale ou minimale.
• La méthode consiste à tracer toutes les contraintes, identifier la région admissible, puis évaluer la fonction objectif en ses sommets.
• En cas de solutions multiples, celles-ci correspondent à une ligne ou une surface de solutions optimales.
• La solution dégénérée survient lorsque plusieurs contraintes se rencontrent en un même point, ce qui peut rendre la résolution plus complexe.

💡 À retenir

La méthode graphique permet d’identifier la solution optimale en analysant les points extrêmes de la région admissible, en exploitant la propriété que la solution optimale d’un programme linéaire se trouve toujours à un sommet de cette région.

📖 9. Problèmes spécifiques

🔑 Notions clés & Définitions

• Solution réalisable : Point ou ensemble de points qui satisfont toutes les contraintes du programme linéaire, représentés graphiquement par l'intersection des demi-plans correspondant à chaque contrainte.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif dans un problème de programmation linéaire.
• Solution de base : Solution extrême correspondant à l’intersection de deux contraintes (droites dans le cas graphique), souvent candidate à l’optimalité.
• Problème non borné : Situation où la valeur de la fonction objectif peut être indéfiniment améliorée (augmentée ou diminuée), sans atteindre de maximum ou minimum fini.
• Problème impossible : Cas où aucune solution ne satisfait toutes les contraintes simultanément, l’espace des solutions réalisables étant vide.
• Solution multiple : Cas où plusieurs solutions donnent la même valeur optimale, souvent représentées par un segment de solutions dans le graphique.
• Dégénérescence : Situation où un point extrême est le point d’intersection de plus de deux contraintes, pouvant compliquer la résolution.

📝 Points essentiels

• La résolution graphique d’un programme linéaire à deux variables consiste à tracer les contraintes sous forme d’inégalités, puis à déterminer la région d’intersection (solutions réalisables).
• La région des solutions possibles est limitée au cadran positif (variables non négatives).
• La solution optimale se trouve généralement à un point extrême de la région réalisable, souvent à l’intersection de deux contraintes.
• La méthode consiste à tracer toutes les contraintes, identifier la région réalisable, puis à tracer des droites parallèles à la fonction objectif pour localiser la valeur maximale ou minimale.
• En cas de solutions multiples, celles-ci se situent sur un segment ou une face de la région réalisable.
• La non-bornitude indique que la valeur de la fonction objectif peut croître indéfiniment dans une direction, rendant le problème non borné.
• L’impossibilité du problème se traduit par l’absence d’intersection de toutes les contraintes, donc aucune solution réalisable.

💡 À retenir

La résolution graphique d’un programme linéaire consiste à identifier la région des solutions réalisables, puis à localiser la solution extrême qui optimise la fonction objectif, en tenant compte des cas particuliers comme la non-bornitude, l’impossibilité ou la dégénérescence.

📖 10. Exemples d’application

🔑 Notions clés & Définitions

• Programme linéaire (PL) : Modèle mathématique visant à optimiser une fonction objectif sous contraintes linéaires.
• Solution réalisable : Point du plan vérifiant toutes les contraintes du PL.
• Solution optimale : Solution réalisable qui maximise ou minimise la fonction objectif.
• Représentation graphique : Méthode visuelle pour résoudre un PL à deux variables en traçant contraintes et fonction objectif.
• Demi-plan : Zone du plan délimitée par une contrainte linéaire, contenant ou non la solution optimale.
• Solution de base : Point d’intersection de contraintes (extrémités du polygone solution).

📝 Points essentiels

• La résolution graphique est limitée aux PL à deux variables, permettant une visualisation claire des contraintes et solutions.
• La région des solutions possibles est l’intersection des demi-plans correspondant à chaque contrainte.
• La solution optimale se trouve sur un point extrême (sommet) du polygone délimité par les contraintes.
• La méthode consiste à tracer toutes les contraintes, identifier la région réalisable, puis rechercher la droite de la fonction objectif la plus éloignée dans le sens de l’optimisation.
• La solution optimale correspond à l’intersection de deux contraintes ou à un sommet du polygone solution.
• La méthode par énumération consiste à calculer la valeur de la fonction objectif en chaque point extrême pour déterminer le maximum ou le minimum.

💡 À retenir

La résolution graphique d’un programme linéaire consiste à représenter les contraintes, identifier la région réalisable, puis localiser le point extrême qui optimise la fonction objectif. La solution optimale se trouve toujours en un sommet de cette région.

📊 Tableaux de Synthèse

Thème	Notions clés	Méthodes principales	Points importants
Modélisation PL	Fonction objectif, variables de décision, contraintes, région admissible	Représentation graphique, énumération des points extrêmes	Solution optimale à un point extrême, solution réalisable vérifiée par contraintes
Système d’axes	Région des solutions, demi-plans, points extrêmes, région réalisable	Tracé des contraintes, intersection des demi-plans, repérage de la région	Visualisation claire, région limitée au cadran positif, solution optimale à un sommet
Représentation contraintes	Demi-plans, solutions réalisables/non réalisables, points de base	Traçage des contraintes, délimitation de la région réalisable	Solution optimale à un point extrême, vérification par point test
Solutions réalisables	Intersection de demi-plans, solutions de base, région réalisable	Représentation graphique, recherche de points extrêmes	Solution optimale souvent à un sommet, région délimitée par contraintes

⚠️ Pièges & Confusions Fréquentes

1. Confondre solution réalisable et solution optimale : la première vérifie toutes les contraintes, la seconde maximise/minimise la fonction objectif.
2. Négliger la non-négativité des variables dans la représentation graphique, ce qui peut conduire à des solutions hors du domaine.
3. Confusion entre demi-plan et région réalisable : la région est l’intersection de tous les demi-plans.
4. Oublier que la solution optimale se trouve généralement à un sommet (point extrême), sauf cas particulier.
5. Traiter la fonction objectif comme une contrainte, alors qu’elle est représentée par une famille de droites parallèles.
6. Erreur dans le tracé des contraintes : inverser le sens du demi-plan ou mal représenter la contrainte.
7. Utiliser la méthode graphique pour plus de deux variables, ce qui est incorrect ou peu fiable.

✅ Checklist Examen

• Vérifier la définition d’un programme linéaire et ses composants.
• Savoir représenter graphiquement une contrainte sous forme de demi-plan.
• Identifier la région réalisable à partir de l’intersection des demi-plans.
• Repérer les points extrêmes de la région réalisable.
• Expliquer pourquoi la solution optimale se trouve à un sommet.
• Décrire la méthode graphique pour résoudre un PL à deux variables.
• Reconnaître la représentation de la fonction objectif par une famille de droites parallèles.
• Comprendre la différence entre solution réalisable, solution optimale, et solution de base.
• Identifier les pièges liés à la non-négativité des variables.
• Savoir comment vérifier si un point appartient à la région réalisable.
• Expliquer le rôle des points extrêmes dans la recherche de la solution optimale.
• Vérifier la cohérence entre la région délimitée par les contraintes et la position de la fonction objectif.
• S’assurer que la représentation graphique respecte le cadran positif si variables non négatives.