Optimising: the corner-point and sliding-line methods

The corner-point method

• The theorem: a linear objective attains its optimum at a corner of the feasible region.
• The method, in four steps:
  • Find every corner exactly, by solving pairs of boundary equations.
  • Evaluate the objective function at each corner, showing the substitution.
  • Select the largest value (for a maximum) or the smallest (for a minimum).
  • State the answer in context, with the decision and the objective value.
• Set the evaluation out as a table. It makes the comparison checkable and it is what assessors look for:

• Show the arithmetic, not just the totals. A single mis-multiplied corner changes the answer, and visible working lets it be found.

The sliding-line method

• The alternative, and the one that explains why the corner method works.
• The objective $P = 40x + 30y$ defines a family of parallel lines, one for each value of $P$:

$$40x + 30y = k \quad \Rightarrow \quad y = -\frac{4}{3}x + \frac{k}{30}$$

• Every line in the family has the same gradient, here $-\frac{4}{3}$. Only the intercept changes.
• The method:
  • Draw one line of the family — pick a convenient $k$, such as $k = 1200$, giving intercepts $(30, 0)$ and $(0, 40)$.
  • Slide it parallel across the region, in the direction that increases $P$.
  • The last corner it touches before leaving the region is the optimum.

• Which way does $P$ increase? For an objective with positive coefficients, $P$ increases away from the origin. Test two lines if unsure — evaluate $P$ at two points and see which is larger.
• Use a ruler and keep the gradient exact. A slightly wrong gradient picks the wrong corner, and the error is invisible in the final number.

Which method to use

• Do both when time allows. The corner-point method gives the number; the sliding line confirms it and shows the reasoning. Agreement between them is a strong check.

Multiple optimal solutions

• When the objective line is PARALLEL to a binding edge, every point on that edge is optimal.
• Detect it by comparing gradients: the objective $px + qy$ has gradient $-\frac{p}{q}$; a constraint $ax + by = c$ has gradient $-\frac{a}{b}$. Equal gradients mean a possible tie.
• It shows up in the corner table as two corners with the same value.
• Report the whole edge, not just one end: "any plan on the line from $(20,60)$ to $(0,80)$ gives the same profit". In context this is good news — the business gets to choose on other grounds.

Minimisation problems

• The method is identical; only the selection changes — take the smallest corner value.
• Minimisation contexts are usually about cost: feed mixes, transport, staffing.
• The constraints are usually $\geq$ ("must supply at least"), so the region is often unbounded above — which is fine, because the minimum still sits at a corner on the lower boundary.

Reporting the answer

• State the decision, the objective value and the binding constraints:
  • "Make 20 trays of Halloumi and 60 of Feta, for a weekly profit of $2,600."
  • "Both the vat and the packing line are fully used; cold storage has 20 trays of spare capacity."
• Say what the business should do with that information. The binding constraints are the ones worth expanding.