Q.The corner points of an unbounded feasible region determined by a set of linear constraints are $(0,4)$, $(2,2)$ and $(5,0)$, and the region extends without bound in the direction of increasing $x$ and increasing $y$ beyond these points. For $Z = 2x + 3y$, find the minimum value of $Z$ on this region, and determine, with reason, whether a maximum value exists.

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:

   From the table, the maximum value of $z$ is $150$. This maximum value occurs at two distinct corner points: $B = (14/5, 18/5)$ and $C = (0,5)$.

   Important

   When the maximum (or minimum) value of the objective function occurs at two adjacent corner points of the feasible region, it implies that all points on the line segment connecting these two corner points are also optimal solutions.

   Let's verify this by comparing the slope of the objective function with the slope of the constraint line connecting points $B$ and $C$.

   The points $B(14/5, 18/5)$ and $C(0,5)$ lie on the constraint line $x + 2y = 10$.

   The slope of this line is $m_c = -\frac{\text{coefficient of } x}{\text{coefficient of } y} = -\frac{1}{2}$.

   Now consider the objective function $z = 15x + 30y$. We can write this as $30y = -15x + z$, or $y = -\frac{15}{30}x + \frac{z}{30} = -\frac{1}{2}x + \frac{z}{30}$.

   The slope of the objective function line is $m_z = -\frac{1}{2}$.

   Since the slope of the objective function line ($m_z = -1/2$) is identical to the slope of the constraint line $x + 2y = 10$ ($m_c = -1/2$), the objective function line is parallel to this edge of the feasible region. When the objective function line passes through the maximum value, it will coincide with the line segment $BC$.

   Every point $(x,y)$ on the line segment connecting $B(14/5, 18/5)$ and $C(0,5)$ will yield the maximum value of $z=150$. A line segment contains infinitely many points. Therefore, there are infinitely many feasible solutions that maximize $z$.