Non-graphical method of solving linear programming
$\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.
$\endgroup$ 22 Answers
$\begingroup$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.
(cleaning up a photograph of the diagram in Gimp took me about twenty times as long as drawing it, but that doesn't count)
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ 3
