Linear Programming Problem Analysis

The given problem is a linear programming problem where we need to maximize an objective function subject to a set of linear constraints. The objective function is:

\( \text{Maximize } z = 3x + 4y \)

The constraints are:

• \( x + y \le 12 \)
• \( 2x + 3y \le 30 \)
• \( x + 4y \le 36 \)
• \( x \ge 0 \)
• \( y \ge 0 \)

To find the optimal solution, we use the graphical method. This involves plotting the feasible region defined by the constraints and then evaluating the objective function at the vertices of this region.

Constraints and Feasible Region

First, we treat the inequalities as equalities to find the boundary lines:

• \( L_1: x + y = 12 \)
• \( L_2: 2x + 3y = 30 \)
• \( L_3: x + 4y = 36 \)

The constraints \( x \ge 0 \) and \( y \ge 0 \) indicate that the feasible region is in the first quadrant.

The feasible region is the area that satisfies all constraints simultaneously. We find the vertices of this region by identifying the intersection points of the boundary lines that lie within the feasible region.

Vertices of the Feasible Region

The potential vertices are the intersections of the boundary lines and the axes, provided they satisfy all constraints:

• Intersection of x=0 and y=0: \( (0,0) \). This point satisfies all constraints.
• Intersection of y=0 and \( L_1 \): \( x + 0 = 12 \implies x = 12 \). Point \( (12,0) \).
  • Check \( L_2 \): \( 2(12) + 3(0) = 24 \le 30 \) (Satisfied)
  • Check \( L_3 \): \( 12 + 4(0) = 12 \le 36 \) (Satisfied)
  Point \( (12,0) \) is a vertex.
• Intersection of x=0 and \( L_3 \): \( 0 + 4y = 36 \implies y = 9 \). Point \( (0,9) \).
  • Check \( L_1 \): \( 0 + 9 = 9 \le 12 \) (Satisfied)
  • Check \( L_2 \): \( 2(0) + 3(9) = 27 \le 30 \) (Satisfied)
  Point \( (0,9) \) is a vertex.
• Intersection of \( L_1 \) and \( L_2 \):

  \( x + y = 12 \quad \dots (1) \)

  \( 2x + 3y = 30 \quad \dots (2) \)

  Multiply (1) by 2: \( 2x + 2y = 24 \quad \dots (3) \). Subtract (3) from (2): \( (2x + 3y) - (2x + 2y) = 30 - 24 \implies y = 6 \). Substitute \( y = 6 \) into (1): \( x + 6 = 12 \implies x = 6 \). Point \( (6,6) \).
  • Check \( L_3 \): \( 6 + 4(6) = 6 + 24 = 30 \le 36 \) (Satisfied)
  Point \( (6,6) \) is a vertex.
• Intersection of \( L_2 \) and \( L_3 \):

  \( 2x + 3y = 30 \quad \dots (4) \)

  \( x + 4y = 36 \quad \dots (5) \)

  Multiply (5) by 2: \( 2x + 8y = 72 \quad \dots (6) \). Subtract (4) from (6): \( (2x + 8y) - (2x + 3y) = 72 - 30 \implies 5y = 42 \implies y = 8.4 \). Substitute \( y = 8.4 \) into (5): \( x + 4(8.4) = 36 \implies x + 33.6 = 36 \implies x = 2.4 \). Point \( (2.4, 8.4) \).
  • Check \( L_1 \): \( 2.4 + 8.4 = 10.8 \le 12 \) (Satisfied)
  Point \( (2.4, 8.4) \) is a vertex.
• Intersection of \( L_1 \) and \( L_3 \):

  \( x + y = 12 \quad \dots (7) \)

  \( x + 4y = 36 \quad \dots (8) \)

  Subtract (7) from (8): \( (x + 4y) - (x + y) = 36 - 12 \implies 3y = 24 \implies y = 8 \). Substitute \( y = 8 \) into (7): \( x + 8 = 12 \implies x = 4 \). Point \( (4,8) \).
  • Check \( L_2 \): \( 2(4) + 3(8) = 8 + 24 = 32 \). \( 32 \not\le 30 \) (Not Satisfied)
  Point \( (4,8) \) is not in the feasible region.

The vertices of the feasible region are \( (0,0) \), \( (12,0) \), \( (6,6) \), \( (2.4, 8.4) \), and \( (0,9) \).

Optimal Solution Evaluation

Now we evaluate the objective function \( z = 3x + 4y \) at each vertex:

Comparing the values of z at the vertices, the maximum value is 42, which occurs at the point \( (6,6) \).

Therefore, the optimal solution is \( x^* = 6 \) and \( y^* = 6 \).

Conclusion

The optimal solution for the given linear programming problem, which maximizes the objective function \( z = 3x + 4y \) subject to the constraints, is found at the vertex \( (6,6) \) of the feasible region. At this point, the maximum value of z is 42.

The optimal values for x and y are:

\( x^* = 6 \)

\( y^* = 6 \)