Module 81: Linear programming · Lesson 81.2 · about 22 min
Linear programming: question types and traps
Every way entrance exams ask about linear programming: formulation of word problems, graphing constraints, identifying the feasible region, the corner point method, bounded and unbounded regions, multiple optimal solutions, empty regions, lattice points and the area of the region, each with a method and its trap.
Maths · Class 12 · about 22 minutes. Read Linear programming first. Here are the question types, worked examples and practice.
The question types
Worked examples
Example 1 (level 3, corner point). Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x, y ≥ 0. Solution. Corners: (0, 0), (2, 0), (0, 3), and the meeting point of the two lines, (20/19, 45/19). Z = 0, 10, 9 and 235/19 ≈ 12.37. Maximum 235/19 at (20/19, 45/19).
Example 2 (level 4, manufacturing). A unit of A needs 2 machine hours and 1 labour hour; a unit of B needs 1 machine hour and 2 labour hours. 10 machine hours and 11 labour hours are available. Profit is Rs 40 per A and Rs 50 per B. Solution. Maximise Z = 40x + 50y with 2x + y ≤ 10, x + 2y ≤ 11, x, y ≥ 0. Corners: (0, 0), (5, 0), (0, 5.5), (3, 4). Z = 0, 200, 275, 320. Make 3 of A and 4 of B for Rs 320.
Example 3 (level 4, unbounded with a tie). Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x, y ≥ 0. Solution. The two slanted lines meet at (0, 3), so the corners are (0, 3) and (6, 0), both giving Z = 6. The half-plane x + 2y < 6 contains no feasible point. Minimum 6 at every point of the segment from (0, 3) to (6, 0): infinitely many optimal points. There is no maximum.
Example 4 (level 5, parameter). For the region with corners (0, 0), (4, 0), (3, 2), (0, 3), find the condition on p, q > 0 for Z = px + qy to be maximised only at (3, 2). Solution. Need Z(3, 2) > Z(4, 0) and Z(3, 2) > Z(0, 3): 3p + 2q > 4p gives q > p/2, and 3p + 2q > 3q gives q < 3p. p/2 < q < 3p.
“If the region is unbounded, just report the best corner.” For a minimum on a region that runs away from the origin this is often right, but you must check: if the half-plane Z < m contains feasible points, Z has no minimum at all. An exam option “no optimal solution” is there for this reason.
- Corner
- a vertex of the feasible region; where two boundary lines meet and every constraint holds
- Half-plane test
- for a candidate minimum m on an unbounded region, check that ax + by < m has no feasible points
- Tie
- equal Z at two adjacent corners means the whole edge is optimal
- Physical meaning
- Sliding the profit line outwards, the last point of the region it touches is the best plan. If it leaves along an edge, every plan on that edge earns the same.
Practise
- “At least” means ≥, “at most” means ≤; always add x, y ≥ 0.
- Draw lines by intercepts; test the origin to choose the side.
- List every corner, including slanted-line intersections; evaluate Z at each.
- Unbounded region: confirm with the half-plane test before reporting an optimum.
- Two tying corners: infinitely many optimal solutions along the edge.
- Optimum only at a given corner: Z there must beat Z at both neighbours.
Check yourself
Sources
- KEAM, CUET and other state engineering entrance syllabi 2026: Linear programming; question patterns studied from published papers (no questions copied)
Your ticks stay in this browser. Save them as a file on the course home.
Updated 2026-11-22. Syllabus and exam patterns follow the official notices checked on 2026-11-22; they can change every year, so check the official exam website. All questions are original fibub work, not copied from past papers or books. Nothing you do here is sent anywhere.