Example 1
Question: Solve the following Linear Programming Problem graphically: Minimise \( Z = 300x + 600y \) subject to the constraints: \[ x + 2y \ge 8 \] \[ 2x + y \le 14 \] \[ x \ge 0, \quad y \ge 0 \]
Solution: We are given: Objective function: \( Z = 300x + 600y \) Constraints: \[ x + 2y \ge 8 \quad \cdots (1) \] \[ 2x + y \le 14 \quad \cdots (2) \] \[ x \ge 0, \quad y \ge 0 \quad \cdots (3) \] Step 1: Find boundary lines and key points. For line \( x + 2y = 8 \): when \( x = 0 \), \( y = 4 \); when \( y = 0 \), \( x = 8 \). So points are \( (0, 4) \) and \( (8, 0) \). For line \( 2x + y = 14 \): when \( x = 0 \), \( y = 14 \); when \( y = 0 \), \( x = 7 \). So points are \( (0, 14) \) and \( (7, 0) \). Step 2: Find the intersection of the two boundary lines. Solve simultaneously: \[ x + 2y = 8 \quad \cdots (i) \] \[ 2x + y = 14 \quad \cdots (ii) \] From (i): \( x = 8 - 2y \). Substituting into (ii): \[ 2(8 - 2y) + y = 14 \] \[ 16 - 4y + y = 14 \] \[ 16 - 3y = 14 \] \[ 3y = 2 \] \[ y = \frac{2}{3} \] Then \( x = 8 - 2 \times \frac{2}{3} = 8 - \frac{4}{3} = \frac{20}{3} \). So the intersection point is \( \left(\frac{20}{3},\ \frac{2}{3}\right) \). Step 3: Determine the feasible region. Constraint (1) requires \( x + 2y \ge 8 \), so the region is above or on the line \( x + 2y = 8 \). Constraint (2) requires \( 2x + y \le 14 \), so the region is below or on the line \( 2x + y = 14 \). With \( x \ge 0 \) and \( y \ge 0 \), the feasible region is bounded. Step 4: Identify corner points of the feasible region. The corner points are: \( A = (0, 4) \) (intersection of \( x + 2y = 8 \) and \( x = 0 \)), \( B = \left(\frac{20}{3}, \frac{2}{3}\right) \) (intersection of the two boundary lines), \( C = (7, 0) \) (intersection of \( 2x + y = 14 \) and \( y = 0 \)). We must verify \( C = (7, 0) \) satisfies constraint (1): \( 7 + 0 = 7 < 8 \). This does NOT satisfy \( x + 2y \ge 8 \), so \( (7, 0) \) is NOT in the feasible region. We must verify \( (8, 0) \): check constraint (2): \( 2(8) + 0 = 16 > 14 \). This does NOT satisfy \( 2x + y \le 14 \), so \( (8, 0) \) is NOT in the feasible region. Also check \( (0, 14) \): satisfies \( x + 2y \ge 8 \) since \( 0 + 28 = 28 \ge 8 \). But \( 0 + 14 = 14 \le 14 \), so it lies on line (2). So the valid corner points of the feasible region are: \( A = (0, 4) \), \( B = \left(\frac{20}{3}, \frac{2}{3}\right) \), and \( D = (0, 14) \). Step 5: Evaluate \( Z = 300x + 600y \) at each corner point. At \( A = (0, 4) \): \[ Z = 300(0) + 600(4) = 0 + 2400 = 2400 \] At \( B = \left(\frac{20}{3}, \frac{2}{3}\right) \): \[ Z = 300 \times \frac{20}{3} + 600 \times \frac{2}{3} = 2000 + 400 = 2400 \] At \( D = (0, 14) \): \[ Z = 300(0) + 600(14) = 0 + 8400 = 8400 \] Step 6: Identify the minimum. The minimum value of \( Z \) is \( 2400 \), achieved at both \( A = (0, 4) \) and \( B = \left(\frac{20}{3}, \frac{2}{3}\right) \). Since two adjacent corner points give the same minimum value, every point on the line segment \( AB \) also gives \( Z = 2400 \). Hence there are infinitely many optimal solutions.
Answer: Minimum value of \( Z = 300x + 600y \) is \( 2400 \), achieved at all points on the segment joining \( (0, 4) \) and \( \left(\frac{20}{3}, \frac{2}{3}\right) \).
Example 2
Question: Solve the following Linear Programming Problem graphically: Minimise \( Z = 400x + 300y \) subject to the constraints: \[ 2x + y \ge 10 \] \[ x + 2y \le 16 \] \[ x \ge 0, \quad y \ge 0 \]
Solution: We are given: Objective function: \( Z = 400x + 300y \) Constraints: \[ 2x + y \ge 10 \quad \cdots (1) \] \[ x + 2y \le 16 \quad \cdots (2) \] \[ x \ge 0, \quad y \ge 0 \quad \cdots (3) \] Step 1: Find boundary lines and key points. For line \( 2x + y = 10 \): when \( x = 0 \), \( y = 10 \); when \( y = 0 \), \( x = 5 \). Points: \( (0, 10) \) and \( (5, 0) \). For line \( x + 2y = 16 \): when \( x = 0 \), \( y = 8 \); when \( y = 0 \), \( x = 16 \). Points: \( (0, 8) \) and \( (16, 0) \). Step 2: Find the intersection of the two boundary lines. Solve: \[ 2x + y = 10 \quad \cdots (i) \] \[ x + 2y = 16 \quad \cdots (ii) \] Multiply (i) by 2: \( 4x + 2y = 20 \). Subtract (ii): \[ (4x + 2y) - (x + 2y) = 20 - 16 \] \[ 3x = 4 \] \[ x = \frac{4}{3} \] Substitute into (i): \[ 2 \times \frac{4}{3} + y = 10 \] \[ \frac{8}{3} + y = 10 \] \[ y = 10 - \frac{8}{3} = \frac{22}{3} \] Intersection point: \( E = \left(\frac{4}{3},\ \frac{22}{3}\right) \). Step 3: Determine the feasible region. Constraint (1): \( 2x + y \ge 10 \) — region on or above the line \( 2x + y = 10 \). Constraint (2): \( x + 2y \le 16 \) — region on or below the line \( x + 2y = 16 \). With \( x \ge 0 \) and \( y \ge 0 \), the feasible region is the intersection of these half-planes in the first quadrant. Step 4: Identify corner points. Candidate corners: \( (5, 0) \): Check constraint (2): \( 5 + 0 = 5 \le 16 \). Valid. \( (16, 0) \): Check constraint (1): \( 32 + 0 = 32 \ge 10 \). Valid. \( (0, 10) \): Check constraint (2): \( 0 + 20 = 20 > 16 \). NOT valid. \( (0, 8) \): Check constraint (1): \( 0 + 8 = 8 < 10 \). NOT valid. \( E = \left(\frac{4}{3}, \frac{22}{3}\right) \): intersection of the two lines. So the valid corner points are: \( A = (5, 0) \), \( B = (16, 0) \), and \( E = \left(\frac{4}{3}, \frac{22}{3}\right) \). Step 5: Evaluate \( Z = 400x + 300y \) at each corner point. At \( A = (5, 0) \): \[ Z = 400(5) + 300(0) = 2000 \] At \( B = (16, 0) \): \[ Z = 400(16) + 300(0) = 6400 \] At \( E = \left(\frac{4}{3}, \frac{22}{3}\right) \): \[ Z = 400 \times \frac{4}{3} + 300 imes \frac{22}{3} = \frac{1600}{3} + \frac{6600}{3} = \frac{8200}{3} \approx 2733.33 \] Step 6: Identify the minimum. Comparing the values: \[ Z(A) = 2000, \quad Z(E) = \frac{8200}{3} \approx 2733, \quad Z(B) = 6400 \] The minimum value of \( Z \) is \( 2000 \) at \( A = (5, 0) \).
Answer: Minimum value of \( Z = 400x + 300y \) is \( 2000 \), attained at \( (5,\ 0) \).