Optimisation linéaire (2D)

PL à 2 variables : région réalisable, optimisation aux sommets

Exemple résolu — Optimisation linéaire (2D)

Maximiser	3x + 2y

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Une région admissible ne promet pas de réponse 🖖

La règle des sommets a un préalable qu'on oublie vite : encore faut-il qu'un optimum existe. Chargez le préréglage non borné — maximiser 2x + y sous x ≥ 0, y ≥ 0, x + y ≥ 2 — et la région admissible est parfaitement non vide, pourtant aucun sommet n'est le meilleur, car vous pouvez marcher vers le nord-est indéfiniment en vous améliorant. Cet outil rend donc l'un de trois verdicts et non un seul : optimal, non admissible ou non borné. Il atteint le troisième en testant l'existence d'une direction de récession améliorante, et non parce qu'il ne trouve pas de sommet. Passez ce même préréglage en minimisation et une réponse finie apparaît aussitôt en (0, 2). Admissibilité et résolubilité sont deux questions distinctes.

Les meilleures solutions se cachent aux sommets 🖖

En clair, vous jonglez avec des ressources limitées sous plusieurs règles à la fois, et chaque inégalité découpe une partie du plan. Là où toutes les règles se chevauchent se trouve la région réalisable, et chaque point à l'intérieur est un plan valide. Comme une fonction objectif linéaire s'améliore toujours dans une direction, la meilleure solution tombe sur un sommet où les contraintes se rencontrent. À retenir : pour optimiser, on ne teste jamais tous les points, seulement la poignée de sommets.

Quand un problème de régime a devancé le simplexe 🖖

En 1945, l'économiste George Stigler a cherché le régime le moins cher couvrant tous les besoins nutritionnels, un problème linéaire à 77 aliments. Faute d'algorithme, il a fait une estimation astucieuse et obtenu environ $39.93 par an (prix de 1939). Quand la méthode du simplexe de Dantzig l'a résolu exactement en 1947, le vrai minimum était $39.69 — l'estimation à la main de Stigler ne s'écartait que d'environ 24 cents par an. L'économie aride est ainsi devenue l'un des cas fondateurs de la programmation linéaire.

PROGRAMMATION LINÉAIRE — POURQUOI ON N’EXAMINE JAMAIS QUE LES SOMMETS

Dans quel cas de programmation linéaire êtes-vous ?

Tout programme linéaire pose la même question : jusqu’où pousser un objectif rectiligne à travers une région clôturée par des contraintes rectilignes ? Comme les deux sont droits, le meilleur point ne peut être qu’un sommet — d’où la méthode : énumérer les sommets et les comparer. Le cas dépend de ce que cette région enferme ou non l’objectif, et de ce que le sommet obtenu soit un nombre réellement utilisable.

Région bornée — l’optimum est sur un sommet z = 10 → (2, 2)

Le meilleur sommet est fractionnaire, et c’est un autre problème z = 24 → (8/3, 8/3)

Région non bornée, réponse bornée min z = 13

Pas d’optimum fini — et les sommets ne vous le diront pas z → ∞

Région bornée — l’optimum est sur un sommet

Ce que vous savez: Un objectif à maximiser et assez de contraintes ≤ pour refermer la région. L’ensemble réalisable est un polygone.

Ce qu’il faut vérifier: z = 10 → (2, 2)

Exemple résolu: Maximiser 3x + 2y sous x + y ≤ 4, x ≤ 2, y ≤ 3. Les sommets sont (0,0), (2,0), (2,2), (1,3), (0,3), et z = 10 en (2,2) les bat tous.

Ouvrir ce cas: Problème de régime

Région bornée — l’optimum est sur un sommet. La droite objectif glisse vers le haut et la droite jusqu’à ne plus toucher le polygone qu’en un seul sommet. Un objectif à maximiser et assez de contraintes ≤ pour refermer la région. L’ensemble réalisable est un polygone. — La droite objectif glisse vers le haut et la droite jusqu’à ne plus toucher le polygone qu’en un seul sommet.

Le meilleur sommet est fractionnaire, et c’est un autre problème

Ce que vous savez: Une région bornée à nouveau, mais le sommet retenu par l’objectif ne tombe pas sur des entiers.

Ce qu’il faut vérifier: z = 24 → (8/3, 8/3)

Exemple résolu: Maximiser 5x + 4y sous 2x + y ≤ 8, x + 2y ≤ 8, x ≤ 4, y ≤ 4. L’optimum est z = 24 en (8/3, 8/3), soit environ (2,67, 2,67).

Ouvrir ce cas: Production d'usine

Le meilleur sommet est fractionnaire, et c’est un autre problème. Les deux contraintes saturées se croisent loin du quadrillage, si bien que le meilleur sommet a des coordonnées fractionnaires. Une région bornée à nouveau, mais le sommet retenu par l’objectif ne tombe pas sur des entiers. — Les deux contraintes saturées se croisent loin du quadrillage, si bien que le meilleur sommet a des coordonnées fractionnaires.

Région non bornée, réponse bornée

Ce que vous savez: Minimisation sous contraintes ≥. La région réalisable file à l’infini, mais l’objectif garde un plancher.

Ce qu’il faut vérifier: min z = 13

Exemple résolu: Minimiser 2x + 3y sous x + y ≥ 6, x ≥ 2, y ≥ 1. La région est infinie, et pourtant le minimum vaut z = 13 en (5,1).

Ouvrir ce cas: Coût minimal

Région non bornée, réponse bornée. La région s’éloigne de l’origine sans limite, mais l’objectif atteint son minimum sur un sommet proche de celle-ci. Minimisation sous contraintes ≥. La région réalisable file à l’infini, mais l’objectif garde un plancher. — La région s’éloigne de l’origine sans limite, mais l’objectif atteint son minimum sur un sommet proche de celle-ci.

Pas d’optimum fini — et les sommets ne vous le diront pas

Ce que vous savez: L’objectif s’améliore le long d’une direction qu’aucune contrainte ne bloque. Il n’existe pas de meilleur point.

Ce qu’il faut vérifier: z → ∞

Exemple résolu: Maximiser 2x + y sous x + y ≥ 2, x ≥ 0, y ≥ 0. Avancez indéfiniment vers les x croissants et l’objectif croît indéfiniment ; la réponse est non bornée.

Ouvrir ce cas: Non borné

Pas d’optimum fini — et les sommets ne vous le diront pas. La région grisée est ouverte vers le haut à droite, et l’objectif continue de s’y améliorer sans fin. L’objectif s’améliore le long d’une direction qu’aucune contrainte ne bloque. Il n’existe pas de meilleur point. — La région grisée est ouverte vers le haut à droite, et l’objectif continue de s’y améliorer sans fin.

Références (3)

The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

Problème entièrement résolu

Le problème du régime pour maximiser Z = 3x + 2y 5 étapes
Quel sommet l'emporte, et quelle est la valeur du sommet adjacent ? Il s'agit du Problème du régime : maximiser Z = 3x + 2y sous les contraintes x + y ≤ 4, x ≤ 2 et y ≤ 3, avec x et y tous deux au moins égaux à 0.
1. Prenez deux points réalisables quelconques et parcourez le segment de droite qui les relie. Une fonction objectif linéaire le long de ce parcours est une moyenne pondérée de ses deux valeurs extrêmes, et une moyenne pondérée ne dépasse jamais la plus grande de ces extrémités. Ainsi, aucun point situé strictement entre deux autres ne peut être l'unique optimum, et appliquer ce principe dans toutes les directions successives isole l'optimum sur un sommet.
  
  $Z (λ A + (1 - λ) B) = λ Z (A) + (1 - λ) Z (B) \leq max {Z (A), Z (B)}, 0 \leq λ \leq 1$
2. Un sommet est l'intersection de deux droites frontières ; les candidats s'obtiennent donc en prenant les cinq droites deux à deux. Dix paires, dont deux parallèles, et seules cinq des huit restantes satisfont aux contraintes dont elles ne sont pas issues — x + y = 4 croise x = 0 en (0, 4), ce qui viole y ≤ 3.
  
  ${x + y = 4, x = 2} \Rightarrow (2, 2); {x + y = 4, y = 3} \Rightarrow (1, 3); (0, 0), (2, 0), (0, 3)$
3. Cinq évaluations arithmétiques et une comparaison, et la recherche est terminée. Il ne reste plus d'intérieur à tester ni d'arête à parcourir.
  
  $Z = 3 x + 2 y : 0, 6, 10, 9, 6 ⟹ (x^{*}, y^{*}) = (2, 2), Z^{*} = 10$
4. Au sommet gagnant, x + y = 4 et x = 2 sont toutes deux saturées, tandis que y = 2 se situe une unité entière en dessous de son plafond de 3. Une contrainte disposant de marge ne limite rien, donc la relâcher ne change rien ; il vaut la peine de résoudre à nouveau les deux autres avec une unité supplémentaire chacune.
  
  $b_{1} : 4 \to 5 \Rightarrow (2, 3), Z = 12, y_{1} = 2; b_{2} : 2 \to 3 \Rightarrow (3, 1), Z = 11, y_{2} = 1; y^{*} = 2 < 3 \Rightarrow y_{3} = 0$
5. Pondérez chacun de ces trois prix par la quantité de cette ressource attribuée dans le problème.
  
  $b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} = 4 (2) + 2 (1) + 3 (0) = 10 = Z^{*}$
Réponse

L'outil affiche x* = 2, y* = 2 et Z* = 10, la troisième des cinq valeurs aux sommets. Les nombres issus de l'étape 4 — 2, 1 et 0 — sont les prix d'ombre, et ils répondent à une question à laquelle le graphique ne peut répondre : une unité supplémentaire du budget x + y vaut deux fois une unité supplémentaire de x, et une unité supplémentaire de y ne vaut absolument rien. L'étape 5 est la dualité forte, et ce n'est pas une coïncidence propre à ces chiffres ; les prix pondérés par les ressources restituent toujours l'optimum, ce qui est précisément ce qui en fait des prix. Un prix d'ombre possède également une date d'expiration. Le budget x + y rapporte 2 par unité seulement jusqu'à 5, où le sommet atteint (2, 3), les deux autres contraintes deviennent saturées et Z bloque à 12 — au-delà de ce point, le prix est 0 et chaque unité supplémentaire achetée est perdue.

$max {c^{⊤} x : A x \leq b, x \geq 0} = min {b^{⊤} y : A^{⊤} y \geq c, y \geq 0} = 10$

Par l’équipe 42Math · Mis à jour 2026-08-17

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Statistiques & Finance →

Exemples de problèmes

Problème de régime - Maximisation bornée classique : l'optimum se situe à un sommet du domaine réalisable.
Production d'usine - Des contraintes de capacité qui se croisent créent une région réalisable polygonale.
Coût minimal - La minimisation sous contraintes à borne inférieure sélectionne le sommet réalisable le plus proche de l'origine dans la direction de l'objectif.
Non borné - Le domaine réalisable peut être non borné, donc l'objectif peut ne pas admettre d'optimum fini.