Graphical LP Solution: 23-Ind-A1 Operations Research, Undated paper, Q3

Question 3: Graphical LP Solution (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Objective $z=6x_1+4x_2$ (maximize); constraints $2x_1+x_2\le 10$, $x_1+x_2\le 8$, $x_2\le 7$, $x_1,x_2\ge 0$.

Find. The optimal $(x_1,x_2)$ and $z^*$ by the graphical method.

Approach. Plot all four boundary lines, shade the common feasible region, identify its corner (extreme) points, and evaluate $z$ at each — the LP optimum always occurs at a corner point.

Feasible region (shaded) for Question 3, with all five corner points and the objective line through the optimum.

Find the corner points of the feasible region by intersecting adjacent boundary lines: $(0,0)$; $(5,0)$ (from $2x_1+x_2=10$, $x_2=0$); $(2,6)$ (intersection of $2x_1+x_2=10$ and $x_1+x_2=8$); $(1,7)$ (intersection of $x_1+x_2=8$ and $x_2=7$); $(0,7)$.
Evaluate $z=6x_1+4x_2$ at every corner point (the optimum of an LP always occurs at a vertex of the feasible region):
Objective value at each corner point
Corner (0,0) (5,0) (2,6) (1,7) (0,7)

$z=6x_1+4x_2$ 0 30 36 34 28

The largest value, $z=36$, occurs at $(2,6)$: $$\boxed{x_1^*=2,\ x_2^*=6,\ z^*=36}$$

Objective value at each corner point
Corner	(0,0)	(5,0)	(2,6)	(1,7)	(0,7)
$z=6x_1+4x_2$	0	30	36	34	28

Final results — Question 3
Item	Value
Optimal $x_1^*$	2
Optimal $x_2^*$	6
Optimal $z^*$	36
Binding constraints	$2x_1{+}x_2\le10$ and $x_1{+}x_2\le8$ (both tight at the optimum)

Topic: Graphical solution of a 2-variable linear program.

Key relations: The feasible region of a set of linear inequalities is a convex polygon; the optimum of a linear objective over a bounded convex polygon always occurs at (at least one) vertex — the Fundamental Theorem of LP.

Why this works: Level curves of a linear objective are parallel lines; sliding the $z=6x_1+4x_2$ line outward (increasing $z$) in the direction of steepest ascent, the last feasible point it touches is a vertex, here $(2,6)$.

Common pitfall: Forgetting the (easy to overlook) constraint $x_2\le 7$ when sketching the region — without it the region is unbounded above and the true vertex $(1,7)$ is missed, though it is not the optimum here.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 3 (graphical solution of two-variable LPs).

Question 3 of 10: Graphical LP Solution

Question 3: Graphical LP Solution (10 marks)