Edexcel IAL - Decision Mathematics 1- 5.3 Integer Programming Problems- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 5.3 Integer Programming Problems -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 5.3 Integer Programming Problems -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 5.3 Integer Programming Problems
Linear Programming with Integer Solutions
In some linear programming problems, the decision variables are required to take integer values only. These problems arise when fractional values have no practical meaning.
Such problems are known as integer linear programming problems.
Why Integer Solutions Are Required
Integer restrictions are necessary when variables represent:
- Number of people
- Number of items or products
- Number of vehicles, machines, or rooms
For example, producing \( 3.5 \) machines or employing \( 2.7 \) workers is not possible.
Formulation with Integer Constraints
An integer linear program is formulated in the same way as a standard linear program, but with an additional restriction:
Decision variables must be integers
For example:
\( \mathrm{x \geq 0,\; y \geq 0} \) and \( \mathrm{x,\; y \in \mathbb{Z}} \)
Graphical Approach with Integer Solutions
When solving graphically:
- First solve the linear programming problem normally
- Identify the feasible region
- List all integer points inside or on the boundary of the feasible region
- Evaluate the objective function at these integer points
The optimal integer solution may differ from the continuous (non-integer) solution.
Important Observations
- The continuous optimum may not be an integer point
- The best integer solution is often near the continuous optimum
- All integer points must satisfy every constraint
Limitations of Integer Programming
- Integer constraints make problems harder to solve
- Graphical methods are practical only for two variables
For IAL Maths, problems will be limited to simple two-variable cases.
Key Examination Points
- Always state that variables must be integers
- Do not accept fractional answers when integers are required
- Check nearby integer points around the continuous optimum
Example
Maximise
\( \mathrm{Z = 4x + 5y} \)
subject to:
\( \mathrm{x + y \leq 7} \)
\( \mathrm{2x + y \leq 10} \)
\( \mathrm{x \geq 0,\; y \geq 0} \)
with the additional condition that \( \mathrm{x} \) and \( \mathrm{y} \) are integers.
▶️ Answer/Explanation
Continuous solution:
Solving \( \mathrm{x + y = 7} \) and \( \mathrm{2x + y = 10} \) gives \( \mathrm{(3,4)} \).
Check integer points in the feasible region:
At \( \mathrm{(3,4)} \): \( \mathrm{Z = 32} \)
At \( \mathrm{(2,5)} \): \( \mathrm{Z = 33} \)
At \( \mathrm{(1,6)} \): \( \mathrm{Z = 34} \)
At \( \mathrm{(0,7)} \): \( \mathrm{Z = 35} \)
Conclusion: Maximum integer value is \( \mathrm{Z = 35} \) at \( \mathrm{(0,7)} \).
Example
Minimise
\( \mathrm{C = 3x + 2y} \)
subject to:
\( \mathrm{x + y \geq 6} \)
\( \mathrm{x + 2y \geq 8} \)
\( \mathrm{x \geq 0,\; y \geq 0} \)
with the additional condition that \( \mathrm{x} \) and \( \mathrm{y} \) are integers.
▶️ Answer/Explanation
Continuous solution:
Solving \( \mathrm{x + y = 6} \) and \( \mathrm{x + 2y = 8} \) gives \( \mathrm{(4,2)} \).
Check integer points in the feasible region:
At \( \mathrm{(4,2)} \): \( \mathrm{C = 16} \)
At \( \mathrm{(3,3)} \): \( \mathrm{C = 15} \)
At \( \mathrm{(2,4)} \): \( \mathrm{C = 14} \)
At \( \mathrm{(1,5)} \): \( \mathrm{C = 13} \)
At \( \mathrm{(0,6)} \): \( \mathrm{C = 12} \)
Conclusion: Minimum integer value is \( \mathrm{C = 12} \) at \( \mathrm{(0,6)} \).
Example
A workshop produces two items, A and B. Each item A gives a profit of ₹6 and each item B gives a profit of ₹8.
The constraints are:
\( \mathrm{3x + 2y \leq 18} \)
\( \mathrm{x + y \leq 8} \)
\( \mathrm{x \geq 0,\; y \geq 0} \)
where \( \mathrm{x} \) and \( \mathrm{y} \) represent the number of items produced and must be integers.
▶️ Answer/Explanation
Continuous optimum:
Solving \( \mathrm{3x + 2y = 18} \) and \( \mathrm{x + y = 8} \) gives \( \mathrm{(2,6)} \).
Check integer points in the feasible region:
At \( \mathrm{(2,6)} \): \( \mathrm{Z = 60} \)
At \( \mathrm{(1,7)} \): \( \mathrm{Z = 62} \)
At \( \mathrm{(0,8)} \): \( \mathrm{Z = 64} \)
Conclusion: Maximum integer profit is \( \mathrm{₹64} \) at \( \mathrm{(0,8)} \).