Minimisation Problems

MATThe Graphical Method

A minimisation LPP seeks the smallest value of a linear cost function $Z = ax + by$ subject to constraints that are usually of the form $\ge$ (diet, fertiliser, nutrient requirements). These problems typically give an unbounded feasible region, so after finding the smallest corner value you must verify with the open half-plane test whether the minimum is actually attained.

ISC sets these as diet, mixture, and cost-allocation word problems.

Standard minimisation LPP

\text{Minimise } Z = ax + by \quad \text{subject to } \ge \text{ constraints, } x \ge 0,\ y \ge 0

Z

is total cost,

a,b

are per-unit costs, and the requirement constraints take the form

a_i x + b_i y \ge c_i

Corner-point evaluation

Z_{\min} = \min\{\, ax_i + by_i : (x_i, y_i) \text{ a corner point} \,\}

Evaluate

Z

at each vertex; the smallest value is the candidate minimum.

Unbounded-region test (for min)

ax + by < m \;\Rightarrow\; \text{no minimum exists}

With

m=Z

at the best corner, if the open half-plane

ax+by<m

has points common with the feasible region, no minimum exists; otherwise

m

is the minimum.

Boundary-line intersection

\begin{cases} a_1 x + b_1 y = c_1 \\ a_2 x + b_2 y = c_2 \end{cases}

Solve simultaneously to find the corner where two binding

\ge

constraint lines meet.

Requirement constraints ("at least") become $\ge$ inequalities; the origin $(0,0)$ usually does NOT satisfy them, so shade the side away from the origin.
The feasible region for a minimisation problem is typically unbounded (extends to infinity), so a minimum may or may not exist.
Compute $Z$ at every corner, then apply the open half-plane test $ax+by<m$ to confirm the minimum is genuinely attained.
If the open region $ax+by<m$ contains no feasible point, the smallest corner value $m$ is the true minimum.
On such an unbounded $\ge$ region a cost objective $Z$ usually has no maximum (it increases without bound), so only the minimum is sought.
Define variables and state the requirement units (vitamins, nitrogen, calcium) precisely before forming inequalities.
Always combine the requirement constraints with non-negativity $x\ge0,\ y\ge0$ to confine the region to the first quadrant.

Where the marks go

Shading toward the origin for a $\ge$ constraint, giving the wrong (often bounded) region.
Quoting the smallest corner value as the minimum for an unbounded region without performing the $ax+by<m$ verification.
Mixing up which food/brand supplies which nutrient, so a constraint coefficient is swapped.
Omitting one of several requirement constraints (e.g. only using two of three $\ge$ inequalities), losing a binding corner.

How the board asks it

Applicationdiet and mixture word problems
A diet for a sick person must contain at least $4000$ units of vitamins, $50$ units of minerals and $1400$ calories. Two foods $A$ and $B$ are available at a cost of $\text{Rs } 4$ and $\text{Rs } 3$ per unit respectively. One unit of food $A$ contains $200$ units of vitamins, $1$ unit of minerals and $40$ calories, while one unit of food $B$ contains $100$ units of vitamins, $2$ units of minerals and $40$ calories. Formulate this as an LPP and find graphically the minimum cost of the diet.
Diagram / graphrequirement constraints become $\ge$ inequalities
Solve the following LPP graphically: minimise $Z = 3x + 5y$ subject to $x + 3y \ge 3$ , $x + y \ge 2$ , $x \ge 0$ , $y \ge 0$ . Shade the feasible region clearly and mark its corner points.
Give reasonsthe open half-plane test $ax+by<m$
For the LPP minimise $Z = 5x + 7y$ on an unbounded feasible region whose smallest corner value is $m = 35$ , determine whether this minimum is actually attained by testing the open half-plane $5x + 7y < 35$ , and justify your conclusion.
Numericalcorner-point evaluation on an unbounded region
Minimise $Z = 200x + 500y$ subject to $x + 2y \ge 10$ , $2x + y \ge 14$ , $x \ge 0$ , $y \ge 0$ by the corner-point method, evaluating $Z$ at each vertex of the unbounded feasible region and confirming the minimum.
Numericalboundary-line intersection
Find the coordinates of the corner point of the feasible region formed by the intersection of the lines $2x + y = 8$ and $x + 2y = 10$ , and hence calculate the value of $Z = 60x + 80y$ at that point.

Practise this topic

PreviousCorner-Point Method — Maximisation NextApplied Problems — Manufacturing, Diet & Allocation

Written for Sublevo. Question text quoted anywhere in these notes is the Council’s and carries its year and paper; the board’s own diagrams are not reproduced.