∑
MathTCG
#196 / 200•Foundations•MathTCG #196 / 500•★Commune•∇Maths Appliquées•Méthode & Idée

Méthode du simplexe

Période historique : 1947 (George Dantzig)

L'algorithme souverain de la programmation linéaire : cheminer de sommet en sommet le long d'un polyèdre convexe pour maximiser un objectif.

Contenu & Formulation mathématique

Principe de la démarche
Navigation le long des sommets d'un polytope convexe de dimension n par pivotage matriciel jusqu'à ce qu'aucun voisin n'offre d'amélioration.
Champs d'application canoniques
Logistique d'approvisionnement, planification de vols des compagnies aériennes, optimisation de portefeuilles et raffinage pétrolier.
max⁡  cTxsous contraintes Ax≤b,  x≥0\max \; c^T x \quad \text{sous contraintes } Ax \le b, \; x \ge 0

Genèse & Portée historique

Algorithme d'optimisation linéaire résolvant des systèmes de contraintes linéaires. Puisque l'optimum se trouve obligatoirement sur un sommet du polytope des solutions réalisables, le simplexe parcourt les arêtes de sommet adjacent en sommet adjacent en augmentant la fonction objectif.

Durant la Seconde Guerre mondiale, George Dantzig développa la méthode pour planifier la logistique colossale de l'US Air Force, transformant les sciences de la gestion et la recherche opérationnelle.

« Glisser d'arête en sommet le long du cristal des contraintes pour atteindre la cime du gain. »

Filiations & Relations conceptuelles (1)

Repose sur le concept#020

Matrice

Résout les systèmes de contraintes par pivotages successifs sur des tableaux matriciels.

Objet de collection MathTCG

#196
★Commune
∇

Méthode du simplexe

Maths Appliquées•MÉTHODE

Principe : Navigation le long des sommets d'un polytope convexe de dimension n par pivotage matriciel jusqu'à ce qu'aucun voisin n'offre d'amélioration.

max⁡  cTxsous contraintes Ax≤b,  x≥0\max \; c^T x \quad \text{sous contraintes } Ax \le b, \; x \ge 0
1947 (George Dantzig)

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.

Extension : Foundations (#196 / 200)
Numéro global MathTCG : MathTCG #196 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Appliquées
Identifiant pérenne : methode-du-simplexe
Consulter mon classeurExplorer tout le recueil