¿por qué en la Fase I del método simplex, si artificiales variable se convierten no básicas, nunca se convertirá en basic?

Question

¿Alguien tiene idea de como resolver este problema ?

"Mostrar que en la Fase I del método simplex, si una variable articial se convierte en no básicas, es necesario que nunca volver a convertirse en basic. Por lo tanto, cuando una variable articial se convierte en no básica, su columna puede ser eliminado del tableau"

Answer 1

Como se mencionó anteriormente, esto es desde el Bertsimas y Tsitsiklis, y la Fase I del enfoque que se están refiriendo es en la Sección 3.5. La forma estándar de los LP que uso es \begin{array}{ll} \text{minimize} & c^T x \\ & A x = b \\ & x \geq 0 \end{array} Ellos asumen que $b\geq 0$; si este no es el caso, negar las filas correspondientes para hacerlo. (Y para simplificar, supongamos $b$ tiene al menos un valor distinto de cero.) La correspondiente Fase I problema se parece a esto: \begin{array}{ll} \text{minimize} & \textstyle\sum_i y_i \\ & A x + y = b \\ & x \geq 0, y \geq 0 \end{array} Ahora puedes ver por qué $b\geq 0$ es importante: $(x,y)=(0,b)$ constituye un trivial solución viable, así que ese es el punto de partida para la Fase I del método, con un objetivo inicial de $\sum_i b_i>0$. Si el valor óptimo de esta Fase I del modelo es igual a cero, entonces el modelo original es factible; de lo contrario, el modelo original no es factible.

Es importante leer la declaración cuidadosamente. Es no afirmar que una variable artificial nunca va a volver a entrar en la base si usted lo deja en el tapete. De hecho, se puede. Si usted tiene el libro, mirar el Ejemplo 3.8. En uno de los pasos, una de las no básicas artificial variables tiene un negativo de la reducción de costos, lo que es un totalmente válido candidato para la selección, dependiendo de la argolla de la regla de usar. (En el ejemplo se eligió un elemento dinámico diferente, sin embargo.)

La declaración, por tanto, no es que nunca va a volver a entrar en la base. Más bien, la declaración dice que no necesita volver a entrar en la base. Lo que queremos mostrar es que la eliminación de una de estas variables desde el tableau no impide que el método del simplex se termine correctamente.

A ver por qué este es el caso, considere la posibilidad de este "reinicio" enfoque a la solución de la Fase I del modelo:

1. Inicializar: base $\mathcal{B}=(y_1,y_2,\dots,y_n)$, $(x,y)=(\vec{0},\vec{1})$.
2. Comenzar el algoritmo del simplex simplex con la base actual $\mathcal{B}$ y actual $(x,y)$.
3. Si el algoritmo termina antes de que una variable artificial es eliminado:
   • Si el coste es cero, PARADA. El problema es factible, pero extra se deben tomar medidas para impulsar el resto de variables artificiales fuera de la base. Consulte la Sección 3.5 para obtener más detalles.
   • Si el costo es positivo, PARADA. el problema es infactible.
4. Tan pronto como una variable artificial es eliminado de la base, detenga el método simplex, y obtener la base actual $\mathcal{B}$ y el punto actual $(x,y)$. (La primera vez, esto ocurrirá en el primer pivote. En las siguientes iteraciones, puede tomar más tiempo.)
5. Quitar el recién no básicas artificial variable del problema. Si no básicos artificial variables permanecen, DETENGA. El problema es factible y usted tiene un básico de una solución factible.
6. Repita los pasos 2-6.

La clave para el éxito de este enfoque es de señalar que, después de la eliminación de un no básicas artificial variable en el Paso 5, todavía estás a la izquierda con la validez de una pseudo-Fase I modelo y un posible punto para ese modelo. El modelo todavía tiene un valor óptimo de $0$ si el modelo es factible. También es importante tener en cuenta que el objetivo valor alcanzado en el Paso 4 va a ser el objetivo inicial valor en el Paso 2. Para no perder el progreso con nuestro reinicia.

De hecho, una manera de ver esto es la siguiente: no estamos realmente reiniciar el algoritmo del simplex de por sí. Más bien, estamos seleccionando para volver a calcular la inversa de la base de la matriz de $B^{-1}$ a partir de cero cada vez que una variable artificial sale de la base. Aún así, expresando el enfoque de esta forma, se espera que sea más fácil ver por qué la eliminación de las no básicas artificial variables no impide que el algoritmo termina.

Una vez que esté satisfecho con esto, usted no necesita realmente reiniciar. Usted recibirá exactamente la misma secuencia de simplex pivotes si simplemente incluir en el pivote de la regla de la cláusula: nunca elija un no básicas artificial variable.

Answer 2

No estoy seguro de si puedo responder a su pregunta o no:

En la Fase I de la función objetivo es $$\min s_1+s_2+\ldots+s_m$$ where $s_i$ for $1\le i \le m$ are the artificial slack variables of the original problem. But one constraint (of the Phase I LP) is that $$s_i\ge 0, \qquad \text{ for } i=1,2, \ldots, m$$ and therefore if one of these variables becomes $0$ es "as good as it gets" (para esa variable y el objetivo de la LP de la Fase I). Esto da la razón de que una variable que sale de la base no se introduzca en la base de nuevo:

1. Desde que se comienza la Fase I con cada una de estas variables que tienen un valor positivo, por lo que uno de ellos igual a $0$, estrictamente mejora el valor de la función objetivo. Pero esto significa que esta variable tiene a la izquierda de la base.
2. Ahora, como siempre que hay un positivo de la variable de holgura que va a hacer estrictamente mejor tomando esto hacia fuera de la base, en lugar de llevar una variable con valor de $0$ (ciclismo).
3. Cuando todas estas variables son iguales a $0$ - si es posible - entonces usted puede terminar con la Fase I.

---

Un buen libro que cubre (más de) los principios básicos de la optimización lineal y proporciona intuitiva explicación para la mayoría de los sujetos, es que de Bertsimas y Tsitsiklis (1997), la mayor parte de los cuales (incluyendo la descripción de la Fase I, p. 111) se puede encontrar en línea aquí.