All subjects · Mathematics · WDM11 (D1)

Linear programming: integer solutions

Often x and y must be whole numbers, such as numbers of buses or machines. The exact optimum may be a fraction, so you then search nearby whole number points.

Find the exact optimum first

Solve the problem as usual. If the optimal vertex has whole number coordinates and the context needs integers, you are done.

Searching for integer points

If the vertex is fractional, list nearby points with whole number coordinates. For each, check every constraint and work out the objective. The best feasible one is the integer optimum.

Look further than you think

The best integer point need not be the nearest one to the vertex, and simply rounding can give a point outside the region. Search along the edge of the region near the vertex, in a table of points tested.

Show it clearly

A table with columns for the point, each constraint value, feasible or not, and the objective value earns the method marks. Finish with a sentence in context.

Worked example

Maximise P = 5x + 6y subject to 3x + 5y ≤ 75, 4x + 3y ≤ 60, x, y ≥ 0, where x and y are integers.

  1. The lines meet at (75/11, 120/11), about (6.82, 10.91), with P = 1095/11
  2. (6, 10): 3x + 5y = 68, 4x + 3y = 54, P = 90
  3. (6, 11): 3x + 5y = 73, 4x + 3y = 57, P = 96
  4. (7, 10): 3x + 5y = 71, 4x + 3y = 58, P = 95
  5. (7, 11): 3x + 5y = 76, 4x + 3y = 61, not feasible
  6. (5, 12): 3x + 5y = 75, 4x + 3y = 56, P = 97

Answer: Integer optimum at (5, 12) with P = 97

Key idea: Solve exactly first, then test whole number points near the optimal vertex against every constraint; the best one may not be the nearest.

Check yourself

  1. For the constraints 3x + 5y ≤ 75 and 4x + 3y ≤ 60, find the x-coordinate where the boundary lines meet, to 2 decimal places.
    Show answer

    6.82. Solving gives x = 75/11 = 6.82.

  2. Maximise P = 5x + 6y subject to 3x + 5y ≤ 75, 4x + 3y ≤ 60, x, y ≥ 0 (not necessarily integers). Find the maximum P, to 1 decimal place.
    Show answer

    99.5. Vertices: (0, 0) gives 0; (0, 15) gives 90; (75/11, 120/11) gives 1095/11; (15, 0) gives 75.

  3. Now x and y must be integers. Find the maximum value of P = 5x + 6y subject to 3x + 5y ≤ 75, 4x + 3y ≤ 60.
    Show answer

    97. (6, 10): 3x + 5y = 68, 4x + 3y = 54, P = 90; (6, 11): 3x + 5y = 73, 4x + 3y = 57, P = 96; (7, 10): 3x + 5y = 71, 4x + 3y = 58, P = 95; (7, 11): 3x + 5y = 76, 4x + 3y = 61, not feasible; (5, 12): 3x + 5y = 75, 4x + 3y = 56, P = 97.

  4. Which integer point maximises P = 5x + 6y subject to 3x + 5y ≤ 75 and 4x + 3y ≤ 60?
    • (7, 11)
    • (6, 11)
    • (7, 10)
    • (5, 12)
    Show answer

    (5, 12). (5, 12): 3x + 5y = 75, 4x + 3y = 56, P = 97; (7, 11): 3x + 5y = 76, 4x + 3y = 61, not feasible; (6, 11): 3x + 5y = 73, 4x + 3y = 57, P = 96; (7, 10): 3x + 5y = 71, 4x + 3y = 58, P = 95.

  5. The exact optimum is at (6.82, 10.91). Why is rounding to (7, 11) not acceptable?
    • Rounding is always too small
    • (7, 11) lies outside the feasible region
    • The answer must be at a vertex
    • (7, 11) gives a smaller P
    Show answer

    (7, 11) lies outside the feasible region. 3(7) + 5(11) = 76 > 75, so it breaks a constraint.

  6. What should you show when finding an integer solution near a fractional vertex?
    • Only the final answer
    • The vertex rounded to the nearest whole numbers
    • The objective line only
    • A table of tested points with constraint checks and objective values
    Show answer

    A table of tested points with constraint checks and objective values. Method marks depend on showing each point tested against every constraint and its objective value.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.