Graphical LP and its Dual: 23-Ind-A1 Operations Research, December 2018, Q3

Question 3: Graphical LP and its Dual (20 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.

(a) Graphical solution

Given. Maximize $z=5x_1+6x_2$ subject to $4x_1+2x_2\le16$, $3x_1+3x_2\ge18$ (i.e. $x_1+x_2\ge6$), $0\le x_2\le5$, $x_1\ge0$.

Find. The optimal $(x_1,x_2)$ and maximum $z$ by the graphical corner-point method.

Approach. Plot each constraint boundary, shade the feasible region they jointly bound, identify its corner points, and evaluate $z$ at each (the LP optimum for a bounded feasible region always occurs at a vertex).

Feasible region (blue triangle) for Question 3(a): vertices $(2,4)$, $(1,5)$, and the optimum $(1.5,5)$ (red dot).

Find the region's corner points by intersecting active boundaries. The region is a triangle bounded by $x_1+x_2=6$ below-left, $4x_1+2x_2=16$ above-right, and $x_2=5$ on top: $$x_1+x_2=6\ \cap\ 4x_1+2x_2=16 \Rightarrow (2,4);\qquad x_1+x_2=6\ \cap\ x_2=5 \Rightarrow (1,5);\qquad 4x_1+2x_2=16\ \cap\ x_2=5 \Rightarrow (1.5,5)$$ (No feasible point exists below $x_2=4$: at $x_2=0$, $x_1+x_2\ge6$ needs $x_1\ge6$ while $4x_1\le16$ needs $x_1\le4$ — infeasible, so the region is exactly this small triangle.)
Evaluate $z=5x_1+6x_2$ at each vertex and pick the maximum:
Corner-point evaluation
Vertex $z=5x_1+6x_2$

(2, 4) 34

(1, 5) 35

(1.5, 5) 37.5

$$\boxed{x_1^*=1.5,\ x_2^*=5,\ z^*=37.5}$$

Corner-point evaluation
Vertex	$z=5x_1+6x_2$
(2, 4)	34
(1, 5)	35
(1.5, 5)	37.5

(b) The dual problem

Given. The primal above, with constraint types $\le$ (resource-1), $\ge$ (resource-2), and $\le$ (the upper bound $x_2\le5$); both $x_1,x_2\ge0$.

Find. The dual LP, stated but not solved.

Approach. For a max primal, assign one dual variable per primal constraint ($y_i\ge0$ for a $\le$ row, $y_i\le0$ for a $\ge$ row), build the dual objective from the primal RHS values, and build each dual constraint from a primal variable's column of coefficients, matched against that variable's own sign restriction.

Let $y_1$ (row 1, $4x_1+2x_2\le16$), $y_2$ (row 2, $3x_1+3x_2\ge18$), $y_3$ (row 3, $x_2\le5$) be the dual variables.

$$\boxed{\text{Minimize } w = 16y_1+18y_2+5y_3}$$ $$\text{subject to:}\quad 4y_1+3y_2\ \ge\ 5\ \ (x_1\text{'s column}),\qquad 2y_1+3y_2+y_3\ \ge\ 6\ \ (x_2\text{'s column})$$ $$y_1\ge0,\quad y_2\le0,\quad y_3\ge0$$

Final results — Question 3
Item	Value
(a) Optimal solution	$x_1=1.5,\ x_2=5$
(a) Maximum $z$	37.5
(b) Dual objective	Minimize $16y_1+18y_2+5y_3$
(b) Dual constraints	$4y_1+3y_2\ge5$; $2y_1+3y_2+y_3\ge6$

Topic: Graphical LP solution and primal–dual construction with mixed constraint types.

Key relations: Corner-point (extreme-point) theorem — an LP optimum over a bounded polyhedron occurs at a vertex; primal–dual sign pairing: a $\le$ primal row ⇒ $y_i\ge0$, a $\ge$ row ⇒ $y_i\le0$, and each primal variable's non-negativity forces its matching dual constraint to be $\ge$ (since the primal is a max problem).

Why this works: The feasible region of two linear inequalities in two variables is always a convex polygon, and a linear objective is optimized at an extreme point because it is monotone along any edge of the polygon; duality mirrors the primal's resource-allocation structure into a cost/shadow-price minimization with one variable per primal constraint.

Common pitfall: Forgetting to flip the dual variable's sign restriction for a $\ge$ row (treating $y_2$ as $\ge0$ instead of $\le0$), or missing that $x_2\le5$ is itself a full structural constraint requiring its own dual variable $y_3$, separate from $x_2\ge0$'s ordinary non-negativity.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 3 (graphical method) & ch. 6 (duality theory).

Question 3 of 10: Graphical LP and its Dual

Question 3: Graphical LP and its Dual (20 marks)

(a) Graphical solution

(b) The dual problem