Optimisation linéaire et régionnement du plan
Fiche élève
Les énoncés du chapitre, à imprimer ou à travailler à l'écran. Sans compte !
Pour aller plus loin
Réservé aux abonnés : la fiche interactive, le corrigé et la fiche prof.
Fiche interactive
Cours + 1 atelier manipulable + exos auto-corrigés.
Corrigé
La correction détaillée, avec les rappels utiles.
Fiche prof
La version enseignant, pour préparer et animer.
Juste besoin de ce chapitre ? Débloquez-le pour 2,99 € : paiement unique, accès à vie (fiche interactive, corrigé, fiche prof et corrigés des exercices).
Avec un code de parrainage, c'est −20 % sur cette première commande.
Le chapitre en bref
Ce que tu vas savoir faire
- Associer à une inéquation un demi-plan, et le déterminer par un point test.
- Représenter la région admissible définie par plusieurs inéquations : le polygone des contraintes.
- Traduire un énoncé en système d'inéquations et en fonction objectif.
- Calculer les sommets du polygone en résolvant des systèmes de deux équations.
- Utiliser les droites de niveau pour comprendre que l'optimum est atteint en un sommet.
- Déterminer la solution optimale, y compris lorsque les inconnues doivent être entières.
Le plan du chapitre
- 1Une inéquation, un demi-plan
- 2Traduire un problème en contraintes
- 3Droites de niveau et optimum en un sommet
- 4Solutions entières et minimisation
À retenir
- Demi-plan : on trace la frontière , puis un point test décide du côté (l'origine si elle n'est pas sur la droite).
- Modéliser : inconnues, une inéquation par ressource (plus , ), fonction objectif .
- La région admissible est l'intersection des demi-plans : ici, un polygone.
- Les droites de niveau sont toutes parallèles ; on les fait glisser jusqu'au bord de la région.
- L'optimum est atteint en un sommet : on calcule z en chaque sommet et on garde le meilleur.
- Sommet = intersection de deux frontières : on résout un système de deux équations.
Les questions éclair
Comment savoir quel demi-plan correspond à ax + by ⩽ c ?
On teste un point hors de la droite (souvent l'origine) : s'il vérifie l'inéquation, c'est son côté.
Qu'est-ce que la région admissible ?
L'ensemble des points qui vérifient TOUTES les contraintes : l'intersection des demi-plans.
Où l'optimum est-il atteint ?
En un sommet du polygone (ou le long d'un côté entier si l'objectif lui est parallèle).
Comment trouve-t-on un sommet ?
C'est l'intersection de deux droites frontières : on résout le système de leurs deux équations.
Et si x et y doivent être entiers ?
On teste les points entiers admissibles voisins du sommet optimal, en vérifiant chaque contrainte.
Le sais-tu ?
L'optimisation linéaire est née en pleine Seconde Guerre mondiale, pour organiser la logistique des armées. En 1947, l'Américain George Dantzig inventa une méthode de calcul, le simplexe, qui passe de sommet en sommet jusqu'à l'optimum : exactement l'idée de ce chapitre, mais en des milliers de dimensions. Anecdote célèbre : étudiant, Dantzig arriva en retard à un cours, recopia au tableau deux problèmes qu'il prit pour des devoirs, et les résolut en quelques jours. C'étaient deux problèmes de statistique réputés non résolus. Aujourd'hui, compagnies aériennes, réseaux électriques et plateformes de livraison s'appuient sur les héritiers de sa méthode.