Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So, there are four inequalities:

$$\begin{eqnarray*} y &\geq &-3x+15; \\ y &\leq &-11/3x+56/3; \\ x &\geq &0; \\ y &\geq &0. \end{eqnarray*}$$

If we draw all those half-planes, we get a section half-plane where all of them have a solution ($x$ and $y$). But, how can I find $\max$ and $\min$ value of $7x+8y$ in that section?

share|improve this question
    
This is a linear programming optimizing problem. Retagged as such. See this introduction. –  Américo Tavares Mar 20 '13 at 0:05

2 Answers 2

up vote 2 down vote accepted

Expanding my comment above the stated optimization problem is solved normally by linear programming. Since the constraints involve only two variables, it has a simple geometric interpretation. The conditions $$ \begin{eqnarray} -3x+15 &\leq &y\leq -11/3x+56/3; \tag{1} \\ x &\geq &0,\quad y\geq 0 \end{eqnarray} $$ define the quadrilateral $Q$ (dark green in the figure below) whose vertices are $$ \begin{equation*} A\left( 0,15\right) ,B\left( 0,56/3\right) ,C\left( 56/11,0\right) ,D\left( 5,0\right) . \end{equation*} $$ Let $$ \begin{equation} z=7x+8y.\tag{2} \end{equation} $$ The equation $$7x+8y=c,\tag{3} $$ where $c$ is a parameter, defines the family of parallel lines in the $xy$-plane whose slope is $-7/8$. The larger $c$ is, the higher the $y$-intercept $c/8$ is. One of these is the blue line of the figure, whose equation is $7x+8y=0$ (i.e. $c=0$). To find $\max z$ subject to the constraints $(1)$ it is enough to compute $z$ at the vertex $B$, because from all the lines of the form $(3)$ with at least a common point to $Q$ the one through $B$ has the maximum value of the parameter $c$, as can be seen in the figure (light green line).

enter image description here

Similarly to find $\min z$ subject to the same constraints $(1)$ we compute $z$ at the vertex $D(5,0)$, because from all the lines of the family $(3)$ with at least a common point to $Q$ it is the one through $D$ (red line) that yields the minimum value for $c$. So $$ \begin{eqnarray*} \underset{Q}{\max }z &=&7\left( 0\right) +8\left( 56/3\right) =\frac{448}{3} \approx 149.33 \\ \underset{Q}{\min }z &=&7\left( 5\right) +8\left( 0\right) =35. \end{eqnarray*} $$

share|improve this answer
    
Thanks, very helpful. –  A6Tech Mar 23 '13 at 15:52
    
@A6Tech You are welcome! –  Américo Tavares Mar 23 '13 at 15:53

You get the domain in the first quadrant (inequalities 3-4) between the lines

$$y=-3x+15\;,\;\;y=-\frac{11}{3}x+\frac{56}{3}$$

The maximum-minimum values of your target function $\,f(x,y):=7x+8y\,$ within this domain are thus obtained on the vertices of the above domain, which are the points

$$(0,15)\,,\,\left(0,\frac{56}{3}\right)\,,\,\,(5,0)\,,\,\,\left(\frac{56}{11},0\right)$$

Now you only need to evaluate your function in each of the above points and choose the highest and lowest value.

Why this works this way is the basis of Linear Programming, and requires some linear algebra and stuff.

share|improve this answer
    
Thanks, very helpful. –  A6Tech Mar 23 '13 at 15:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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