Linear Programming Simplex Method: What exactly are the basic and non-basic variables

linear programmingoptimization

I'm having a little bit of confusion understanding what exactly are the basic and non-basic variables in a linear programming problem when using the Simplex Method. From my understanding and reading the textbook, basic variables are the variables that we solve for (slack variables), and non-basic variables are the ones that are set to 0 (the objective function P's initial parameters).

However, looking at some other videos (https://www.youtube.com/watch?v=i2QL4YvSzi0&ab_channel=CatherineSporer at 2:06), it seems that some of the slack variables are actually considered basic variables. Is there a standardized way for determining straight away from a standard LP problem statement, what are the basic and non-basic variables?

Best Answer

Which variables are the basic variables will change over time. In the simplex method, you:

  1. Find a basic feasible solution: a feasible solution where we set the nonbasic variables to $0$, which lets us uniquely solve for the basic variables.
  2. Do a pivot step where we change a nonbasic variable to basic, and then make one of the old basic variables nonbasic. This gives us a different basic feasible solution. If we chose the entering variable correctly, it's a better one.
  3. Repeat this, moving from one basic feasible solution to another, until we get to the optimal solution.

What the slack variables give us is a starting set of basic variables. The simplex method is helpless if it doesn't have a basic feasible solution to work with. In the special case where our constraints are $Ax \le b, x \ge 0$ with nonnegative $b$, we can find a basic feasible solution easily. First change the constraints to $Ax + Is = b$ with $x,s \ge 0$; then make $s$ basic and $x$ nonbasic.

As we perform the simplex method, the set of basic variables will change. Some slack variables will become nonbasic, and some of the other variables will become basic.

(Also, if we don't have an LP in the special form where we can add slack variables, then it is much harder to find an initial basic feasible solution - and it might not even exist. This is where the two-phase simplex method comes in.)

Related Question