Suppose I've a simple linear programming problem

Maximize some arbitrary objective function subject to the following constraints:

$x_1+2x_2 \leq 6$

$x_1-x_2 \leq 4$

$x_2 \leq 2$

$x_1,x_2 \geq 0$

It was simple enough to graph and the extreme points are at:

$(0,0), (0,2), (4,0), (2,2), (\frac{14}{3}, \frac{2}{3})$

For each extreme point how do I determine which are the basic and non-basic variables?

I think there should be 2 basic and 3 non-basic, right? I also think for the point $(0,0)$ 2 slack variables are the basic variables? But there are 3 in this problem.

I'm not sure how to know exactly which without an objective function. Any ideas?


You will have as many basic variables as constraints, i.e., $3$ here. Typically, a basic variable has a positive value.

If you consider the point $(0,0)$, it means that $x_1=x_2=0$, and that the slack variables $e_1,e_2,e_3$ are positive (for the constraints to hold). So the basic variables are $e_1,e_2,e_3$.

For point $(0,2)$, $x_1=0$ and $x_2>0$, so $x_2$ is a basic variables. You need two more. You can either find them algebraically by plugging the values of $x_1$ and $x_2$ in the constraints: you will find that $e_3=0$, and that $e_1,e_2>0$, so $e_1,e_2$ are your remaining basic variables. You can also work graphically. $(0,2)$ is at the intersection between $x_2=2$ and $x_1=0$, in other words at this point only the third constraint is active, which means that first and second constraints are inactive, i.e., $e_1,e_2 >0$.

Can you do the same for the other points?

  • $\begingroup$ Got it! I'd known this before but forgot :D Thanks !! $\endgroup$ – Gregory Peck Mar 2 '17 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.