• Practice
  • About 17 min
  • 5 practice questions

Multiple optima, infeasible problems and whole-number answers

Spot multiple optimal solutions from the slopes and describe all of them, show quickly that a problem is infeasible, and find the best whole-number plan without the rounding trap.

If something looks wrong, please tell us.

Three special outcomes appear again and again in exam questions: a whole edge of optimal points, constraints that contradict each other, and answers that must be whole numbers (tables, buses, packets). Each has a quick test and a classic wrong answer, and this lesson covers all three.

Multiple optimal solutions

If the objective is parallel to an edge of the region, that is, if px + qy is a multiple of the edge's expression, and that edge is on the optimal side, then every point of the edge is optimal. In multiple-choice questions, look for an objective whose coefficients are proportional to a constraint's.

Worked example 1: a whole edge of the lamp region

On the lamp region (x + 3y ≤ 24, 3x + 2y ≤ 24, x + y ≤ 10, x, y ≥ 0), maximise Z = 6x + 4y. Note that Z = 2(3x + 2y) ≤ 2 × 24 = 48 everywhere in the region. The corners (4, 6) and (8, 0) lie on 3x + 2y = 24 and give 48; the others give 46 at (3, 7), 32 at (0, 8) and 0 at the origin. So the maximum is 48, at every point of the segment from (4, 6) to (8, 0). All of them can be written as (4 + 4t, 6 − 6t) with 0 ≤ t ≤ 1; t = 1/2 gives (6, 3), and 36 + 12 = 48.

A tie between two adjacent corners means the whole edge joining them is optimal: infinitely many solutions, not two.

Infeasible problems: prove it in one line

To show that a ≤ constraint and a ≥ constraint clash, find the largest possible value of the ≥ expression on the ≤ region. If it falls short, the problem is infeasible. Worked example 2: x + 2y ≤ 6, 3x + 4y ≥ 20, x, y ≥ 0. On the triangle (0, 0), (6, 0), (0, 3), the largest value of 3x + 4y is 18, at (6, 0). Since 18 < 20, no point satisfies both: no feasible solution. In one line: 3x + 4y = 3(x + 2y) − 2y ≤ 18.

Whole-number answers: the rounding trap

When the variables count whole objects and the LP optimum is fractional, rounding can fail in two ways: the rounded point may be infeasible, or it may be feasible but not the best. Search the whole-number points near the LP optimum and compare.

Worked example 3: a fractional optimum

Maximise Z = 3x + 2y subject to 2x + 3y ≤ 12, 4x + y ≤ 10, x, y ≥ 0, with x and y whole numbers. The lines meet where y = 10 − 4x and 2x + 30 − 12x = 12, so x = 9/5 and y = 14/5. The corners (0, 0), (5/2, 0), (9/5, 14/5) and (0, 4) give Z = 0, 7.5, 11 and 8, so the LP maximum is 11 at (1.8, 2.8).

Whole-number point2x + 3y ≤ 12?4x + y ≤ 10?Z = 3x + 2y
(2, 3) (rounded)13: no11: noinfeasible
(1, 2) (rounded down)8: yes6: yes7
(1, 3)11: yes7: yes9
(2, 2)10: yes10: yes10
(0, 4)12: yes4: yes8

The best whole-number plan is (2, 2) with Z = 10. Rounding to the nearest point gave an infeasible plan, and rounding down gave only 7.

Key takeaways: an objective proportional to an edge's constraint signals infinitely many optima along that edge. Prove infeasibility by bounding one constraint's expression over the other's region. For whole-number problems, test nearby lattice points, and never just round the LP answer.

Check your understanding

  1. 1. Minimise Z = 6x + 4y subject to 3x + 2y ≥ 12, x + 2y ≥ 8, x, y ≥ 0. Which statement is correct?

    1. The minimum is 24, only at (2, 3)
    2. The minimum is 24, only at (0, 6)
    3. The minimum is 24, at every point of the segment joining (0, 6) and (2, 3)
    4. There is no minimum because the region is unbounded
    Show answer

    Answer: C. Corners (0, 6), (2, 3), (8, 0) give 24, 24, 48. Also Z = 2(3x + 2y) ≥ 24 everywhere in the region, so 24 is the minimum. It is attained wherever 3x + 2y = 12 inside the region, which is the whole edge from (0, 6) to (2, 3).

  2. 2. Together with x ≥ 0 and y ≥ 0, which system has NO feasible point?

    1. x + 2y ≤ 4 and 2x + 3y ≥ 10
    2. x + 2y ≤ 4 and 2x + 3y ≥ 8
    3. x + 2y ≥ 4 and 2x + 3y ≤ 10
    4. x − y ≥ 2 and x + y ≤ 4
    Show answer

    Answer: A. On x + 2y ≤ 4 (corners (0, 0), (4, 0), (0, 2)) the largest value of 2x + 3y is 8, at (4, 0). So 2x + 3y ≥ 10 is impossible there, but 2x + 3y ≥ 8 is just possible, at (4, 0). The third system contains (4, 0) and the fourth contains (2, 0).

  3. 3. Maximise Z = x + y subject to 3x + 2y ≤ 12, x + 3y ≤ 9, x, y ≥ 0, where x and y must be whole numbers. What is the maximum?

    1. 5
    2. 4
    3. 33/7
    4. 3
    Show answer

    Answer: B. The LP optimum is at (18/7, 15/7) with Z = 33/7 ≈ 4.71, which is not a whole-number point. Rounding Z up to 5 needs, for example, (3, 2) or (2, 3), but 3(3) + 2(2) = 13 > 12 and 2 + 3(3) = 11 > 9, and no other whole-number point with x + y = 5 is feasible either. (2, 2) and (3, 1) are feasible and give 4, so the integer maximum is 4.

  4. 4. The LP optimum of a maximisation problem is at (2.6, 3.7), but x and y must be whole numbers. What is the correct way to proceed?

    1. Round to (3, 4); it is always the integer optimum
    2. Round down to (2, 3); rounding down is always optimal
    3. Check the feasible whole-number points near the optimum and evaluate Z at each
    4. Take the LP value of Z and round it down; that is the integer answer
    Show answer

    Answer: C. Rounding to the nearest point may leave the feasible region, and rounding down keeps feasibility but can miss a better point. The integer maximum is never more than the LP maximum, but it can be smaller than the LP value rounded down. The safe method is to list the feasible whole-number points near the optimum (and along the edges near it) and compare Z.

  5. 5. On the region 2x + y ≥ 6, x + y ≥ 4, x, y ≥ 0 (corners (0, 6), (2, 2), (4, 0)), how many points give the minimum of Z = x + y?

    1. Exactly one
    2. Exactly two
    3. None, the region is unbounded
    4. Infinitely many
    Show answer

    Answer: D. Z = 6, 4, 4 at the corners, and x + y ≥ 4 everywhere in the region, so the minimum is 4. It is attained along the whole edge of x + y = 4 from (2, 2) to (4, 0), for example at (3, 1): infinitely many points.

Privacy · Terms · Refunds · Delivery