Linear Programming

In this chapter: objective function, constraints and non-negativity restrictions, formulating a problem, graphing the feasible region, the corner point method, bounded and unbounded feasible regions, and problems with no solution or many optimal solutions.

The vocabulary

• Decision variables: the quantities we choose, usually x and y.
• Objective function: the linear expression Z = ax + by to be maximised or minimised.
• Constraints: linear inequalities (or equations) the variables must satisfy, such as x + 2y ≤ 10.
• Non-negativity restrictions: x ≥ 0, y ≥ 0, since quantities like the number of items cannot be negative.
• Feasible region: the common region of all constraints including non-negativity. Every point in it is a feasible solution; points outside are infeasible.
• Optimal solution: a feasible point that gives the maximum or minimum value of Z.

Formulating a problem

Word problems (diet, manufacturing, transportation, allocation) all follow the same pattern: name the variables with units, write the objective function, turn every limit on resources into an inequality, and add x, y ≥ 0. Arrange the data in a table first; it prevents mixing up the rows.

Worked example (formulation): A dealer sells tables at a profit of ₹3 hundred and chairs at ₹2 hundred each. A table needs 1 hour of carpentry and 3 hours of polishing; a chair needs 2 hours of carpentry and 1 hour of polishing. At most 10 hours of carpentry and 15 hours of polishing are available. Formulate the problem.
Solution: Let x tables and y chairs be made. Maximise Z = 3x + 2y (in ₹ hundred) subject to x + 2y ≤ 10 (carpentry), 3x + y ≤ 15 (polishing), x ≥ 0, y ≥ 0.

Graphing the feasible region

For each constraint, draw the line ax + by = c using its two intercepts. Test the origin: if (0, 0) satisfies the inequality, shade the side containing the origin; otherwise shade the other side. (If the line passes through the origin, test any other point.) With x, y ≥ 0, only the first quadrant is used. The feasible region is where all shadings overlap.

The corner point method

Fundamental theorem: if the feasible region R is bounded (it can be enclosed in a circle), the objective function Z = ax + by has both a maximum and a minimum value on R, and each occurs at a corner point (vertex) of R. The steps:

1. Draw the feasible region and find all its corner points, solving pairs of boundary equations where needed.
2. Evaluate Z at every corner point.
3. For a bounded region, the largest value is the maximum and the smallest is the minimum.

Worked example (solution): Solve the dealer's problem above.
Solution: The lines x + 2y = 10 and 3x + y = 15 meet where x + 2(15 − 3x) = 10, that is, −5x = −20, so x = 4 and y = 3. The corner points are O(0, 0), A(5, 0), B(4, 3) and C(0, 5). Z = 0, 15, 18 and 10 respectively. The maximum is Z = 18 at (4, 3): make 4 tables and 3 chairs for a profit of ₹1800.

If two adjacent corners give the same optimal value, every point on the edge joining them is also optimal, so the problem has infinitely many optimal solutions. The value of Z is still unique.

Unbounded feasible regions

When the region is unbounded, an optimal value may not exist. Evaluate Z at the corners as before, then check:

• Let M be the largest corner value. The maximum is M only if the open half-plane ax + by > M has no point in common with the feasible region. Otherwise Z has no maximum.
• Let m be the smallest corner value. The minimum is m only if the open half-plane ax + by < m has no point in common with the feasible region. Otherwise Z has no minimum.

Worked example: Minimise Z = 3x + 5y subject to x + 3y ≥ 3, x + y ≥ 2, x, y ≥ 0.
Solution: Corner points: (3, 0), (0, 2), and the intersection of x + 3y = 3 and x + y = 2, which is (3/2, 1/2). Z = 9, 10 and 7. The region is unbounded, so check the half-plane 3x + 5y < 7. Since 3x + 5y = 2(x + y) + (x + 3y) ≥ 2(2) + 3 = 7 at every feasible point, no feasible point satisfies 3x + 5y < 7. The minimum is Z = 7 at (3/2, 1/2). Z has no maximum here, because it grows without limit as x or y increases.

If the constraints have no common region at all (for example x + y ≤ 2 and x + y ≥ 5 with x, y ≥ 0), the problem has no feasible solution.

Common mistakes: (1) Shading the wrong side of a line because the origin test was skipped. (2) Missing a corner point, especially one on an axis. (3) Solving for the intersection of the wrong pair of lines, which gives a point outside the region. (4) Declaring a maximum for an unbounded region without the half-plane check. (5) Answering with the value of Z when the question asks for the values of x and y (or both).

JEE and MHT‑CET focus

• Identifying the correct feasible region from a set of inequalities, often from given graphs.
• Finding corner points and the optimal value quickly.
• Unbounded regions and the half-plane test; problems where the maximum or minimum does not exist.
• Recognising multiple optimal solutions when two corners give the same value.
• Formulating diet, manufacturing and allocation problems from words.

Practice questions