Algoritmo simplex y puntos extremos
Para esta pregunta, mi abreviatura es LP = programa lineal, BFS = solución básica factible, SEF = forma de igualdad estándar.
Dado que el algoritmo Simplex itera de un punto extremo a otro (lo que corresponde al hecho de que Simplex itera de BFS a BFS cuando LP está en SEF), ¿cómo funciona geométricamente el algoritmo Simplex cuando la región factible es un poliedro que no se puede realizar en SEF (por ejemplo, un medio espacio)? Supongamos que tenemos un LP para el que la región factible no tiene puntos extremos. Entonces podemos escribir un LP "equivalente" que esté en SEF y ejecutar el algoritmo Simplex en él. Pero hay puntos extremos para este nuevo poliedro, mientras que no hay ninguno para el original, por supuesto. Originalmente pensé que los puntos extremos de un LP correspondían biyectivamente a los puntos extremos del otro, pero evidentemente este no es el caso.
Entonces, ¿cuándo exactamente los puntos extremos de la versión SEF de un LP corresponden biyectivamente a los puntos extremos del original? Y además, cuando tal biyección no se cumple, ¿cómo se supone que debemos interpretar geométricamente lo que está haciendo el algoritmo Simplex en términos del LP original?
Respuestas
el algoritmo Simplex itera desde el punto extremo al punto extremo
Técnicamente, no. El algoritmo simplex itera de base a base . Simplemente sucede que las soluciones básicas factibles corresponden a puntos extremos. (por ejemplo, el simplex dual itera a través de soluciones básicas de factibilidad dual, que no son puntos extremos de la región factible primaria).
Considere un LP en forma estándar, que escribe \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}La región factible de ese LP es siempre poliédrica. Si no tiene puntos extremos, entonces está vacío (y no hay soluciones básicas factibles) o un subespacio afín de$\mathbb{R}^{n}$. Ahora, el último caso no puede suceder, porque ningún subespacio afín puede ser un subconjunto de$\mathbb{R}_{+}^{n}$.
Ahora, volviendo a (lo que creo que es) su pregunta original: dado un poliedro original y una representación SEF para él, ¿esa representación tiene puntos extremos y corresponden a los puntos extremos del poliedro original? La respuesta es: sí, el SEF tendrá puntos extremos y no, es posible que no siempre correspondan a los puntos extremos de su poliedro original.
Aquí hay un ejemplo simple: tome $\mathcal{P} = \{x \in \mathbb{R}\}$, que es un poliedro unidimensional. Su formulación tiene una variable libre y sin restricciones.
Para construir una representación SEF, reemplace $x$ por $x^{+} - x^{-}$ con $x^{\pm} \geq 0$. Ahora,$(0, 0)$ es un punto extremo de ese SEF, que corresponde a $x=0$, que no es un punto extremo de $\mathcal{P}$.
No estoy seguro de entender completamente su pregunta, pero supongo que su confusión se deriva de la suposición de que una solución básica es un "punto extremo". Una solución básica (no necesariamente primaria o factible dual) es solo la intersección de restricciones de número de filas (algunas de las cuales podrían ser límites). Es posible que un problema no tenga una solución factible primaria o dual, en consecuencia, sea inviable o ilimitado. Los algoritmos simplex de los libros de texto a veces omiten el hecho de que se necesita algún tipo de enfoque de fase 1 para establecer un BFS para iniciar realmente el algoritmo. Es posible que una fase primaria 1 encuentre inviable el problema primario y también es posible que una fase dual 1 encuentre que el problema es ilimitado.
Actualización: la respuesta de mtanneau probablemente dice todo lo que hay que decir, para una sola restricción con variables libres se aplica lo mismo. Solo quiero agregar que las implementaciones simplex funcionan con variables libres directamente y no las convierten a dos variables limitadas por 0. Pero lo mismo ocurre, el algoritmo itera sobre soluciones básicas y se hace la convención de que las variables libres no básicas toman el valor 0. Observe también que para los poliedros acotados, las soluciones básicas corresponden a puntos extremos.