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?
Best Answer
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?