Cours Programmation linéaire et Optimisation en PDF (Avancé)

Programmation linéaire et Optimisation : Ce qu'il faut savoir. La programmation linéaire traite la maximisation ou la minimisation d'une fonction linéaire soumise à des contraintes linéaires (égalités, inégalités) et aux contraintes de non-négativité. Elle fournit un formalisme standard — forme canonique ou forme d'écart — pour traduire des problèmes industriels (production, transport, planification) en systèmes linéaires exploitables algorithmiquement. Discipline centrale de la Recherche Opérationnelle, le document propose des démonstrations détaillées et des exemples numériques pour maîtriser la méthode du simplexe, la dualité et l'analyse de sensibilité.

Prérequis nécessaires

• Algèbre linéaire (matrices, déterminants, systèmes d'équations linéaires)
• Calcul différentiel de base (dérivées, gradients pour l'interprétation locale)
• Géométrie euclidienne (vecteurs, plans, polytopes en dimension 2 et 3)

Objectifs pédagogiques

• Modélisation — Construire une formulation valide à partir d'un énoncé : choix des variables, fonction objectif et contraintes opérationnelles.
• Résolution graphique et économique — Résoudre en dimension 2, identifier sommets du polytpe et interpréter prix marginaux (Shadow Price).
• Méthode du simplexe — Variables d'écart, choix d'entrée/sortie et opérations de pivot pour obtenir une solution de base réalisable et optimale.
• Dualité — Formulation du dual et vérification de l'égalité valeur-primal/valeur-dual comme certificat d'optimalité.
• Analyse de sensibilité — Bornes de variation des paramètres (RHS, coûts) et interprétation des intervalles de validité de la base.

Résolution graphique

La résolution graphique se fonde sur l'intersection de demi-plans en dimension 2 et l'examen des sommets admissibles du polytpe. L'approche identifie le sommet optimal en comparant les valeurs de la fonction objectif aux sommets et relie ces résultats aux variables duales pour l'interprétation économique.

Méthode des droites d'isovaleur : tracer plusieurs droites d'isovaleur (lignes de niveau) de la fonction objectif, puis déplacer la droite dans la direction d'amélioration jusqu'à rencontrer le dernier point admissible du polytpe. Ce contact au sommet fournit la solution optimale graphique et permet d'estimer visuellement les prix marginaux associés aux contraintes actives.

📑 Sommaire du document

1. Chapitre 1 — Un problème d'optimisation linéaire en dimension 2
2. Chapitre 2 — Un problème d'optimisation linéaire en dimension supérieure
3. Chapitre 3 — Méthode du simplexe : un aperçu par l'exemple (incluant l'algorithme de transport optimal)

Logiciels d'optimisation abordés

Le document presents des exemples d'utilisation et des recommandations d'intégration pour des outils courants, en précisant la formulation compatible, l'extraction des solutions et l'interprétation des rapports de sensibilité.

• Solver (Excel) — Intégré à Excel, adapté aux modèles de petite à moyenne taille ; facilité d'entrée de modèle et visualisation directe des résultats dans un tableur. Rapports de sensibilité disponibles selon la version.
• Xpress‑MP — Solveur professionnel conçu pour des modèles à grande échelle ; performances supérieures pour des instances industrielles et options avancées pour l'extraction détaillée des variables et le diagnostic numérique.
• Comparaison pratique : Solver favorise la rapidité d'expérimentation et l'intégration avec des feuilles de calcul, Xpress‑MP privilégie la robustesse numérique et la montée en charge. Les deux permettent l'obtention de certificats d'optimalité et de rapports utiles pour l'analyse post‑optimale.

Pourquoi choisir ce cours ?

Approche progressive : exemples graphiques en dimension 2 puis montée en complexité par réductions algébriques et simplexe. La démarche privilégie des calculs explicites (tableaux, pivots de Gauss, expression de la fonction objectif en variables non basiques) pour comprendre les fondements avant l'utilisation d'un solveur. Rédigé par Didier Smets, le texte suit une méthode rigoureuse et reproductible ; exercices d'application inclus pour ancrer les savoir‑faire.

Modélisation et méthodologie

La traduction d'un énoncé métier en modèle mathématique suit une méthodologie reproductible : identification des paramètres pertinents, définition claire des variables et de la fonction objectif, et énoncé exhaustif des contraintes opérationnelles. Mention explicite des contraintes de non-négativité (contraintes de positivité) pour garantir l'interprétation physique des variables.

Étapes concrètes : 1) extraire les ressources et capacités pertinentes, 2) définir les variables avec leurs domaines, 3) formuler la fonction objectif en unités cohérentes, 4) convertir les contraintes opérationnelles en contraintes linéaires, 5) vérifier la cohérence dimensionnelle et l'hypothèse de linéarité. Des checklists et des cas applicatifs (production, transport, mélange) accompagnent l'implémentation et la validation avant résolution numérique.

Exemple de modélisation mathématique

Maximiser z = 16000 x + 10000 y
s.c.
  3 x + 2 y ≤ 600
  x + 4 y ≤ 480
  x, y ≥ 0

Du problème Primal au problème Dual

La construction du dual s'obtient en associant une variable duale à chaque contrainte du primal et en échangeant le rôle des coefficients de la matrice et des membres de droite selon les règles standard. L'analyse duale fournit des prix ombre interprétables économiquement et sert de test d'optimalité : si les solutions primal et dual satisfont l'égalité des valeurs objectifs, la solution est optimale. La dualité facilite également l'analyse de sensibilité et l'obtention de bornes théoriques pour des variantes du modèle.

Interprétation géométrique des solutions optimales

L'interprétation géométrique s'appuie sur la représentation du domaine admissible comme un polytpe convexe ; les solutions basiques correspondent aux sommets de ce polytpe. En examinant les directions admissibles au sommet optimal, on identifie les contraintes actives et on calcule les prix marginaux associés. Les concepts géométriques facilitent la compréhension des scénarios "what‑if" et l'impact des variations de paramètres sur la base optimale.

Exercices corrigés de programmation linéaire

Le PDF contient une série d'exercices corrigés : problèmes de transport équilibré et déséquilibré, production multi‑produits avec capacités limitées, modèles de mélange et exercices de réduction de dimension. Chaque exercice présente l'énoncé métier, la modélisation complète, la résolution pas à pas et l'interprétation opérationnelle des résultats.

• Exemples de transport avec étude manuelle et vérification duale.
• Cas de production multi‑produits avec contraintes de capacité et coûts variables.
• Problèmes de mélange illustrant les variables libres et les bornes admissibles.

❓ Foire Aux Questions (FAQ)

Comment interprète-t-on les prix marginaux obtenus dans les exemples ?

Les prix marginaux correspondent aux variables duales et mesurent la variation de la valeur objectif par unité supplémentaire de ressource. Ils sont calculés graphiquement ou via la résolution du dual et s'interprètent comme le gain marginal associé à une augmentation de capacité.

Quelles conditions indiquent l'optimalité dans une solution simplexe présentée ici ?

Une solution simplexe est optimale lorsque, après avoir exprimé la fonction objectif en fonction des variables non basiques, tous les coefficients des variables non basiques ne permettent aucune amélioration admissible (pour un problème de maximisation : coefficients ≤ 0). Dans ce cas la base courante est optimale et un certificat d'optimalité peut être construit à partir des valeurs duales.