regarde wiki/Algorithme_du_simplexe
la forme la plus couramment utilisée pour présenter et étudier les algorithmes, qui est celle supposée par l'algorithme du simplexe révisé, est la forme standard :
min c^T x
Ax = b
et x >= 0
où c,b sont des vecteurs connus, A une matrice connue, et x un vecteur qu'on cherche
la principale difficulté est de montrer que x* (le x optimal) est forcément sur un sommet du polytope admissible
à mon avis le plus simple c'est d'abord de montrer que soit x = infini sur une des composante soit le peut être vu comme borné (en rajoutant des contraintes u^T x <= v qui ne changent rien à la solution), puis de dire que si x* est dans l'intérieur du polytope, alors x* est sur le segment [ab] où a est un sommet et b un point d'une face, a et b sont admissibles et c^Tx est une fonction linéaire donc
c^Ta < c^Tb ou c^Tb < c^Ta ou c^Ta = c^Tb
dans les deux premiers cas x* n'est pas la solution et dans le troisième a et b sont également solution
si x* est sur une face c'est le même principe
s'en suit l'algorithme du simple où l'on se balade de sommets en sommets adjacents
Partager