# Finding the number of basic/zero variables at an optimal corner point in linear programming

Draw a graph of the following problem \begin{align}4x+3y &\leq 180 \\ 7x+4y &\leq 280 \\ y &\leq 40 \\ x &\geq 0 \\ y &\geq 0\end{align}

a) If the problem is to maximize the objective function $z= 5x+6y$ subject to above constrains, what would be the optimal solution? Find it graphically.

So I found it and the optimal solution is at $x=15$, $y=40$ where $z=315$.

b) How many basic and zero variables are there at an optimal corner point?

Well yeah, I don't know how to answer part b.

• Hint Each constraint requires one basic variable. Alternatively, how many non-zero variables are there after you write the LP in standard form. – Daryl Apr 30 '13 at 21:13
• So there's two non-zero (basic) variables, but how many zero variables? – Zack Apr 30 '13 at 21:16

Writing your LP in standard form gives: \begin{aligned} \max z=5x+6y\\ 4x+3y+s_1&=180\\ 7x+4y+s_2&=280\\ y+s_3&=40\\ x,y&\geq0 \end{aligned} The optimal solution, as you have shown is $x=14,y=40, z=315$. Substituting the values for $x$ and $y$ into the constraints above, we can see that $s_1=0,\,s_2=15,\,s_3=0$.
Thus, the basic variables are $x,y,s_2$ and the non-basic variables are $s_1,s_3$.
In response to my comments, each constraint corresponds to one basic variable. With $m$ constraints and $n$ variables ($m<n$), at each feasible solution, we are solving a linear system of $m$ equations in $m$ variables, having set $n-m$ variables to be zero. The set of variables we are solving for are called basic variables and the set of variables which we assign the value zero are non-basic variables.