- Practice
- About 15 min
- 5 practice questions
Checking answers: feasible is not optimal, and what a new constraint does
Verify a proposed answer in three steps, tell a feasible plan from the optimal one, predict the effect of adding or removing a constraint, and catch sign and direction slips.
If something looks wrong, please tell us.
Many multiple-choice questions on linear programming are really checking questions. A plan is offered and you must say whether it is feasible, whether it is optimal, or what happens if a constraint is changed. The reasoning needs no new calculation, only a clear idea of what the optimum means.
Three checks for any offered answer
- Is it feasible? Substitute it into every constraint and both sign conditions.
- Is the value of Z correct? Recompute Z from the plan.
- Is it optimal? Compare with the other corners or with a neighbouring corner.
Worked example 1: feasible but not optimal
Maximise Z = 3x + 4y subject to x + y ≤ 8, 2x + y ≤ 12, x, y ≥ 0. A student says the answer is (4, 4) with Z = 28. Check feasibility: 4 + 4 = 8 ≤ 8 and 8 + 4 = 12 ≤ 12, both binding, so (4, 4) is a corner. Z = 12 + 16 = 28 is correct. But the other corners are (0, 0), (6, 0) and (0, 8), with Z = 0, 18 and 32. Since 32 > 28, the true maximum is 32 at (0, 8). The student's plan is feasible and its value is correct, but it is not optimal. A feasible corner is only a candidate.
What happens when a constraint is added?
Adding a constraint can never improve a maximum or lower a minimum. If the old optimum still satisfies the new constraint, it is still the optimum.
The new region is part of the old one, so the best value over it cannot be better than before. If the old best point is still inside, nothing is better elsewhere in the smaller region, so it remains optimal.
Worked example 2: a constraint that cuts off the optimum
Add y ≤ 6 to the problem above. The old optimum (0, 8) has y = 8 > 6, so it is cut off. The new corners are (0, 0), (6, 0), (4, 4), (2, 6) and (0, 6). The point (2, 6) comes from y = 6 meeting x + y = 8. The values are 0, 18, 28, 3(2) + 4(6) = 30 and 24. The new maximum is 30 at (2, 6), lower than 32, as predicted.
Worked example 3: a constraint that cuts off nothing useful
Instead add x ≤ 5. The old optimum (0, 8) has x = 0 ≤ 5, so it is still feasible and therefore still optimal: the maximum remains 32 at (0, 8). Only the corner (6, 0) is lost (it becomes (5, 0) and (5, 2)), and its value was lower anyway.
Typical slips to check for
- A ≥ written where ≤ was meant (a limit on a resource is always a ≤ constraint).
- Using the wrong profit for a product, or swapping the coefficients of x and y between the constraint and the objective.
- Reporting the corner but not Z, or Z but not the corner.
- Choosing the greatest value for a minimisation question, or the least for a maximisation question.
A final test: if every constraint is a resource limit (≤) and the profits are positive, the best plan must use at least one resource fully, because otherwise you could make a little more of a product and increase the profit. A claimed optimum with slack in every resource is therefore suspicious.
Key takeaways: check feasibility, value and optimality separately; a feasible corner is not necessarily the best; adding a constraint cannot improve the optimum, and if the old optimum survives it remains optimal; if the old optimum is cut off, the new value is no better.
Check your understanding
-
1. For the problem in Worked example 1, is the plan (4, 4) feasible?
- yes, and it is a corner
- no, it breaks x + y ≤ 8
- no, it breaks 2x + y ≤ 12
- yes, and it is the maximum
Show answer
Answer: A. 4 + 4 = 8 ≤ 8 and 2(4) + 4 = 12 ≤ 12, so it is feasible and both constraints are binding. But Z = 28 is less than 32 at (0, 8).
-
2. After adding a new constraint to a maximisation problem, the maximum value:
- is always larger than before
- is always unchanged by it
- is not larger than before
- is always smaller than before
Show answer
Answer: C. The new region lies inside the old one, so the maximum cannot rise. It may stay the same or fall.
-
3. In Worked example 2, why does adding y ≤ 6 lower the maximum?
- the new constraint is redundant
- the old optimum (0, 8) is cut off
- (2, 6) is not a corner
- the objective changes
Show answer
Answer: B. The old optimum has y = 8, which violates y ≤ 6. The best remaining corner gives 30, lower than 32.
-
4. In Worked example 3, adding x ≤ 5 leaves the maximum unchanged. Why?
- x ≤ 5 is a ≥ constraint
- (6, 0) is the optimum
- Z has no x term
- (0, 8) satisfies x ≤ 5
Show answer
Answer: D. x = 0 ≤ 5, so the old optimum remains feasible, and an optimum that survives stays optimal.
-
5. A student finds, for maximising Z = 3x + 4y, the corner values 0, 18, 28 and 32 and reports 18. The error is:
- a wrong sign in a constraint line
- reporting a corner that is not the largest
- using the wrong objective function
- forgetting to test the origin point
Show answer
Answer: B. For a maximum the greatest corner value, 32, must be reported, not 18.
Sign in to keep track of the lessons you finish.