I am learning the simplex method and was wondering why we always search for solutions of the form basic $\cup$ nonbasic where nonbasic variables take on zero value.
Let's look at a concrete example:
let 8$x_1$+10$x_2$+7$x_3$= z
$x_1$+3$x_2$+2$x_3$+$s_1$=10
$x_1$+5$x_2$+$x_3$+$s_2$=8
$x_1,x_2,x_3,s_1,s_2 \geq 0$
We start with $s_1$, $s_2$ as basic slack variables. They are nonnegative while $x_1,x_2,x_3$ are all zero nonbasic variables. This is a feasible solution to the linear programming problem.
We then find a "better solution" by finding a pivot that will tell us the incoming and outgoing variables.
In this case the 5 is the pivot value with outgoing variable $s_2$ and incoming variable $x_2$.
After row reduction we read off from the tableau that $x_2$ and $s_1$ are basic variables that take on nonnegative values while $x_1$, $x_3$, $s_2$ take on zero values as nonbasic variables.
Why do we assume nonbasic variables are always zero?
Does it have something to do with searching for extreme points? Can anyone reference a proof for this?
Best Answer
Indeed, this has to do with the fact that we are pivoting from one extreme point to another. When you are on an extreme point, necessarily some of your variables equal $0$, do you see why ?
In two dimensions, you need at least two lines to define a point. In terms of linear programming, an extreme point is at the intersection between two constraints that are active. And for a constraint to be active, necessarily the corresponding slack variable equals $0$. So in two dimensions, you need at least two variables to have value $0$ to be on an extreme point (and the other variables to be non negative).