so I am working through the proofs and reading the book "Linear and NonLinear Programming" by Luenberger and wanted to ask for some help. If someone could read the following extract and explain the concept to me I would be very grateful.
For the standard problem:
$Ax = b$
$x \geq 0$
For a basic feasible solution:
$x = (x_1, x_2,…,x_m, 0 ,0, 0)$ or equivalenty:
$x_1a_1 + x_2a_2 +···+ x_ma_m = b$ (1)
Suppose we decide to bring into the representation $a_q$. Then we can represent this in terms of the current basis:
$a_q = y_{1q}a_1 + y_{2q}a_2 +···+ y_{mq}a_m $ (2)
If we multiply (2) by $\epsilon \geq 0$ and subtract (2) from (1) then we have the following:
$(x_1 −\epsilon y_{1q})a_1 +(x2 −\epsilon y_{2q})a_2 +···+(xm −\epsilon y_{mq})a_m +a_q = b$
Now if $\epsilon = 0$ then we have the basic solution meaning that $x_i, i=1,..,m \ge0$ and the remaining $x_i = 0$.
My confusion comes from the text where it states that for $\epsilon \geq 0$ then the solution is feasible but non-basic. Could someone explain to me why? Is it because the corresponding element for $a_q$ in the solution vector $x$ is non-zero?
The question comes from an explanation from the book "Linear and NonLinear Programming" by Luenberger. I am accessing a university pdf and so cannot share the link but here is a screenshot from the book on page 49:
Best Answer
It's non basic because you have $m+1$ nonzero coefficients but a basis of size $m$. To make the new point basic, increase $\epsilon$ until the first coefficient $x_i - \epsilon y_{iq}$ becomes zero, in which case you recover $m$ nonzero coefficients.