Example 1
Question: Solve the following linear programming problem graphically: Minimise and Maximise \(Z = 5x + 10y\) subject to the constraints: \(x + 2y \le 120\), \(x + y \ge 20\), \(x \le 2y\), \(x \ge 0,\ y \ge 0\).
Solution: We wish to find the minimum and maximum of \(Z = 5x + 10y\) subject to the given constraints. Step 1: Identify the boundary lines. Constraint 1: \(x + 2y = 120\) — passes through \((120, 0)\) and \((0, 60)\). Constraint 2: \(x + y = 20\) — passes through \((20, 0)\) and \((0, 20)\). Constraint 3: \(x = 2y\) — passes through \((0, 0)\), \((20, 10)\), and \((40, 20)\). Step 2: Determine the feasible region. The feasible region satisfies all five conditions: \(x + 2y \le 120\), \(x + y \ge 20\), \(x \le 2y\), \(x \ge 0\), \(y \ge 0\). Step 3: Find the corner points of the feasible region. Corner A — intersection of \(x + y = 20\) and \(x = 2y\): Substituting \(x = 2y\) into \(x + y = 20\): \[2y + y = 20 \Rightarrow 3y = 20 \Rightarrow y = \frac{20}{3},\quad x = \frac{40}{3}\] So A = \(\left(\frac{40}{3},\ \frac{20}{3}\right)\). Corner B — intersection of \(x + 2y = 120\) and \(x = 2y\): Substituting \(x = 2y\): \[2y + 2y = 120 \Rightarrow 4y = 120 \Rightarrow y = 30,\quad x = 60\] So B = \((60, 30)\). Corner C — intersection of \(x + 2y = 120\) and \(x + y = 20\): Subtracting: \((x + 2y) - (x + y) = 120 - 20\) \[y = 100,\quad x = 20 - 100 = -80\] This gives \(x = -80 < 0\), which is outside the feasible region. So C is not a valid corner. Corner D — intersection of \(x + 2y = 120\) and \(x = 0\): \[2y = 120 \Rightarrow y = 60\] Check \(x \le 2y\): \(0 \le 120\) — satisfied. Check \(x + y \ge 20\): \(60 \ge 20\) — satisfied. So D = \((0, 60)\). Corner E — intersection of \(x + y = 20\) and \(x = 0\): \[y = 20\] Check \(x \le 2y\): \(0 \le 40\) — satisfied. Check \(x + 2y \le 120\): \(40 \le 120\) — satisfied. So E = \((0, 20)\). Step 4: The feasible region is bounded with vertices A\(\left(\frac{40}{3}, \frac{20}{3}\right)\), B\((60, 30)\), D\((0, 60)\), E\((0, 20)\). Step 5: Evaluate \(Z = 5x + 10y\) at each corner. At A\(\left(\frac{40}{3}, \frac{20}{3}\right)\): \[Z = 5 \cdot \frac{40}{3} + 10 \cdot \frac{20}{3} = \frac{200}{3} + \frac{200}{3} = \frac{400}{3} \approx 133.33\] At B\((60, 30)\): \[Z = 5(60) + 10(30) = 300 + 300 = 600\] At D\((0, 60)\): \[Z = 5(0) + 10(60) = 600\] At E\((0, 20)\): \[Z = 5(0) + 10(20) = 200\] Step 6: Compare the values. Minimum \(Z = \dfrac{400}{3}\) at A\(\left(\dfrac{40}{3}, \dfrac{20}{3}\right)\). Maximum \(Z = 600\) at both B\((60, 30)\) and D\((0, 60)\). Since maximum is achieved at two corner points, it is also achieved at every point on the segment BD. Thus, Minimum \(Z = \dfrac{400}{3}\) at \(\left(\dfrac{40}{3}, \dfrac{20}{3}\right)\), and Maximum \(Z = 600\) along the line segment from \((60, 30)\) to \((0, 60)\).
Answer: Minimum \(Z = \dfrac{400}{3}\) at \(\left(\dfrac{40}{3},\ \dfrac{20}{3}\right)\); Maximum \(Z = 600\) at all points on the segment joining \((60, 30)\) and \((0, 60)\).
Example 2
Question: Solve the following linear programming problem graphically: Minimise and Maximise \(Z = 4x + 6y\) subject to the constraints: \(2x + y \le 40\), \(x + y \ge 15\), \(y \le 2x\), \(x \ge 0,\ y \ge 0\).
Solution: We wish to find the minimum and maximum of \(Z = 4x + 6y\) subject to the given constraints. Step 1: Identify the boundary lines. Constraint 1: \(2x + y = 40\) — passes through \((20, 0)\) and \((0, 40)\). Constraint 2: \(x + y = 15\) — passes through \((15, 0)\) and \((0, 15)\). Constraint 3: \(y = 2x\) — passes through \((0, 0)\), \((5, 10)\), and \((10, 20)\). Step 2: Determine the feasible region satisfying all constraints. Step 3: Find the corner points. Corner A — intersection of \(x + y = 15\) and \(y = 2x\): Substituting \(y = 2x\): \[x + 2x = 15 \Rightarrow 3x = 15 \Rightarrow x = 5,\quad y = 10\] So A = \((5, 10)\). Check \(2x + y \le 40\): \(10 + 10 = 20 \le 40\) — satisfied. Corner B — intersection of \(2x + y = 40\) and \(y = 2x\): Substituting \(y = 2x\): \[2x + 2x = 40 \Rightarrow 4x = 40 \Rightarrow x = 10,\quad y = 20\] So B = \((10, 20)\). Check \(x + y \ge 15\): \(10 + 20 = 30 \ge 15\) — satisfied. Corner C — intersection of \(2x + y = 40\) and \(x + y = 15\): Subtracting: \((2x + y) - (x + y) = 40 - 15\) \[x = 25,\quad y = 15 - 25 = -10\] Since \(y = -10 < 0\), this point is outside the feasible region. Corner D — intersection of \(2x + y = 40\) and \(y = 0\): \[2x = 40 \Rightarrow x = 20\] Check \(y \le 2x\): \(0 \le 40\) — satisfied. Check \(x + y \ge 15\): \(20 \ge 15\) — satisfied. So D = \((20, 0)\). Corner E — intersection of \(x + y = 15\) and \(y = 0\): \[x = 15\] Check \(y \le 2x\): \(0 \le 30\) — satisfied. Check \(2x + y \le 40\): \(30 \le 40\) — satisfied. So E = \((15, 0)\). Step 4: The feasible region has vertices A\((5, 10)\), B\((10, 20)\), D\((20, 0)\), E\((15, 0)\). Step 5: Evaluate \(Z = 4x + 6y\) at each vertex. At A\((5, 10)\): \[Z = 4(5) + 6(10) = 20 + 60 = 80\] At B\((10, 20)\): \[Z = 4(10) + 6(20) = 40 + 120 = 160\] At D\((20, 0)\): \[Z = 4(20) + 6(0) = 80 + 0 = 80\] At E\((15, 0)\): \[Z = 4(15) + 6(0) = 60 + 0 = 60\] Step 6: Compare the values. Minimum \(Z = 60\) at E\((15, 0)\). Maximum \(Z = 160\) at B\((10, 20)\). Also note that \(Z = 80\) at both A\((5, 10)\) and D\((20, 0)\), meaning \(Z = 80\) along the entire segment AD, but this is neither the global minimum nor the global maximum. Thus, Minimum \(Z = 60\) at \((15, 0)\), and Maximum \(Z = 160\) at \((10, 20)\).
Answer: Minimum \(Z = 60\) at \((15, 0)\); Maximum \(Z = 160\) at \((10, 20)\).