# Max and min value of $7x+8y$ in a given half-plane limited by straight lines?

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?

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

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 $$$$z=7x+8y.\tag{2}$$$$ 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).

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*}$$

-
Thanks, very helpful. – A6SE 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.

-
Thanks, very helpful. – A6SE Mar 23 '13 at 15:52