0

$\max x+y$
s.t.
$2x+y\le14\\-x+2y\le8\\2x-y\le10\\x\ge0\\y\ge0$

Is there a non graphical way to solve this quickly? Drawing the graph etc can be pretty time consuming in competitive exams!

Thanks in advance for any help.

GNUSupporter 8964民主女神 地下教會
  • 17,627
user405925
  • 343
  • 3
  • 13

2 Answers2

2

I don't think there is anything quicker than just sketching the situation on graph paper. You just need to be quicker at drawing, I'm afraid.

The diagram below (ignore the "11/12" things in the left corner from a different calculation) took me 76 seconds to draw, without being in any particular hurry. I don't think I could have completed any symbolic or algebraic approach that fast.

For each of the lines one can easily read off the $x$ and $y$ intercepts from the equation, and since the slopes are nice small integer ratios, one can even sketch the lines without needing a ruler. While drawing, we remember that the side of each of the lines that is relevant is the one the origin is on.

It is now quick to see that the northeasternmost point in the pentagonal domain is at $(4,6)$, giving $x+y=10$.

The graphical method is particularly fast here because even with quite sloppy lines, it is obvious that the solution is at an integral point. If we had been less lucky, we would just have found which two lines intersect at the optimal corner, and we'd then need to go back to their equations and find the precise intersection algebraically.

diagram of the area in the question

(cleaning up a photograph of the diagram in Gimp took me about twenty times as long as drawing it, but that doesn't count)

hmakholm left over Monica
  • 286,031
1

Since the OP asks for a non-graphical method, I'll give a pure algebraic one making use of $u=x+y$, which transform the problem to

$\max u$ such that $$ 2u-y \le 14 \\ -u+3y \le 8 \\ 2u - 3y \le 10 \\ u - y \ge 0 \quad (\because u-y=x\ge0) \\ y,u \ge 0 \quad (\because u=x+y\ge0) $$

A simple rearrangement gives

$\max u$ such that \begin{align} u &\le 7 + \frac12y \tag1\label1 \\ u &\le 5 + \frac32y \tag2\label2 \\ 3y-8 &\le u \tag3\label3 \\ y &\le u \tag4\label4 \\ y,u &\ge 0 \end{align}

Observe that $u$ is bounded by some degree-one polynomials of $y$ with positive coefficient, so to maximise $u$, it's natural to think of the bounds for $y$, especially the upper bound.

\begin{align} &\eqref1,\eqref3: 3y-8\le7+\frac12y\implies \bbox[2px,border:1px solid]{y\le6}\\ &\eqref1,\eqref4: y\le7+\frac12y\implies y\le14\\ &\eqref2,\eqref3: 3y-8\le5+\frac32y\implies y\le\frac{26}{3} \\ &\eqref2,\eqref4: y\le5+\frac32y \text{ is redundant} \end{align}

Therefore, set $y=6$, then the inequality from \eqref{1},\eqref{3} becomes an equality, so $u = 7+6/2=10$ gives the required maximum with $(x,y) = (4,6)$.

In tests/exams, you may want to be safe and check the feasibility.

\begin{align} 2(4)+6&=14 \\ -4+2(6)&=8 \\ 2(4)-6<10 \end{align}

So it's feasible.

GNUSupporter 8964民主女神 地下教會
  • 17,627
  • 1
    Thankyou! This makes sense. But, i guess the conclusion is that graphical method is faster :) – user405925 Mar 19 '17 at 02:46
  • @MAthsjunky In this case, you may say so. This is because the slopes of the straight lines are distinct. However, if you come across lines with similar slopes, and you have to do it on a blank ruff work sheet, I believe that the best way is to "combine" the graphical and the algebraic approaches. 1. Through theoretical learning, you know the shape (convex in the 1st quadrant, bounded by straight lines) of the feasible region, and that optimal solution occurs at a vertex. 2. You know the relationship between the geometric properties (boundary) and the algebraic properties (slack variable). – GNUSupporter 8964民主女神 地下教會 Mar 19 '17 at 02:56
  • If a calculator is allowed, in a 2d feasible region, you set exactly two of the given inequalities (including $x,y\ge0$) into equalities. (Since a point in $\Bbb R^2$ is determined by two lines.) Check if the solution found by Cramer's rule verifies the other constraints. This also works for $\Bbb R^3$, and can be generalized to $\Bbb R^n$. But as $n$ grows, I think it's better to use the simplex method, if you're comfortable with row operations.
    • – GNUSupporter 8964民主女神 地下教會 Mar 19 '17 at 03:01