Linear Programming: Complete Concepts and Practice

Big picture

A furniture maker has limited machine hours and wants the most profit. A dietician wants the cheapest diet that still meets nutrition needs. Both are optimisation problems: make something as large or as small as possible while staying within limits.

When the quantity to optimise and every limit are linear expressions in two variables, the problem is a linear programming problem (LPP). The board exam always asks one LPP: formulate it (if given in words), draw the region, list the corner points and pick the best one. This chapter shows every step.

Learning goals

• Identify decision variables, the objective function and constraints, and formulate an LPP from a word problem.

• Draw the feasible region of up to three non-trivial constraints.

• Apply the corner point method to find maximum and minimum values.

• Handle unbounded regions correctly, and recognise multiple optima and infeasible problems.

Core ideas

1. Terminology

2. Formulating an LPP

Example. A workshop makes chairs and tables. A chair needs 2 hours on machine A and 1 hour on machine B. A table needs 1 hour on machine A and 2 hours on machine B. Each machine is available for at most 12 hours a day. The profit is ₹40 per chair and ₹50 per table. How many of each should be made to maximise profit?

Let x = number of chairs, y = number of tables.
Maximise   Z = 40x + 50y
subject to 2x + y  <= 12   (machine A)
            x + 2y <= 12   (machine B)
            x >= 0, y >= 0

Always define the variables in words before writing anything else.

3. Drawing the feasible region

1. Replace each inequality by an equation and draw the line using its intercepts. For 2x + y = 12, the intercepts are (6, 0) and (0, 12).

2. Test a point not on the line, usually the origin (0, 0). For 2x + y ≤ 12: 0 ≤ 12 is true, so the region is the side containing the origin.

3. Shade the region common to all constraints (in the first quadrant, because of x, y ≥ 0).

4. Find the corner points: intercepts on the axes and intersections of lines (solve the two equations together).

4. The corner point method

Theorem. If the feasible region is bounded (enclosed by a polygon), the objective function has both a maximum and a minimum, and each occurs at a corner point.

Steps: find all corner points, evaluate Z at each, and pick the largest (maximum) or smallest (minimum).

Solving the workshop problem. Lines 2x + y = 12 and x + 2y = 12 intersect where: multiply the second by 2, 2x + 4y = 24; subtract the first: 3y = 12, so y = 4 and x = 4.

Make 4 chairs and 4 tables for a maximum profit of ₹360.

A second bounded example. Maximise Z = 3x + 5y subject to x + y ≤ 8, x + 3y ≤ 12, x, y ≥ 0.

Corner points: (0, 0), (8, 0), (0, 4), and the intersection of x + y = 8 and x + 3y = 12, which gives 2y = 4, y = 2, x = 6.

Maximum Z = 28 at (6, 2).

5. Unbounded feasible regions

If the feasible region is unbounded (extends without limit), an optimum may or may not exist. The test:

• Let M be the largest value of Z at the corner points. M is the maximum 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 value at the corners. m is the minimum only if the open half-plane ax + by < m has no point in common with the feasible region.

Example. Minimise Z = 2x + 3y subject to x + y ≥ 5, x + 2y ≥ 6, x, y ≥ 0.

The region lies above both lines (the origin fails both inequalities), so it is unbounded. Corner points: (0, 5) on the y-axis from x + y = 5, (6, 0) on the x-axis from x + 2y = 6, and the intersection of the two lines: subtracting gives y = 1, x = 4.

Draw 2x + 3y < 11. This open half-plane lies below the line 2x + 3y = 11 and has no point in common with the feasible region, so the minimum is 11 at (4, 1).

Notice that for the same region, Z has no maximum: you can make x and y as large as you like, so Z grows without limit.

6. Special cases

Example of multiple optima: maximise Z = x + y over the workshop region but with the constraint x + y ≤ 8 included as an edge; if two corners such as (6, 2) and (8, 0) both give Z = 8, every point between them is optimal.

7. Types of problems you may meet

• Manufacturing problems: maximise profit subject to machine hours, labour and raw material limits.

• Diet problems: minimise cost subject to minimum requirements of nutrients.

• Allocation problems: distribute limited resources (land, money) to maximise return.

The method is the same for all: define variables, write Z and constraints, draw, find corners, evaluate, and check unboundedness.

A reliable problem-solving routine

1. Define the decision variables in words.

2. Write the objective function and all constraints, including x, y ≥ 0.

3. Draw each line from its intercepts and shade the correct side using a test point.

4. Find every corner point, solving intersections algebraically.

5. Evaluate Z at each corner in a table.

6. If the region is unbounded, apply the half-plane test before declaring the optimum.

7. Write the final answer in words, in the context of the problem.

Connections that matter

• Linear inequalities (Class 11) teaches how to graph and shade inequalities.

• Straight lines (Class 11) gives intercepts and intersection of lines.

• Economics: producer behaviour uses the same idea of choosing the best output under constraints.

Common mistakes

• Shading the wrong side of a line; always test a point.

• Missing a corner point, especially one on an axis.

• Declaring a maximum for an unbounded region without the half-plane test.

• Writing ≥ instead of ≤ for "at most" (≤) and "at least" (≥).

• Forgetting the non-negativity constraints.

Revision checklist

• I can formulate an LPP from a word problem.

• I can draw a feasible region and find its corner points.

• I can apply the corner point method to bounded regions.

• I can use the half-plane test for unbounded regions.

• I can recognise multiple optima, unbounded solutions and infeasible problems.