Example 1
Question: Solve the following Linear Programming Problem graphically: Maximize \( Z = 500x + 300y \) Subject to constraints: \[ x + y \le 10 \] \[ 3x + y \ge 9 \] \[ x + 2y \le 14 \] \[ x, y \ge 0 \]
Solution: We identify the constraints and plot each boundary line. Constraint 1: \( x + y = 10 \) passes through \( (10, 0) \) and \( (0, 10) \). Constraint 2: \( 3x + y = 9 \) passes through \( (3, 0) \) and \( (0, 9) \). Constraint 3: \( x + 2y = 14 \) passes through \( (14, 0) \) and \( (0, 7) \). With \( x \ge 0 \) and \( y \ge 0 \), the feasible region lies in the first quadrant, above the line \( 3x + y = 9 \), and below (or on) the lines \( x + y = 10 \) and \( x + 2y = 14 \). Finding corner points: Corner A: Intersection of \( x + y = 10 \) and \( x = 0 \): point \( (0, 10) \). Check \( x + 2y = 0 + 20 = 20 > 14 \), so \( (0, 10) \) violates constraint 3. So this is not in the feasible region. Let us find the vertices systematically by intersecting boundary lines within the feasible region. Point P: Intersection of \( 3x + y = 9 \) and \( x = 0 \): \[ y = 9, \quad x = 0 \] Check \( x + y = 9 \le 10 \) and \( x + 2y = 18 > 14 \). This violates constraint 3. Not feasible. Point P: Intersection of \( 3x + y = 9 \) and \( y = 0 \): \[ x = 3, \quad y = 0 \] Check \( x + y = 3 \le 10 \) and \( x + 2y = 3 \le 14 \). Feasible. Corner point \( (3, 0) \). Point Q: Intersection of \( x + 2y = 14 \) and \( y = 0 \): \[ x = 14, \quad y = 0 \] Check \( x + y = 14 > 10 \). Not feasible. Point Q: Intersection of \( x + y = 10 \) and \( x + 2y = 14 \): Subtracting the first from the second: \( y = 4 \), then \( x = 6 \). Check \( 3x + y = 18 + 4 = 22 \ge 9 \). Feasible. Corner point \( (6, 4) \). Point R: Intersection of \( x + y = 10 \) and \( 3x + y = 9 \): Subtracting: \( 2x = -1 \), so \( x = -0.5 \). Not feasible (\( x < 0 \)). Point S: Intersection of \( 3x + y = 9 \) and \( x + 2y = 14 \): From first equation: \( y = 9 - 3x \). Substituting: \[ x + 2(9 - 3x) = 14 \] \[ x + 18 - 6x = 14 \] \[ -5x = -4 \] \[ x = \frac{4}{5} = 0.8, \quad y = 9 - 3(0.8) = 9 - 2.4 = 6.6 \] Check \( x + y = 7.4 \le 10 \). Feasible. Corner point \( (0.8, 6.6) \). Point T: On \( y \)-axis with \( 3x + y \ge 9 \): at \( x = 0 \), need \( y \ge 9 \). But \( x + 2y \le 14 \) gives \( y \le 7 \). No feasible point on the \( y \)-axis. So the feasible region has vertices: \( (3, 0) \), \( (6, 4) \), and \( (0.8, 6.6) \). Also check \( (10, 0) \): \( 3(10) + 0 = 30 \ge 9 \), \( 10 + 0 = 10 \le 10 \), \( 10 + 0 = 10 \le 14 \). Feasible! Corner point \( (10, 0) \). Updated vertices: \( (3, 0) \), \( (10, 0) \), \( (6, 4) \), and \( (0.8, 6.6) \). Now evaluate \( Z = 500x + 300y \) at each corner: At \( (3, 0) \): \[ Z = 500(3) + 300(0) = 1500 \] At \( (10, 0) \): \[ Z = 500(10) + 300(0) = 5000 \] At \( (6, 4) \): \[ Z = 500(6) + 300(4) = 3000 + 1200 = 4200 \] At \( (0.8, 6.6) \): \[ Z = 500(0.8) + 300(6.6) = 400 + 1980 = 2380 \] The maximum value of Z is 5000 at \( (10, 0) \).
Answer: Maximum \( Z = 5000 \) at \( x = 10,\ y = 0 \).
Example 2
Question: Solve the following Linear Programming Problem graphically: Maximize \( Z = 400x + 700y \) Subject to constraints: \[ 2x + 3y \le 18 \] \[ x + 5y \ge 10 \] \[ 3x + y \le 15 \] \[ x, y \ge 0 \]
Solution: We plot the boundary lines of all constraints. Line 1: \( 2x + 3y = 18 \) passes through \( (9, 0) \) and \( (0, 6) \). Line 2: \( x + 5y = 10 \) passes through \( (10, 0) \) and \( (0, 2) \). Line 3: \( 3x + y = 15 \) passes through \( (5, 0) \) and \( (0, 15) \). The feasible region satisfies \( 2x + 3y \le 18 \), \( x + 5y \ge 10 \), \( 3x + y \le 15 \), and \( x, y \ge 0 \). Finding corner points: Point A: Intersection of \( x + 5y = 10 \) and \( y = 0 \): \[ x = 10, \quad y = 0 \] Check \( 2(10) + 3(0) = 20 > 18 \). Not feasible. Point A: Intersection of \( x + 5y = 10 \) and \( 3x + y = 15 \): From the second equation: \( y = 15 - 3x \). Substituting: \[ x + 5(15 - 3x) = 10 \] \[ x + 75 - 15x = 10 \] \[ -14x = -65 \] \[ x = \frac{65}{14} \approx 4.64, \quad y = 15 - 3 \times \frac{65}{14} = 15 - \frac{195}{14} = \frac{210 - 195}{14} = \frac{15}{14} \approx 1.07 \] Check \( 2x + 3y = 2 \times \frac{65}{14} + 3 \times \frac{15}{14} = \frac{130 + 45}{14} = \frac{175}{14} = 12.5 \le 18 \). Feasible. Corner point \( \left(\frac{65}{14}, \frac{15}{14}\right) \). Point B: Intersection of \( 3x + y = 15 \) and \( 2x + 3y = 18 \): From first: \( y = 15 - 3x \). Substituting: \[ 2x + 3(15 - 3x) = 18 \] \[ 2x + 45 - 9x = 18 \] \[ -7x = -27 \] \[ x = \frac{27}{7} \approx 3.86, \quad y = 15 - 3 \times \frac{27}{7} = 15 - \frac{81}{7} = \frac{105 - 81}{7} = \frac{24}{7} \approx 3.43 \] Check \( x + 5y = \frac{27}{7} + \frac{120}{7} = \frac{147}{7} = 21 \ge 10 \). Feasible. Corner point \( \left(\frac{27}{7}, \frac{24}{7}\right) \). Point C: Intersection of \( 2x + 3y = 18 \) and \( x = 0 \): \[ y = 6, \quad x = 0 \] Check \( x + 5y = 30 \ge 10 \) and \( 3x + y = 6 \le 15 \). Feasible. Corner point \( (0, 6) \). Point D: Intersection of \( 3x + y = 15 \) and \( x = 0 \): \[ y = 15, \quad x = 0 \] Check \( 2(0) + 3(15) = 45 > 18 \). Not feasible. Point D: Intersection of \( x + 5y = 10 \) and \( x = 0 \): \[ y = 2, \quad x = 0 \] Check \( 2(0) + 3(2) = 6 \le 18 \) and \( 3(0) + 2 = 2 \le 15 \). Feasible. Corner point \( (0, 2) \). So the feasible region has corner points: \( (0, 2) \), \( \left(\frac{65}{14}, \frac{15}{14}\right) \), \( \left(\frac{27}{7}, \frac{24}{7}\right) \), and \( (0, 6) \). Now evaluate \( Z = 400x + 700y \) at each corner: At \( (0, 2) \): \[ Z = 400(0) + 700(2) = 1400 \] At \( \left(\frac{65}{14}, \frac{15}{14}\right) \): \[ Z = 400 \times \frac{65}{14} + 700 \times \frac{15}{14} = \frac{26000}{14} + \frac{10500}{14} = \frac{36500}{14} \approx 2607 \] At \( \left(\frac{27}{7}, \frac{24}{7}\right) \): \[ Z = 400 \times \frac{27}{7} + 700 \times \frac{24}{7} = \frac{10800}{7} + \frac{16800}{7} = \frac{27600}{7} \approx 3943 \] At \( (0, 6) \): \[ Z = 400(0) + 700(6) = 4200 \] The maximum value of Z is 4200 at \( (0, 6) \).
Answer: Maximum \( Z = 4200 \) at \( x = 0,\ y = 6 \).