Linear Programming, Worked Examples (medium)

(a) The region is bounded by four lines: the axes $x=0$ and $y=0$, the line $x+y=8$, and the line $y=3x$. Find the corners by solving these boundaries in pairs, keeping only the crossings that satisfy every inequality.

$$y=3x,\; y=0 \;\Rightarrow\; (0,0)$$

$$x+y=8,\; y=0 \;\Rightarrow\; (8,0)$$

$$y=3x,\; x+y=8 \;\Rightarrow\; x+3x=8,\; 4x=8,\; x=2,\; y=6$$

So the region is the triangle with vertices $O(0,0)$, $B(8,0)$ and $C(2,6)$.

(b) Evaluate $k=5x+4y$ at each vertex:

$$\text{At } O(0,0):\quad k=5(0)+4(0)=0$$

$$\text{At } B(8,0):\quad k=5(8)+4(0)=40$$

$$\text{At } C(2,6):\quad k=5(2)+4(6)=10+24=34$$

(a) Translate each condition. 'At most 12 in total' caps the sum; 'pies at most twice the cakes' bounds $y$ by $2x$; 'at least 2 cakes' sets a floor on $x$.

$$x+y\le 12,\qquad y\le 2x,\qquad x\ge 2$$

(b) The corners of this region are where the boundary lines $x=2$, $y=0$, $y=2x$ and $x+y=12$ meet in pairs. Solve each pair and keep the points that obey every constraint:

$$x=2,\; y=0 \;\Rightarrow\; (2,0)$$

$$x=2,\; y=2x \;\Rightarrow\; y=4,\quad (2,4)$$

$$y=2x,\; x+y=12 \;\Rightarrow\; 3x=12,\; x=4,\; y=8,\quad (4,8)$$

$$x+y=12,\; y=0 \;\Rightarrow\; (12,0)$$

Now evaluate the profit $P=5x+9y$ at each corner:

$$\text{At }(2,0):\; P=5(2)+9(0)=10$$

$$\text{At }(2,4):\; P=5(2)+9(4)=10+36=46$$

$$\text{At }(4,8):\; P=5(4)+9(8)=20+72=92$$

$$\text{At }(12,0):\; P=5(12)+9(0)=60$$

The two $\ge$ constraints push the region away from the origin, so it stretches out to the upper right without an upper bound, there is no maximum, but a minimum exists at a corner. Find the corners by pairing the boundaries and keeping those that satisfy both inequalities.

$$x+2y=8,\; y=0 \;\Rightarrow\; (8,0)$$

$$2x+y=10,\; x=0 \;\Rightarrow\; (0,10)$$

The two slanted lines also cross. Take $x=8-2y$ from the first and substitute into the second:

$$2(8-2y)+y=10 \;\Rightarrow\; 16-3y=10 \;\Rightarrow\; y=2,\; x=4$$

So the corners of the region are $(8,0)$, $(4,2)$ and $(0,10)$. The other axis crossings each break the constraint they were not built from: $(5,0)$ gives $x+2y=5<8$, and $(0,4)$ gives $2x+y=4<10$, so neither is a vertex.

Now evaluate $C=3x+2y$:

$$\text{At }(8,0):\; C=3(8)+2(0)=24$$

$$\text{At }(4,2):\; C=3(4)+2(2)=12+4=16$$

$$\text{At }(0,10):\; C=3(0)+2(10)=20$$

A point lies in the feasible region only if it satisfies every inequality at once, not just one of them. Test each point against $2x+y\le 10$ and $x+3y\le 12$, all three points already have $x\ge 0$ and $y\ge 0$.

$$A(3,2):\quad 2(3)+2=8\le 10, \qquad 3+3(2)=9\le 12$$

Both limits hold for $A$, so it satisfies every constraint and lies inside the region.

$$B(5,3):\quad 2(5)+3=13>10 \qquad C(1,4):\quad 1+3(4)=13>12$$

$B$ already breaks the first constraint, and $C$ passes the first ($2(1)+4=6\le 10$) but breaks the second, so neither point is feasible.

(a) Use the two intercepts to form the equation: the line crosses the $x$-axis at $4$ and the $y$-axis at $6$, so write it in intercept form and clear the fractions.

$$\frac{x}{4}+\frac{y}{6}=1 \;\Rightarrow\; 3x+2y=12$$

(b) Since the origin lies inside the region, substitute $(0,0)$ into the left-hand side and compare it with $12$.

$$3(0)+2(0)=0, \quad 0<12$$

Substitute the vertex and the given maximum value into the objective function; this gives one equation in $q$.

$$3(6)+q(4)=38$$

$$18+4q=38 \;\Rightarrow\; 4q=20 \;\Rightarrow\; q=5$$

(a) The region is bounded by the axes, the line $x=8$ and the line $x+2y=12$. Pair the boundaries to find each vertex.

$$x=0,\;y=0 \;\Rightarrow\;(0,0) \qquad x=8,\;y=0 \;\Rightarrow\;(8,0)$$

$$x=8,\;x+2y=12 \;\Rightarrow\; y=2,\;(8,2) \qquad x=0,\;x+2y=12 \;\Rightarrow\; y=6,\;(0,6)$$

(b) Evaluate $K=x+2y$ at every vertex.

$$K(0,0)=0,\quad K(8,0)=8,\quad K(8,2)=8+4=12,\quad K(0,6)=0+12=12$$

$K$ reaches $12$ at both $(8,2)$ and $(0,6)$, and this is not a coincidence. $K=x+2y$ has exactly the same gradient as the boundary line $x+2y=12$, so every point along that edge already satisfies $x+2y=12$, which means $K=12$ all the way along it, not only at the two endpoints.

(a) Translate each condition. 'At least 12 in total' sets a floor on the sum; 'hygiene boxes at least half the food boxes' bounds $y$ below by $\frac{x}{2}$; 'at most 16 food boxes' caps $x$.

$$x+y\ge 12,\qquad x\le 2y,\qquad x\le 16$$

(b) The vertices of this region sit where $x+y=12$, $x=2y$ and $x=16$ meet in pairs, together with the axis $x=0$. Solve each relevant pair:

$$x=0,\;x+y=12 \;\Rightarrow\;(0,12) \qquad x+y=12,\;x=2y \;\Rightarrow\; 2y+y=12,\;y=4,\;x=8,\;(8,4)$$

$$x=2y,\;x=16 \;\Rightarrow\; y=8,\;(16,8)$$

Now evaluate the cost $C=8x+5y$ at each corner:

$$C(0,12)=8(0)+5(12)=60,\quad C(8,4)=64+20=84,\quad C(16,8)=128+40=168$$