Algoritmo simplex e pontos extremos
Para esta questão, minha abreviação é LP = programa linear, BFS = solução básica viável, SEF = forma de igualdade padrão.
Uma vez que o algoritmo Simplex itera de ponto extremo a ponto extremo (correspondendo ao fato de que Simplex itera de BFS para BFS quando o LP está em SEF), como o algoritmo Simplex funciona geometricamente quando a região viável é um poliedro que não pode ser realizado em SEF (por exemplo, meio espaço)? Suponha que temos um LP para o qual a região viável não tem pontos extremos. Então, podemos escrever um LP 'equivalente' que está em SEF e executar o algoritmo Simplex nele. Mas há pontos extremos para esse novo poliedro, enquanto não há nenhum para o original, por suposição. Originalmente, pensei que os pontos extremos de um LP correspondiam bijetivamente aos pontos extremos do outro, mas evidentemente não é o caso.
Então, quando exatamente os pontos extremos da versão SEF de um LP correspondem bijetivamente aos pontos extremos do original? E, além disso, quando tal bijeção não se sustenta, como devemos interpretar geometricamente o que o algoritmo Simplex está fazendo em termos do LP original?
Respostas
o algoritmo Simplex itera de ponto extremo a ponto extremo
Tecnicamente, não. O algoritmo simplex itera de base para base . Acontece que soluções básicas viáveis correspondem a pontos extremos. (por exemplo, o simplex dual itera através de soluções básicas dual-factíveis, que não são pontos extremos da região primal-viável).
Considere um LP em formato padrão, que escreve \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}A região viável desse LP é sempre poliédrica. Se não tiver pontos extremos, então está vazio (e não há soluções básicas viáveis) ou um subespaço afim de$\mathbb{R}^{n}$. Agora, o último caso não pode acontecer, porque nenhum subespaço afim pode ser um subconjunto de$\mathbb{R}_{+}^{n}$.
Agora, voltando (o que eu acho) à sua pergunta original: dado um poliedro original e uma representação SEF para ele, essa representação tem pontos extremos, e eles correspondem aos pontos extremos do poliedro original? A resposta é: sim, o SEF terá pontos extremos e não, eles podem nem sempre corresponder aos pontos extremos de seu poliedro original.
Aqui está um exemplo simples: pegue $\mathcal{P} = \{x \in \mathbb{R}\}$, que é um poliedro unidimensional. Sua formulação tem uma variável livre e sem restrições.
Para construir uma representação SEF, substitua $x$ de $x^{+} - x^{-}$ com $x^{\pm} \geq 0$. Agora,$(0, 0)$ é um ponto extremo desse SEF, que corresponde a $x=0$, que não é um ponto extremo de $\mathcal{P}$.
Não tenho certeza se entendi completamente sua pergunta, mas acho que sua confusão decorre da suposição de que uma solução básica é um "ponto extremo". Uma solução básica (não necessariamente primal ou dual viável) é apenas a interseção das restrições de número de linhas (algumas das quais podem ser limites). É possível que um problema não tenha uma solução viável primal ou dupla em como resultado seja inviável ou ilimitado. Algoritmos simplex de livros didáticos às vezes ignoram o fato de que alguma forma de abordagem da fase 1 é necessária para estabelecer um BFS para realmente iniciar o algoritmo. É possível que uma fase 1 primal considere o problema inviável primal e também é possível que uma fase 1 dual encontre o problema ilimitado.
Atualização: A resposta de mtanneau provavelmente está dizendo tudo o que há a dizer, para uma única restrição com variáveis livres, o mesmo se aplica. Só quero acrescentar que as implementações simplex funcionam com variáveis livres diretamente e não as convertem em duas variáveis limitadas por 0. Mas o mesmo se aplica, o algoritmo itera sobre soluções básicas e a convenção é que as variáveis livres não básicas assumem o valor 0. Observe também que, para poliedros limitados, as soluções básicas correspondem a pontos extremos.