Programmation linéaire : Exercices modélisation et optimisation

Modélisation et Résolution Graphique (Ex 1 à 3)

Exercice 1 - Modélisation Variables : x₁ (nombre de lots n°1), x₂ (nombre de lots n°2). Maximiser Z = 6x₁ + 10x₂ Sous les contraintes : x₁ + x₂ ≤ 20 (guides) 10x₁ + 50x₂ ≤ 500 (cartes) x₁, x₂ ≥ 0. Forme standard : x₁ + x₂ + e₁ = 20 et 10x₁ + 50x₂ + e₂ = 500 (avec variables d'écart e₁, e₂ ≥ 0).

Exercice 2 - Mélange Variables en proportions de la tonne : x₁ (orge), x₂ (arachides), x₃ (sésame). Minimiser le coût C = 25x₁ + 41x₂ + 39x₃ Sous les contraintes : x₁ + x₂ + x₃ = 1 (composition totale) 0,12x₁ + 0,52x₂ + 0,42x₃ ≥ 0,22 (protéines) 0,02x₁ + 0,02x₂ + 0,10x₃ ≥ 0,036 (graisses) x₁, x₂, x₃ ≥ 0.

Exercice 3 - Espace non borné Le domaine des solutions réalisables est ouvert. La fonction économique Z = x₂ - x₁ n'admet pas de maximum fini car la variable x₂ peut croître indéfiniment sans violer les contraintes.

Simplexe et Bases (Ex 4 à 8)

Exercice 4 : La matrice de base B = (A₃, A₄) donne un déterminant non nul. Elle est réalisable si B⁻¹b ≥ 0. Exercice 5 : Le premier programme (P L) possède une solution initiale évidente car le vecteur b est positif pour des contraintes "≤" (les variables d'écart forment la base). Le second nécessite des variables artificielles (contraintes "≥"). Exercice 6 : En substituant X = (0, 0, 230, 200, 0, 420) dans les contraintes, toutes les égalités sont satisfaites (ex: 230 + 200 = 430). C'est une solution de base réalisable. Exercice 7 : La méthode des deux phases exige d'abord de minimiser la somme des variables artificielles (Phase 1) avant d'optimiser la fonction Z d'origine (Phase 2). Exercice 8 : L'introduction du paramètre λ modifie la pente de la fonction objectif Z. La solution optimale bascule d'un sommet à l'autre selon les valeurs critiques de λ.

Dualité (Ex 9 à 12)

Exercice 9 - Dual Pour le premier problème (Max Z) avec égalités, les variables duales y₁ et y₂ sont initialement de signe quelconque, mais contraintes par les variables du primal : Minimiser W = 60y₁ + 140y₂ Sous : 6y₁ + 2y₂ ≥ 15 ; 10y₁ + 10y₂ ≥ 40 ; 2y₁ + 6y₂ ≥ 12 ; y₁ ≥ 0 ; y₂ ≥ 0.

Exercice 10 : Le dual P2 s'écrit Max W = 8y₁ + 8y₂ + 47y₃. Les valeurs optimales des variables primales se lisent directement dans la ligne des coûts réduits du tableau optimal dual. Exercice 11 : Selon le théorème des écarts complémentaires, si une contrainte du primal n'est pas saturée (écart > 0) à l'optimum, la variable duale associée est strictement nulle. Exercice 12 : En posant x₃ = 0, le problème devient bidimensionnel. Il se résout graphiquement dans le plan (x₁, x₂) en évaluant Z sur les sommets du polygone des contraintes.

Méthode

Pour réussir efficacement ce type d'épreuve :

• Définition stricte : Identifiez toujours clairement les unités (quantités, pourcentages) avant d'écrire vos variables de décision.
• Standardisation : Ajoutez systématiquement des variables d'écart positives (+e) pour les inégalités "≤" et des variables d'écart négatives assorties de variables artificielles (-e +a) pour les "≥".
• Règles de dualité : Rappelez-vous qu'une contrainte d'égalité dans le programme primal engendre une variable de signe quelconque dans le programme dual.

Quel concept spécifique (modélisation, méthode du simplexe ou théorie de la dualité) souhaitez-vous approfondir en priorité pour vos révisions ?