Algorithme simplex et points extrêmes
Pour cette question, mon raccourci est LP = programme linéaire, BFS = solution faisable de base, SEF = forme d'égalité standard.
Puisque l'algorithme Simplex itère du point extrême au point extrême (correspondant au fait que Simplex itère de BFS à BFS lorsque le LP est en SEF), comment l'algorithme Simplex fonctionne-t-il géométriquement lorsque la région réalisable est un polyèdre qui ne peut pas être réalisé en SEF (par exemple un demi-espace)? Supposons que nous ayons un LP pour lequel la région réalisable n'a pas de points extrêmes. Ensuite, nous pouvons écrire un LP «équivalent» qui est en SEF et exécuter l'algorithme Simplex dessus à la place. Mais il y a des points extrêmes pour ce nouveau polyèdre, alors qu'il n'y en a pas pour l'original, par hypothèse. Je pensais à l'origine que les points extrêmes d'un LP correspondaient bijectivement aux points extrêmes de l'autre, mais ce n'est évidemment pas le cas.
Alors, quand exactement les points extrêmes de la version SEF d'un LP correspondent-ils bijectivement aux points extrêmes de l'original? Et de plus, lorsqu'une telle bijection ne tient pas, comment sommes-nous supposés interpréter géométriquement ce que fait l'algorithme Simplex en termes de LP d'origine?
Réponses
l'algorithme Simplex itère du point extrême au point extrême
Techniquement, non. L'algorithme simplex de itère base à base . Il se trouve que les solutions de base réalisables correspondent à des points extrêmes. (par exemple, le double simplex itère à travers des solutions de base à double faisabilité, qui ne sont pas des points extrêmes de la région primale-faisable).
Considérez un LP sous forme standard, qui écrit \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}La région réalisable de cette LP est toujours polyédrique. S'il n'a pas de points extrêmes, alors il est soit vide (et il n'y a pas de solutions basiques réalisables), soit un sous-espace affine de$\mathbb{R}^{n}$. Or, ce dernier cas ne peut pas se produire, car aucun sous-espace affine ne peut être un sous-ensemble de$\mathbb{R}_{+}^{n}$.
Maintenant, revenons à (ce que je pense être) votre question initiale: étant donné un polyèdre original et une représentation SEF pour celui-ci, cette représentation a-t-elle des points extrêmes, et correspondent-ils aux points extrêmes du polyèdre original? La réponse est: oui, le SEF aura des points extrêmes, et non, ils peuvent ne pas toujours correspondre aux points extrêmes de votre polyèdre d'origine.
Voici un exemple simple: prenez $\mathcal{P} = \{x \in \mathbb{R}\}$, qui est un polyèdre unidimensionnel. Sa formulation a une variable libre et aucune contrainte.
Pour créer une représentation SEF, remplacez $x$ par $x^{+} - x^{-}$ avec $x^{\pm} \geq 0$. Maintenant,$(0, 0)$ est un point extrême de ce SEF, qui correspond à $x=0$, qui n'est pas un point extrême de $\mathcal{P}$.
Je ne suis pas sûr de bien comprendre votre question, mais je suppose que votre confusion vient de l’hypothèse qu’une solution de base est un «point extrême». Une solution de base (pas nécessairement primale ou double faisable) est juste l'intersection du nombre de contraintes de lignes (dont certaines peuvent être des limites). Il est possible qu'un problème n'ait pas de solution primale ou double faisable car le résultat est soit irréalisable, soit illimité. Les algorithmes simplex de manuels ignorent parfois le fait qu'une certaine forme d'approche de phase 1 est nécessaire pour établir un BFS afin de démarrer réellement l'algorithme. Il est possible qu'une phase primale 1 trouve le problème primal irréalisable et il est également possible qu'une phase double 1 trouve le problème illimité.
Mise à jour: La réponse de mtanneau est probablement de dire tout ce qu'il y a à dire, pour une seule contrainte avec des variables libres, la même chose s'applique. Je veux juste ajouter que les implémentations simplex fonctionnent directement avec des variables libres et ne les convertissent pas en deux variables limitées par 0. Mais il en va de même, l'algorithme itère sur les solutions de base et la convention est faite que les variables libres non basiques prennent la valeur 0. Notez également que pour les polyèdres bornés, les solutions basiques correspondent aux points extrêmes.