SOLVER7 Study. Nothing Else.
2023 Board Paper Q29

Solve graphically the following linear programming problem :
\begin{aligned} \text{Maximize z = 6x + 3y,}\\ \text{subject to the constraints}\\ 4x + y \ge 80,\\ 3x + 2y \le 150,\\ x + 5y \ge 115,\\ x \ge 0,\; y \ge 0. \end{aligned}

CBSE Class 12 Maths · Linear Programming

Solution

👶 Simple Explanation

Simple Explanation

Imagine you run a small shop and want to earn as much money as possible. You have rules about how many items you can make or sell each day. The best earning happens at one of the corner points of the allowed region on a graph. We check every corner to see which one gives the highest earnings. Here, the highest value of \( z = 6x + 3y \) turns out to be \( 285 \), earned when \( x = 40 \) and \( y = 15 \).

Answer: The maximum value is \( z = 285 \), attained at the point \( (40, 15) \), i.e. \( x = 40, \; y = 15 \).

📖 Graphical Solution of an LPP (Maximize z = 6x + 3y)

Detailed Explanation

In a Linear Programming Problem (LPP), we want to maximize or minimize a linear objective function subject to linear constraints. We first draw each constraint line, decide which side satisfies the inequality, and shade the common region called the feasible region. According to the Corner Point Theorem, the optimal value of the objective function (if it exists) always occurs at a corner (vertex) of the feasible region. So we only need to evaluate the objective function at the corner points and pick the best value. Since some constraints here are of the form \( \ge \), the feasible region may be unbounded, so we must check carefully whether a finite maximum actually exists.

Formula Used

Objective function: \( z = 6x + 3y \). Constraints: \( 4x + y \ge 80 \), \( 3x + 2y \le 150 \), \( x + 5y \ge 115 \), \( x \ge 0 \), \( y \ge 0 \). Corner Point Theorem: the optimum of \( z \) occurs at a vertex of the feasible region.

Solution

  1. Step 1: Convert each inequality into an equation to draw the boundary lines. \[ 4x + y = 80 \] \[ 3x + 2y = 150 \] \[ x + 5y = 115 \] We also have the axes \( x = 0 \) and \( y = 0 \).
  2. Step 2: Find points to plot each line. For \( 4x + y = 80 \): at \( x = 0, y = 80 \); at \( y = 0, x = 20 \). For \( 3x + 2y = 150 \): at \( x = 0, y = 75 \); at \( y = 0, x = 50 \). For \( x + 5y = 115 \): at \( x = 0, y = 23 \); at \( y = 0, x = 115 \).
  3. Step 3: Decide the correct side of each line using a test point. Take \( (0,0) \). For \( 4x + y \ge 80 \): \( 0 \ge 80 \) is false, so the region is away from the origin. For \( 3x + 2y \le 150 \): \( 0 \le 150 \) is true, so the region is towards the origin. For \( x + 5y \ge 115 \): \( 0 \ge 115 \) is false, so the region is away from the origin. Along with \( x \ge 0 \) and \( y \ge 0 \), the common shaded area is the feasible region.
  4. Step 4: Find the corner points by solving the boundary lines pairwise. Intersection of \( 4x + y = 80 \) and \( x + 5y = 115 \): from the first, \( y = 80 - 4x \). Substitute: \[ x + 5(80 - 4x) = 115 \] \[ x + 400 - 20x = 115 \] \[ -19x = -285 \] \[ x = 15, \quad y = 80 - 60 = 20 \] So one corner is \( (15, 20) \).
  5. Step 5: Intersection of \( 4x + y = 80 \) and \( 3x + 2y = 150 \): from the first, \( y = 80 - 4x \). Substitute: \[ 3x + 2(80 - 4x) = 150 \] \[ 3x + 160 - 8x = 150 \] \[ -5x = -10 \] \[ x = 2, \quad y = 80 - 8 = 72 \] So another corner is \( (2, 72) \).
  6. Step 6: Intersection of \( 3x + 2y = 150 \) and \( x + 5y = 115 \): from the second, \( x = 115 - 5y \). Substitute: \[ 3(115 - 5y) + 2y = 150 \] \[ 345 - 15y + 2y = 150 \] \[ -13y = -195 \] \[ y = 15, \quad x = 115 - 75 = 40 \] So another corner is \( (40, 15) \).
  7. Step 7: The feasible region is bounded with corner points \( (2, 72) \), \( (15, 20) \) and \( (40, 15) \). Evaluate \( z = 6x + 3y \) at each corner. \[ z(2,72) = 6(2) + 3(72) = 12 + 216 = 228 \] \[ z(15,20) = 6(15) + 3(20) = 90 + 60 = 150 \] \[ z(40,15) = 6(40) + 3(15) = 240 + 45 = 285 \]
  8. Step 8: Compare the values of \( z \) at all corner points. The largest value is \( 285 \), which occurs at \( (40, 15) \). Since the feasible region is bounded, this maximum is guaranteed to be the optimal solution.

Final Answer

The maximum value is \( z = 285 \), attained at the point \( (40, 15) \), i.e. \( x = 40, \; y = 15 \).

Common Mistake

A common mistake is shading the wrong side of a \( \ge \) constraint. Since \( (0,0) \) fails \( 4x + y \ge 80 \) and \( x + 5y \ge 115 \), the feasible region must lie away from the origin for those lines, not towards it. Choosing the wrong side gives a wrong region and wrong corner points.

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: Write the boundary equation for each constraint by replacing the inequality sign with an equals sign. The three non-trivial boundary lines are: \[ 4x + y = 80, \] \[ 3x + 2y = 150, \] \[ x + 5y = 115. \] Reason: We plot straight lines first; the inequalities then tell us which half-plane (side of each line) belongs to the feasible region.
  2. Step 2: Find two intercept points for each line to make plotting easy. For \( 4x + y = 80 \): set \( x = 0 \) to get \( y = 80 \), set \( y = 0 \) to get \( x = 20 \). For \( 3x + 2y = 150 \): set \( x = 0 \) to get \( y = 75 \), set \( y = 0 \) to get \( x = 50 \). For \( x + 5y = 115 \): set \( x = 0 \) to get \( y = 23 \), set \( y = 0 \) to get \( x = 115 \). Reason: Two points uniquely determine a line, so this gives enough information to draw all three boundary lines on a graph.
  3. Step 3: Use the test point \( (0, 0) \) to identify which side of each boundary line satisfies the inequality, then shade the feasible region (the intersection of all satisfied half-planes). Checking \( 4(0) + 0 = 0 \): this is NOT \( \ge 80 \), so the feasible side is away from the origin. Checking \( 3(0) + 2(0) = 0 \): this IS \( \le 150 \), so the feasible side includes the origin. Checking \( 0 + 5(0) = 0 \): this is NOT \( \ge 115 \), so the feasible side is again away from the origin. Reason: The common region satisfying ALL constraints simultaneously is the feasible region in which any solution must lie.
  4. Step 4: Find the corner (vertex) points of the feasible region by solving pairs of boundary lines simultaneously. Intersect \( 4x + y = 80 \) and \( 3x + 2y = 150 \): multiply the first by 2 to get \( 8x + 2y = 160 \), subtract the second: \( 5x = 10 \), so \( x = 2 \) and \( y = 72 \). This gives corner \( (2, 72) \). Intersect \( 3x + 2y = 150 \) and \( x + 5y = 115 \): from the second, \( x = 115 - 5y \); substitute: \( 3(115 - 5y) + 2y = 150 \), giving \( 345 - 15y + 2y = 150 \), so \( 13y = 195 \), \( y = 15 \), \( x = 115 - 75 = 40 \). This gives corner \( (40, 15) \). Also check boundary intersections with the axes to confirm \( (0, 80) \) satisfies \( 3(0)+2(80) = 160 \le 150 \) — it does NOT, so \( (0,80) \) is outside the feasible region. 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 \( z = 6x + 3y \) at each feasible corner point. At \( (2, 72) \): \( z = 6(2) + 3(72) = 12 + 216 = 228 \). At \( (40, 15) \): \( z = 6(40) + 3(15) = 240 + 45 = 285 \). Reason: Comparing the values directly tells us where the objective function reaches its maximum over the feasible region.
  6. Step 6: Since the constraints \( 4x + y \ge 80 \) and \( x + 5y \ge 115 \) are of the \( \ge \) type, the feasible region extends to infinity in some directions. We must verify that no unbounded direction increases \( z \) further. Construct a half-plane \( 6x + 3y \ge 285 \) and check whether it shares any common point with the feasible region other than \( (40, 15) \). The check shows the feasible region does NOT extend into values where \( z > 285 \), confirming the maximum is finite and equals 285. Reason: For problems with unbounded feasible regions, a maximum may or may not exist; this verification step ensures we have found the true global maximum.

Final Answer

The maximum value is \( z = 285 \), attained at the point \( (40, 15) \), i.e. \( x = 40, \; y = 15 \).

Common Mistake

One common mistake: students forget to verify whether a finite maximum actually exists when the feasible region is unbounded (due to \( \ge \) constraints). Always check that no direction in the feasible region pushes the objective function to infinity before declaring a maximum.

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Find corner points of the feasible region: Solve pairs of boundary equations. Intersection of \( 4x + y = 80 \) and \( x + 5y = 115 \): multiply first by 5 to get \( 20x + 5y = 400 \), subtract second to get \( 19x = 285 \), so \( x = 15 \), \( y = 20 \). Intersection of \( 4x + y = 80 \) and \( 3x + 2y = 150 \): multiply first by 2 to get \( 8x + 2y = 160 \), subtract second to get \( 5x = 10 \), so \( x = 2 \), \( y = 72 \). Intersection of \( x + 5y = 115 \) and \( 3x + 2y = 150 \): multiply first by 3 to get \( 3x + 15y = 345 \), subtract second to get \( 13y = 195 \), so \( y = 15 \), \( x = 40 \).
  2. Step 2: Evaluate objective function at each corner: At \( (15, 20) \): \( z = 6(15) + 3(20) = 90 + 60 = 150 \). At \( (2, 72) \): \( z = 6(2) + 3(72) = 12 + 216 = 228 \). At \( (40, 15) \): \( z = 6(40) + 3(15) = 240 + 45 = 285 \).
  3. Step 3: Identify maximum: Maximum value \( z = 285 \) occurs at \( (40, 15) \).

Answer: The maximum value is \( z = 285 \), attained at the point \( (40, 15) \), i.e. \( x = 40, \; y = 15 \).

➕ More Examples

More Examples

Example 1

Question: Solve graphically the following linear programming problem: Maximize \( z = 5x + 4y \), subject to the constraints \( 6x + y \ge 60 \), \( x + y \le 50 \), \( x + 4y \ge 80 \), \( x \ge 0 \), \( y \ge 0 \).

Solution: Step 1: Write the constraints and objective function. Objective: Maximize \( z = 5x + 4y \) Constraints: \[ 6x + y \ge 60 \] \[ x + y \le 50 \] \[ x + 4y \ge 80 \] \[ x \ge 0, \quad y \ge 0 \] Step 2: Find intercepts of each boundary line. For \( 6x + y = 60 \): x-intercept = \( (10, 0) \), y-intercept = \( (0, 60) \). For \( x + y = 50 \): x-intercept = \( (50, 0) \), y-intercept = \( (0, 50) \). For \( x + 4y = 80 \): x-intercept = \( (80, 0) \), y-intercept = \( (0, 20) \). Step 3: Determine the feasible region satisfying all constraints simultaneously (including \( x \ge 0, y \ge 0 \)). Step 4: Find the corner points of the feasible region. Intersection of \( 6x + y = 60 \) and \( x + y = 50 \): Subtracting: \( 5x = 10 \), so \( x = 2 \), \( y = 48 \). Point: \( (2, 48) \). Check all constraints for \( (2, 48) \): \( 6(2) + 48 = 60 \ge 60 \) ✓, \( 2 + 48 = 50 \le 50 \) ✓, \( 2 + 4(48) = 194 \ge 80 \) ✓. Intersection of \( x + y = 50 \) and \( x + 4y = 80 \): Subtracting: \( -3y = -30 \), so \( y = 10 \), \( x = 40 \). Point: \( (40, 10) \). Check: \( 6(40) + 10 = 250 \ge 60 \) ✓, \( 40 + 10 = 50 \le 50 \) ✓, \( 40 + 40 = 80 \ge 80 \) ✓. Intersection of \( 6x + y = 60 \) and \( x + 4y = 80 \): From first: \( y = 60 - 6x \). Substituting: \( x + 4(60 - 6x) = 80 \), so \( x + 240 - 24x = 80 \), so \( -23x = -160 \), thus \( x = \frac{160}{23} \approx 6.96 \), \( y = 60 - 6 \cdot \frac{160}{23} = \frac{420}{23} \approx 18.26 \). Check \( x + y = \frac{160}{23} + \frac{420}{23} = \frac{580}{23} = \frac{580}{23} \approx 25.2 \le 50 \) ✓. Point: \( \left(\frac{160}{23}, \frac{420}{23}\right) \). So the corner points of the feasible region are: \( A = \left(\frac{160}{23}, \frac{420}{23}\right) \), \( B = (2, 48) \), \( C = (40, 10) \). Step 5: Evaluate \( z = 5x + 4y \) at each corner point. At \( A = \left(\frac{160}{23}, \frac{420}{23}\right) \): \[ z = 5 \cdot \frac{160}{23} + 4 \cdot \frac{420}{23} = \frac{800 + 1680}{23} = \frac{2480}{23} \approx 107.8 \] At \( B = (2, 48) \): \[ z = 5(2) + 4(48) = 10 + 192 = 202 \] At \( C = (40, 10) \): \[ z = 5(40) + 4(10) = 200 + 40 = 240 \] Step 6: The maximum value is \( z = 240 \) at \( (40, 10) \).

Answer: Maximum value of \( z = 240 \) at \( x = 40 \), \( y = 10 \).

Example 2

Question: Solve graphically the following linear programming problem: Maximize \( z = 7x + 5y \), subject to the constraints \( 2x + y \ge 14 \), \( x + 2y \le 28 \), \( x + y \ge 10 \), \( x \ge 0 \), \( y \ge 0 \).

Solution: Step 1: Write the objective function and constraints. Objective: Maximize \( z = 7x + 5y \) Constraints: \[ 2x + y \ge 14 \] \[ x + 2y \le 28 \] \[ x + y \ge 10 \] \[ x \ge 0, \quad y \ge 0 \] Step 2: Find intercepts of each boundary line. For \( 2x + y = 14 \): x-intercept = \( (7, 0) \), y-intercept = \( (0, 14) \). For \( x + 2y = 28 \): x-intercept = \( (28, 0) \), y-intercept = \( (0, 14) \). For \( x + y = 10 \): x-intercept = \( (10, 0) \), y-intercept = \( (0, 10) \). Step 3: Identify the feasible region satisfying all constraints with \( x \ge 0, y \ge 0 \). Step 4: Find corner points of the feasible region. Intersection of \( 2x + y = 14 \) and \( x + y = 10 \): Subtracting: \( x = 4 \), \( y = 6 \). Point: \( (4, 6) \). Check \( x + 2y = 4 + 12 = 16 \le 28 \) ✓. Intersection of \( 2x + y = 14 \) and \( x + 2y = 28 \): From first: \( y = 14 - 2x \). Substituting: \( x + 2(14 - 2x) = 28 \), so \( x + 28 - 4x = 28 \), thus \( -3x = 0 \), giving \( x = 0 \), \( y = 14 \). Point: \( (0, 14) \). Check \( x + y = 0 + 14 = 14 \ge 10 \) ✓, \( 2(0) + 14 = 14 \ge 14 \) ✓. Intersection of \( x + 2y = 28 \) and \( x + y = 10 \): Subtracting: \( y = 18 \), \( x = -8 \). Since \( x < 0 \), this point is outside the feasible region (violates \( x \ge 0 \)). Intersection of \( x + 2y = 28 \) with \( x = 0 \): \( y = 14 \). Already found: \( (0, 14) \). Intersection of \( 2x + y = 14 \) with \( y = 0 \): \( x = 7 \). Point: \( (7, 0) \). Check \( x + y = 7 \ge 10 \)? No, \( 7 < 10 \). This violates \( x + y \ge 10 \), so \( (7, 0) \) is NOT in the feasible region. Intersection of \( x + y = 10 \) with \( y = 0 \): \( x = 10 \). Point: \( (10, 0) \). Check \( 2(10) + 0 = 20 \ge 14 \) ✓, \( 10 + 0 = 10 \le 28 \) ✓. Intersection of \( x + 2y = 28 \) with \( y = 0 \): \( x = 28 \). Point: \( (28, 0) \). Check \( 2(28) + 0 = 56 \ge 14 \) ✓, \( 28 + 0 = 28 \ge 10 \) ✓. So the feasible region is unbounded (for large \( x \)) with corner points: \( (0, 14) \), \( (4, 6) \), \( (10, 0) \), and the region extends toward \( (28, 0) \) and beyond along \( x + 2y \le 28 \). The boundary of the feasible region has vertices: \( P_1 = (0, 14) \), \( P_2 = (4, 6) \), \( P_3 = (10, 0) \), \( P_4 = (28, 0) \). Step 5: Evaluate \( z = 7x + 5y \) at each vertex. At \( P_1 = (0, 14) \): \[ z = 7(0) + 5(14) = 70 \] At \( P_2 = (4, 6) \): \[ z = 7(4) + 5(6) = 28 + 30 = 58 \] At \( P_3 = (10, 0) \): \[ z = 7(10) + 5(0) = 70 \] At \( P_4 = (28, 0) \): \[ z = 7(28) + 5(0) = 196 \] Since the region is unbounded (extending in the direction of large \( x \)) and the coefficient of \( x \) in the objective function is positive, \( z \) increases without bound as \( x \) increases. Therefore, we check whether there exists a half-plane \( 7x + 5y > 196 \) that has a common point with the feasible region. Since for any \( x > 28 \) with \( y = 0 \), both \( x + 2y \le 28 \) is violated, the feasible region is actually bounded by \( x + 2y \le 28 \) and the maximum is attained at \( P_4 = (28, 0) \). Verifying \( (28, 0) \) satisfies all constraints: \( 2(28) + 0 = 56 \ge 14 \) ✓, \( 28 + 0 = 28 \le 28 \) ✓, \( 28 + 0 = 28 \ge 10 \) ✓, \( x = 28 \ge 0 \) ✓, \( y = 0 \ge 0 \) ✓. Step 6: Maximum value is \( z = 196 \) at \( (28, 0) \).

Answer: Maximum value of \( z = 196 \) at \( x = 28 \), \( y = 0 \).

🎯 Try a Similar Question

Try a Similar Question

Question: Solve graphically the following linear programming problem: Maximize \( z = 5x + 4y \), subject to the constraints \( 2x + y \ge 40 \), \( x + 2y \le 100 \), \( x + 3y \ge 90 \), \( x \ge 0 \), \( y \ge 0 \).

Solution

  1. Step 1: Convert inequalities to equations for graphing: Write the boundary lines: \( L_1: 2x + y = 40 \), \( L_2: x + 2y = 100 \), \( L_3: x + 3y = 90 \).
  2. Step 2: Find intercepts of each boundary line: For \( L_1: 2x + y = 40 \): x-intercept \( (20, 0) \), y-intercept \( (0, 40) \). For \( L_2: x + 2y = 100 \): x-intercept \( (100, 0) \), y-intercept \( (0, 50) \). For \( L_3: x + 3y = 90 \): x-intercept \( (90, 0) \), y-intercept \( (0, 30) \).
  3. Step 3: Identify the feasible region: The constraints \( 2x + y \ge 40 \) and \( x + 3y \ge 90 \) require the region on or above those lines, while \( x + 2y \le 100 \) requires the region on or below that line. Combined with \( x \ge 0 \) and \( y \ge 0 \), the feasible region is a bounded polygon.
  4. Step 4: Find the corner points (vertices) of the feasible region: Intersection of \( L_1 \) and \( L_3 \): Solve \( 2x + y = 40 \) and \( x + 3y = 90 \). From the first equation \( y = 40 - 2x \). Substituting: \( x + 3(40 - 2x) = 90 \), so \( x + 120 - 6x = 90 \), giving \( -5x = -30 \), hence \( x = 6 \), \( y = 28 \). Corner point: \( (6, 28) \). Intersection of \( L_1 \) and \( L_2 \): Solve \( 2x + y = 40 \) and \( x + 2y = 100 \). From the first: \( y = 40 - 2x \). Substituting: \( x + 2(40 - 2x) = 100 \), so \( x + 80 - 4x = 100 \), giving \( -3x = 20 \), hence \( x = -\frac{20}{3} \). Since \( x < 0 \), this is outside the feasible region. Intersection of \( L_2 \) and \( L_3 \): Solve \( x + 2y = 100 \) and \( x + 3y = 90 \). Subtracting: \( y = -10 \). Since \( y < 0 \), this is outside the feasible region. Check axis intersections with constraints: At \( x = 0 \): from \( 2(0) + y \ge 40 \Rightarrow y \ge 40 \); from \( 0 + 3y \ge 90 \Rightarrow y \ge 30 \); from \( 0 + 2y \le 100 \Rightarrow y \le 50 \). So \( y \in [40, 50] \) giving corners \( (0, 40) \) and \( (0, 50) \). At \( y = 0 \): from \( 2x \ge 40 \Rightarrow x \ge 20 \); from \( x \ge 90 \); from \( x \le 100 \). So \( x \in [90, 100] \) giving corners \( (90, 0) \) and \( (100, 0) \). Also find intersection of \( L_2 \) with \( y = 0 \): \( (100, 0) \), and with \( x = 0 \): \( (0, 50) \). Intersection of \( L_3 \) with \( y = 0 \): \( (90, 0) \), and with \( x = 0 \): \( (0, 30) \) but this violates \( 2(0) + 30 = 30 < 40 \). The feasible corner points are: \( A = (6, 28) \), \( B = (0, 40) \), \( C = (0, 50) \), \( D = (100, 0) \), \( E = (90, 0) \).
  5. Step 5: Evaluate the objective function at each corner point: At \( A(6, 28) \): \( z = 5(6) + 4(28) = 30 + 112 = 142 \). At \( B(0, 40) \): \( z = 5(0) + 4(40) = 0 + 160 = 160 \). At \( C(0, 50) \): \( z = 5(0) + 4(50) = 0 + 200 = 200 \). At \( D(100, 0) \): \( z = 5(100) + 4(0) = 500 + 0 = 500 \). At \( E(90, 0) \): \( z = 5(90) + 4(0) = 450 + 0 = 450 \).
  6. Step 6: Determine the maximum value: Comparing all values: \( z = 142, 160, 200, 500, 450 \). The maximum value is \( z = 500 \) at the corner point \( D(100, 0) \).

Answer: The maximum value of \( z = 5x + 4y \) is \( z = 500 \), attained at the point \( (100, 0) \), i.e. \( x = 100, \; y = 0 \).

Everything you get with Solver7

More questions in Linear Programming