Solving Linear Programming Problems

This chapter introduces fundamental methodologies for solving Linear Programming Problems (LPPs), essential for optimizing resource allocation. Mastery of graphical and simplex methods is crucial for CUET PG, as these techniques frequently appear in problem-solving and theoretical questions.

---

Chapter Contents

| # | Topic |
|---|-------|
| 1 | Graphical Method |
| 2 | Basic Feasible Solutions |
| 3 | Simplex Method |

---

We begin with Graphical Method.

Part 1: Graphical Method

The graphical method provides an intuitive approach to solving Linear Programming Problems (LPPs) involving two decision variables. We employ this technique to visualize the feasible region defined by the constraints and to identify the optimal solution that maximizes or minimizes the objective function. This method is fundamental for understanding the geometric interpretation of LPPs, which is crucial for higher-dimensional solution techniques.

---

Core Concepts

1. Fundamentals of Linear Programming Problems (LPPs)

An LPP seeks to optimize (maximize or minimize) a linear objective function subject to a set of linear constraints. These constraints typically include non-negativity restrictions on the decision variables.

Quick Example: Plotting a Feasible Region

Consider the constraints:

Step 1: Plot the lines corresponding to the equality of the constraints.

> For $x + y = 4$: Points are $(4,0)$ and $(0,4)$.
> For $2x + y = 6$: Points are $(3,0)$ and $(0,6)$.

Step 2: Determine the feasible region for each inequality.

> For $x + y \le 4$: Test $(0,0) \Rightarrow 0 \le 4$, which is true. Shade below the line.
> For $2x + y \le 6$: Test $(0,0) \Rightarrow 0 \le 6$, which is true. Shade below the line.
> For $x \ge 0$: Shade to the right of the y-axis.
> For $y \ge 0$: Shade above the x-axis.

Step 3: Identify the intersection of all shaded regions. This common region is the feasible region.

x
y




x+y=4
2x+y=6








(0,0)
(3,0)
(2,2)
(0,4)

:::question type="MCQ" question="Which of the following points is NOT part of the feasible region defined by $x+y \le 5$, $2x+y \ge 4$, and $x,y \ge 0$?" options=["$(1,1)$","$(0,4)$","$(2,3)$","$(3,0)$"] answer="$(1,1)$" hint="Plot the constraints and test each point against all inequalities." solution="Step 1: We evaluate each given point against the constraints: $x+y \le 5$, $2x+y \ge 4$, $x,y \ge 0$.

For $(1,1)$:

* $1+1 = 2 \le 5$ (True)
* $2(1)+1 = 3 \ge 4$ (False)
Since $3 \ge 4$ is false, $(1,1)$ does not satisfy all constraints and is therefore not in the feasible region.

For $(0,4)$:

* $0+4 = 4 \le 5$ (True)
* $2(0)+4 = 4 \ge 4$ (True)
* $0 \ge 0, 4 \ge 0$ (True)
This point is in the feasible region.

For $(2,3)$:

* $2+3 = 5 \le 5$ (True)
* $2(2)+3 = 7 \ge 4$ (True)
* $2 \ge 0, 3 \ge 0$ (True)
This point is in the feasible region.

For $(3,0)$:

* $3+0 = 3 \le 5$ (True)
* $2(3)+0 = 6 \ge 4$ (True)
* $3 \ge 0, 0 \ge 0$ (True)
This point is in the feasible region.

Step 2: Identify the point that is not in the feasible region.
Therefore, the point $(1,1)$ is not part of the feasible region.

Answer: $\boxed{(1,1)}$"
:::

2. The Corner Point Method

The fundamental theorem of LPP states that if an optimal solution to an LPP exists, it must occur at a corner point (or vertex) of the feasible region. The corner point method systematically evaluates the objective function at each vertex.

Steps for Solving an LPP Graphically:

Formulate the LPP: Clearly define the objective function and all constraints.

Plot the Constraints: Graph each constraint as an equation to identify the boundary lines.

Identify the Feasible Region: Determine the area that satisfies all inequalities, including non-negativity constraints.

Find Corner Points: Identify the coordinates of all vertices (corner points) of the feasible region. These are typically intersections of constraint lines or intersections with the axes.

Evaluate Objective Function: Substitute the coordinates of each corner point into the objective function ($Z$) to find its value.

Determine Optimal Solution: For maximization, the corner point yielding the largest $Z$ value is the optimal solution. For minimization, it is the smallest $Z$ value.

Worked Example (Standard Maximization - similar to PYQ 1, 6):

Maximize

Subject to:

Step 1: Plot the constraint lines.

> For $x + y = 2$: Points are $(2,0)$ and $(0,2)$.
> For $2x + y = 3$: Points are $(1.5,0)$ and $(0,3)$.

Step 2: Identify the feasible region.
The feasible region is bounded by $x=0$, $y=0$, $x+y=2$, and $2x+y=3$. It is the area satisfying all $\le$ inequalities and $x,y \ge 0$.

x
y




x+y=2
2x+y=3








(0,0)
(1.5,0)
(1,1)
(0,2)

Step 3: Determine the corner points.

> $A = (0,0)$
> $B = (1.5,0)$ (intersection of $2x+y=3$ and $y=0$)
> $C = (1,1)$ (intersection of $x+y=2$ and $2x+y=3$)
> Subtracting $(x+y=2)$ from $(2x+y=3)$ yields $x=1$. Substituting $x=1$ into $x+y=2$ yields $1+y=2 \Rightarrow y=1$. So $C=(1,1)$.
> $D = (0,2)$ (intersection of $x+y=2$ and $x=0$)

Step 4: Evaluate $Z = 2x + 3y$ at each corner point.

> At $A(0,0)$: $Z = 2(0) + 3(0) = 0$
> At $B(1.5,0)$: $Z = 2(1.5) + 3(0) = 3$
> At $C(1,1)$: $Z = 2(1) + 3(1) = 5$
> At $D(0,2)$: $Z = 2(0) + 3(2) = 6$

Step 5: Identify the maximum value.

> The maximum value of $Z$ is $6$ at point $(0,2)$.

Answer: $\boxed{6}$

:::question type="MCQ" question="Maximize

subject to the constraints:


" options=["$12$","$16$","$10$","$8$"] answer="$16$" hint="Plot the feasible region, find corner points, and evaluate $Z$." solution="Step 1: Plot the constraint lines.
* $x+y=4$: Points $(4,0), (0,4)$
* $x-y=0 \implies x=y$: Points $(0,0), (4,4)$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region.
The feasible region is bounded by $y=0$, $x=y$, and $x+y=4$. It's the area satisfying $x+y \le 4$ (below the line), $x-y \ge 0$ (below $x=y$, or $x \ge y$), and $x,y \ge 0$.

x
y




x+y=4
x=y







(0,0)
(4,0)
(2,2)

Step 3: Determine the corner points.
* $A = (0,0)$ (intersection of $x=0, y=0$)
* $B = (4,0)$ (intersection of $x+y=4$ and $y=0$)
* $C = (2,2)$ (intersection of $x+y=4$ and $x=y$)
* Substitute $x=y$ into $x+y=4 \Rightarrow y+y=4 \Rightarrow 2y=4 \Rightarrow y=2$. So $x=2$. Thus $C=(2,2)$.

Step 4: Evaluate $Z = 4x + y$ at each corner point.
* At $A(0,0)$: $Z = 4(0) + 0 = 0$
* At $B(4,0)$: $Z = 4(4) + 0 = 16$
* At $C(2,2)$: $Z = 4(2) + 2 = 8 + 2 = 10$

Step 5: Identify the maximum value.
The maximum value of $Z$ is $16$ at point $(4,0)$.

Answer: $\boxed{16}$"
:::

3. Minimization Problems

The graphical method for minimization problems follows the same steps as maximization. The key difference lies in identifying the optimal solution: we select the corner point that yields the smallest value of the objective function. Minimization problems often lead to unbounded feasible regions.

Worked Example (Standard Minimization - similar to PYQ 7):

Minimize

Subject to:

Step 1: Plot the constraint lines.

> For $x + y = 7$: Points $(7,0)$ and $(0,7)$.
> For $x + 2y = 10$: Points $(10,0)$ and $(0,5)$.

Step 2: Identify the feasible region.
The feasible region is bounded by $x=0$, $y=0$, $x+y=7$, and $x+2y=10$. It is the area satisfying all $\ge$ inequalities and $x,y \ge 0$. This region is unbounded.

x
y




x+y=7
x+2y=10







(10,0)
(4,3)
(0,5)

Step 3: Determine the corner points.

> $A = (10,0)$ (intersection of $x+2y=10$ and $y=0$)
> $B = (4,3)$ (intersection of $x+y=7$ and $x+2y=10$)
> Subtracting $(x+y=7)$ from $(x+2y=10)$ yields $y=3$. Substituting $y=3$ into $x+y=7$ yields $x+3=7 \Rightarrow x=4$. So $B=(4,3)$.
> $C = (0,7)$ (intersection of $x+y=7$ and $x=0$)

Step 4: Evaluate $Z = 3x + 2y$ at each corner point.

> At $A(10,0)$: $Z = 3(10) + 2(0) = 30$
> At $B(4,3)$: $Z = 3(4) + 2(3) = 12 + 6 = 18$
> At $C(0,7)$: $Z = 3(0) + 2(7) = 14$

Step 5: Identify the minimum value.

> The minimum value of $Z$ is $14$ at point $(0,7)$.
> Note: For unbounded feasible regions, we must ensure that the objective function does not go to $-\infty$ (for minimization) or $+\infty$ (for maximization) within the feasible region. We can check this by drawing an isocost line (e.g., $3x+2y=14$) and seeing if it can be moved further into the feasible region while decreasing $Z$. Here, moving it further to the left/down would reduce $Z$, but it would leave the feasible region.

Answer: $\boxed{14}$

:::question type="NAT" question="Minimize

subject to the constraints:



What is the minimum value of $Z$?" answer="27" hint="Plot the lines, identify the unbounded feasible region, find corner points, and evaluate the objective function." solution="Step 1: Plot the constraint lines.
* $2x + y = 10$: Points $(5,0), (0,10)$
* $x + 3y = 15$: Points $(15,0), (0,5)$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region.
This is an unbounded region above and to the right of the constraint lines.

Step 3: Determine the corner points.
* $A = (15,0)$ (intersection of $x+3y=15$ and $y=0$)
* $B = (3,4)$ (intersection of $2x+y=10$ and $x+3y=15$)
* Multiply $2x+y=10$ by 3: $6x+3y=30$.
* Subtract $x+3y=15$ from $6x+3y=30$: $5x=15 \Rightarrow x=3$.
* Substitute $x=3$ into $2x+y=10$: $2(3)+y=10 \Rightarrow 6+y=10 \Rightarrow y=4$. So $B=(3,4)$.
* $C = (0,10)$ (intersection of $2x+y=10$ and $x=0$)

Step 4: Evaluate $Z = 5x + 3y$ at each corner point.
* At $A(15,0)$: $Z = 5(15) + 3(0) = 75$
* At $B(3,4)$: $Z = 5(3) + 3(4) = 15 + 12 = 27$
* At $C(0,10)$: $Z = 5(0) + 3(10) = 30$

Step 5: Identify the minimum value.
The minimum value of $Z$ is $27$ at point $(3,4)$.

Answer: $\boxed{27}$"
:::

---

Advanced Applications and Special Cases

1. Unbounded Solutions

An LPP has an unbounded solution if the feasible region is unbounded and the objective function can be increased (for maximization) or decreased (for minimization) indefinitely within this region without violating any constraints.

Worked Example (Unbounded Maximization - similar to PYQ 3, 5):

Maximize

Subject to:

Step 1: Plot the constraint lines.

> For $x - y = -1 \Rightarrow y = x + 1$: Points $(0,1), (1,2)$.
> For $x + y = 1$: Points $(1,0), (0,1)$.

Step 2: Identify the feasible region.
The feasible region is defined by $y \le x+1$, $y \ge -x+1$, and $x,y \ge 0$. This region is unbounded in the positive $x$ and $y$ directions.

x
y




x-y=-1
x+y=1






(0,1)
(1,0)

Step 3: Determine the corner points.

> $A = (1,0)$ (intersection of $x+y=1$ and $y=0$)
> $B = (0,1)$ (intersection of $x-y=-1$ and $x=0$, also $x+y=1$ and $x=0$)

Step 4: Evaluate $Z = x + 2y$ at the corner points.

> At $A(1,0)$: $Z = 1 + 2(0) = 1$
> At $B(0,1)$: $Z = 0 + 2(1) = 2$

Step 5: Check for unboundedness.
The feasible region extends infinitely in the direction where both $x$ and $y$ increase. Consider a point like $(5,5)$ in the feasible region: $Z = 5 + 2(5) = 15$. Consider $(10,10)$: $Z = 10 + 2(10) = 30$. As we move further into the feasible region, $Z$ continues to increase without bound.

Answer: $\boxed{\text{Unbounded solution}}$

:::question type="MCQ" question="Consider the LPP:
Maximize

Subject to:



Which of the following describes the solution?" options=["Unique optimal solution","Multiple optimal solutions","Unbounded solution","No feasible solution"] answer="Unbounded solution" hint="Plot the feasible region. If it is unbounded and the objective function's direction of increase points into the unbounded region, the solution is unbounded." solution="Step 1: Plot the constraint lines.
* $x - y = 0 \implies x=y$: Points $(1,1), (5,5)$, etc.
* $x = 1$: A vertical line at $x=1$.
* $y = 0$: The x-axis.

Step 2: Identify the feasible region.
* $x-y \ge 0 \implies y \le x$: Below or on the line $x=y$.
* $x \ge 1$: To the right of or on the line $x=1$.
* $y \ge 0$: Above or on the x-axis.
The feasible region is unbounded, extending to infinity in the positive $x$ and $y$ directions, starting from $(1,0)$ and $(1,1)$.

x
y




x=y
x=1






(1,0)
(1,1)

Step 3: Determine the corner points.
* $A = (1,0)$ (intersection of $x=1$ and $y=0$)
* $B = (1,1)$ (intersection of $x=1$ and $x=y$)

Step 4: Evaluate $Z = 3x + 2y$ at the corner points.
* At $A(1,0)$: $Z = 3(1) + 2(0) = 3$
* At $B(1,1)$: $Z = 3(1) + 2(1) = 5$

Step 5: Check for unboundedness.
The feasible region extends indefinitely towards positive $x$ and $y$. For example, take point $(5,5)$ (which is feasible: $5-5 \ge 0$, $5 \ge 1$, $5 \ge 0$). $Z = 3(5) + 2(5) = 15+10 = 25$. As $x$ and $y$ increase, $Z$ will also increase indefinitely.

Answer: $\boxed{\text{Unbounded solution}}$"
:::

2. No Feasible Solution (Infeasible LPP)

An LPP is infeasible if there is no point $(x,y)$ that satisfies all the constraints simultaneously. Graphically, this means the feasible region is empty; the shaded regions for the constraints do not overlap.

Worked Example (Infeasible LPP - similar to PYQ 2):

Maximize

Subject to:

Step 1: Plot the constraint lines.

> For $x + y = 2$: Points $(2,0), (0,2)$.
> For $x + y = 4$: Points $(4,0), (0,4)$.

Step 2: Identify the feasible region.
For $x+y \le 2$, we shade below the line $x+y=2$.
For $x+y \ge 4$, we shade above the line $x+y=4$.
Since these two regions are on opposite sides of parallel lines, they do not overlap. There is no common region that satisfies both $x+y \le 2$ and $x+y \ge 4$.

x
y




x+y=2
x+y=4

Answer: $\boxed{\text{No feasible solution}}$

:::question type="MCQ" question="The LPP:
Maximize

Subject to:



has:" options=["A unique optimal solution","Multiple optimal solutions","An unbounded solution","No feasible solution"] answer="No feasible solution" hint="Check if there is any region that satisfies all constraints simultaneously." solution="Step 1: Plot the constraint lines.
* $x = 1$: A vertical line at $x=1$.
* $x = 2$: A vertical line at $x=2$.
* $y = 0$: The x-axis.

Step 2: Identify the feasible region.
* $x \le 1$: To the left of or on the line $x=1$.
* $x \ge 2$: To the right of or on the line $x=2$.
* $y \ge 0$: Above or on the x-axis.
There is no $x$ value that can be simultaneously less than or equal to $1$ AND greater than or equal to $2$. Therefore, the constraints $x \le 1$ and $x \ge 2$ are contradictory.
There is no common region that satisfies all constraints.

Answer: $\boxed{\text{No feasible solution}}$"
:::

3. Multiple Optimal Solutions

Multiple optimal solutions occur when the objective function is parallel to one of the binding constraints (a constraint that forms part of the boundary of the feasible region at the optimal solution). In this case, every point on the line segment formed by that binding constraint within the feasible region yields the same optimal value.

Worked Example (Multiple Optimal Solutions - similar to PYQ 4):

Maximize

Subject to:

Step 1: Plot the constraint lines.

> For $x + 2y = 6$: Points $(6,0), (0,3)$.
> For $x + y = 4$: Points $(4,0), (0,4)$.

Step 2: Identify the feasible region.
The feasible region is bounded by $x=0$, $y=0$, $x+2y=6$, and $x+y=4$.

x
y




x+2y=6
x+y=4








(0,0)
(4,0)
(2,2)
(0,3)

Step 3: Determine the corner points.

> $A = (0,0)$
> $B = (4,0)$ (intersection of $x+y=4$ and $y=0$)
> $C = (2,2)$ (intersection of $x+y=4$ and $x+2y=6$)
> Subtracting $x+y=4$ from $x+2y=6$ yields $y=2$. Substituting $y=2$ into $x+y=4$ yields $x+2=4 \Rightarrow x=2$. So $C=(2,2)$.
> $D = (0,3)$ (intersection of $x+2y=6$ and $x=0$)

Step 4: Evaluate $Z = 2x + 4y$ at each corner point.

> At $A(0,0)$: $Z = 2(0) + 4(0) = 0$
> At $B(4,0)$: $Z = 2(4) + 4(0) = 8$
> At $C(2,2)$: $Z = 2(2) + 4(2) = 4 + 8 = 12$
> At $D(0,3)$: $Z = 2(0) + 4(3) = 12$

Step 5: Identify the maximum value.
We observe that both corner points $C(2,2)$ and $D(0,3)$ yield the maximum value of $Z=12$. Since the objective function $Z=2x+4y$ has a slope of $-2/4 = -1/2$, which is the same as the slope of the constraint $x+2y=6$ (also $-1/2$), the entire line segment $CD$ represents optimal solutions.

Answer: $\boxed{\text{Multiple optimal solutions, } Z=12}$

:::question type="MSQ" question="Which of the following LPPs can exhibit multiple optimal solutions?

Maximize $Z = 3x + 6y$ subject to $x+2y \le 10$, $x+y \le 6$, $x,y \ge 0$.

Maximize $Z = 2x + 3y$ subject to $x+y \le 5$, $2x+y \le 8$, $x,y \ge 0$.

Minimize $Z = 4x + 2y$ subject to $x+y \ge 4$, $2x+y \ge 6$, $x,y \ge 0$.

Maximize $Z = x + 2y$ subject to $x+y \le 4$, $x \le 2$, $x,y \ge 0$." options=["Maximize $Z = 3x + 6y$ subject to $x+2y \le 10$, $x+y \le 6$, $x,y \ge 0$.","Maximize $Z = 2x + 3y$ subject to $x+y \le 5$, $2x+y \le 8$, $x,y \ge 0$.","Minimize $Z = 4x + 2y$ subject to $x+y \ge 4$, $2x+y \ge 6$, $x,y \ge 0$.","Maximize $Z = x + 2y$ subject to $x+y \le 4$, $x \le 2$, $x,y \ge 0$."] answer='["Maximize $Z = 3x + 6y$ subject to $x+2y \le 10$, $x+y \le 6$, $x,y \ge 0$.", "Minimize $Z = 4x + 2y$ subject to $x+y \ge 4$, $2x+y \ge 6$, $x,y \ge 0$."]' hint="Multiple optimal solutions occur when the objective function's slope is identical to a binding constraint's slope at optimality." solution="Step 1: We examine the slopes of the objective function and constraints for each LPP. Multiple optimal solutions arise when the objective function is parallel to a binding constraint.

Maximize $Z = 3x + 6y$ subject to $x+2y \le 10$, $x+y \le 6$, $x,y \ge 0$.

* Objective function slope: $Z = 3x + 6y \implies 6y = -3x + Z \implies y = -\frac{1}{2}x + \frac{Z}{6}$. Slope is $-1/2$.
* Constraint $x+2y \le 10 \implies 2y = -x + 10 \implies y = -\frac{1}{2}x + 5$. Slope is $-1/2$.
Since the objective function's slope is identical to the slope of a constraint, this LPP is a candidate for multiple optimal solutions. Upon plotting, the feasible region's corner points are $(0,0)$, $(6,0)$, $(2,4)$, $(0,5)$.
* At $(0,0)$, $Z=0$.
* At $(6,0)$, $Z=18$.
* At $(2,4)$, $Z=3(2)+6(4)=6+24=30$. (Intersection of $x+y=6$ and $x+2y=10$)
* At $(0,5)$, $Z=3(0)+6(5)=30$.
Both $(2,4)$ and $(0,5)$ yield $Z=30$. Thus, all points on the line segment connecting $(2,4)$ and $(0,5)$ are optimal. This LPP has multiple optimal solutions.

Maximize $Z = 2x + 3y$ subject to $x+y \le 5$, $2x+y \le 8$, $x,y \ge 0$.

* Objective function slope: $y = -\frac{2}{3}x + \frac{Z}{3}$. Slope is $-2/3$.
* Constraint $x+y \le 5$: Slope is $-1$.
* Constraint $2x+y \le 8$: Slope is $-2$.
None of the constraint slopes match the objective function slope. This LPP will have a unique optimal solution. (Intersection $(3,2)$, $Z=12$).

Minimize $Z = 4x + 2y$ subject to $x+y \ge 4$, $2x+y \ge 6$, $x,y \ge 0$.

* Objective function slope: $y = -2x + \frac{Z}{2}$. Slope is $-2$.
* Constraint $x+y \ge 4$: Slope is $-1$.
* Constraint $2x+y \ge 6$: Slope is $-2$.
The objective function's slope matches the $2x+y \ge 6$ constraint. This is a candidate for multiple optimal solutions.
Corner points are $(0,6)$, $(2,2)$, $(4,0)$.
* At $(0,6)$, $Z=4(0)+2(6)=12$.
* At $(2,2)$, $Z=4(2)+2(2)=8+4=12$. (Intersection of $x+y=4$ and $2x+y=6$)
* At $(4,0)$, $Z=4(4)+2(0)=16$.
Both $(0,6)$ and $(2,2)$ yield $Z=12$. Thus, all points on the line segment connecting $(0,6)$ and $(2,2)$ are optimal. This LPP has multiple optimal solutions.

Maximize $Z = x + 2y$ subject to $x+y \le 4$, $x \le 2$, $x,y \ge 0$.

* Objective function slope: $y = -\frac{1}{2}x + \frac{Z}{2}$. Slope is $-1/2$.
* Constraint $x+y \le 4$: Slope is $-1$.
* Constraint $x \le 2$: Vertical line, undefined slope.
No matching slopes. This LPP will have a unique optimal solution. (Corner points: $(0,0)$, $(2,0)$, $(2,2)$, $(0,4)$. Max $Z=8$ at $(0,4)$).

Step 2: Identify LPPs with multiple optimal solutions.
Based on our analysis, both LPP 1 and LPP 3 can exhibit multiple optimal solutions.

Answer: $\boxed{\text{Options 1 and 3}}$"
:::

4. Redundant Constraints

A constraint is considered redundant if its removal does not alter the feasible region of the LPP. This means the constraint does not bind the optimal solution and does not affect the set of feasible points. Redundant constraints do not affect the optimal solution but can be identified graphically.

Worked Example (Redundant Constraint - similar to PYQ 7):

Minimize

Subject to:



Consider adding a redundant constraint: $x+y \ge 5$.

Step 1: Plot the primary constraint lines.

> For $x + y = 6$: Points $(6,0), (0,6)$.
> For $2x + y = 10$: Points $(5,0), (0,10)$.

Step 2: Identify the feasible region (without $x+y \ge 5$).
The corner points are $A(0,10)$, $B(4,2)$, $C(6,0)$.
$A=(0,10)$
$B=(4,2)$ (intersection of $x+y=6$ and $2x+y=10$)
$C=(6,0)$

x
y




x+y=6
2x+y=10







(0,10)
(4,2)
(6,0)

Step 3: Evaluate $Z = 5x + 8y$ at these corner points.

> At $A(0,10)$: $Z = 5(0) + 8(10) = 80$
> At $B(4,2)$: $Z = 5(4) + 8(2) = 20 + 16 = 36$
> At $C(6,0)$: $Z = 5(6) + 8(0) = 30$
The minimum $Z$ is $30$ at $(6,0)$.

Step 4: Now, consider the constraint $x+y \ge 5$.
The line $x+y=5$ passes through $(5,0)$ and $(0,5)$.
The original feasible region (above $x+y=6$ and $2x+y=10$) already satisfies $x+y \ge 5$ because all points in the region have $x+y \ge 6$. Since $6 > 5$, any point satisfying $x+y \ge 6$ also satisfies $x+y \ge 5$.
Thus, the constraint $x+y \ge 5$ is redundant. It does not cut off any part of the original feasible region.

Answer: $\boxed{x+y \ge 5 \text{ is redundant}}$

:::question type="MCQ" question="For the LPP:
Minimize

Subject to:



Which of the following constraints is redundant?" options=["$x \ge 0$","$y \ge 0$","$x + y \ge 5$","$x \ge 4$"] answer="$x + y \ge 5$" hint="A constraint is redundant if its removal does not change the feasible region. Visually, it means the constraint's boundary line does not 'cut into' the existing feasible region." solution="Step 1: Plot the binding constraints to determine the initial feasible region.
* $x+y=8$: Points $(8,0), (0,8)$
* $x+2y=10$: Points $(10,0), (0,5)$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region's corner points.
* $A=(10,0)$ (intersection of $x+2y=10$ and $y=0$)
* $B=(6,2)$ (intersection of $x+y=8$ and $x+2y=10$)
* Subtracting $x+y=8$ from $x+2y=10$ yields $y=2$.
* Substitute $y=2$ into $x+y=8 \Rightarrow x+2=8 \Rightarrow x=6$. So $B=(6,2)$.
* $C=(0,8)$ (intersection of $x+y=8$ and $x=0$)
The feasible region is unbounded, starting from these corner points.

Step 3: Test each option for redundancy.
* $x \ge 0$: This is a non-negativity constraint. Removing it would extend the feasible region into negative $x$ values, so it's not redundant.
* $y \ge 0$: This is a non-negativity constraint. Removing it would extend the feasible region into negative $y$ values, so it's not redundant.
* $x + y \ge 5$: The line $x+y=5$ passes through $(5,0)$ and $(0,5)$. Our feasible region is defined by $x+y \ge 8$ and $x+2y \ge 10$.
Any point satisfying $x+y \ge 8$ will also satisfy $x+y \ge 5$ (since $8 > 5$).
Any point satisfying $x+2y \ge 10$ will also have $x+y \ge 5$ (e.g., if $y=0$, $x \ge 10 \implies x \ge 5$; if $x=0$, $2y \ge 10 \implies y \ge 5 \implies y \ge 5$).
Thus, the region $x+y \ge 5$ completely encompasses the existing feasible region. Adding $x+y \ge 5$ does not restrict the feasible region further. This constraint is redundant.
* $x \ge 4$: The line $x=4$. Our feasible region includes points like $(0,8)$ and $(6,2)$. The point $(0,8)$ has $x=0$, which is less than $4$. If we add $x \ge 4$, it would cut off parts of the feasible region (e.g., the segment from $(0,8)$ to $(4,4)$ on $x+y=8$). So, this is not redundant.

Answer: $\boxed{x+y \ge 5}$"
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Maximize $Z = 5x + 4y$ subject to:
$x + 2y \le 10$
$x + y \le 7$
$x \le 5$
$x, y \ge 0$" options=["$30$","$35$","$33$","$31$"] answer="$33$" hint="Plot the feasible region, identify all corner points, and evaluate the objective function at each." solution="Step 1: Plot the constraint lines:
* $x + 2y = 10$: Points $(10,0), (0,5)$
* $x + y = 7$: Points $(7,0), (0,7)$
* $x = 5$: A vertical line at $x=5$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region and its corner points:
The feasible region is bounded by $x=0$, $y=0$, $x=5$, $x+y=7$, and $x+2y=10$.
* $A = (0,0)$
* $B = (5,0)$ (intersection of $x=5$ and $y=0$)
* $C = (5,2)$ (intersection of $x=5$ and $x+y=7 \Rightarrow 5+y=7 \Rightarrow y=2$)
* $D = (4,3)$ (intersection of $x+y=7$ and $x+2y=10$)
* Subtract $(x+y=7)$ from $(x+2y=10) \Rightarrow y=3$.
* Substitute $y=3$ into $x+y=7 \Rightarrow x+3=7 \Rightarrow x=4$. So $D=(4,3)$.
* $E = (0,5)$ (intersection of $x+2y=10$ and $x=0$)

Step 3: Evaluate $Z = 5x + 4y$ at each corner point:
* At $A(0,0)$: $Z = 5(0) + 4(0) = 0$
* At $B(5,0)$: $Z = 5(5) + 4(0) = 25$
* At $C(5,2)$: $Z = 5(5) + 4(2) = 25 + 8 = 33$
* At $D(4,3)$: $Z = 5(4) + 4(3) = 20 + 12 = 32$
* At $E(0,5)$: $Z = 5(0) + 4(5) = 20$

Step 4: Determine the maximum value.
The maximum value of $Z$ is $33$ at point $(5,2)$.
Answer: $\boxed{33}$"

:::question type="NAT" question="Minimize $Z = 7x + 3y$ subject to:
$x + y \ge 6$
$2x + y \ge 8$
$x, y \ge 0$
What is the minimum value of $Z$?" answer="18" hint="This is a minimization problem with an unbounded feasible region. Find the corner points and evaluate $Z$." solution="Step 1: Plot the constraint lines:
* $x + y = 6$: Points $(6,0), (0,6)$
* $2x + y = 8$: Points $(4,0), (0,8)$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region and its corner points:
The feasible region is unbounded, defined by $x+y \ge 6$, $2x+y \ge 8$, and $x,y \ge 0$.
* $A = (4,0)$ (intersection of $2x+y=8$ and $y=0$)
* $B = (2,4)$ (intersection of $x+y=6$ and $2x+y=8$)
* Subtract $(x+y=6)$ from $(2x+y=8) \Rightarrow x=2$.
* Substitute $x=2$ into $x+y=6 \Rightarrow 2+y=6 \Rightarrow y=4$. So $B=(2,4)$.
* $C = (0,6)$ (intersection of $x+y=6$ and $x=0$)

Step 3: Evaluate $Z = 7x + 3y$ at each corner point:
* At $A(4,0)$: $Z = 7(4) + 3(0) = 28$
* At $B(2,4)$: $Z = 7(2) + 3(4) = 14 + 12 = 26$
* At $C(0,6)$: $Z = 7(0) + 3(6) = 18$

Step 4: Determine the minimum value.
The minimum value of $Z$ is $18$ at point $(0,6)$.
Answer: $\boxed{18}$"

:::question type="MCQ" question="The feasible region for an LPP is defined by:
$x + y \le 6$
$x \ge 2$
$y \ge 1$
$x, y \ge 0$
Which of the following points is a corner point of this feasible region?" options=["$(2,0)$","$(0,1)$","$(5,1)$","$(2,6)$"] answer="$(5,1)$" hint="Plot the lines and identify their intersections. Then, check if these intersections satisfy all constraints to be a corner point." solution="Step 1: Plot the constraint lines:
* $x + y = 6$: Points $(6,0), (0,6)$
* $x = 2$: A vertical line at $x=2$
* $y = 1$: A horizontal line at $y=1$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region.
The feasible region is bounded by $x=2$, $y=1$, and $x+y=6$.
The non-negativity constraints $x \ge 0, y \ge 0$ are implied by $x \ge 2, y \ge 1$.

Step 3: Find the intersection points of these lines:
* Intersection of $x=2$ and $y=1$: $(2,1)$.
* Check: $2+1=3 \le 6$ (True). So $(2,1)$ is a corner point.
* Intersection of $x=2$ and $x+y=6$:
* Substitute $x=2 \Rightarrow 2+y=6 \Rightarrow y=4$. So $(2,4)$.
* Check: $y=4 \ge 1$ (True). So $(2,4)$ is a corner point.
* Intersection of $y=1$ and $x+y=6$:
* Substitute $y=1 \Rightarrow x+1=6 \Rightarrow x=5$. So $(5,1)$.
* Check: $x=5 \ge 2$ (True). So $(5,1)$ is a corner point.

Step 4: Compare with the given options.
* $(2,0)$: Violates $y \ge 1$. Not a corner point.
* $(0,1)$: Violates $x \ge 2$. Not a corner point.
* $(5,1)$: This is one of the corner points we identified.
* $(2,6)$: Violates $x+y \le 6$ ($2+6=8 \not\le 6$). Not a corner point.

Answer: $\boxed{(5,1)}$"

:::question type="MCQ" question="An LPP has the objective function Maximize $Z = 6x + 5y$. The feasible region is a polygon with corner points $(0,0)$, $(5,0)$, $(3,4)$, $(0,6)$. The optimal value of $Z$ is:" options=["$30$","$36$","$38$","$40$"] answer="$38$" hint="Evaluate the objective function at each given corner point and select the maximum." solution="Step 1: List the given corner points.
* $(0,0)$
* $(5,0)$
* $(3,4)$
* $(0,6)$

Step 2: Evaluate $Z = 6x + 5y$ at each corner point.
* At $(0,0)$: $Z = 6(0) + 5(0) = 0$
* At $(5,0)$: $Z = 6(5) + 5(0) = 30$
* At $(3,4)$: $Z = 6(3) + 5(4) = 18 + 20 = 38$
* At $(0,6)$: $Z = 6(0) + 5(6) = 30$

Step 3: Determine the maximum value.
The maximum value of $Z$ is $38$ at point $(3,4)$.

Answer: $\boxed{38}$"

:::question type="MSQ" question="Consider the LPP:
Maximize $Z = x + y$
Subject to:
$x - y \le 1$
$x + y \ge 3$
$x, y \ge 0$
Which of the following statements are correct?

The feasible region is bounded.

The LPP has an unbounded solution.

The corner points are $(1,0)$, $(3,0)$, $(0,3)$, $(0,1)$.

The optimal solution does not exist." options=["The feasible region is bounded.","The LPP has an unbounded solution.","The corner points are $(1,0)$, $(3,0)$, $(0,3)$, $(0,1)$.","The optimal solution does not exist."] answer="The LPP has an unbounded solution.,The optimal solution does not exist." hint="Plot the constraints carefully. Determine the nature of the feasible region and then evaluate the objective function's behavior." solution="Step 1: Plot the constraint lines.

* $x - y = 1$: Points $(1,0), (0,-1)$
* $x + y = 3$: Points $(3,0), (0,3)$
* $x=0, y=0$ (axes)

Step 2: Identify the feasible region.
* $x - y \le 1 \implies y \ge x - 1$: Above or on the line $y=x-1$.
* $x + y \ge 3$: Above or on the line $x+y=3$.
* $x \ge 0, y \ge 0$: In the first quadrant.

The feasible region starts from the intersection of $y=x-1$ and $x+y=3$.
Add the two equations: $(x-y=1) + (x+y=3) \Rightarrow 2x=4 \Rightarrow x=2$.
Substitute $x=2$ into $x+y=3 \Rightarrow 2+y=3 \Rightarrow y=1$.
So, $(2,1)$ is a corner point.

The feasible region is bounded by the lines $x+y=3$ (from $y$-axis to $(2,1)$), $y=x-1$ (from $(2,1)$ to $x$-axis), and then extends unboundedly outwards.
The corner points are $(0,3)$, $(2,1)$, $(3,0)$.

Step 3: Evaluate the statements.

The feasible region is bounded.

* Graphically, the region extends indefinitely in the positive $x$ and $y$ directions. For example, $(10,10)$ satisfies $10-10 \le 1$ (True), $10+10 \ge 3$ (True), $10 \ge 0, 10 \ge 0$ (True). This point is in the feasible region. As $x, y$ increase, the region continues. Thus, the feasible region is unbounded. (Statement 1 is incorrect).

The LPP has an unbounded solution.

* Objective function: $Z = x + y$.
* At corner point $(0,3)$: $Z = 0+3=3$.
* At corner point $(2,1)$: $Z = 2+1=3$.
* At corner point $(3,0)$: $Z = 3+0=3$.
* Consider a point further in the unbounded region, e.g., $(10,10)$. $Z = 10+10 = 20$.
* Since the objective function $Z=x+y$ can increase indefinitely as $x$ and $y$ increase within the feasible region, the LPP has an unbounded solution. (Statement 2 is correct).

The corner points are $(1,0)$, $(3,0)$, $(0,3)$, $(0,1)$.

* Our identified corner points are $(0,3)$, $(2,1)$, $(3,0)$.
* $(1,0)$ is on $x-y=1$, but $1+0=1 \not\ge 3$, so it's not feasible.
* $(0,1)$ is on $x-y=1$, but $0+1=1 \not\ge 3$, so it's not feasible.
* Thus, statement 3 is incorrect.

The optimal solution does not exist.

* For an unbounded maximization problem, the maximum value tends to infinity. In such cases, a finite optimal solution does not exist. (Statement 4 is correct).

Answer: $\boxed{\text{The LPP has an unbounded solution.,The optimal solution does not exist.}}$"

---

Summary

---

What's Next?

---

---

Part 2: Basic Feasible Solutions

In linear programming, we seek to optimize an objective function subject to linear constraints. The concept of a Basic Feasible Solution (BFS) is fundamental to solving Linear Programming Problems (LPPs), particularly through the Simplex method. We define and explore the properties of these solutions, which correspond to the corner points of the feasible region.

---

Core Concepts

1. Feasible Solution

A feasible solution to an LPP is a set of values for the decision variables that satisfies all the problem's constraints simultaneously, including the non-negativity restrictions. The collection of all feasible solutions forms the feasible region.

Quick Example:
Consider the constraints:
$x_1 + x_2 \leq 4$
$x_1, x_2 \geq 0$

Is $X = (1, 2)$ a feasible solution?

Step 1: Check constraints

Step 2: Check non-negativity

Answer: Yes, $X = (1, 2)$ is a feasible solution.

:::question type="MCQ" question="Given the constraints: $2x_1 + x_2 \leq 10$, $x_1 - x_2 \geq 2$, $x_1, x_2 \geq 0$. Which of the following points is a feasible solution?" options=["$(3, 1)$","$(6, -1)$","$(1, 0)$","$(4, 3)$"] answer="$(3, 1)$" hint="Substitute each point into all constraints and non-negativity conditions." solution="Let's check each option:
For $(3, 1)$:

Thus, $(3, 1)$ is a feasible solution.

For $(6, -1)$: $x_2 = -1$ violates $x_2 \geq 0$. Not feasible.
For $(1, 0)$: $1 - 0 = 1 \not\geq 2$. Not feasible.
For $(4, 3)$: $2(4) + 3 = 11 \not\leq 10$. Not feasible."
:::

---

2. Basic Solution

For a system of $m$ linear equations with $n$ variables, $AX=b$, where $A$ is an $m \times n$ matrix and $\operatorname{rank}(A) = m$ (assuming $m < n$), a basic solution is obtained by setting $n-m$ variables to zero and solving for the remaining $m$ variables. These $m$ variables are called basic variables, and the $n-m$ variables set to zero are called non-basic variables.

Quick Example:
Consider the system:

Here $m=2, n=4$. We need to set $n-m = 4-2=2$ variables to zero.

Let $x_3=0, x_4=0$ (non-basic variables). The system becomes:

Step 1: Solve the reduced system
Multiply the second equation by 2:
>

Subtract the first equation from this:
>

Step 2: Substitute $x_1$ back into $x_1 + 2x_2 = 4$
>

Answer: A basic solution is

Here, $x_1, x_2$ are basic variables and $x_3, x_4$ are non-basic variables.

:::question type="MCQ" question="For the system:

If $x_1$ and $x_2$ are chosen as basic variables, what is the value of $x_1$?" options=["3","2","1","4"] answer="3" hint="Set non-basic variables to zero and solve the resulting system for $x_1$ and $x_2$." solution="The system has $m=2$ equations and $n=4$ variables. If $x_1, x_2$ are basic variables, then $x_3, x_4$ are non-basic variables, so we set $x_3=0$ and $x_4=0$.
The system becomes:

Add equation (1) and (2):

Substitute $x_1=3$ into (1):

The basic solution is $(3, 2, 0, 0)$. Thus, $x_1=3$.
Answer: \boxed{3}"
:::

---

3. Number of Basic Solutions

The maximum number of basic solutions for a system of $m$ equations and $n$ variables ($m < n$) is given by the combination formula $^nC_m$. This represents the number of ways to choose $m$ variables out of $n$ to be basic variables.

Quick Example:
For a system with $m=3$ equations and $n=5$ variables, what is the maximum number of basic solutions?

Step 1: Identify $n$ and $m$
> $n=5$
> $m=3$

Step 2: Apply the formula $^nC_m$
>

Answer: There can be a maximum of 10 basic solutions.

:::question type="MCQ" question="A linear programming problem has 4 constraints and 6 variables. Assuming the rank of the constraint matrix is equal to the number of constraints, what is the maximum possible number of basic solutions?" options=["15","24","30","60"] answer="15" hint="Use the combination formula $^nC_m$ where $n$ is the number of variables and $m$ is the number of constraints." solution="We are given $m=4$ (number of constraints) and $n=6$ (number of variables).
The maximum number of basic solutions is given by $^nC_m$.

Therefore, the maximum possible number of basic solutions is 15.
Answer: \boxed{15}"
:::

---

4. Basic Feasible Solution (BFS)

A basic solution is a Basic Feasible Solution (BFS) if all the basic variables satisfy the non-negativity constraint (i.e., they are $\geq 0$). BFS are crucial because they correspond to the corner points (vertices) of the feasible region. For any LPP with a finite optimal solution, at least one optimal solution occurs at a BFS.

Quick Example:
Consider the system:

$x_1, x_2, x_3, x_4 \geq 0$

From a previous example, we found a basic solution by setting $x_3=0, x_4=0$:

Step 1: Check non-negativity of all components
> $x_1 = \frac{8}{5} \geq 0 \text{ (True)}$
> $x_2 = \frac{6}{5} \geq 0 \text{ (True)}$
> $x_3 = 0 \geq 0 \text{ (True)}$
> $x_4 = 0 \geq 0 \text{ (True)}$

Answer: Since all components are non-negative, this is a Basic Feasible Solution.

:::question type="MCQ" question="Consider the system:

with $x_i \geq 0$ for all $i$. Which of the following is a Basic Feasible Solution?" options=["$(1, 2, 0, 0)$","$(0, 3, 1, 0)$","$(2, 1, 0, -1)$","$(0, 0, 3, 2)$"] answer="$(0, 0, 3, 2)$" hint="For each option, first verify if it's a basic solution (by identifying non-basic variables and checking consistency), then check non-negativity." solution="Let's analyze each option:

$(1, 2, 0, 0)$: Here $x_3=0, x_4=0$ are non-basic variables.

This is not a solution.

$(0, 3, 1, 0)$: Here $x_1=0, x_4=0$ are non-basic variables.

This is not a solution.

$(2, 1, 0, -1)$: $x_4 = -1$ violates non-negativity. Not feasible.

$(0, 0, 3, 2)$: Here $x_1=0, x_2=0$ are non-basic variables.

All components are non-negative. This is a basic solution and a BFS.
Therefore, $(0, 0, 3, 2)$ is a Basic Feasible Solution.
Answer: \boxed{(0, 0, 3, 2)}}"
:::

---

5. Degenerate and Non-Degenerate BFS

A Basic Feasible Solution can be further classified based on the values of its basic variables. This distinction is important for understanding the behavior of algorithms like the Simplex method.

Quick Example:
Consider the system:

$x_1, x_2, x_3, x_4 \geq 0$

Let's find a basic solution by setting $x_1=0, x_2=0$.
The system becomes:

The basic solution is

Here, $x_3, x_4$ are basic variables, and $x_1, x_2$ are non-basic. Since all components are $\geq 0$, this is a BFS.
Are any basic variables zero? No, $x_3=2, x_4=2$.
Therefore, $X = (0, 0, 2, 2)$ is a non-degenerate BFS.

Now, let's find another basic solution by setting $x_2=0, x_4=0$.
The system becomes:

Substitute $x_1=2$ into the first equation:

The basic solution is

Here, $x_1, x_3$ are basic variables, and $x_2, x_4$ are non-basic. All components are $\geq 0$, so this is a BFS.
Are any basic variables zero? Yes, $x_3=0$.
Therefore, $X = (2, 0, 0, 0)$ is a degenerate BFS.

:::question type="MCQ" question="For the system:

with $x_i \geq 0$. Which of the following basic feasible solutions is degenerate?" options=["$(0, 0, 2, 2)$","$(2, 0, 0, 0)$","$(0, 2, 0, 0)$","$(1, 1, 0, 0)$"] answer="$(2, 0, 0, 0)$" hint="Identify the basic variables for each BFS and check if any of them are zero." solution="The system has $m=2$ equations and $n=4$ variables. For a basic solution, $n-m=2$ variables are non-basic (set to 0), and $m=2$ variables are basic.

$(0, 0, 2, 2)$: Non-basic $x_1=0, x_2=0$. Basic $x_3=2, x_4=2$. Both basic variables are positive. Non-degenerate BFS.

$(2, 0, 0, 0)$: Non-basic $x_2=0, x_4=0$. Basic $x_1=2, x_3=0$. Since $x_3=0$ (a basic variable is zero), this is a degenerate BFS.

$(0, 2, 0, 0)$: Non-basic $x_1=0, x_4=0$. Basic $x_2=2, x_3=0$. Since $x_3=0$ (a basic variable is zero), this is also a degenerate BFS.

$(1, 1, 0, 0)$: Non-basic $x_3=0, x_4=0$. Basic $x_1=1, x_2=1$. Both basic variables are positive. Non-degenerate BFS.

Therefore, $(2, 0, 0, 0)$ is a degenerate BFS.
Answer: \boxed{(2, 0, 0, 0)}}"
:::

---

Advanced Applications

We now consider a more complex system to find all basic feasible solutions and identify their properties.

Worked Example:
Find all basic feasible solutions for the system:

Here $m=2, n=4$. The maximum number of basic solutions is

We need to set $n-m=2$ variables to zero.

Case 1: $x_1=0, x_2=0$ (non-basic)

BFS: $(0, 0, 4, 7)$. Basic variables $x_3=4, x_4=7$. Both positive. Non-degenerate BFS.

Case 2: $x_1=0, x_3=0$ (non-basic)

Substitute $x_2=4$:



This solution is not feasible because $x_4 < 0$. Not a BFS.

Case 3: $x_1=0, x_4=0$ (non-basic)

Substitute $x_2=\frac{7}{3}$:


BFS: $\left(0, \frac{7}{3}, \frac{5}{3}, 0\right)$. Basic variables $x_2=\frac{7}{3}, x_3=\frac{5}{3}$. Both positive. Non-degenerate BFS.

Case 4: $x_2=0, x_3=0$ (non-basic)

Substitute $x_1=4$:



This solution is not feasible because $x_4 < 0$. Not a BFS.

Case 5: $x_2=0, x_4=0$ (non-basic)

Substitute $x_1=\frac{7}{2}$:


BFS: $\left(\frac{7}{2}, 0, \frac{1}{2}, 0\right)$. Basic variables $x_1=\frac{7}{2}, x_3=\frac{1}{2}$. Both positive. Non-degenerate BFS.

Case 6: $x_3=0, x_4=0$ (non-basic)

Multiply the first equation by 2:

Subtract this from the second equation:


This solution is not feasible because $x_2 < 0$. Not a BFS.

Answer: The basic feasible solutions are $(0, 0, 4, 7)$, $\left(0, \frac{7}{3}, \frac{5}{3}, 0\right)$, and $\left(\frac{7}{2}, 0, \frac{1}{2}, 0\right)$. All are non-degenerate.

:::question type="NAT" question="Consider the system:

with $x_i \geq 0$. If $x_3$ and $x_4$ are chosen as non-basic variables, calculate the value of $x_1 + x_2$ for the resulting basic solution." answer="5" hint="Set $x_3=0$ and $x_4=0$. Solve the remaining system for $x_1$ and $x_2$, then sum them." solution="Given system:

Set non-basic variables $x_3=0$ and $x_4=0$:

Add equation (1) and (2):

Substitute $x_1=3$ into equation (1):

The basic solution is $(3, 2, 0, 0)$. All components are non-negative, so this is a BFS.
We need to calculate $x_1 + x_2$:

Answer: \boxed{5}"
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Given the system of equations:

with $x_i \geq 0$. What is the maximum number of distinct basic solutions for this system?" options=["$4$","$6$","$8$","$10$"] answer="$6$" hint="Identify the number of equations ($m$) and variables ($n$), then use the combination formula $^nC_m$." solution="The system has $m=2$ equations and $n=4$ variables ($x_1, x_2, x_3, x_4$).
The maximum number of distinct basic solutions is given by $^nC_m$.

Thus, there are a maximum of 6 distinct basic solutions."
:::

:::question type="MSQ" question="For the system

with $x_i \geq 0$. Select ALL statements that are correct regarding its basic feasible solutions." options=["The solution $(0, 0, 3, 0)$ is a degenerate BFS.","There are at most 6 basic solutions.","The solution $(1, 1, 1, 0)$ is a BFS.","All basic feasible solutions for this system are non-degenerate."] answer="The solution $(0, 0, 3, 0)$ is a degenerate BFS.,There are at most 6 basic solutions." hint="Systematically find basic solutions for different choices of non-basic variables and check for feasibility and degeneracy. Recall that for a basic solution, exactly $m$ variables must be non-zero." solution="The system has $m=2$ equations and $n=4$ variables.

Maximum basic solutions: $^nC_m = ^4C_2 = \frac{4!}{2!2!} = 6$. So, 'There are at most 6 basic solutions' is Correct.

Let's find the BFS:
* Case 1: $x_1=0, x_2=0$ (non-basic)

Solution $(0, 0, 3, 0)$. Basic variables $x_3=3, x_4=0$. Since a basic variable ($x_4$) is zero, this is a degenerate BFS. So, 'The solution $(0, 0, 3, 0)$ is a degenerate BFS' is Correct.
* Case 2: $x_1=0, x_3=0$ (non-basic)


Solution $(0, 3, 0, 3)$. Basic variables $x_2=3, x_4=3$. Both positive. Non-degenerate BFS.
* Case 3: $x_1=0, x_4=0$ (non-basic)

Then $x_3=3$.
Solution $(0, 0, 3, 0)$. This is the same as Case 1.
* Case 4: $x_2=0, x_3=0$ (non-basic)

Not feasible.
* Case 5: $x_2=0, x_4=0$ (non-basic)

Then $x_3=3$.
Solution $(0, 0, 3, 0)$. This is the same as Case 1.
* Case 6: $x_3=0, x_4=0$ (non-basic)


Substitute $x_1=x_2$ into the first equation: So $x_2=3/2$.
Solution $(3/2, 3/2, 0, 0)$. Basic variables $x_1=3/2, x_2=3/2$. Both positive. Non-degenerate BFS.

Now evaluate the other options:
* 'The solution $(1, 1, 1, 0)$ is a BFS.'
Check if it's a solution:
$1+1+1=3$ (True)
$1-1+0=0$ (True)
All components are $\geq 0$. So it is a feasible solution.
Check basicity: It has 3 non-zero variables ($x_1=1, x_2=1, x_3=1$). For a basic solution, there must be exactly $m=2$ non-zero (basic) variables. Since there are 3 non-zero variables, this is not a basic solution, and thus not a BFS. So this statement is Incorrect.
* 'All basic feasible solutions for this system are non-degenerate.'
We found $(0, 0, 3, 0)$ to be a degenerate BFS. So this statement is Incorrect.

Therefore, the correct statements are 'The solution $(0, 0, 3, 0)$ is a degenerate BFS.' and 'There are at most 6 basic solutions.' "
:::

:::question type="MCQ" question="A feasible solution to a linear programming problem must satisfy which of the following conditions?" options=["It must optimize the objective function.","It must be a basic solution.","It must satisfy all constraints and non-negativity conditions.","It must be unique."] answer="It must satisfy all constraints and non-negativity conditions." hint="Recall the fundamental definition of a feasible solution in LPP." solution="A feasible solution is any point within the feasible region, meaning it satisfies all the problem's constraints (including equality/inequality constraints and non-negativity conditions) simultaneously.

• Optimizing the objective function describes an optimal solution, not just any feasible solution.


• Being a basic solution describes a specific type of feasible solution (a BFS), not all feasible solutions.


• Feasible solutions are not necessarily unique; there can be infinitely many feasible solutions."

:::

:::question type="NAT" question="Consider the system:

with $x_i \geq 0$. If $x_1$ is chosen as a non-basic variable, calculate the value of $x_3$ for the resulting basic solution." answer="3" hint="Set the non-basic variable $x_1$ to zero. Solve the system for the remaining basic variables $x_2$ and $x_3$." solution="Given system:

We have $m=2$ equations and $n=3$ variables. If $x_1$ is chosen as a non-basic variable, we set $x_1=0$. The remaining variables $x_2, x_3$ will be basic variables.

Substitute $x_1=0$ into the equations:

Substitute $x_2=3$ from (2) into (1):

The basic solution is $(0, 3, 3)$. Since all components are non-negative, this is a Basic Feasible Solution. The value of $x_3$ is 3.
Answer: \boxed{3}"
:::

---

Summary

---

What's Next?

---

---

Part 3: Simplex Method

The Simplex Method is a fundamental algebraic procedure for solving Linear Programming Problems (LPPs). We employ an iterative approach to move from one basic feasible solution to another, systematically improving the objective function value until an optimal solution is attained.

---

---

Core Concepts

1. Standard Form of a Linear Programming Problem

For application of the Simplex Method, an LPP must first be transformed into its standard form. This involves expressing the objective function as a maximization problem and all constraints as equalities, while ensuring all variables are non-negative.

Conversion Rules:

* Minimization to Maximization: To minimize $Z$, maximize $Z' = -Z$.
* $\le$ Constraints: Introduce a non-negative slack variable ($s_i$) to convert to equality:

Slack variables represent unused resources.
* $\ge$ Constraints: Introduce a non-negative surplus variable (or excess variable, $-s_i$) to convert to equality:

Surplus variables represent the amount by which the LHS exceeds the RHS.
* Unrestricted Variables: If $x_j$ is unrestricted in sign, substitute $x_j = x_j' - x_j''$, where $x_j', x_j'' \ge 0$.

Quick Example: Convert the following LPP to standard form:

Subject to:


$x_1 \ge 0$, $x_2$ unrestricted

Step 1: Convert minimization to maximization.

Step 2: Convert $x_2$ to non-negative variables.
Let $x_2 = x_2' - x_2''$, where $x_2', x_2'' \ge 0$.

Step 3: Convert constraints to equalities.
For $x_1 + x_2 \le 10$, introduce slack variable $s_1 \ge 0$:

For $2x_1 - x_2 \ge 5$, introduce surplus variable $s_2 \ge 0$:

Answer:

Subject to:

:::question type="MCQ" question="Convert the following LPP into standard form for maximization:

Subject to:




How many slack variables and surplus variables are introduced, respectively?" options=["1 slack, 2 surplus","2 slack, 1 surplus","1 slack, 1 surplus","2 slack, 2 surplus"] answer="1 slack, 2 surplus" hint="Identify the type of inequality for each constraint and the corresponding variable type." solution="Step 1: Convert minimization to maximization.

Step 2: Convert constraints to equalities.
For $3x_1 + x_2 \ge 3$, introduce surplus variable $s_1 \ge 0$:

(1 surplus variable)

For $4x_1 + 3x_2 \ge 6$, introduce surplus variable $s_2 \ge 0$:

(1 surplus variable)

For $x_1 + 2x_2 \le 4$, introduce slack variable $s_3 \ge 0$:

(1 slack variable)

Thus, 1 slack variable and 2 surplus variables are introduced.

Final Standard Form:

Subject to:



"
:::

---

2. Basic Feasible Solutions (BFS)

A basic feasible solution is a fundamental concept in the Simplex Method. It represents a corner point of the feasible region.

For the Simplex Method, we begin with an initial BFS. Often, this is achieved by using slack variables as initial basic variables, as they naturally form an identity matrix in the constraint coefficients.

Quick Example: Consider the system:

where $x_1, x_2, s_1, s_2 \ge 0$.

Step 1: Identify $n$ and $m$. Here $n=4$ (variables $x_1, x_2, s_1, s_2$) and $m=2$ (equations). We need to set $n-m = 4-2=2$ variables to zero.

Step 2: Find an initial BFS by setting decision variables to zero.
Set $x_1 = 0, x_2 = 0$.
Then, $s_1 = 6$ and $s_2 = 8$.
Since $s_1, s_2 \ge 0$, this is a BFS.
Basic variables: $s_1, s_2$. Non-basic variables: $x_1, x_2$.

Answer: A BFS is $(x_1, x_2, s_1, s_2) = (0, 0, 6, 8)$.

:::question type="MCQ" question="Given the system of equations from an LPP in standard form:

Which of the following is a basic feasible solution?" options=["$(x_1, x_2, s_1, s_2) = (0,0,10,12)$","$(x_1, x_2, s_1, s_2) = (6,0,0,6)$","$(x_1, x_2, s_1, s_2) = (0,4,6,0)$","$(x_1, x_2, s_1, s_2) = (3,4,0,0)$"] answer="$(x_1, x_2, s_1, s_2) = (0,4,6,0)$" hint="A BFS must have $n-m$ variables set to zero and all $m$ basic variables must be non-negative. Here $n=4, m=2$, so 2 variables must be zero." solution="We have $n=4$ variables ($x_1, x_2, s_1, s_2$) and $m=2$ equations. A BFS requires $n-m = 2$ variables to be zero.

Let's check each option:
* $(0,0,10,12)$: $x_1=0, x_2=0$. $s_1=10, s_2=12$. All non-negative. This is a BFS.
* $(6,0,0,6)$: $x_2=0, s_1=0$.

So this solution is $(5,0,0,7)$, not $(6,0,0,6)$. This is not a correct solution.
* $(0,4,6,0)$: $x_1=0, s_2=0$.


Substitute $x_2=4$ into the first equation: $4 + s_1 = 10 \Rightarrow s_1 = 6$.
So this solution is $(0,4,6,0)$. All non-negative. This is a BFS.
* $(3,4,0,0)$: $s_1=0, s_2=0$.


Multiply the first equation by 3: $6x_1 + 3x_2 = 30$.
Subtract the second equation from this:

Substitute $x_1=3.6$ into $x_1 + 3x_2 = 12$: $3.6 + 3x_2 = 12 \Rightarrow 3x_2 = 8.4 \Rightarrow x_2 = 2.8$.
So this solution is $(3.6, 2.8, 0, 0)$. All non-negative. This is a BFS, but the option given is $(3,4,0,0)$, which is incorrect.

The only correct BFS from the options is $(0,4,6,0)$.
"
:::

---

3. Simplex Tableau

The Simplex Method is efficiently implemented using a tabular representation known as the Simplex Tableau. This matrix format systematizes the iterative process of moving between BFS.

Initial Tableau Construction:

Ensure LPP is in standard form (maximization, equality constraints, non-negative variables).

Identify an initial BFS, typically by using slack variables as basic variables.

Fill in the coefficients of the constraints and the RHS values.

Fill in the objective function coefficients ($C_j$) for all variables.

Calculate $Z_j$ and $C_j - Z_j$ rows. For the initial tableau with slack variables as basic, $C_j$ for basic variables are usually 0, making $Z_j=0$ and $C_j-Z_j = C_j$.

Quick Example: Construct the initial simplex tableau for:

Subject to:

Step 1: Convert to standard form.
Introduce slack variables $s_1, s_2 \ge 0$.

Subject to:

Step 2: Identify initial BFS.
Set $x_1=0, x_2=0$. Then $s_1=4, s_2=6$. Basic variables: $s_1, s_2$.

Step 3: Construct the tableau.
The objective coefficients are $C_j = [3, 2, 0, 0]$ for $x_1, x_2, s_1, s_2$.
The basic variables $s_1, s_2$ have $C_B = [0, 0]$.

Answer: The tableau above is the initial simplex tableau.

:::question type="MCQ" question="Construct the initial simplex tableau for the LPP:

Subject to:



What are the values in the $C_j - Z_j$ row for $x_1, x_2, s_1, s_2$ respectively?" options=["$[5, 3, 0, 0]$","$[0, 0, 0, 0]$","$[5, 3, 1, 1]$","$[2, 6, 0, 0]$"] answer="$[5, 3, 0, 0]$" hint="For the initial tableau with slack variables as basic, $Z_j$ values are typically zero, so $C_j - Z_j$ equals $C_j$." solution="Step 1: Convert to standard form.
Introduce slack variables $s_1, s_2 \ge 0$.

Subject to:

Step 2: Identify initial BFS.
Set $x_1=0, x_2=0$. Then $s_1=2, s_2=6$. Basic variables: $s_1, s_2$.
The objective coefficients for basic variables $s_1, s_2$ are $C_B = [0, 0]$.

Step 3: Calculate $Z_j$ and $C_j - Z_j$ for the initial tableau.
For each column $j$: $Z_j = \sum_{i=1}^m C_{Bi} a_{ij}$.
Since $C_{Bi}$ are all 0 for the initial basic variables ($s_1, s_2$), all $Z_j$ values will be 0.
Therefore, $C_j - Z_j = C_j - 0 = C_j$.

The $C_j$ values for $x_1, x_2, s_1, s_2$ are $5, 3, 0, 0$ respectively.
So, the $C_j - Z_j$ row will be $[5, 3, 0, 0]$.

"
:::

---

4. Optimality Condition (Maximization)

The Simplex Method iterates by moving from one BFS to an adjacent one, improving the objective function value at each step. The optimality condition determines when this process should stop.

If there are positive values in the $C_j - Z_j$ row, the current BFS is not optimal.
The entering variable (or pivot column) is chosen as the non-basic variable with the most positive $C_j - Z_j$ value. This variable will enter the basis, as it offers the largest potential increase in the objective function per unit.

Quick Example: Consider the $C_j - Z_j$ row of a simplex tableau:
$C_j - Z_j = [0, 5, -2, 0, -3]$ for variables $x_1, x_2, x_3, s_1, s_2$.

Step 1: Examine the $C_j - Z_j$ values.
We observe $C_j - Z_j$ values of $5$ for $x_2$.

Step 2: Identify the most positive value.
The largest positive value is $5$, corresponding to variable $x_2$.

Answer: The current solution is not optimal, and $x_2$ is the entering variable.

:::question type="MCQ" question="Given the $C_j - Z_j$ row of a simplex tableau for a maximization problem:

corresponding to variables $x_1, x_2, x_3, s_1, s_2, s_3$.
Which variable should enter the basis?" options=["$x_1$","$x_2$","$x_3$","$s_3$"] answer="$s_3$" hint="The entering variable is the non-basic variable with the largest positive $C_j - Z_j$ value." solution="We are looking for the most positive value in the $C_j - Z_j$ row.
The values are:
$x_1: -2$
$x_2: 4$
$x_3: -1$
$s_1: 0$
$s_2: 0$
$s_3: 6$

The positive values are $4$ (for $x_2$) and $6$ (for $s_3$).
The largest positive value is $6$, which corresponds to the variable $s_3$.
Therefore, $s_3$ should enter the basis."
:::

---

5. Feasibility Condition (Min-Ratio Test)

Once the entering variable is determined, we must identify which basic variable will leave the basis to maintain feasibility. This is done using the min-ratio test.

The element at the intersection of the pivot row and pivot column is called the pivot element.

Quick Example: Consider a tableau snippet:
Entering variable is $x_1$.

Step 1: Identify the pivot column.
The pivot column is $x_1$. Its coefficients are $1$ (for $s_1$) and $2$ (for $s_2$).

Step 2: Calculate ratios.
For row $s_1$: $\frac{\text{RHS}_1}{\text{coefficient of } x_1 \text{ in row } 1} = \frac{4}{1} = 4$.
For row $s_2$: $\frac{\text{RHS}_2}{\text{coefficient of } x_1 \text{ in row } 2} = \frac{6}{2} = 3$.

Step 3: Identify the smallest non-negative ratio.
The ratios are $4$ and $3$. The smallest is $3$.

Answer: The leaving variable is $s_2$ (corresponding to the row with ratio $3$), and the pivot element is $2$ (at the intersection of $s_2$ row and $x_1$ column).

:::question type="MCQ" question="In a simplex tableau for a maximization problem, $x_2$ is the entering variable. The relevant part of the tableau is:

Which variable leaves the basis?" options=["$x_1$","$x_2$","$s_1$","$s_2$"] answer="$s_2$" hint="Perform the min-ratio test by dividing the RHS by the positive coefficients in the pivot column ($x_2$ column)." solution="Step 1: Identify the pivot column.
The entering variable is $x_2$, so the pivot column is the column under $x_2$. The coefficients are $2$ (in $s_1$ row) and $1$ (in $s_2$ row).

Step 2: Calculate ratios of RHS to pivot column coefficients.
For row $s_1$: $\frac{\text{RHS}_1}{\text{coefficient of } x_2 \text{ in row } 1} = \frac{10}{2} = 5$.
For row $s_2$: $\frac{\text{RHS}_2}{\text{coefficient of } x_2 \text{ in row } 2} = \frac{2}{1} = 2$.

Step 3: Identify the smallest non-negative ratio.
The ratios are $5$ and $2$. The smallest non-negative ratio is $2$.

Step 4: Determine the leaving variable.
The smallest ratio ($2$) corresponds to the basic variable $s_2$.
Therefore, $s_2$ is the leaving variable.

Answer: $\boxed{s_2}$"
:::

---

6. Pivoting

Pivoting is the core algebraic operation in each Simplex iteration, transforming the tableau to a new BFS. It involves row operations to make the pivot element 1 and other elements in the pivot column 0.

These operations are equivalent to Gaussian elimination steps, ensuring that the new basic variable has a coefficient of 1 in its row and 0 in all other constraint rows, maintaining the identity matrix structure for basic variables.

Corrected Example: Perform a pivot operation given the tableau:
Pivot element is $\mathbf{3}$ (in $s_2$ row, $x_1$ column). $x_1$ enters, $s_2$ leaves.

Step 1: Normalize the pivot row ($s_2$ row).
New $s_2$ row (now $x_1$ row) = Old $s_2$ row / $3$.

Step 2: Update other rows.
* For $s_1$ row:
Coefficient of $x_1$ in $s_1$ row is $2$.
New $s_1$ row = Old $s_1$ row - $2 \times$ New $x_1$ row.
Old $s_1$ row: $[2, 1, 1, 0, 10]$
$2 \times$ New $x_1$ row: $[2 \times 1, 2 \times 1/3, 2 \times 0, 2 \times 1/3, 2 \times 8/3] = [2, 2/3, 0, 2/3, 16/3]$
New $s_1$ row: $[2-2, 1-2/3, 1-0, 0-2/3, 10-16/3]$

* For $C_j - Z_j$ row:
Coefficient of $x_1$ in $C_j - Z_j$ row is $5$.
New $C_j - Z_j$ row = Old $C_j - Z_j$ row - $5 \times$ New $x_1$ row.
Old $C_j - Z_j$ row: $[5, 3, 0, 0, 0]$ (Note: the last $0$ is for the $Z$ value in the $Z_j$ row, not $C_j-Z_j$)
For calculation, the $Z_j$ value is $0$.
New $C_j - Z_j$ row: $[5-5\times 1, 3-5\times 1/3, 0-5\times 0, 0-5\times 1/3, 0-5\times 8/3]$

(The last element is the new value of $-Z$, so $Z = 40/3$).

Answer: The updated tableau after one pivot operation is:

:::question type="NAT" question="Given the following simplex tableau for a maximization problem, where $x_2$ is the entering variable and $s_1$ is the leaving variable (pivot element = 2):

What is the new value in the $s_2$ row under the $x_1$ column after the pivot operation?" answer="2.5" hint="Normalize the pivot row first, then use it to zero out the $x_2$ coefficient in the $s_2$ row." solution="Step 1: Normalize the pivot row ($s_1$ row, which becomes $x_2$ row).
New $x_2$ row = Old $s_1$ row / $2$.
Old $s_1$ row: $[1, 2, 1, 0, 10]$
New $x_2$ row: $[1/2, 1, 1/2, 0, 5]$

Step 2: Update the $s_2$ row.
The coefficient of the pivot column ($x_2$) in the $s_2$ row is $1$.
New $s_2$ row = Old $s_2$ row - $1 \times$ New $x_2$ row.
Old $s_2$ row: $[3, 1, 0, 1, 8]$
$1 \times$ New $x_2$ row: $[1/2, 1, 1/2, 0, 5]$
New $s_2$ row: $[3 - 1/2, 1 - 1, 0 - 1/2, 1 - 0, 8 - 5]$

The new value in the $s_2$ row under the $x_1$ column is $5/2$.

Answer: $\boxed{2.5}$"
:::

---

7. Two-Phase Method and Big M Method

When an LPP contains $\ge$ or $=$ constraints, slack variables alone do not provide an initial BFS (as surplus variables have -1 coefficients and equality constraints have no slack/surplus). We introduce artificial variables to obtain an initial identity matrix for the basis. These artificial variables must be driven to zero in the optimal solution.

7.1. Big M Method

In the Big M method, a very large penalty (denoted by $M$) is assigned to artificial variables in the objective function to force them out of the basis.

Quick Example: Set up the initial tableau for Big M method:
Maximize $Z = 2x_1 + x_2$
Subject to:
$x_1 + x_2 \ge 2$
$x_1 + 2x_2 = 5$
$x_1, x_2 \ge 0$

Step 1: Convert to standard form and introduce artificial variables.
$x_1 + x_2 - s_1 + R_1 = 2$ (Introduce surplus $s_1$ and artificial $R_1$)
$x_1 + 2x_2 + R_2 = 5$ (Introduce artificial $R_2$)
$x_1, x_2, s_1, R_1, R_2 \ge 0$.

Step 2: Formulate the Big M objective function.
Maximize $Z = 2x_1 + x_2 + 0s_1 - MR_1 - MR_2$.

Step 3: Construct the initial tableau.
Basic variables: $R_1, R_2$. Their objective coefficients are $-M$.
Objective coefficients $C_j = [2, 1, 0, -M, -M]$.

Answer: The tableau above is the initial Big M tableau.

:::question type="MCQ" question="Consider the LPP:
Minimize $Z = 4x_1 + x_2$
Subject to:
$3x_1 + x_2 = 3$
$4x_1 + 3x_2 \ge 6$
$x_1 + 2x_2 \le 4$
$x_1, x_2 \ge 0$
When converting this to standard form for the Big M method, how many artificial variables are required?" options=["1","2","3","0"] answer="2" hint="Artificial variables are introduced for '=' constraints and '$\ge$' constraints after introducing surplus variables." solution="Step 1: Convert minimization to maximization.
Maximize $Z' = -4x_1 - x_2$.

Step 2: Convert constraints:
* $3x_1 + x_2 = 3$: This is an equality constraint. It requires an artificial variable. Let's call it $R_1$.
Equation: $3x_1 + x_2 + R_1 = 3$.
* $4x_1 + 3x_2 \ge 6$: This is a '$\ge$' constraint. It requires a surplus variable ($s_1$) and an artificial variable ($R_2$).
Equation: $4x_1 + 3x_2 - s_1 + R_2 = 6$.
* $x_1 + 2x_2 \le 4$: This is a '$\le$' constraint. It requires a slack variable ($s_2$).
Equation: $x_1 + 2x_2 + s_2 = 4$.

Step 3: Count artificial variables.
We introduced $R_1$ and $R_2$. Thus, 2 artificial variables are required.

Answer: $\boxed{2}$"
:::

7.2. Two-Phase Method

The Two-Phase method separates the problem into two distinct phases.

Quick Example: Formulate the Phase I objective for the LPP:
Maximize $Z = 2x_1 + x_2$
Subject to:
$x_1 + x_2 \ge 2$
$x_1 + 2x_2 = 5$
$x_1, x_2 \ge 0$

Step 1: Convert to standard form and introduce artificial variables.
$x_1 + x_2 - s_1 + R_1 = 2$
$x_1 + 2x_2 + R_2 = 5$
$x_1, x_2, s_1, R_1, R_2 \ge 0$.

Step 2: Formulate the Phase I objective function.
The objective of Phase I is to minimize the sum of artificial variables.
Minimize $W = R_1 + R_2$.
Convert to maximization for simplex: Maximize $W' = -R_1 - R_2$.

Answer: The Phase I objective function for maximization is $W' = -R_1 - R_2$.

:::question type="MCQ" question="For an LPP with artificial variables $R_1, R_2, R_3$, what is the objective function for Phase I of the Two-Phase Simplex method, when formulated for maximization?" options=["Maximize $W = R_1 + R_2 + R_3$","Maximize $W = -R_1 - R_2 - R_3$","Minimize $W = R_1 + R_2 + R_3$","Maximize $W = 0x_1 + 0x_2 + \dots - R_1 - R_2 - R_3$"] answer="Maximize $W = 0x_1 + 0x_2 + \dots - R_1 - R_2 - R_3$" hint="Phase I minimizes the sum of artificial variables. For Simplex, this is converted to maximization." solution="Phase I of the Two-Phase method aims to minimize the sum of artificial variables.
So, the objective is: Minimize $W = R_1 + R_2 + R_3$.

For the Simplex method, we always work with maximization problems. Therefore, we convert the minimization problem into a maximization problem by multiplying the objective function by -1.
Maximize $W' = -(R_1 + R_2 + R_3) = -R_1 - R_2 - R_3$.

The coefficients of the original decision variables and slack/surplus variables in the Phase I objective are zero, as they do not affect the feasibility of the artificial variables.
Thus, the correct formulation for maximization is: Maximize $W = 0x_1 + 0x_2 + \dots + 0s_j - R_1 - R_2 - R_3$.
The option 'Maximize $W = -R_1 - R_2 - R_3$' is technically correct but 'Maximize $W = 0x_1 + 0x_2 + \dots - R_1 - R_2 - R_3$' explicitly shows all variables in the objective function, which is the standard way to represent it in the tableau.

Answer: $\boxed{\text{Maximize } W = 0x_1 + 0x_2 + \dots - R_1 - R_2 - R_3}$"
:::

---

Advanced Applications

8. Special Cases in Simplex Method

The Simplex Method can reveal specific characteristics of an LPP beyond just an optimal solution.

8.1. Degeneracy

Degeneracy can lead to cycling, where the Simplex method might endlessly cycle through a sequence of non-improving BFS without reaching an optimal solution. While rare in practice, methods like Bland's Rule can prevent cycling.

Quick Example: Identify degeneracy.
Consider a tableau after a min-ratio test:
Entering variable $x_1$. Ratios: $s_1: 4/1 = 4$, $s_2: 0/2 = 0$.
The smallest ratio is $0$.

Answer: Since the smallest non-negative ratio is $0$, and it corresponds to a basic variable ($s_2$) that will leave, the next BFS will be degenerate.

:::question type="MCQ" question="Degeneracy in a Simplex tableau is typically indicated by which of the following conditions?" options=["All $C_j - Z_j \le 0$ for non-basic variables.","A tie in the min-ratio test, where one of the tied ratios is zero.","All coefficients in the pivot column are negative or zero.","Multiple optimal solutions exist."] answer="A tie in the min-ratio test, where one of the tied ratios is zero." hint="Degeneracy relates to basic variables having zero values. The min-ratio test reveals this." solution="Let's analyze the options:
* 'All $C_j - Z_j \le 0$ for non-basic variables.' This indicates an optimal solution, not degeneracy.
'A tie in the min-ratio test, where one of the tied ratios is zero.' Degeneracy occurs when a basic variable takes a zero value. If a basic variable's RHS is zero, and it's chosen to leave (smallest ratio of $0$), the new BFS will have a basic variable at zero, indicating degeneracy. A tie in the min-ratio test can* lead to degeneracy, especially if one of the tied ratios is zero, or if any basic variable in the current BFS is zero. The most direct indication is a basic variable having a value of zero, which often arises from a zero ratio in the min-ratio test.
* 'All coefficients in the pivot column are negative or zero.' This indicates an unbounded solution, not degeneracy.
* 'Multiple optimal solutions exist.' This occurs when a non-basic variable has $C_j - Z_j = 0$ at optimality, not degeneracy.

The most precise answer related to the process is when a basic variable becomes zero, which can happen if the min-ratio test results in a zero ratio.

Answer: $\boxed{\text{A tie in the min-ratio test, where one of the tied ratios is zero.}}$"
:::

8.2. Unbounded Solution

If all coefficients in the pivot column are $\le 0$, no finite positive ratio can be computed, meaning no variable can leave the basis. The entering variable can be increased indefinitely, leading to an unbounded objective function.

Quick Example: Identify an unbounded solution.
Consider a tableau where $x_1$ is the entering variable ($C_1 - Z_1 > 0$).
Pivot column $x_1$:

Step 1: Identify the pivot column.
The pivot column is $x_1$. Its coefficients are $-1$ (for $s_1$) and $-2$ (for $s_2$).

Step 2: Check coefficients in the pivot column.
All coefficients in the $x_1$ column ($-1$ and $-2$) are negative.

Answer: Since $x_1$ is the entering variable and all coefficients in its column are negative, the problem has an unbounded solution.

:::question type="MCQ" question="In a maximization LPP, an unbounded solution is indicated in the Simplex tableau when:" options=["All $C_j - Z_j \le 0$ for non-basic variables.","There is a tie in the min-ratio test.","For an entering variable, all coefficients in its column are negative or zero.","An artificial variable remains in the basis at a positive level after Phase I."] answer="For an entering variable, all coefficients in its column are negative or zero." hint="An unbounded solution means the objective can increase infinitely. This occurs when no basic variable can limit the increase of the entering variable." solution="Let's analyze the options:
* 'All $C_j - Z_j \le 0$ for non-basic variables.' This indicates an optimal solution.
* 'There is a tie in the min-ratio test.' This can indicate degeneracy or multiple optimal solutions in certain contexts, but not directly unboundedness.
* 'For an entering variable, all coefficients in its column are negative or zero.' If an entering variable ($C_j - Z_j > 0$) has no positive coefficients in its column, then no basic variable can be driven to zero by increasing the entering variable. This means the entering variable can be increased infinitely without violating feasibility, leading to an unbounded objective function. This is the definition of an unbounded solution.
* 'An artificial variable remains in the basis at a positive level after Phase I.' This indicates that the original LPP has no feasible solution.

Answer: $\boxed{\text{For an entering variable, all coefficients in its column are negative or zero.}}$"
:::

8.3. Multiple Optimal Solutions

If such a non-basic variable enters the basis, the objective function value will not change, leading to an alternative optimal BFS. Any convex combination of these optimal BFS will also be optimal.

Quick Example: Identify multiple optimal solutions.
Consider a final simplex tableau for a maximization problem:
$C_j - Z_j = [-2, 0, -1, 0, -3]$ for variables $x_1, x_2, x_3, s_1, s_2$.
The current basic variables are $x_1, s_1$.

Step 1: Check for optimality.
All $C_j - Z_j \le 0$. The tableau is optimal.

Step 2: Look for zero $C_j - Z_j$ values for non-basic variables.
The variable $x_2$ is non-basic and has $C_2 - Z_2 = 0$.

Answer: Since $x_2$ is a non-basic variable with a $C_j - Z_j$ value of $0$ at optimality, there are multiple optimal solutions.

:::question type="MCQ" question="In a maximization LPP, the existence of multiple optimal solutions is indicated by which condition in the final Simplex tableau?" options=["All $C_j - Z_j < 0$ for all non-basic variables.","An artificial variable remains in the basis at a positive level.","A non-basic variable has a $C_j - Z_j = 0$ value at optimality.","The objective function value is zero."] answer="A non-basic variable has a $C_j - Z_j = 0$ value at optimality." hint="A zero $C_j - Z_j$ for a non-basic variable at optimality means it can enter the basis without changing the objective value." solution="Let's analyze the options:
* 'All $C_j - Z_j < 0$ for all non-basic variables.' This indicates a unique optimal solution.
* 'An artificial variable remains in the basis at a positive level.' This indicates no feasible solution.
* 'A non-basic variable has a $C_j - Z_j = 0$ value at optimality.' If a non-basic variable has a $C_j - Z_j = 0$ value in an optimal tableau, it means bringing this variable into the basis will not change the optimal objective function value, thus leading to an alternative optimal solution. This is the correct indicator for multiple optimal solutions.
* 'The objective function value is zero.' This simply means the optimal value of $Z$ is zero, which is possible but doesn't, by itself, indicate multiple solutions.

Answer: $\boxed{\text{A non-basic variable has a } C_j - Z_j = 0 \text{ value at optimality.}}$"
:::

8.4. No Feasible Solution

In the Big M method, if an artificial variable remains in the basis at a positive level in the optimal tableau, it implies that no feasible solution exists for the original problem (assuming $M$ is sufficiently large). In the Two-Phase method, if the minimum value of $W$ (sum of artificial variables) at the end of Phase I is positive, then no feasible solution exists.

Quick Example: Identify no feasible solution.
Consider the final tableau of Phase I for a minimization problem (which sought to minimize $R_1+R_2$):
The objective value (sum of artificials) is $W = 5$.
Artificial variable $R_1$ is in the basis with value $3$. $R_2$ is non-basic.

Answer: Since the minimum value of $W$ is $5$ (which is positive) and $R_1$ (an artificial variable) remains in the basis at a positive level, the original LPP has no feasible solution.

:::question type="MCQ" question="Which of the following conditions in a final Simplex tableau (after applying Big M or Two-Phase method) indicates that the LPP has no feasible solution?" options=["All $C_j - Z_j \le 0$ for non-basic variables.","An artificial variable remains in the basis at a positive level.","A non-basic variable has a $C_j - Z_j = 0$ value at optimality.","All coefficients in the pivot column are negative or zero for an entering variable."] answer="An artificial variable remains in the basis at a positive level." hint="Artificial variables are introduced to aid in finding an initial BFS. If they cannot be driven out or to zero, it means no valid BFS exists for the original problem." solution="Let's analyze the options:
* 'All $C_j - Z_j \le 0$ for non-basic variables.' This indicates an optimal solution (unique or multiple).
* 'An artificial variable remains in the basis at a positive level.' This is the definitive indicator of no feasible solution. If an artificial variable, which has no physical meaning, cannot be driven out of the basis or reduced to zero, it means the original constraints cannot be satisfied.
* 'A non-basic variable has a $C_j - Z_j = 0$ value at optimality.' This indicates multiple optimal solutions.
* 'All coefficients in the pivot column are negative or zero for an entering variable.' This indicates an unbounded solution.

Answer: $\boxed{\text{An artificial variable remains in the basis at a positive level.}}$"
:::

9. Shadow Prices (Dual Prices)

The concept of shadow price is crucial for sensitivity analysis and economic interpretation of the optimal solution. It is directly related to the dual problem in linear programming.

Reading Shadow Prices from the Simplex Tableau (Maximization LPP):
* For a $\le$ constraint (with a slack variable $s_i$): The shadow price is the absolute value of the $C_j - Z_j$ value corresponding to the slack variable $s_i$ in the final optimal tableau. Alternatively, it is the $Z_j$ value of the slack variable column.
* For a $\ge$ constraint (with a surplus variable $-s_i$ and an artificial variable $R_i$): The shadow price is the absolute value of the $C_j - Z_j$ value corresponding to the surplus variable $s_i$ in the final optimal tableau (or the $Z_j$ value of the surplus variable column).
* For an $=$ constraint (with an artificial variable $R_i$): The shadow price is the absolute value of the $C_j - Z_j$ value corresponding to the artificial variable $R_i$ in the final optimal tableau (or the $Z_j$ value of the artificial variable column).

Quick Example: Interpret shadow price.
Suppose the optimal tableau for a maximization LPP shows:
$C_j - Z_j$ for $s_1$ (slack for constraint 1: $x_1+x_2 \le 10$) is $-0.5$.
The objective value is $Z = 20$.

Step 1: Identify the shadow price for $s_1$.
The shadow price for constraint 1 is $|-0.5| = 0.5$.

Step 2: Interpret the meaning.
If the RHS of constraint 1 increases by one unit (from 10 to 11), the optimal objective function value $Z$ will increase by $0.5$.

Answer: The shadow price of $0.5$ for constraint 1 indicates that an additional unit of the resource associated with this constraint would increase the maximum profit by $0.5$.

:::question type="MCQ" question="The term 'shadow price' in linear programming refers to:" options=["The cost of adding one unit to objective function.","The value of non-negativity constraint.","The cost of adding one unit to the right-hand side of a constraint.","The cost of remaining constraint."] answer="The cost of adding one unit to the right-hand side of a constraint." hint="Shadow price measures the marginal value of a resource or constraint." solution="The shadow price (or dual price) in linear programming quantifies the change in the optimal objective function value for a one-unit increase in the right-hand side of a constraint, assuming all other parameters remain constant. It represents the marginal value of relaxing a constraint or the marginal cost of tightening it.
* 'The cost of adding one unit to objective function.' This is not the definition of shadow price.
* 'The value of non-negativity constraint.' Non-negativity constraints usually have shadow prices of zero if the variable is positive, or reflect the cost of forcing a variable to be zero if it would naturally be positive. This option is too vague.
* 'The cost of adding one unit to the right-hand side of a constraint.' This is precisely the definition of a shadow price. It tells us how much the objective function's optimal value would change if we had one more unit of a particular resource or relaxed a constraint by one unit. For a maximization problem, it's the marginal profit; for minimization, it's the marginal cost.
* 'The cost of remaining constraint.' This is not a standard term in linear programming.

Therefore, the most accurate description is 'The cost of adding one unit to the right-hand side of a constraint.'

Answer: $\boxed{\text{The cost of adding one unit to the right-hand side of a constraint.}}$"
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the Simplex tableau for a maximization problem:

What is the pivot element for the next iteration?" options=["1 (in $s_1$ row, $x_1$ col)","2 (in $s_1$ row, $x_2$ col)","3 (in $s_2$ row, $x_1$ col)","1 (in $s_2$ row, $x_2$ col)"] answer="2 (in $s_1$ row, $x_2$ col)" hint="First, identify the entering variable (most positive $C_j - Z_j$). Then, apply the min-ratio test to find the leaving variable." solution="Step 1: Identify the entering variable.
The $C_j - Z_j$ values are $4$ for $x_1$ and $5$ for $x_2$. The most positive is $5$, so $x_2$ is the entering variable (pivot column).

Step 2: Identify the leaving variable using the min-ratio test.
Ratios are calculated as RHS / (Pivot column coefficient).
For $s_1$ row: $8/2 = 4$.
For $s_2$ row: $9/1 = 9$.
The smallest non-negative ratio is $4$, which corresponds to the $s_1$ row. So, $s_1$ is the leaving variable (pivot row).

Step 3: Identify the pivot element.
The pivot element is at the intersection of the pivot row ($s_1$ row) and the pivot column ($x_2$ column). This value is $2$.

Answer: $\boxed{\text{2 (in } s_1 \text{ row, } x_2 \text{ col)}}$"
:::

:::question type="NAT" question="A company produces two products, A and B. Product A requires 2 hours of labor and 1 unit of raw material. Product B requires 1 hour of labor and 2 units of raw material. The company has 100 hours of labor and 120 units of raw material available. The profit per unit of A is $3 and per unit of B is$2. If $x_1$ is the number of units of A and $x_2$ is the number of units of B, what is the initial value of the objective function (profit) when the initial BFS is formed using slack variables?" answer="0" hint="The initial BFS in Simplex typically assumes decision variables are zero, and slack variables take the RHS values. The objective function is calculated based on these values." solution="Step 1: Formulate the LPP.
Maximize $Z = 3x_1 + 2x_2$
Subject to:
$2x_1 + x_2 \le 100$ (Labor constraint)
$x_1 + 2x_2 \le 120$ (Raw material constraint)
$x_1, x_2 \ge 0$

Step 2: Convert to standard form.
Introduce slack variables $s_1, s_2$.
Maximize $Z = 3x_1 + 2x_2 + 0s_1 + 0s_2$
Subject to:
$2x_1 + x_2 + s_1 = 100$
$x_1 + 2x_2 + s_2 = 120$
$x_1, x_2, s_1, s_2 \ge 0$

Step 3: Determine the initial BFS.
In the initial Simplex tableau, we typically set the decision variables to zero.
So, $x_1 = 0, x_2 = 0$.
From the constraints:
$s_1 = 100$
$s_2 = 120$
The initial BFS is $(x_1, x_2, s_1, s_2) = (0, 0, 100, 120)$.

Step 4: Calculate the initial objective function value.
Substitute the BFS values into the objective function:
$Z = 3(0) + 2(0) + 0(100) + 0(120) = 0$.

Answer: $\boxed{0}$"
:::

:::question type="MSQ" question="Which of the following scenarios indicate that an LPP has no feasible solution when using the Two-Phase Simplex method?" options=["The optimal value of the original objective function is zero.","At the end of Phase I, the minimum value of the artificial objective function is positive.","An artificial variable remains in the basis with a positive value at the end of Phase I.","All $C_j - Z_j \le 0$ for non-basic variables in the final tableau of Phase II."] answer="At the end of Phase I, the minimum value of the artificial objective function is positive.,An artificial variable remains in the basis with a positive value at the end of Phase I." hint="The purpose of Phase I is to eliminate artificial variables. If this cannot be achieved, it means the original problem is infeasible." solution="Let's analyze each option:
* 'The optimal value of the original objective function is zero.' This simply means the maximum (or minimum) profit/cost is zero, which is a valid feasible solution. It does not indicate infeasibility.
* 'At the end of Phase I, the minimum value of the artificial objective function is positive.' The objective of Phase I is to minimize the sum of artificial variables. If this minimum value is positive, it means that at least one artificial variable could not be driven to zero, implying no feasible solution for the original LPP. This is a correct indicator.
* 'An artificial variable remains in the basis with a positive value at the end of Phase I.' This is an equivalent statement to the previous point. If an artificial variable is still basic and positive, its value contributes to a positive sum of artificial variables, indicating infeasibility. This is also a correct indicator.
* 'All $C_j - Z_j \le 0$ for non-basic variables in the final tableau of Phase II.' This indicates that an optimal solution has been found for the original LPP in Phase II. It does not indicate infeasibility.

Answer: $\boxed{\text{At the end of Phase I, the minimum value of the artificial objective function is positive.,An artificial variable remains in the basis with a positive value at the end of Phase I.}}$"
:::

:::question type="MCQ" question="In the final optimal tableau of a maximization LPP, if a non-basic variable has a $C_j - Z_j$ value of zero, what does this imply?" options=["The solution is degenerate.","The solution is unbounded.","There are multiple optimal solutions.","The problem has no feasible solution."] answer="There are multiple optimal solutions." hint="A zero $C_j - Z_j$ for a non-basic variable at optimality means it can enter the basis without changing the objective value." solution="Let's analyze the implications:
* Degeneracy: Occurs when a basic variable has a value of zero, often identified by a zero ratio in the min-ratio test.
* Unbounded Solution: Occurs when an entering variable has all negative or zero coefficients in its column, meaning it can be increased indefinitely.
* Multiple Optimal Solutions: If, at optimality (all $C_j - Z_j \le 0$), a non-basic variable has a $C_j - Z_j$ value of zero, it means that this variable can be introduced into the basis without changing the optimal objective function value. This leads to an alternative optimal basic feasible solution, hence multiple optimal solutions.
* No Feasible Solution: Indicated by an artificial variable remaining in the basis with a positive value.

Therefore, a non-basic variable with $C_j - Z_j = 0$ at optimality implies multiple optimal solutions.

Answer: $\boxed{\text{There are multiple optimal solutions.}}$"
:::

:::question type="NAT" question="A final simplex tableau for a maximization LPP shows that the shadow price for the first constraint (a $\le$ constraint) is $0.75$. If the RHS of this constraint increases by 4 units, by how much will the optimal objective function value increase?" answer="3" hint="The shadow price indicates the change in the objective function per unit increase in the RHS. Multiply the shadow price by the change in RHS." solution="Step 1: Understand the definition of shadow price.
The shadow price of $0.75$ for the first constraint means that for every one-unit increase in the RHS of that constraint, the optimal objective function value will increase by $0.75$.

Step 2: Calculate the total increase.
The RHS of the constraint increases by $4$ units.
Total increase in objective function = Shadow price $\times$ Change in RHS
Total increase = $0.75 \times 4 = 3$.

Answer: $\boxed{3}$"
:::

---

Summary

---

What's Next?

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider the LPP: Maximize $Z = 3x_1 + 2x_2$ subject to $x_1 + x_2 \le 7$, $2x_1 + x_2 \le 10$, $x_1, x_2 \ge 0$. Using the graphical method, what is the maximum value of $Z$?" options=["14", "17", "21", "24"] answer="17" hint="Identify the feasible region and evaluate the objective function at its corner points." solution="The corner points of the feasible region are (0,0), (5,0), (3,4), and (0,7). Evaluating Z at these points:
Z(0,0) = 0
Z(5,0) = 3(5) + 2(0) = 15
Z(3,4) = 3(3) + 2(4) = 9 + 8 = 17
Z(0,7) = 3(0) + 2(7) = 14
The maximum value of Z is 17.

Answer: $\boxed{17}$"
:::

:::question type="NAT" question="To convert the constraint $4x_1 - 2x_2 + x_3 \ge 15$ into an equality for the Simplex method, how many surplus variables are required?" answer="1" hint="Surplus variables are subtracted from $\ge$ constraints to convert them into equalities." solution="A surplus variable is subtracted from a 'greater than or equal to' ($\ge$) constraint to convert it into an equality. Therefore, one surplus variable is required: $4x_1 - 2x_2 + x_3 - s_1 = 15$.

Answer: $\boxed{1}$"
:::

:::question type="MCQ" question="Which of the following statements about Basic Feasible Solutions (BFS) in Linear Programming is FALSE?" options=["Every corner point of the feasible region corresponds to a BFS.", "A degenerate BFS has at least one basic variable equal to zero.", "The Simplex method always moves from one BFS to an adjacent, improved BFS.", "An optimal solution must always be a non-degenerate BFS."] answer="An optimal solution must always be a non-degenerate BFS." hint="Consider cases where an optimal solution might be degenerate or lie on an edge." solution="An optimal solution does not necessarily have to be a non-degenerate BFS. It can be a degenerate BFS, or in cases of multiple optima, it can lie on an edge connecting two BFSs, meaning any point on that edge is optimal.

Answer: $\boxed{\text{An optimal solution must always be a non-degenerate BFS.}}$"
:::

:::question type="NAT" question="Consider an LPP with 3 decision variables and 2 constraints (excluding non-negativity). If the problem has a unique optimal solution, how many non-basic variables will be at zero in the optimal BFS?" answer="2" hint="In a non-degenerate optimal BFS, the number of binding constraints equals the number of basic variables. If the 2 constraints are binding, their corresponding slack/surplus variables will be zero and thus non-basic." solution="In a standard Simplex tableau, for an LPP with $M$ constraints, if the optimal solution lies at the intersection of $M$ binding constraints, then the $M$ corresponding slack/surplus variables will be non-basic (i.e., equal to zero).
Here, we have 2 constraints. If both of these constraints are binding at the optimal solution, then their corresponding slack/surplus variables will be zero. These zero-valued slack/surplus variables are considered non-basic variables.
Therefore, 2 non-basic variables (specifically, the slack/surplus variables for the binding constraints) will be at zero in the optimal BFS.

Answer: $\boxed{2}$"
:::