¿Cómo sabemos que la variable que ingresa la base en Simplex tiene un vector de columna correspondiente que es linealmente independiente de la base actual?

Answer 1

http://dcs.gla.ac.uk/~fischerf/t…, página 2, el último párrafo de 3.1 lo cubre brevemente, pero lo asume sin mucha discusión. Lo que sigue es un poco de combustible para la intuición, en lugar de algo formal.

Considere un LP donde exactamente una columna, la columna k, puede representarse como una combinación lineal de las otras columnas de la matriz A. Entonces, se puede lograr el mismo cambio en el LHS de todas las restricciones

1. Elegir la columna k, con coeficiente objetivo Ck, con un valor de 1: esto cambiará la función objetivo en 1 * Ck
2. Elegir una combinación lineal de columnas (estas columnas forman el conjunto J) con coeficientes Lambda_j que suman 1. Esto hará que el valor de la función objetivo cambie por sum_j (Lambda_j * Cj)

Si uno u otro tiene un impacto preferible en la función objetivo (uno más pequeño, si estamos minimizando), entonces claramente no necesitamos el otro, ya que eventualmente se eliminará gradualmente de la solución óptima. Se puede lograr el mismo impacto de restricción para más barato, por lo que ninguna solución óptima contendrá la opción más cara.

Si Ck es más costoso que la combinación lineal, puede soltar la columna k, y ahora sus columnas en A son independientes.

Si ambos tienen el mismo coeficiente y, por lo tanto, es irrelevante lo que elija, y también puede patear la columna k, haciendo que las columnas de A sean independientes.

Si la combinación lineal es más costosa, entonces la columna k se queda, pero esto hace que la misma situación surja para otra columna, la columna l. El “impacto de restricción” de la columna l ahora se puede lograr de manera más económica eligiendo una combinación lineal diferente de las columnas de A (esta nueva combinación lineal incluye la columna k), por lo que la columna l es la que se patea. Nuevamente, terminas con una matriz A que tiene columnas linealmente independientes

Debido a que puede reducir su LP a un formulario con columnas linealmente independientes antes de comenzar el método simplex, se supone que el método simplex comienza en un LP que se ha reducido de esta manera.

Lo anterior no es riguroso (en particular, he dicho “Las columnas de A son linealmente independientes”, donde quiero decir “Cualquier elección de columnas de A para formar una base B hace que B tenga columnas linealmente independientes”), pero espero que sea algo de ayuda, no quería desordenarlo demasiado.

Avíseme si tiene alguna pregunta, si cree que estoy equivocado, si estoy hablando tonterías, etc. Ha pasado un tiempo desde que estudié esto = P