Méthode du simplexe

[claudy33]

Bonjour

Je cherche à comprendre la méthode du simplexe mais quelque chose m'échappe. J'ai bien compris que l'ensemble des solutions admissibles était un polyèdre convexe et qu'il suffisait de chercher parmi les sommets de ce polyèdre pour trouver les solutions optimales. J'ai également compris que choisir un sommet revient à choisir une base de la matrice A c'est à dire une matrice extraite inversible (problème sous forme standard de type Ax=b avec m contraintes de A de rang m)

Mais en pratique comment fait-on pour "se déplacer de sommet en sommet" ? Certes la matrice A est de rang m mais ça ne garantit pas pour autant que toute matrice extraite de taille m est inversible il me semble...
Dans tous les exemples que je vois j'ai l'impression qu'il suffit de choisir une variable sortante, une variable entrante et on retombe directement sur un sommet.
Une fois qu'on a le premier sommet je ne comprends pas comment passer aux suivants...

Merci beaucoup pour votre aide !
-----

[claudy33]

A la relecture mon message est peut-être pas très clair
En fait je me demande ce qui garantit que, lorsqu'on fait sortir une variable de la base et entrer une autre, on retombe bien sur une base. Je ne comprends pas pourquoi on n'a pas besoin de vérifier que la nouvelle base est effectivement une base

[gg0]

Bonjour.

Si mes souvenirs de ma méthode sont bons (*), on remplace un vecteur u de la base par une combinaison linéaire des vecteurs de base où le coefficient de u est non nul. Dans ce cas, la nouvelle famille obtenue est toujours génératrice, et, ayant le bon nombre d'éléments est donc une base.

Cordialement.

(*) J'ai vaguement regardé ça à une époque où mon épouse pratiquait la méthode sans explication.

[claudy33]

Oui effectivement c'est ça qui m'échappait, merci !

[A voir en vidéo sur Futura]