Finding the Optimal Integer Solution (Edexcel International AS Maths: Decision 1)

What is meant by integer solutions?

• The optimal solution to a linear programming problem lies on a vertex of the feasible region
  • The values of the decision variables at this vertex may not take integer values
• Sometimes the context of the problem may demand that the decision variables take integer values
  • Decision variables are often a 'number of things'
    • Is it possible for the furniture manufacturer to make 3.65 chairs per day?
    • For public health reasons, it would not be appropriate for a food factory to leave a tin of beans partially produced overnight!
• This is what is meant by the phrase integer solutions

How do I find the integer solutions to a linear programming problem?

• Find the optimal solution of the linear programming problem as usual
  • Use the objective line or vertex method
• Consider the four points with integer coordinates that surround the optimal solution
  
  • E.g.
    For an optimal solution of , the four surrounding points would be
    (3, 4), (3, 5), (4, 5) and (4, 4)

• Check whether each of these four points satisfies all of the constraints
  • It may be obvious that one (or more) do not but they should still be mentioned
• For those coordinates that do satisfy all the constraints
  • Evaluate the objective function () at each of the coordinates
  • The integer solution will be the point that maximises or minimises the objective function as required
• The integer solution may not be the optimal solution
  • Depending on the exact nature (gradient) of the objective line
    • The objective line 'moves away' from the boundary of the feasible region when an integer solution is found
    • So there could be another integer solution inside (or on the boundary of) the feasible region some way from the optimal solution
    • This other integer solution may be closer to the boundary of the feasible region than the one just found
  • You will not be expected to find this other integer solution
    • Just recognise that the integer solution found using the above process is not necessarily optimal