Q.Define optimal solution in Linear programming problem.

The problem gives you a feasible region (a polygon) and asks for the difference between the maximum and minimum values of $Z = 5x + 7y$ over that region. In linear programming, the optimal values of a linear objective function always occur at the vertices (corner points) of the feasible region — this is the corner point theorem. So you don't need to check every point inside; just the corners.

Let’s work through it step by step.

1. Identify the corner points from the graph.

   The feasible region shown is a quadrilateral. From the diagram, the vertices are:

   • $O(0, 0)$
   • $A(7, 0)$
   • $B(3, 4)$
   • $C(0, 3)$

   (If the graph had labelled coordinates, these are the intersections of the constraint lines.)

2. Evaluate $Z = 5x + 7y$ at each corner.

   • At $O(0, 0)$: $Z = 5(0) + 7(0) = 0$
   • At $A(7, 0)$: $Z = 5(7) + 7(0) = 35$
   • At $B(3, 4)$: $Z = 5(3) + 7(4) = 15 + 28 = 43$
   • At $C(0, 3)$: $Z = 5(0) + 7(3) = 21$

3. Find the maximum and minimum values.

   • Maximum $Z$ among these: $43$ (at $B$)
   • Minimum $Z$ among these: $0$ (at $O$)

4. Compute the required difference.

   $$$$

In Linear Programming Problems (LPP), we aim to optimize (maximize or minimize) a linear objective function subject to a set of linear constraints. Understanding the nature of the feasible region and where optimal solutions lie is crucial.

The feasible region is the set of all points $(x,y)$ that satisfy all the given constraints. It's typically a convex polygon (or an unbounded convex region) in a 2D graph. An optimal solution is a point within this feasible region that gives the best possible value (maximum or minimum) for the objective function.

Let's break down the given assertion and reason.

1. Analyzing Assertion (A): "Every point of the feasible region of a Linear Programming Problem is an optimal solution."

This assertion is incorrect. An optimal solution is a specific point or set of points within the feasible region that yields the maximum or minimum value of the objective function. It is not the entire feasible region itself.

Consider a simple example:

Maximize $Z = x + y$

Subject to:

$x \ge 0$

$y \ge 0$

$x + y \le 1$

The feasible region for this problem is a triangle with vertices at $(0,0)$, $(1,0)$, and $(0,1)$.

• At the point $(0,0)$, $Z = 0 + 0 = 0$.
• At the point $(0.5, 0.1)$, which is inside the feasible region, $Z = 0.5 + 0.1 = 0.6$.
• At the point $(1,0)$, $Z = 1 + 0 = 1$.
• At the point $(0,1)$, $Z = 0 + 1 = 1$.

The maximum value of $Z$ is $1$, which occurs at $(1,0)$ and $(0,1)$. Clearly, the point $(0.5, 0.1)$ is part of the feasible region, but it is not an optimal solution because $Z=0.6$ is not the maximum value. Therefore, not every point in the feasible region is an optimal solution.

Thus, Assertion (A) is false.

2. Analyzing Reason (R): "The optimal solution for a Linear Programming Problem exists only at one or more corner point(s) of the feasible region."

This statement is a fundamental theorem in Linear Programming, often called the Corner Point Theorem. It is true.

In linear programming, the optimal value of a linear objective function over a convex polygon (the feasible region) always lies at a vertex — a corner point. This is the Fundamental Theorem of Linear Programming. So instead of testing infinitely many points inside the region, we only need to check the corners.

Here, the constraints are simple: $x \ge 0$, $y \ge 0$ (first quadrant), and $4x + 3y \le 12$. That last inequality is a half-plane bounded by the line $4x + 3y = 12$.

Let’s find the vertices of the feasible region.

1. Intersection with $x = 0$

   Put $x = 0$ into $4x + 3y = 12$:

   $3y = 12 \implies y = 4$.

   So one vertex is $(0, 4)$.

2. Intersection with $y = 0$

   Put $y = 0$ into $4x + 3y = 12$:

   $4x = 12 \implies x = 3$.

   So another vertex is $(3, 0)$.

3. Origin

   The intersection of $x = 0$ and $y = 0$ is $(0, 0)$, which also satisfies $4x + 3y \le 12$. So $(0, 0)$ is a vertex.

These three points form a right triangle in the first quadrant. No other corner exists because the line $4x + 3y = 12$ cuts the axes at exactly those two points.

Now evaluate $z = 3x + 5y$ at each vertex:

• At $(0, 0)$: $z = 3(0) + 5(0) = 0$
• At $(3, 0)$: $z = 3(3) + 5(0) = 9$
• At $(0, 4)$: $z = 3(0) + 5(4) = 20$ …

The key idea here is a fundamental property of linear programming: when the maximum of a linear objective function occurs at two different corner points of the feasible region, it actually occurs at every point on the line segment joining them. This happens because the objective function’s contour lines (lines of constant $z$) are parallel to that edge of the feasible region.

Let’s unpack why.

1. What the problem tells us

   The feasible region is a convex polygon with vertices at $(0,0)$, $(4,0)$, $(2,4)$, and $(0,5)$. The objective $z = ax + by$ (with $a, b > 0$) attains its maximum at both $(2,4)$ and $(4,0)$. Since the feasible region is convex, the entire line segment between these two points must also give the same maximum value.

2. What that implies about the objective

   If two distinct points give the same $z$-value, then the objective function is constant along the line joining them. That means the line $ax + by = \text{constant}$ is parallel to the line through $(2,4)$ and $(4,0)$.

3. Find the slope of the edge

   The slope of the line through $(2,4)$ and $(4,0)$ is:

4. Match the slope of the objective function The objective $ax + by = k$ can be rewritten as $y = -\frac{a}{b}x + \frac{k}{b}$. Its slope is $-\frac{a}{b}$. For the objective to be constant along the edge, its slope must equal the slope of the edge: $-\frac{a}{b} = -2 \quad \Rightarrow \quad \frac{a}{b} = 2 \quad \Rightarrow \quad a = 2b$ …