SOLVER7 Study. Nothing Else.
2024 Board Paper Q30

Solve the following linear programming problem graphically :
\(\begin{align}\text{Maximise z= 500x + 300y}\\ \text{Subject to constraints }\\ x + 2y \le 12\\ 2x +y \le12\\ 4x+5y\ge20\\ x \ge 0,\ y\ge 0\end{align}\)

CBSE Class 12 Maths · Linear Programming

Solution

👶 Simple Explanation

Simple Explanation

Imagine you run a small shop selling two types of toys, and you want to earn as much money as possible. You have limited materials, so you cannot make unlimited toys — there are rules (like a budget) that you must follow. The region where all the rules are satisfied at once is like a fenced yard on a map. The best earning spot is always at one of the corners of that yard. So you just check every corner, calculate the money earned at each, and pick the biggest one. Here the biggest earning is at the corner where \( x = 4 \) and \( y = 4 \).

Answer: The maximum value is \( z = 3200 \), attained at the point \( (x, y) = (4, 4) \).

📖 Graphical Solution of a Linear Programming Problem

Detailed Explanation

In a Linear Programming Problem (LPP) we want to optimise (here, maximise) a linear objective function subject to linear inequality constraints. The set of all points satisfying every constraint is called the feasible region. A very important result, the Corner Point Theorem, states that if an optimal value of the objective function exists, it always occurs at a corner point (vertex) of the feasible region. So the method is: draw each constraint line, shade the correct side of each inequality, identify the common shaded region (feasible region), locate its corner points, and finally evaluate the objective function \( z \) at every corner. The largest value gives the maximum.

Formula Used

Maximise \( z = 500x + 300y \) subject to \( x + 2y \le 12 \), \( 2x + y \le 12 \), \( 4x + 5y \ge 20 \), \( x \ge 0 \), \( y \ge 0 \). Evaluate \( z \) at each corner point and choose the maximum.

Solution

  1. Step 1: Convert inequalities into boundary lines: Replace each inequality by an equation to draw its boundary line. \[ x + 2y = 12 \] \[ 2x + y = 12 \] \[ 4x + 5y = 20 \] Also keep in mind the axes lines from \( x \ge 0 \) and \( y \ge 0 \), which restrict us to the first quadrant.
  2. Step 2: Find intercepts of each line: For \( x + 2y = 12 \): when \( x = 0, y = 6 \); when \( y = 0, x = 12 \). For \( 2x + y = 12 \): when \( x = 0, y = 12 \); when \( y = 0, x = 6 \). For \( 4x + 5y = 20 \): when \( x = 0, y = 4 \); when \( y = 0, x = 5 \). Plot these points and draw the three lines.
  3. Step 3: Decide the correct side of each line: Test the origin \( (0,0) \) in each inequality. For \( x + 2y \le 12 \): \( 0 \le 12 \) is true, so keep the origin side. For \( 2x + y \le 12 \): \( 0 \le 12 \) is true, keep origin side. For \( 4x + 5y \ge 20 \): \( 0 \ge 20 \) is false, so keep the side away from the origin. The feasible region is the common area satisfying all these, lying in the first quadrant.
  4. Step 4: Find the corner points of the feasible region: The corners come from intersections of the boundary lines. Intersection of \( x + 2y = 12 \) and \( 2x + y = 12 \): subtracting suitably gives \( x = 4, y = 4 \), the point \( (4,4) \). Where \( 2x + y = 12 \) meets \( 4x + 5y = 20 \): from the first \( y = 12 - 2x \), substitute to get \( 4x + 5(12 - 2x) = 20 \), so \( -6x + 60 = 20 \), giving \( x = \tfrac{20}{3}, y = -\tfrac{4}{3} \), which is not in the first quadrant, so discard it. The valid corner points are \( (5,0) \), \( (6,0) \), \( (4,4) \), \( (0,6) \), and \( (0,4) \).
  5. Step 5: Evaluate z at each corner point: Substitute each corner into \( z = 500x + 300y \). At \( (0,4): z = 500(0) + 300(4) = 1200 \). At \( (5,0): z = 500(5) + 300(0) = 2500 \). At \( (6,0): z = 500(6) + 300(0) = 3000 \). At \( (4,4): z = 500(4) + 300(4) = 2000 + 1200 = 3200 \). At \( (0,6): z = 500(0) + 300(6) = 1800 \).
  6. Step 6: Choose the maximum: Comparing all values, the largest is \( z = 3200 \), occurring at the corner point \( (4,4) \). Since the feasible region is bounded, this is the maximum value of \( z \).

Final Answer

The maximum value is \( z = 3200 \), attained at the point \( (x, y) = (4, 4) \).

Common Mistake

A common mistake is shading the wrong side for \( 4x + 5y \ge 20 \). Since the origin fails this inequality \( (0 \ge 20 \) is false), the feasible side is the one away from the origin, not towards it.

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: Write the boundary lines: Replace each inequality with an equality to get the boundary lines: \[ x + 2y = 12 \] \[ 2x + y = 12 \] \[ 4x + 5y = 20 \] Reason: The boundary lines form the edges of the feasible region; we need them to sketch and identify corner points.
  2. Step 2: Find intercepts of each boundary line: For \( x + 2y = 12 \): set \( x = 0 \) to get \( y = 6 \), and set \( y = 0 \) to get \( x = 12 \). Points: \( (0, 6) \) and \( (12, 0) \). For \( 2x + y = 12 \): set \( x = 0 \) to get \( y = 12 \), and set \( y = 0 \) to get \( x = 6 \). Points: \( (0, 12) \) and \( (6, 0) \). For \( 4x + 5y = 20 \): set \( x = 0 \) to get \( y = 4 \), and set \( y = 0 \) to get \( x = 5 \). Points: \( (0, 4) \) and \( (5, 0) \). Reason: Two points uniquely determine a straight line, so intercepts are the quickest way to draw each boundary.
  3. Step 3: Identify the feasible region: The constraints \( x \ge 0 \) and \( y \ge 0 \) restrict us to the first quadrant. Check the origin \( (0, 0) \) in each inequality: \( 0 + 0 \le 12 \) (TRUE, so shade below \( x + 2y = 12 \)), \( 0 + 0 \le 12 \) (TRUE, so shade below \( 2x + y = 12 \)), \( 0 \ge 20 \) (FALSE, so shade away from the origin for \( 4x + 5y \ge 20 \)). The feasible region is the area in the first quadrant that satisfies all three inequalities simultaneously. Reason: We must work in the region where every constraint holds at once — this is the only valid search space for the optimal solution.
  4. Step 4: Find the corner points of the feasible region: Corner points arise where boundary lines meet each other or the axes. Intersection of \( x + 2y = 12 \) and \( 2x + y = 12 \): subtract the first from twice the second to get \( 3x = 12 \), so \( x = 4 \); substituting back gives \( y = 4 \). Corner: \( (4, 4) \). Intersection of \( x + 2y = 12 \) with the y-axis (\( x = 0 \)): \( y = 6 \). Corner: \( (0, 6) \). Intersection of \( 2x + y = 12 \) with the x-axis (\( y = 0 \)): \( x = 6 \). Corner: \( (6, 0) \). Verify that \( (0, 6) \) and \( (6, 0) \) also satisfy \( 4x + 5y \ge 20 \): for \( (0,6) \), \( 30 \ge 20 \) (TRUE); for \( (6,0) \), \( 24 \ge 20 \) (TRUE). Reason: By the Corner Point Theorem, the optimal value of \( z \) must occur at one of these vertices.
  5. Step 5: Evaluate the objective function at each corner: At \( (0, 6) \): \[ z = 500(0) + 300(6) = 1800 \] At \( (6, 0) \): \[ z = 500(6) + 300(0) = 3000 \] At \( (4, 4) \): \[ z = 500(4) + 300(4) = 2000 + 1200 = 3200 \] Reason: The Corner Point Theorem guarantees the maximum lies at one of these vertices, so comparing all three values identifies the global maximum.
  6. Step 6: Select the maximum value: Comparing the three values — \( 1800 \), \( 3000 \), and \( 3200 \) — the largest is \( 3200 \), achieved at \( (4, 4) \). Reason: The point that gives the highest value of \( z \) is the optimal solution to the maximisation problem.

Final Answer

The maximum value is \( z = 3200 \), attained at the point \( (x, y) = (4, 4) \).

Common Mistake

One common mistake: students forget to verify that all corner points actually satisfy every constraint (especially the \( \ge \) type), and they may include infeasible points in their comparison, leading to an incorrect maximum.

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Find corner points of feasible region: Intersection of \( x + 2y = 12 \) and \( 2x + y = 12 \): solving gives \( x = 4,\, y = 4 \). Other vertices: \( (0, 6) \), \( (6, 0) \), \( (0, 4) \), \( (5, 0) \).
  2. Step 2: Evaluate \( z \) at each corner point: \[\begin{aligned} z(0,6) &= 500(0)+300(6)=1800 \\ z(4,4) &= 500(4)+300(4)=3200 \\ z(6,0) &= 500(6)+300(0)=3000 \end{aligned}\]

Answer: The maximum value is \( z = 3200 \), attained at the point \( (x, y) = (4, 4) \).

➕ More Examples

More Examples

Example 1

Question: Solve the following linear programming problem graphically: Maximise \( z = 400x + 600y \) subject to the constraints: \( x + 2y \le 10 \), \( 3x + y \le 12 \), \( 5x + 8y \ge 40 \), \( x \ge 0 \), \( y \ge 0 \).

Solution: We need to maximise \( z = 400x + 600y \) subject to the given constraints. Step 1: Draw the boundary lines. Line 1: \( x + 2y = 10 \). When \( x = 0 \), \( y = 5 \); when \( y = 0 \), \( x = 10 \). Points: \( (0, 5) \) and \( (10, 0) \). Line 2: \( 3x + y = 12 \). When \( x = 0 \), \( y = 12 \); when \( y = 0 \), \( x = 4 \). Points: \( (0, 12) \) and \( (4, 0) \). Line 3: \( 5x + 8y = 40 \). When \( x = 0 \), \( y = 5 \); when \( y = 0 \), \( x = 8 \). Points: \( (0, 5) \) and \( (8, 0) \). Step 2: Determine the feasible region. For \( x + 2y \le 10 \): the region is on and below Line 1. For \( 3x + y \le 12 \): the region is on and below Line 2. For \( 5x + 8y \ge 40 \): the region is on and above Line 3. With \( x \ge 0 \) and \( y \ge 0 \), the feasible region lies in the first quadrant. Step 3: Find the corner points of the feasible region. Corner A: Intersection of \( x + 2y = 10 \) and \( x = 0 \): point \( (0, 5) \). Corner B: Intersection of \( x + 2y = 10 \) and \( 3x + y = 12 \). From the first equation: \( x = 10 - 2y \). Substituting: \( 3(10 - 2y) + y = 12 \), so \( 30 - 6y + y = 12 \), giving \( 5y = 18 \), hence \( y = \frac{18}{5} \) and \( x = 10 - 2 \times \frac{18}{5} = \frac{14}{5} \). Point: \( \left(\frac{14}{5},\ \frac{18}{5}\right) \). Corner C: Intersection of \( 3x + y = 12 \) and \( y = 0 \): \( x = 4 \). Point: \( (4, 0) \). Corner D: Intersection of \( 5x + 8y = 40 \) and \( y = 0 \): \( x = 8 \). But we must check \( 3x + y \le 12 \): at \( (8,0) \), \( 24 \le 12 \) is false. So \( (8, 0) \) is not feasible. Corner D (revised): Intersection of \( 5x + 8y = 40 \) and \( x = 0 \): \( y = 5 \). This coincides with Point A \( (0, 5) \). So the feasible region is bounded by the corner points \( (0, 5) \), \( \left(\frac{14}{5}, \frac{18}{5}\right) \), and \( (4, 0) \). We verify \( (4, 0) \) satisfies \( 5x + 8y \ge 40 \): \( 20 \ge 40 \) is false. So \( (4, 0) \) is NOT in the feasible region. Let us carefully re-examine: The feasible region must satisfy all three inequalities simultaneously. Checking the origin \( (0, 0) \): \( 5(0)+8(0) = 0 \ge 40 \) is false, so the origin is not feasible. The feasible region is above Line 3 and below Lines 1 and 2. Intersection of \( 5x + 8y = 40 \) and \( 3x + y = 12 \): From the second, \( y = 12 - 3x \). Substituting: \( 5x + 8(12 - 3x) = 40 \), so \( 5x + 96 - 24x = 40 \), giving \( -19x = -56 \), hence \( x = \frac{56}{19} \) and \( y = 12 - 3 \cdot \frac{56}{19} = \frac{228 - 168}{19} = \frac{60}{19} \). Point E: \( \left(\frac{56}{19}, \frac{60}{19}\right) \). The feasible corner points are: \( A = (0, 5) \), \( B = \left(\frac{14}{5}, \frac{18}{5}\right) \), \( E = \left(\frac{56}{19}, \frac{60}{19}\right) \). Step 4: Evaluate \( z = 400x + 600y \) at each corner point. At \( A = (0, 5) \): \[ z = 400(0) + 600(5) = 3000 \] At \( B = \left(\frac{14}{5}, \frac{18}{5}\right) \): \[ z = 400 \times \frac{14}{5} + 600 \times \frac{18}{5} = \frac{5600}{5} + \frac{10800}{5} = \frac{16400}{5} = 3280 \] At \( E = \left(\frac{56}{19}, \frac{60}{19}\right) \): \[ z = 400 \times \frac{56}{19} + 600 \times \frac{60}{19} = \frac{22400 + 36000}{19} = \frac{58400}{19} \approx 3073.7 \] Step 5: The maximum value of \( z \) is \( 3280 \) at \( \left(\frac{14}{5}, \frac{18}{5}\right) \).

Answer: Maximum value of \( z = 3280 \) at \( x = \frac{14}{5} \), \( y = \frac{18}{5} \).

Example 2

Question: Solve the following linear programming problem graphically: Maximise \( z = 300x + 500y \) subject to the constraints: \( x + y \le 8 \), \( x + 3y \le 18 \), \( 2x + y \ge 6 \), \( x \ge 0 \), \( y \ge 0 \).

Solution: We need to maximise \( z = 300x + 500y \) subject to the given constraints. Step 1: Draw the boundary lines. Line 1: \( x + y = 8 \). Points: \( (0, 8) \) and \( (8, 0) \). Line 2: \( x + 3y = 18 \). Points: \( (0, 6) \) and \( (18, 0) \). Line 3: \( 2x + y = 6 \). Points: \( (0, 6) \) and \( (3, 0) \). Step 2: Determine the feasible region. For \( x + y \le 8 \): region on and below Line 1. For \( x + 3y \le 18 \): region on and below Line 2. For \( 2x + y \ge 6 \): region on and above Line 3. With \( x \ge 0 \), \( y \ge 0 \): first quadrant. The origin \( (0, 0) \): check \( 2(0) + 0 = 0 \ge 6 \) is false, so the origin is not feasible. The feasible region is above Line 3. Step 3: Find the corner points. Corner A: Intersection of \( 2x + y = 6 \) and \( x = 0 \): \( y = 6 \). Point: \( (0, 6) \). Check \( x + y = 6 \le 8 \) (true) and \( x + 3y = 18 \le 18 \) (true). Feasible. Corner B: Intersection of \( x + 3y = 18 \) and \( x + y = 8 \). Subtracting: \( 2y = 10 \), so \( y = 5 \) and \( x = 3 \). Point: \( (3, 5) \). Check \( 2(3) + 5 = 11 \ge 6 \) (true). Feasible. Corner C: Intersection of \( x + y = 8 \) and \( 2x + y = 6 \). Subtracting: \( x = -2 \). Since \( x \ge 0 \), this is not feasible. Corner D: Intersection of \( 2x + y = 6 \) and \( y = 0 \): \( x = 3 \). Point: \( (3, 0) \). Check \( x + y = 3 \le 8 \) (true) and \( x + 3y = 3 \le 18 \) (true). Feasible. Corner E: Intersection of \( x + y = 8 \) and \( y = 0 \): \( x = 8 \). Point: \( (8, 0) \). Check \( 2(8) + 0 = 16 \ge 6 \) (true). Feasible. So the feasible corner points are: \( A = (0, 6) \), \( B = (3, 5) \), \( E = (8, 0) \), and \( D = (3, 0) \). Step 4: Evaluate \( z = 300x + 500y \) at each corner point. At \( A = (0, 6) \): \[ z = 300(0) + 500(6) = 3000 \] At \( B = (3, 5) \): \[ z = 300(3) + 500(5) = 900 + 2500 = 3400 \] At \( E = (8, 0) \): \[ z = 300(8) + 500(0) = 2400 \] At \( D = (3, 0) \): \[ z = 300(3) + 500(0) = 900 \] Step 5: The maximum value of \( z \) is \( 3400 \) at \( (3, 5) \).

Answer: Maximum value of \( z = 3400 \) at \( x = 3 \), \( y = 5 \).

🎯 Try a Similar Question

Try a Similar Question

Question: Solve the following linear programming problem graphically: Maximise \( z = 400x + 600y \) subject to the constraints \( x + 2y \le 14 \), \( 2x + y \le 14 \), \( 3x + 4y \ge 12 \), \( x \ge 0 \), \( y \ge 0 \).

Solution

  1. Step 1: Write Down the Constraints: The constraints are: \( x + 2y \le 14 \) \( 2x + y \le 14 \) \( 3x + 4y \ge 12 \) \( x \ge 0,\; y \ge 0 \) The objective function is \( z = 400x + 600y \).
  2. Step 2: Find Intercepts of the Boundary Lines: For \( x + 2y = 14 \): set \( x = 0 \) to get \( y = 7 \), and set \( y = 0 \) to get \( x = 14 \). Points: \( (0, 7) \) and \( (14, 0) \). For \( 2x + y = 14 \): set \( x = 0 \) to get \( y = 14 \), and set \( y = 0 \) to get \( x = 7 \). Points: \( (0, 14) \) and \( (7, 0) \). For \( 3x + 4y = 12 \): set \( x = 0 \) to get \( y = 3 \), and set \( y = 0 \) to get \( x = 4 \). Points: \( (0, 3) \) and \( (4, 0) \).
  3. Step 3: Identify the Feasible Region: The region satisfying all constraints simultaneously is bounded. The inequalities \( x + 2y \le 14 \) and \( 2x + y \le 14 \) restrict the region from above-right, while \( 3x + 4y \ge 12 \) restricts from below-left. Combined with \( x \ge 0 \) and \( y \ge 0 \), the feasible region is a polygon in the first quadrant.
  4. Step 4: Find the Corner Points: Corner Point A — intersection of \( x + 2y = 14 \) and \( x = 0 \): \( (0, 7) \). Corner Point B — intersection of \( x + 2y = 14 \) and \( 2x + y = 14 \): Subtract the first from twice the second: \( 4x + 2y - x - 2y = 28 - 14 \), giving \( 3x = 14 \), so \( x = \frac{14}{3} \). Then \( y = 14 - 2 \times \frac{14}{3} = \frac{14}{3} \). Point: \( \left(\frac{14}{3}, \frac{14}{3}\right) \). Corner Point C — intersection of \( 2x + y = 14 \) and \( y = 0 \): \( (7, 0) \). Corner Point D — intersection of \( 3x + 4y = 12 \) and \( y = 0 \): \( (4, 0) \). Corner Point E — intersection of \( 3x + 4y = 12 \) and \( x = 0 \): \( (0, 3) \). So the vertices of the feasible region are \( (0, 3) \), \( (0, 7) \), \( \left(\frac{14}{3}, \frac{14}{3}\right) \), \( (7, 0) \), and \( (4, 0) \).
  5. Step 5: Evaluate the Objective Function at Each Corner Point: At \( (0, 3) \): \( z = 400(0) + 600(3) = 1800 \). At \( (0, 7) \): \( z = 400(0) + 600(7) = 4200 \). At \( \left(\frac{14}{3}, \frac{14}{3}\right) \): \[ z = 400 \times \frac{14}{3} + 600 \times \frac{14}{3} = \frac{5600}{3} + \frac{8400}{3} = \frac{14000}{3} \approx 4666.67 \] At \( (7, 0) \): \( z = 400(7) + 600(0) = 2800 \). At \( (4, 0) \): \( z = 400(4) + 600(0) = 1600 \).
  6. Step 6: Identify the Maximum: Comparing all values: \( 1800,\; 4200,\; \frac{14000}{3},\; 2800,\; 1600 \). The largest value is \( \frac{14000}{3} \approx 4666.67 \), attained at \( \left(\frac{14}{3}, \frac{14}{3}\right) \). Therefore, the maximum value of \( z \) is \( \frac{14000}{3} \) at \( x = \frac{14}{3},\; y = \frac{14}{3} \).

Answer: The maximum value of \( z = 400x + 600y \) is \( \dfrac{14000}{3} \) (approximately \( 4666.67 \)), attained at the point \( \left(\dfrac{14}{3},\, \dfrac{14}{3}\right) \).

Everything you get with Solver7

More questions in Linear Programming