La présentation d’Algorithme du simplexe

L’algorithme du simplexe est un algorithme de résolution des problèmes d’optimisation linéaire. Il a été introduit par George Dantzig à partir de 1947. C’est probablement le premier algorithme permettant de minimiser une fonction sur un ensemble défini par des inégalités. De ce fait, il a beaucoup contribué au démarrage de l’optimisation numérique. L’algorithme du simplexe a longtemps été la méthode la plus utilisée pour résoudre les problèmes d’optimisation linéaire. Depuis les années 1985-90, il est concurrencé par les méthodes de points intérieurs, mais garde une place de choix dans certaines circonstances (en particulier si l’on a une idée des contraintes d’inégalité actives en la solution).

Le nom de l’algorithme est dérivé de la notion de simplexe et a été suggéré par Motzkin. En réalité, l’algorithme n’utilise pas de simplexes, mais certaines interprétations de l’ensemble admissible du problème renvoient au concept de simplexe.

Connaissances supposées : l’algèbre linéaire, le calcul différentiel, le vocabulaire de l’optimisation mathématique.

Source: https://fr.wikipedia.org/wiki/Algorithme_du_simplexe

Théorèmes

Théorème 1S’il existe une solution admissible au problème A.X ≥ 0, X ≥ 0 alors il existe une solution de base admissible.

S’il existe une solution optimale admissible, il existe une solution de base admissible optimale.

Théorème 2 L’ensemble des solutions admissibles forme un ensemble convexe K.

Preuve : Soient X et Y deux solutions dans K.

theoreme2

Théorème 3 Si K est un ensemble convexe, un point de K solution admissible de A.X ≥ 0, X ≥ 0 est un sommet de K ssi X est une solution de base admissible

Théorème 4 Toute solution de A.X ≥ 0, X ≥ 0 est une combinaison linéaire convexe des sommets. La solution optimale est donc une combinaison linéaire convexe des sommets.

Théorème 5 L’optimum de z, s’il existe, est atteint en au moins un sommet de K. Preuve : (Par l’absurde) Soit X∗ un optimum de z qui ne soit pas un sommet de K

theoreme3

 

 

Choisissons les λi tels que Capture (Théorème 4). Donc Capture2 absurde, X∗ est donc un sommet.

Théorème 6 Si z atteint son optimum pour plusieurs sommets, il l’atteint aussi pour toute combinaison linéaire convexe de ces sommets.

Preuve :

theoreme6

 

Pas encore de commentaire.

Laisser un commentaire

Techno95 |
MANJ |
TOUT SUR LE MAC |
Unblog.fr | Annuaire | Signaler un abus | Informatique11
| Cartiertechno
| Supermarketlady