Corner-Point Method — Maximisation · Linear Programming

MATThe Graphical Method

Corner-Point Method — Maximisation

A maximisation Linear Programming Problem (LPP) asks for the largest value of a linear objective function $Z = ax + by$ over a feasible region carved out by linear constraints. The corner-point method exploits the key theorem that the optimum of a linear function over a convex feasible region occurs at a corner point (vertex), so you only need to evaluate $Z$ at finitely many corners.

ISC examines this through manufacturing-profit word problems where you must formulate, graph, find corners, and pick the maximum.

Standard maximisation LPP

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

Z

is the objective (profit),

a,b

are per-unit profits, and

x,y\ge 0

are the non-negative decision variables.

Corner-point evaluation

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

Evaluate

Z

at every vertex

(x_i,y_i)

of the feasible region; the largest value is the maximum.

Intersection of two boundary lines

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

Solve simultaneously to locate the corner where two binding constraint lines meet.

Unbounded-region test (for max)

ax + by > M \;\Rightarrow\; \text{no maximum exists}

If the open half-plane

ax+by>M

(with

M=Z

at the best corner) shares points with an unbounded feasible region,

Z

has no maximum.

Step 1: define decision variables $x,y$ clearly; Step 2: write the objective $Z=ax+by$ ; Step 3: translate each resource limit into a $\le$ inequality; Step 4: add $x\ge 0,\ y\ge 0$ .
Draw each line $a x + b y = c$ by its intercepts, then shade the side satisfying the inequality (test the origin $(0,0)$ when the line does not pass through it).
The feasible region for a typical maximisation problem (all $\le$ constraints with $x,y\ge0$ ) is a bounded convex polygon.
List every corner point exactly: include the origin and axis-intercepts as well as line intersections, where these are feasible.
By the Corner Point Theorem the maximum over a bounded region is always attained at a corner; tabulate $Z$ at each corner and select the largest.
If two corners give the same maximum $Z$ , every point on the joining edge is optimal, so there are infinitely many optimal solutions.
Production quantities are usually required to be non-negative; state the optimal $x,y$ and the maximum profit explicitly with units (Rs).

Where the marks go

Shading the wrong side of a constraint line, which produces an incorrect feasible region and wrong corners.
Forgetting to test or include all corner points (especially axis intercepts and the origin), so the true maximum is missed.
For an unbounded region, assuming a maximum exists without applying the open half-plane $ax+by>M$ check.
Reading off the graph approximately instead of solving the two boundary lines simultaneously for exact corner coordinates.

How the board asks it

Applicationmanufacturing-profit formulation and solution
A company manufactures two types of toys, $A$ and $B$ . Each toy of type $A$ requires $3$ minutes on machine $I$ and $1$ minute on machine $II$ , while each toy of type $B$ requires $1$ minute on machine $I$ and $2$ minutes on machine $II$ . Machine $I$ is available for at most $60$ minutes and machine $II$ for at most $40$ minutes. If the profit is $5$ on each toy $A$ and $4$ on each toy $B$ (in Rs), formulate the LPP and find the number of toys of each type that should be produced to maximise the profit.
Diagram / graphfeasible region by intercepts and origin test
Solve the following LPP graphically: Maximise $Z = 3x + 4y$ subject to $x + y \le 4$ , $x \ge 0$ , $y \ge 0$ . Draw the feasible region, mark its corner points, and hence find the maximum value of $Z$ .
Numericalcorner points from simultaneous boundary lines
The feasible region of an LPP is bounded by the lines $2x + y = 10$ and $x + 3y = 15$ together with the coordinate axes. Find the coordinates of all the corner points of this region.
Numericalcorner point theorem; tabulate and select maximum
The corner points of a feasible region are $O(0,0)$ , $A(5,0)$ , $B(3,4)$ and $C(0,5)$ . For the objective function $Z = 6x + 9y$ , evaluate $Z$ at each corner point and hence determine the point at which $Z$ is maximum and the maximum value of $Z$ .
Give reasonsinfinitely many optimal solutions along an edge
For a maximisation LPP the objective function $Z = 4x + 8y$ attains the value $32$ at the two corner points $B(2,3)$ and $C(8,0)$ of a bounded feasible region. State, with reasons, how many optimal solutions the problem has and describe the set of all such solutions.
Multiple choicecorner point theorem
The maximum value of $Z = 11x + 7y$ subject to the constraints $2x + y \le 6$ , $x \le 2$ , $x \ge 0$ , $y \ge 0$ occurs at the corner point: (a) $(0,0)$ (b) $(2,0)$ (c) $(2,2)$ (d) $(0,6)$ .

Practise this topic

PreviousGraphical Method & the Feasible Region NextMinimisation Problems

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.