1

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?

user352102
  • 904

1 Answers1

3

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).

Kuifje
  • 9,584