Q.The number of feasible solutions of the linear programming problem given as Maximize $z = 15x + 30y$ subject to constraints : $3x + y \leq 12$, $x + 2y \leq 10$, $x \geq 0$, $y \geq 0$ is

The key idea here is Multiple Optimal Solutions in Linear Programming. This situation arises when the objective function's gradient is parallel to one of the binding constraints that forms an edge of the feasible region, along which the objective function is maximized.

1. First, we identify the corner points of the feasible region defined by the constraints $3x + y \leq 12$, $x + 2y \leq 10$, $x \geq 0$, $y \geq 0$. These points are $(0,0)$, $(4,0)$, $(0,5)$, and the intersection of $3x+y=12$ and $x+2y=10$, which is $(14/5, 18/5)$.
2. Next, we evaluate the objective function $z = 15x + 30y$ at each corner point:
   • At $(0,0)$, $z = 0$.
   • At $(4,0)$, $z = 15(4) + 30(0) = 60$.
   • At $(0,5)$, $z = 15(0) + 30(5) = 150$.
   • At $(14/5, 18/5)$, $z = 15(14/5) + 30(18/5) = 3(14) + 6(18) = 42 + 108 = 150$. …

In a Linear Programming Problem (LPP), we aim to maximize or minimize an objective function subject to a set of linear constraints. The set of all points satisfying these constraints is called the feasible region. This region is always a convex polygon. A fundamental theorem of LPP states that if an optimal solution exists, it will occur at one of the corner points (vertices) of this feasible region.

However, it is possible for an LPP to have multiple optimal solutions. This occurs when the objective function line is parallel to one of the edges of the feasible region, and that edge lies on the boundary of the optimal value. In such a scenario, every point on that entire edge segment, including its two corner points, will yield the same optimal value. Since a line segment contains infinitely many points, there will be infinitely many optimal solutions.

Let's solve the given problem step-by-step.

1. Graph the Feasible Region:

   We need to plot the lines corresponding to the given constraints and identify the region that satisfies all inequalities.

   • $3x + y \leq 12$ (Let's call the line $L_1: 3x + y = 12$)
     • If $x=0$, $y=12$. Point: $(0,12)$
     • If $y=0$, $3x=12 \implies x=4$. Point: $(4,0)$
   • $x + 2y \leq 10$ (Let's call the line $L_2: x + 2y = 10$)
     • If $x=0$, $2y=10 \implies y=5$. Point: $(0,5)$
     • If $y=0$, $x=10$. Point: $(10,0)$
   • $x \geq 0$ (This means the feasible region is to the right of the y-axis)
   • $y \geq 0$ (This means the feasible region is above the x-axis)

   The feasible region is bounded by these lines and the axes. We need to find the corner points of this region.

2. Identify the Corner Points (Vertices):

   The corner points are the intersections of these lines within the first quadrant ($x \geq 0, y \geq 0$).

   • Origin: $O = (0,0)$ (Intersection of $x=0$ and $y=0$)
   • Intersection of $L_1$ and $y=0$: $3x + 0 = 12 \implies x=4$. Point: $A = (4,0)$
   • Intersection of $L_2$ and $x=0$: $0 + 2y = 10 \implies y=5$. Point: $C = (0,5)$
   • Intersection of $L_1$ and $L_2$: We solve the system of equations:
     1. $3x + y = 12$
     2. $x + 2y = 10$ From (1), $y = 12 - 3x$. Substitute this into (2): $x + 2(12 - 3x) = 10$ $x + 24 - 6x = 10$ $-5x = 10 - 24$ $-5x = -14$ $x = \frac{14}{5}$ Now find $y$: $y = 12 - 3\left(\frac{14}{5}\right) = 12 - \frac{42}{5} = \frac{60 - 42}{5} = \frac{18}{5}$ Point: $B = \left(\frac{14}{5}, \frac{18}{5}\right)$ or $(2.8, 3.6)$

   The feasible region is the polygon $OABC$ with vertices $(0,0)$, $(4,0)$, $(14/5, 18/5)$, and $(0,5)$.

3. Evaluate the Objective Function at Each Corner Point:

   The objective function is $z = 15x + 30y$. We calculate its value at each vertex:

   Corner Point $(x,y)$	Value of $z = 15x + 30y$
   $O = (0,0)$	$15(0) + 30(0) = 0$
   $A = (4,0)$	$15(4) + 30(0) = 60$
   $B = (14/5, 18/5)$	$15(14/5) + 30(18/5) = 3(14) + 6(18) = 42 + 108 = 150$
   $C = (0,5)$	$15(0) + 30(5) = 150$

4. Determine the Maximum Value and Optimal Solutions: …