Chapter 12 Linear Programming
Practice questions
Assertion (A): The problem 'Maximise Z = x + y subject to x + y ≤ 2, x + y ≥ 4, x ≥ 0, y ≥ 0' has no optimal solution. Reason (R): No point satisfies all the constraints, so the feasible region is empty.
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true, but R is false
- A is false, but R is true
Answer and explanation
Answer: A
x + y cannot be at most 2 and at least 4 at once, so the feasible region is empty (R). With no feasible point there is nothing to optimise, which is why A holds.
For the same unbounded region, what is true of the maximum of Z = 5x + 2y?
- It is 40, at (8, 0)
- It is 24, at (4, 2)
- It is 20, at (0, 10)
- Z has no maximum value
Answer and explanation
Answer: D
The largest corner value is 40, but the half-plane 5x + 2y > 40 contains feasible points such as (10, 10). Z grows without limit, so there is no maximum.
Minimise Z = 5x + 2y subject to 2x + y ≥ 10, x + 2y ≥ 8, x ≥ 0, y ≥ 0. The corners are (0, 10), (4, 2) and (8, 0). What is the minimum value?
- 24
- 20
- 40
- It has no minimum
Answer and explanation
Answer: B
Values: 0 + 20 = 20, 20 + 4 = 24, 40 + 0 = 40, so m = 20 at (0, 10). The half-plane 5x + 2y < 20 contains no feasible point (every feasible point has 2x + y ≥ 10, and 5x + 2y = 2(2x + y) + x ≥ 20), so 20 is the minimum.
The corners of a bounded feasible region are (4, 0), (4, 2), (0, 6) and (0, 2). For Z = 2x + y, which statement is correct?
- Maximum 10 at (4, 2); minimum 2 at (0, 2)
- Maximum 6 at (0, 6); minimum 2 at (0, 2)
- Maximum 10 at (4, 2); minimum 8 at (4, 0)
- Maximum 8 at (4, 0); minimum 6 at (0, 6)
Answer and explanation
Answer: A
Values: Z(4, 0) = 8, Z(4, 2) = 10, Z(0, 6) = 6, Z(0, 2) = 2. Largest 10 at (4, 2), smallest 2 at (0, 2).
Over the same region (corners (0, 0), (5, 0), (3, 4), (0, 5)), what is the minimum of Z = x − y?
- 0
- −1
- −5
- 5
Answer and explanation
Answer: C
Values of x − y: 0, 5, −1, −5. The region is bounded, so the minimum is the smallest corner value, −5 at (0, 5).
Maximise Z = 3x + 5y subject to 2x + y ≤ 10, x + 3y ≤ 15, x ≥ 0, y ≥ 0. What is the maximum value?
- 25
- 15
- 29
- 30
Answer and explanation
Answer: C
Corners: (0, 0), (5, 0), (3, 4), (0, 5). Values: 0, 15, 9 + 20 = 29, 25. The maximum is 29 at (3, 4).
Which system has a bounded feasible region?
- x + y ≥ 3, x ≥ 0, y ≥ 0
- x − y ≤ 2, x ≥ 0, y ≥ 0
- y ≥ 1, x ≥ 0
- x + y ≤ 3, x ≥ 0, y ≥ 0
Answer and explanation
Answer: D
x + y ≤ 3 in the first quadrant is the triangle with vertices (0, 0), (3, 0) and (0, 3), which fits in a circle. Each of the others extends indefinitely.
Which point is NOT a feasible solution of 2x + y ≤ 10, x + 3y ≤ 15, x ≥ 0, y ≥ 0?
- (2, 4)
- (4, 3)
- (5, 0)
- (0, 5)
Answer and explanation
Answer: B
For (4, 3): 2(4) + 3 = 11 > 10, so the first constraint fails. (2, 4) gives 8 and 14; (5, 0) gives 10 and 5; (0, 5) gives 5 and 15; all within the limits.
Which is a corner point of the feasible region of 2x + y ≤ 10, x + 3y ≤ 15, x ≥ 0, y ≥ 0?
- (3, 4)
- (5, 5)
- (0, 10)
- (15, 0)
Answer and explanation
Answer: A
Solving 2x + y = 10 and x + 3y = 15: y = 10 − 2x, so x + 30 − 6x = 15, x = 3, y = 4. The other points break a constraint: (0, 10) gives x + 3y = 30 > 15 and (15, 0) gives 2x + y = 30 > 10.
Food P costs ₹6 per kg and food Q costs ₹4 per kg. The objective function for the cheapest diet is
- Maximise Z = 6x + 4y
- Minimise Z = 4x + 6y
- Minimise Z = 6x + 4y
- Minimise Z = 10(x + y)
Answer and explanation
Answer: C
The cost of x kg of P and y kg of Q is 6x + 4y rupees, and cost is to be minimised.
Food P has 3 units of a vitamin per kg and food Q has 2 units per kg; a diet needs at least 12 units. With x kg of P and y kg of Q, the constraint is
- 3x + 2y ≤ 12
- 3x + 2y ≥ 12
- 2x + 3y ≥ 12
- x + y ≥ 12
Answer and explanation
Answer: B
Vitamin supplied is 3x + 2y units, and it must be at least 12, so 3x + 2y ≥ 12.
A dealer buys fans at ₹500 each and lamps at ₹250 each, has at most ₹5000, and space for at most 15 items. With x fans and y lamps, the constraints (besides x, y ≥ 0) are
- 2x + y ≥ 20, x + y ≥ 15
- x + 2y ≤ 20, x + y ≤ 15
- 500x + 250y ≤ 15, x + y ≤ 5000
- 2x + y ≤ 20, x + y ≤ 15
Answer and explanation
Answer: D
Money: 500x + 250y ≤ 5000, which divides by 250 to 2x + y ≤ 20. Space: x + y ≤ 15. Both are 'at most' limits, so ≤.
Assertion (A): The word 'programming' in linear programming refers to writing computer programs. Reason (R): The word 'linear' means that all the mathematical relations in the problem are linear.
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true, but R is false
- A is false, but R is true
Answer and explanation
Answer: D
R is true. A is false: 'programming' here means planning a programme or course of action, as in choosing a production plan.
In an LPP, the variables x and y whose values are to be decided are called
- decision variables
- constraints
- corner points
- objective variables of degree two
Answer and explanation
Answer: A
x and y represent the decisions to be made, such as how many of each item to produce, so they are called decision variables.
Which of the following is NOT allowed in a linear programming problem?
- A constraint such as 3x + 2y ≤ 12
- An objective function such as Z = 4x − y
- A constraint such as xy ≥ 4
- The restrictions x ≥ 0, y ≥ 0
Answer and explanation
Answer: C
xy ≥ 4 contains the product of the variables, so it is not linear. All constraints and the objective function of an LPP must be linear.
Assertion (A): If the feasible region of an LPP is unbounded, the objective function Z = ax + by may have no maximum value. Reason (R): An unbounded region extends indefinitely, so Z may increase without limit within it.
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true, but R is false
- A is false, but R is true
Answer and explanation
Answer: A
Both are true. For example, in the canteen problem the cost 10x + 12y has no maximum because the region extends indefinitely. R explains A; it is also why the open half-plane test is needed.
Which system of constraints has no feasible region?
- x + y ≤ 2, x + y ≥ 5, x ≥ 0, y ≥ 0
- x + y ≥ 2, x + y ≤ 5, x ≥ 0, y ≥ 0
- x ≤ 4, y ≥ 1, x ≥ 0
- x + 2y ≥ 4, x ≥ 0, y ≥ 0
Answer and explanation
Answer: A
No point can have x + y at most 2 and at least 5 at the same time, so the first system is contradictory. The others all have feasible points, such as (1, 2), (0, 1) and (4, 0).
Maximise Z = 2x + 4y subject to x + 2y ≤ 8, x + y ≤ 6, x, y ≥ 0. The corners are (0, 0), (6, 0), (4, 2) and (0, 4). Which points give the maximum?
- Only (4, 2)
- Only (0, 4)
- Exactly the two points (4, 2) and (0, 4)
- Every point of the segment joining (4, 2) and (0, 4)
Answer and explanation
Answer: D
Z at the corners: 0, 12, 16, 16. The maximum 16 occurs at two adjacent corners, so it occurs at every point of the edge joining them (that edge lies on x + 2y = 8, and Z = 2(x + 2y)).
For the same region, what can be said about the maximum of Z = 3x + 2y?
- It is 18, at (6, 0)
- Z has no maximum value
- It is 12, at (0, 6)
- It is 10, at (2, 2)
Answer and explanation
Answer: B
The largest corner value is 18, but the half-plane 3x + 2y > 18 contains feasible points such as (10, 10). Z can be made as large as we like, so it has no maximum.
An unbounded feasible region has corners (0, 6), (2, 2) and (6, 0) and lies on the far side of x + 2y = 6 and 2x + y = 6 from the origin. What is the minimum of Z = 3x + 2y?
- 12
- 18
- 10
- It has no minimum
Answer and explanation
Answer: C
Corner values: 12, 6 + 4 = 10, 18, so m = 10 at (2, 2). The open half-plane 3x + 2y < 10 lies on the origin side of the line through (2, 2) and contains no feasible point, so 10 is the minimum.