1

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.

TMM
  • 9,976
Zack
  • 141
  • 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

1 Answers1

4

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.

Daryl
  • 5,598
  • How you calculated that S1=0 and S2=15 :P ? – user3100974 Feb 03 '14 at 20:38
  • @user3100974 As I said above, the values for the slack variables can be calculated by substituting the values of the decision variables into the constraints. Since each slack variable appears once, it is trivial to calculate their values. – Daryl Feb 04 '14 at 02:56