Linear Programming by the Corner-Point Method, Worked Solutions

Ques­tion 1: Max­imise over a bounded region#

The prob­lem#

Max­imise $Z = 3x + 2y$ sub­ject to $x + 2y \le 10$, $3x + y \le 15$, $x, y \ge 0$.

Under­stand­ing the prob­lem#

We want the largest value of $Z$ among all points $(x, y)$ that sat­isfy all four inequal­i­ties. $x, y \ge 0$ keeps us in the first quad­rant.

The idea#

Use the cor­ner-point method. The region will be bounded (a closed poly­gon), so the max­i­mum is sim­ply the largest value of $Z$ at the cor­ners.

Step-by-step solu­tion#

Step 1. Draw the bound­ary lines. For each "$\le$" con­straint, find where its line meets the axes.

• $x + 2y = 10$ meets the axes at $(10, 0)$ and $(0, 5)$.
• $3x + y = 15$ meets the axes at $(5, 0)$ and $(0, 15)$.

Step 2. Shade the fea­si­ble region. Test the ori­gin: $0 \le 10$ and $0 \le 15$ are true, so each region is the side of its line con­tain­ing $(0, 0)$. The fea­si­ble region is the quadri­lat­eral in the first quad­rant below both lines.

Step 3. Find the cor­ners. Three are on the axes: $(0, 0)$, $(5, 0)$ (where $3x + y = 15$ meets the $x$-axis, it comes before $(10, 0)$), and $(0, 5)$ (where $x + 2y = 10$ meets the $y$-axis, it comes before $(0, 15)$). The fourth is where the two lines cross:

$$\begin{aligned} x + 2y &= 10 \\ 3x + y &= 15. \end{aligned}$$

From the sec­ond, $y = 15 - 3x$. Sub­sti­tute: $x + 30 - 6x = 10$, so $5x = 20$, $x = 4$, $y = 3$. Cor­ner $(4, 3)$.

Step 4. Eval­u­ate $Z = 3x + 2y$.

Step 5. Decide. The region is bounded, so the largest value, $18$, is the max­i­mum.

Check­ing the answer#

$(4, 3)$ sat­is­fies $4 + 6 = 10 \le 10$ and $12 + 3 = 15 \le 15$, it uses both lim­its exactly, as an inter­sec­tion cor­ner should.

Answer#

Max­i­mum $Z = 18$ at $x = 4$, $y = 3$.

Ques­tion 2: Min­imise over a tri­an­gle#

The prob­lem#

Min­imise $Z = 2x + 3y$ sub­ject to $x + y \ge 5$, $x \le 4$, $y \le 4$, $x, y \ge 0$.

Under­stand­ing the prob­lem#

Now we want the small­est $Z$. The con­straint $x + y \ge 5$ keeps us away from the ori­gin; $x \le 4$ and $y \le 4$ cap each vari­able.

The idea#

Graph, find the cor­ners, eval­u­ate. Check whether the region is bounded.

Step-by-step solu­tion#

Step 1. Lines. $x + y = 5$ through $(5, 0)$ and $(0, 5)$; the ver­ti­cal line $x = 4$; the hor­i­zon­tal line $y = 4$.

Step 2. Region. For $x + y \ge 5$ the ori­gin fails ($0 \ge 5$ is false), so we take the side away from the ori­gin. Together with $x \le 4$ (left of the ver­ti­cal line) and $y \le 4$ (below the hor­i­zon­tal line), the region is a small tri­an­gle, bounded.

Step 3. Cor­ners.

• $x = 4$ and $x + y = 5$: $(4, 1)$.
• $x = 4$ and $y = 4$: $(4, 4)$.
• $y = 4$ and $x + y = 5$: $(1, 4)$.

Step 4. Eval­u­ate $Z = 2x + 3y$.

Step 5. Decide. Bounded region, so the min­i­mum is the small­est value, $11$.

Check­ing the answer#

$(4, 1)$: $4 + 1 = 5 \ge 5$, $4 \le 4$, $1 \le 4$, fea­si­ble. Since $y$ costs more ($3$ per unit) than $x$ ($2$), it makes sense to use as much $x$ as allowed.

Answer#

Min­i­mum $Z = 11$ at $x = 4$, $y = 1$.

Ques­tion 3: A region with five cor­ners#

The prob­lem#

Max­imise $Z = 5x + 4y$ sub­ject to $x + y \le 7$, $x - y \le 1$, $y \le 5$, $x, y \ge 0$.

Under­stand­ing the prob­lem#

Three con­straints plus the axes. The line $x - y = 1$ is slanted upwards, so the region has more cor­ners than usual. Find them care­fully.

The idea#

Cor­ner-point method on a bounded region.

Step-by-step solu­tion#

Step 1. Lines.

• $x + y = 7$: through $(7, 0)$ and $(0, 7)$.
• $x - y = 1$: through $(1, 0)$ and $(4, 3)$; it rises to the right.
• $y = 5$: hor­i­zon­tal.

Step 2. Region. The ori­gin sat­is­fies all three ($0 \le 7$, $0 \le 1$, $0 \le 5$), so each time take the side con­tain­ing the ori­gin: below $x + y = 7$, to the left of/above $x - y = 1$, below $y = 5$.

Step 3. Cor­ners. Go round the bound­ary start­ing at the ori­gin.

• $(0, 0)$.
• Along the $x$-axis until $x - y = 1$: $(1, 0)$.
• Along $x - y = 1$ until it meets $x + y = 7$: adding, $2x = 8$, $x = 4$, $y = 3$: $(4, 3)$.
• Along $x + y = 7$ until $y = 5$: $x = 2$: $(2, 5)$.
• Along $y = 5$ back to the $y$-axis: $(0, 5)$.

Step 4. Eval­u­ate $Z = 5x + 4y$.

Step 5. Decide. Bounded region; the max­i­mum is $32$.

Check­ing the answer#

$(4, 3)$: $7 \le 7$, $1 \le 1$, $3 \le 5$ ✓. The run­ner-up $(2, 5)$ gives $30$, close but smaller.

Answer#

Max­i­mum $Z = 32$ at $x = 4$, $y = 3$.

Ques­tion 4: An objec­tive with no max­i­mum#

The prob­lem#

Show that $Z = x + y$ has no max­i­mum value sub­ject to $x - y \le 1$, $x + y \ge 2$, $x, y \ge 0$.

Under­stand­ing the prob­lem#

We must prove that $Z$ can be made as large as we like while stay­ing fea­si­ble, so no largest value exists.

The idea#

Find the fea­si­ble region; if it is unbounded in a direc­tion in which $Z$ increases, there is no max­i­mum. The clean­est proof is to give an explicit fam­ily of fea­si­ble points on which $Z$ grows with­out limit.

Step-by-step solu­tion#

Step 1. Region. $x + y \ge 2$ is the side of the line $x + y = 2$ away from the ori­gin. $x - y \le 1$ means $y \ge x - 1$: on or above the line $y = x - 1$. With $x, y \ge 0$, the region is open upwards, it con­tains every point with large $y$, so it is unbounded.

Step 2. Cor­ners. $(0, 2)$ (on the $y$-axis), and the inter­sec­tion of $x + y = 2$ with $x - y = 1$: $\displaystyle x = \tfrac32$, $\displaystyle y = \tfrac12$. At these $Z = 2$, these give the min­i­mum, not a max­i­mum.

Step 3. A fam­ily of fea­si­ble points. Take $(t, t)$ with $t \ge 1$. Check each con­straint:

$$t - t = 0 \le 1, \qquad t + t = 2t \ge 2, \qquad t \ge 0.$$

All hold, so every such point is fea­si­ble.

Step 4. Eval­u­ate $Z$ on the fam­ily. $Z = t + t = 2t$, which exceeds any num­ber $M$ once $\displaystyle t > \tfrac{M}{2}$.

Step 5. Con­clude. What­ever value $M$ we pro­pose as a max­i­mum, a fea­si­ble point gives a larger $Z$. So $Z$ has no max­i­mum. $\blacksquare$

Check­ing the answer#

With $t = 100$: $(100, 100)$ is fea­si­ble and $Z = 200$; with $t = 1000$, $Z = 2000$, no ceil­ing.

Answer#

The region is unbounded and the fea­si­ble points $(t, t)$, $t \ge 1$, give $Z = 2t \to \infty$; hence $Z$ has no max­i­mum.

Ques­tion 5: Fans and lamps, a deal­er's profit#

The prob­lem#

A dealer has ₹$50{,}000$ to invest and space for at most $40$ items. A fan costs ₹$1{,}000$ and gives a profit of ₹$250$; a lamp costs ₹$1{,}500$ and gives a profit of ₹$300$. How many of each should she buy to max­imise her profit?

Under­stand­ing the prob­lem#

Two lim­its: money (₹$50{,}000$) and space ($40$ items). Two choices: num­ber of fans and num­ber of lamps. The goal: great­est total profit.

The idea#

For­mu­late as an LPP, then use the cor­ner-point method.

Step-by-step solu­tion#

Step 1. Deci­sion vari­ables. Let $x$ = num­ber of fans and $y$ = num­ber of lamps, $x, y \ge 0$.

Step 2. Objec­tive. Profit $Z = 250x + 300y$, to be max­imised.

Step 3. Con­straints.

• Money: $1000x + 1500y \le 50{,}000$, which on divid­ing by $500$ becomes $2x + 3y \le 100$.
• Space: $x + y \le 40$.

Step 4. Cor­ners. $2x + 3y = 100$ meets the axes at $(50, 0)$ and $\displaystyle \left(0, \tfrac{100}{3}\right)$; $x + y = 40$ at $(40, 0)$ and $(0, 40)$. The bind­ing lim­its are $(40, 0)$ on the $x$-axis and $\displaystyle \left(0, \tfrac{100}{3}\right)$ on the $y$-axis. The lines cross where

$$2x + 3y = 100, \quad x + y = 40 \;\Longrightarrow\; 2x + 3(40 - x) = 100 \;\Longrightarrow\; x = 20,\ y = 20.$$

Step 5. Eval­u­ate $Z$.

Step 6. Decide. The region is bounded; the max­i­mum is ₹$11{,}000$ at $(20, 20)$, con­ve­niently whole num­bers.

Check­ing the answer#

Cost: $20 \times 1000 + 20 \times 1500 = 50{,}000$ ✓ (all the money). Items: $40$ ✓ (all the space). Profit: $5000 + 6000 = 11{,}000$ ✓.

Answer#

Buy $20$ fans and $20$ lamps, for a max­i­mum profit of ₹$11{,}000$.

Ques­tion 6: Allo­cat­ing land between wheat and gram#

The prob­lem#

A farmer has $30$ hectares to plant with wheat and gram. Wheat earns ₹$20{,}000$ per hectare and gram ₹$15{,}000$ per hectare. Wheat needs $4$ work­ers per hectare and gram $2$, and $100$ work­ers are avail­able. How should the land be allo­cated to max­imise earn­ings?

Under­stand­ing the prob­lem#

Lim­its: land ($30$ ha) and labour ($100$ work­ers). Choices: hectares of wheat and of gram. Goal: max­i­mum earn­ings.

The idea#

For­mu­late, then cor­ner-point method.

Step-by-step solu­tion#

Step 1. Vari­ables. $x$ = hectares of wheat, $y$ = hectares of gram, $x, y \ge 0$.

Step 2. Objec­tive. $Z = 20{,}000x + 15{,}000y$ (max­imise).

Step 3. Con­straints. Land: $x + y \le 30$. Labour: $4x + 2y \le 100$, i.e. $2x + y \le 50$.

Step 4. Cor­ners. $x + y = 30$ meets the axes at $(30, 0)$, $(0, 30)$; $2x + y = 50$ at $(25, 0)$, $(0, 50)$. Bind­ing axis points: $(25, 0)$ and $(0, 30)$. Inter­sec­tion: sub­tract $x + y = 30$ from $2x + y = 50$ to get $x = 20$, then $y = 10$. Cor­ners: $(0, 0)$, $(25, 0)$, $(20, 10)$, $(0, 30)$.

Step 5. Eval­u­ate $Z$.

Step 6. Decide. The max­i­mum is ₹$5{,}50{,}000$ at $(20, 10)$.

Check­ing the answer#

Land $20 + 10 = 30$ ✓; work­ers $80 + 20 = 100$ ✓; earn­ings $4{,}00{,}000 + 1{,}50{,}000 = 5{,}50{,}000$ ✓.

Answer#

Plant $20$ hectares of wheat and $10$ hectares of gram, earn­ing ₹$5{,}50{,}000$.

Ques­tion 7: The cheap­est vit­a­min mix­ture#

The prob­lem#

A mix­ture must con­tain at least $10$ units of vit­a­min A and $12$ units of vit­a­min B. Food P has $2$ units of A and $3$ of B per packet and costs ₹$5$; food Q has $2$ units of A and $2$ of B per packet and costs ₹$4$. Find the cheap­est mix­ture.

Under­stand­ing the prob­lem#

Now the con­straints are "at least" ($\ge$) and the goal is min­i­mum cost. Such regions are usu­ally unbounded, so the extra half-plane check is needed.

The idea#

For­mu­late, find cor­ners, eval­u­ate, then con­firm the can­di­date min­i­mum with the half-plane test (as in Exam­ple 2 and Exam­ple 4).

Step-by-step solu­tion#

Step 1. Vari­ables. $x$ = pack­ets of P, $y$ = pack­ets of Q, $x, y \ge 0$.

Step 2. Objec­tive. Cost $Z = 5x + 4y$ (min­imise).

Step 3. Con­straints. Vit­a­min A: $2x + 2y \ge 10$, i.e. $x + y \ge 5$. Vit­a­min B: $3x + 2y \ge 12$.

Step 4. Region. The ori­gin fails both, so the region lies on the far side of both lines, unbounded, away from the ori­gin.

Step 5. Cor­ners.

• On the $y$-axis ($x = 0$): need $y \ge 5$ and $y \ge 6$, so $(0, 6)$.
• On the $x$-axis ($y = 0$): need $x \ge 5$ and $x \ge 4$, so $(5, 0)$.
• Inter­sec­tion: sub­tract $2x + 2y = 10$ from $3x + 2y = 12$: $x = 2$, then $y = 3$. Cor­ner $(2, 3)$.

Step 6. Eval­u­ate $Z = 5x + 4y$.

Step 7. Half-plane check. The can­di­date min­i­mum is $22$. Draw $5x + 4y = 22$; it passes through $(2, 3)$. Its slope $\displaystyle -\tfrac54$ lies between the slopes of the two bound­ary lines ($\displaystyle -\tfrac32$ and $-1$), so it touches the region only at $(2, 3)$, and the open half-plane $5x + 4y < 22$ (the side towards the ori­gin) con­tains no fea­si­ble point. So $22$ is the true min­i­mum.

Check­ing the answer#

At $(2, 3)$: vit­a­min A $= 4 + 6 = 10$ ✓, vit­a­min B $= 6 + 6 = 12$ ✓, cost $10 + 12 = 22$ ✓.

Answer#

Use $2$ pack­ets of P and $3$ pack­ets of Q; the min­i­mum cost is ₹$22$.

Com­mon mis­take to avoid#

For an unbounded region, stop­ping at "the small­est cor­ner value" with­out the half-plane check. Here it con­firms the answer, but in Ques­tion 4 the same short­cut would have been wrong.

Ques­tion 8: Why the opti­mum is at a cor­ner#

The prob­lem#

Explain why the opti­mum of a lin­ear objec­tive func­tion over a bounded poly­gon must occur at a cor­ner.

Under­stand­ing the prob­lem#

This is a rea­son­ing ques­tion. You must jus­tify the cor­ner-point the­o­rem in words, using a geo­met­ric pic­ture.

The idea#

The points where $Z = ax + by$ takes a fixed value $k$ form a straight line. Chang­ing $k$ slides this line par­al­lel to itself. The opti­mum is the extreme value of $k$ for which the line still touches the region.

Step-by-step solu­tion#

Step 1. Level lines. For each num­ber $k$, the points with $Z = k$ lie on the line $ax + by = k$. All these lines are par­al­lel (same slope $\displaystyle -\tfrac{a}{b}$).

Step 2. Slid­ing. Increas­ing $k$ moves the line steadily in one direc­tion across the plane. $Z$ takes the value $k$ some­where in the fea­si­ble region exactly when the line $ax + by = k$ meets the region.

Step 3. The last con­tact. Because the region is a bounded poly­gon, as we keep increas­ing $k$ the line even­tu­ally leaves it. The max­i­mum of $Z$ is the value of $k$ at the last moment of con­tact.

Step 4. Where that con­tact hap­pens. At the last moment, the whole poly­gon lies on one side of the line and the line just touches its edge. A straight line touch­ing a con­vex poly­gon from out­side touches it either at a sin­gle ver­tex or along a whole edge, and an edge ends in two ver­tices. Either way, a cor­ner attains the opti­mum.

Step 5. The same argu­ment with decreas­ing $k$ gives the min­i­mum. $\blacksquare$

Check­ing the answer#

In Ques­tion 1, the level line $3x + 2y = 18$ touches the region only at $(4, 3)$, exactly the cor­ner that gave the max­i­mum.

Answer#

$Z$ is con­stant along the par­al­lel lines $ax + by = k$; slid­ing such a line across the bounded region, the last point it touches (for a max­i­mum) or the first (for a min­i­mum) is a ver­tex, or an edge whose end­points are ver­tices, so the opti­mum occurs at a cor­ner.