Lernzettel: Optimisation linéaire et dualité

📋 Plan du Cours

1. Programme linéaire primal
2. Programme dual
3. Résolution dual et primal
4. Interprétation résultats
5. Optimisation colorants
6. Méthode du simplexe
7. Analyse sensibilité prix
8. Vente matière à un concurrent

📖 1. Programme linéaire primal

🔑 Notions clés & Définitions

• Programme linéaire (PL) : Modèle mathématique d'optimisation visant à maximiser ou minimiser une fonction objectif linéaire, sous des contraintes linéaires.
  Exemple : Maximiser le profit ou minimiser le coût.

• Fonction objectif : Fonction à optimiser (maximiser ou minimiser), généralement une somme pondérée des variables de décision.
  Exemple : Z = c₁x₁ + c₂x₂ + ... + cₙxₙ.

• Contraintes : Équations ou inéquations linéaires représentant les limitations ou conditions du problème.
  Exemple : 36x₁ + 45x₂ ≥ 13.

• Variables de décision : Quantités à déterminer pour optimiser la fonction objectif, généralement contraintes à être positives ou nulles (x ≥ 0).
  Exemple : Quantités de produits à produire.

• Solution réalisable : Ensemble des valeurs des variables qui satisfont toutes les contraintes.
  Exemple : Un point dans l'espace des solutions respectant toutes les inégalités.

• Solution optimale : La solution réalisable qui optimise la fonction objectif (max ou min).
  Exemple : La production qui maximise le bénéfice.

📝 Points essentiels

• La formulation du problème doit respecter la structure : fonction objectif + contraintes linéaires + non-négativité des variables.
• La résolution peut se faire par la méthode du simplexe, qui explore les sommets du polytope de solutions réalisables.
• Le problème primal a un problème dual associé, dont la solution donne des informations sur la valeur marginale des ressources.
• La dualité permet d'interpréter la valeur du dual comme le prix ou la valeur marginale des contraintes.
• La solution optimale du primal et du dual sont reliées par le théorème du dual, qui garantit leur égalité en valeur optimale.

💡 À retenir

Le programme linéaire primal consiste à optimiser une fonction linéaire sous contraintes linéaires, et sa résolution permet d'obtenir la meilleure solution dans un espace défini par ces contraintes. La dualité offre une interprétation économique ou stratégique précieuse.

📖 2. Programme dual

🔑 Notions clés & Définitions

• Programme primal : Modèle mathématique d'optimisation linéaire visant à maximiser ou minimiser une fonction objectif sous contraintes.
• Programme dual : Modèle associé au primal, construit à partir des contraintes et de la fonction objectif du primal, permettant d'analyser la sensibilité et la valeur des ressources.
• Variables duales : Variables associées aux contraintes du primal, représentant la valeur marginale ou le prix shadow de chaque ressource.
• Théorème de dualité : En optimisation linéaire, affirme que le minimum du primal est égal au maximum du dual, sous certaines conditions de faisabilité.
• Valeur shadow : La variation du coût ou du bénéfice total lorsque la ressource disponible est modifiée d'une unité, donnée par la variable duale.
• Complémentarité : Condition où, pour chaque contrainte, soit la contrainte est saturée, soit la variable duale associée est nulle.

📝 Points essentiels

• La formulation du programme dual permet d’évaluer la valeur des ressources et d’optimiser la gestion des contraintes dans le primal.
• La résolution du dual fournit des prix shadow, indicateurs cruciaux pour la prise de décision stratégique.
• La relation entre primal et dual est fondamentale : si le primal est optimal, le dual l’est aussi, et leurs solutions sont liées par le théorème de dualité forte.
• La sensibilité à un paramètre (ex : prix de vente, coûts) est analysée via la solution du dual, notamment par la valeur shadow.
• La compréhension de la complémentarité permet d’identifier quelles contraintes sont actives ou inactives à l’optimum.

💡 À retenir

Le programme dual est un outil puissant pour interpréter la valeur des ressources et optimiser la production, en complément du programme primal, grâce à la dualité forte et à l’analyse de sensibilité.

📖 3. Résolution dual et primal

🔑 Notions clés & Définitions

• Programme primal : Le problème d’optimisation initial, généralement une minimisation ou maximisation sous contraintes linéaires. Exemple : minimiser Z = cᵗx sous Ax ≥ b, x ≥ 0.

• Programme dual : Le problème associé au primal, construit en échangeant les rôles des contraintes et variables. Si le primal est une minimisation, le dual sera une maximisation, et vice versa. Exemple : maximiser bᵗy sous Aᵗy ≤ c, y ≥ 0.

• Relation primal-dual : La valeur optimale du primal est égale à celle du dual (théorème de la dualité forte), sous certaines conditions de faisabilité.

• Solution primal : Ensemble des valeurs de variables qui optimisent le problème primal.

• Solution dual : Ensemble des valeurs de variables duales qui optimisent le problème dual.

• Complémentarité : Condition selon laquelle, à l’optimum, le produit de chaque variable primal par la contrainte duale correspondante est nul, permettant d’identifier la solution optimale.

📝 Points essentiels

• La résolution du problème primal peut être facilitée par la résolution du dual, surtout si ce dernier est plus simple ou plus petit en nombre de contraintes ou variables.

• La formulation du dual se construit en transposant la matrice des contraintes et en échangeant les rôles des vecteurs de coûts et de ressources.

• La dualité forte garantit que, sous faisabilité, la valeur optimale du primal est égale à celle du dual, ce qui permet de vérifier la cohérence des solutions.

• La méthode du simplexe peut s'appliquer aussi bien au primal qu’au dual, et leur convergence est liée par la théorie de la dualité.

• L’analyse de sensibilité permet d’étudier l’impact des variations des coefficients (coût, ressources) sur la solution optimale.

💡 À retenir

La résolution duale d’un programme linéaire offre une perspective complémentaire et souvent plus simple pour analyser et résoudre le problème, tout en garantissant l’égalité des valeurs optimales grâce à la dualité forte.

📖 4. Interprétation résultats

🔑 Notions clés & Définitions

• Solution optimale : La valeur de (x₁, x₂, ...) qui maximise ou minimise la fonction objectif tout en respectant les contraintes du programme linéaire.
• Programme dual : Un problème associé au problème primal, construit à partir de ses contraintes et de sa fonction objectif, permettant d’obtenir des informations complémentaires sur la solution.
• Interprétation économique : Analyse des résultats pour comprendre la signification des variables et des coûts ou bénéfices dans le contexte du problème.
• Analyse de sensibilité : Étude de l’impact des variations des coefficients (par exemple, prix de vente ou coûts) sur la solution optimale, pour évaluer la stabilité du résultat.
• Valeur duale (ou prix dual) : La variation de la valeur optimale du problème primal en réponse à une unité supplémentaire d’une contrainte, indiquant la valeur marginale de cette contrainte.

📝 Points essentiels

• La résolution d’un programme linéaire permet d’identifier la combinaison optimale de variables pour atteindre un objectif (maximisation ou minimisation).
• La solution du problème dual fournit des informations sur la valeur marginale des ressources ou contraintes, facilitant la prise de décision.
• La relation entre le problème primal et dual est fondamentale : la valeur optimale du primal est égale à celle du dual (théorème de dualité forte).
• L’analyse de sensibilité permet d’évaluer la robustesse de la solution face à des modifications des coefficients, notamment les prix ou coûts.
• Lorsqu’une contrainte devient non-active (non saturée), la valeur duale associée est nulle, indiquant que cette contrainte ne limite pas la solution optimale.

💡 À retenir

L’interprétation des résultats en programmation linéaire repose sur la compréhension de la solution optimale, des valeurs duales et de leur sens économique, ainsi que sur l’analyse de sensibilité pour assurer la stabilité des décisions.

📖 5. Optimisation colorants

🔑 Notions clés & Définitions

Notion	Définition	Points essentiels
Programme linéaire (PL)	Modèle mathématique d'optimisation visant à maximiser ou minimiser une fonction objectif sous contraintes linéaires.	Permet de modéliser des problèmes de production, de coûts ou de bénéfices.
Dualité	Concept selon lequel à chaque programme linéaire primal correspond un programme dual dont la solution donne des informations complémentaires.	La solution du dual donne des bornes sur la solution du primal et permet une analyse de sensibilité.
Méthode du simplexe	Algorithme itératif pour résoudre efficacement un programme linéaire.	Utilisée pour déterminer la solution optimale en déplaçant d’un sommet à un autre du polytope de solutions.
Analyse de sensibilité	Étude de l’impact des variations des coefficients (coût, prix, ressources) sur la solution optimale.	Permet d’évaluer la stabilité de la solution face aux changements de paramètres.
Capacité de ressources	Quantité maximale disponible d’une matière ou ressource dans un problème d’optimisation.	Limite la production ou la consommation dans le modèle.

📝 Points essentiels

• La formulation du problème doit respecter la nature des variables (souvent ≥ 0) et les contraintes linéaires.
• La résolution du programme primal peut être complétée par la résolution du programme dual, qui fournit des bornes et des informations sur la valeur marginale des ressources.
• La méthode du simplexe optimise la fonction objectif en se déplaçant d’un sommet à un autre du polytope défini par les contraintes.
• L’analyse de sensibilité permet d’anticiper l’effet d’une variation des prix ou des ressources sur la solution optimale.
• La dualité offre une interprétation économique : les variables duales représentent la valeur marginale des ressources.

💡 À retenir

L’optimisation colorants repose sur la modélisation par programme linéaire, dont la résolution via la méthode du simplexe et l’analyse de sensibilité permettent d’obtenir une solution optimale et d’évaluer sa stabilité face aux variations des paramètres.

📖 6. Méthode du simplexe

🔑 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. Exemple : maximiser ou minimiser une fonction linéaire sous des contraintes linéaires.

• Méthode du simplexe : Algorithme itératif permettant de résoudre efficacement les programmes linéaires en trouvant la solution optimale en se déplaçant d’un sommet à un autre du polytope défini par les contraintes.

• Solution de base : Ensemble de variables (de base) qui satisfont les contraintes avec d’autres variables égales à zéro. La solution associée est appelée solution de base.

• Pivot : Opération de changement de variables dans la méthode du simplexe, permettant de passer d’une solution de base à une autre plus favorable.

• Fonction objectif : Fonction à optimiser (maximiser ou minimiser) dans un programme linéaire, généralement notée Z.

• Solution optimale : La solution qui donne la meilleure valeur (maximale ou minimale) de la fonction objectif tout en respectant toutes les contraintes.

📝 Points essentiels

• La méthode du simplexe commence par une solution de base initiale, souvent la solution de référence où toutes les variables non basiques sont nulles.

• À chaque étape, on choisit une variable entrante (améliorant la valeur de Z) et une variable sortante pour effectuer un pivot, afin d’améliorer la solution.

• La méthode s’arrête lorsque aucune variable entrante ne peut améliorer la valeur de la fonction objectif, indiquant que la solution optimale est atteinte.

• La résolution du problème dual permet d’obtenir des bornes sur la valeur de la fonction objectif du problème primal, et vice versa.

• La méthode du simplexe est efficace pour des problèmes de grande dimension, mais nécessite une bonne gestion des pivots pour éviter les cycles.

💡 À retenir

La méthode du simplexe est un algorithme puissant pour résoudre les programmes linéaires en exploitant la structure géométrique du polytope défini par les contraintes, en se déplaçant de sommets en sommets jusqu’à atteindre la solution optimale.

📖 7. Analyse sensibilité prix

🔑 Notions clés & Définitions

Notion	Définition	Points essentiels
Analyse de sensibilité	Étude de l’impact des variations des paramètres (notamment prix) sur la solution optimale d’un problème de programmation linéaire.	Permet d’évaluer la stabilité de la solution face aux changements de prix ou de coefficients.
Prix dual	Coefficient associé à une contrainte dans le programme dual, représentant la valeur marginale ou le coût d’une unité supplémentaire de ressource.	Indicateur de la sensibilité du coût ou du bénéfice à une variation de la contrainte.
Intervalle de variation	Plage dans laquelle un paramètre (prix ou coefficient) peut varier sans changer la solution optimale.	Crucial pour déterminer la stabilité de la solution face aux fluctuations de prix.
Coefficient marginal	Variation du résultat optimal en réponse à une petite variation d’un paramètre (prix ou coefficient).	Permet de mesurer l’impact immédiat d’un changement sur la solution.
Solution optimale	Ensemble de valeurs de variables qui maximise ou minimise la fonction objectif tout en respectant les contraintes.	La solution reste valable tant que les paramètres restent dans leur intervalle de stabilité.

📝 Points essentiels

• La sensibilité prix permet d’évaluer la stabilité de la solution face aux variations de prix ou de coefficients dans le modèle.
• La méthode d’analyse consiste à déterminer l’intervalle de variation d’un paramètre (prix ou coefficient) pour lequel la solution optimale ne change pas.
• Le prix dual associé à une contrainte indique la valeur marginale de la ressource ou du paramètre concerné.
• La compréhension de l’impact des variations de prix est essentielle pour la prise de décision stratégique, notamment en fixation de prix ou en négociation commerciale.
• La solution duale fournit des informations complémentaires sur la valeur des contraintes et leur influence sur la solution optimale.

💡 À retenir

L’analyse de sensibilité prix permet d’anticiper l’effet des fluctuations de prix sur la solution optimale, en identifiant notamment les intervalles de stabilité et la valeur marginale des ressources.

📖 8. Vente matière à un concurrent

🔑 Notions clés & Définitions

Notion	Définition	Points essentiels
Vente matière à un concurrent	Opération commerciale consistant à céder une quantité de matière première ou de produit à un concurrent.	Peut influencer la stratégie de production, la rentabilité et la position sur le marché.
Programme linéaire	Modèle mathématique d’optimisation visant à maximiser ou minimiser une fonction objectif sous contraintes.	Utilisé pour planifier la production, la distribution ou la vente dans un contexte donné.
Dualité en programmation linéaire	Relation entre un problème primal et son problème dual, où la solution d’un donne des informations sur l’autre.	La solution duale permet d’analyser la sensibilité et le coût d’opportunité.
Analyse de sensibilité	Étude de l’impact des variations des paramètres (prix, coûts, contraintes) sur la solution optimale.	Aide à prendre des décisions stratégiques face à l’incertitude ou la négociation.
Méthode du simplexe	Algorithme permettant de résoudre efficacement les programmes linéaires.	Permet d’obtenir la solution optimale en parcourant les sommets du polytope défini par les contraintes.

📝 Points essentiels

• La vente matière à un concurrent doit être analysée en termes de coûts, bénéfices et impact stratégique.
• La résolution de programmes linéaires permet d’optimiser la quantité à vendre ou produire pour maximiser le profit.
• La dualité offre une compréhension approfondie des coûts d’opportunité et des limites de la capacité de production.
• L’analyse de sensibilité est cruciale pour ajuster la stratégie face aux fluctuations du marché ou des coûts.
• La négociation avec un concurrent peut impliquer la fixation d’un prix minimum basé sur le coût marginal ou la valeur stratégique de la matière.

💡 À retenir

La vente matière à un concurrent s’inscrit dans une démarche d’optimisation stratégique, où la modélisation par programme linéaire et l’analyse de sensibilité sont essentielles pour prendre des décisions éclairées.

📊 Tableaux de Synthèse

Programme linéaire primal	Programme dual
Max ou Min de Z = cᵗx	Max ou Min de W = bᵗy
Variables : x ≥ 0	Variables duales : y ≥ 0
Contraintes : Ax ≥ b ou ≤ b	Contraintes : Aᵗy ≤ c ou ≥ c
Solution réalisable : respect des contraintes	Solution duale : respect des inégalités duales
Théorème du dual : valeur optimale identique	La dualité forte garantit l’égalité des valeurs

Résolution primal vs dual	Interprétation des résultats
Résoudre le primal ou le dual selon la simplicité	La valeur duale indique la valeur marginale d’une contrainte
La solution optimale du primal = celle du dual	La solution fournit une interprétation économique ou stratégique
La méthode du simplexe s’applique aux deux	La sensibilité analyse l’impact des variations des coefficients

⚠️ Pièges & Confusions Fréquentes

1. Confondre la variable de décision avec la variable duale (ex : prix shadow).
2. Oublier que le programme dual est construit à partir du primal, en échangeant contraintes et variables.
3. Négliger la condition de non-négativité des variables duales dans le dual.
4. Confondre maximisation et minimisation dans la formulation primal et dual.
5. Interpréter à tort la valeur duale comme un coût ou une variable de décision.
6. Ignorer la complémentarité : une contrainte active a une variable duale non nulle, inactives ont variable duale nulle.
7. Se tromper dans la construction du problème dual (transposition de la matrice, échange des rôles).

✅ Checklist Examen

• Vérifier la formulation correcte du problème primal (fonction objectif + contraintes + non-négativité).
• Savoir construire le problème dual à partir du primal.
• Identifier les variables duales et leur interprétation.
• Appliquer la théorie de la dualité forte pour vérifier la cohérence des solutions.
• Analyser la complémentarité entre contraintes et variables duales.
• Interpréter la valeur duale dans un contexte économique ou stratégique.
• Résoudre un problème primal ou dual avec la méthode du simplexe.
• Effectuer une analyse de sensibilité sur les coefficients de la fonction objectif et des contraintes.
• Comprendre le lien entre solution optimale, valeur marginale et prix shadow.
• Vérifier la faisabilité et l’optimalité des solutions trouvées.
• Interpréter les résultats en termes de gestion des ressources ou de stratégie.
• Évaluer l’impact d’une modification de la disponibilité d’une contrainte.
• Vérifier la cohérence entre primal et dual en comparant leurs valeurs optimales.