EduProd
EduProd
JEE PCM PLATFORM
πŸ“Š Dashboard
LEARN MODULE Β· SCHEMATIC MODE

Trace it. Derive it. Know it.

Every cluster below maps one schematic path β€” from first principles to the final equation. Expand a node to follow the full derivation trace.

⚑ INTEGRATED VIRTUAL LABORATORIES (1)
Open Subject Labs Catalog β†—
Feasible Region
Stage β†—
01

Mathematical Formulation of Linear Programming Problems & Canonical Components

3 concepts Β· Core
3 nodes

How are real-world industrial resource limitations mathematically translated into linear objective functions and inequality systems?

An LPP optimizes a linear objective function Z = ax + by subject to a set of linear inequalities (constraints) and non-negativity restrictions x >= 0, y >= 0. Decision variables x and y quantify resource allocation, and non-negativity confines the problem to the first coordinate quadrant.

01

Decision Variables and Non-Negativity Constraints (x >= 0, y >= 0)

Decision variables x and y represent the unknown quantities to be decided (e.g. number of items manufactured). Physical constraints dictate that x >= 0 and y >= 0, confining all feasible solutions to the first quadrant of the Cartesian coordinate plane.

Key Idea
Always define decision variables explicitly with units (e.g., 'Let x be the number of packets of food P').
Why It Works
Physical goods, hours, and inventory can never take negative values in realistic operational settings.
Boundary Trap
Omitting non-negativity constraints x >= 0, y >= 0 in written board exam solutions, which loses marks.
Application Note
If a carpenter produces x tables and y chairs, the non-negativity constraints are x >= 0, y >= 0.
Derivation Trace Β· Decision Variables and Non-Negativity Constraints (x >= 0, y >= 0)
Think of an LPP as running a bakery. You want to make cakes (x) and cookies (y) to make maximum money (Z = 50x + 20y). But you only have so much flour and sugar (constraints). Because you cannot bake negative cakes, x >= 0 and y >= 0. The goal is to find the exact pair (x, y) that extracts the maximum possible cash from your limited ingredients.
A linear programming problem is one that is concerned with finding the optimal value (maximum or minimum) of a linear function of several variables (called objective function) subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). The variables x and y are called decision variables.
Never forget to write x >= 0, y >= 0 when formulating word problems in board exams! In CBSE grading schemes, omitting non-negativity constraints results in an immediate 1-mark deduction even if your objective function and structural constraints are 100% correct.
Open the Half-Plane Interactive Lab. Toggle inequalities from <= to >= and see how constraint boundaries partition the first quadrant into admissible and forbidden half-planes.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Why is the feasible region always restricted to the first quadrant in standard LPP?

Answer: Due to the non-negativity constraints x >= 0 and y >= 0.

02

Linear Objective Function: Z = ax + by

The objective function Z = ax + by is a linear function of decision variables x and y that needs to be optimized (either maximized or minimized). Coefficients a and b represent unit profit, revenue, or cost.

Key Idea
The objective function Z is not an inequality; it is a linear scalar field whose value depends on the chosen point (x, y).
Why It Works
Linears models assume constant marginal returns: each additional unit of x adds exactly 'a' to the objective value Z regardless of scale.
Boundary Trap
Setting Z equal to a constant or inequality when formulating the initial problem.
Application Note
If profit per table is Rs 250 and profit per chair is Rs 75, the objective function is Maximize Z = 250x + 75y.
Derivation Trace Β· Linear Objective Function: Z = ax + by
Think of an LPP as running a bakery. You want to make cakes (x) and cookies (y) to make maximum money (Z = 50x + 20y). But you only have so much flour and sugar (constraints). Because you cannot bake negative cakes, x >= 0 and y >= 0. The goal is to find the exact pair (x, y) that extracts the maximum possible cash from your limited ingredients.
A linear programming problem is one that is concerned with finding the optimal value (maximum or minimum) of a linear function of several variables (called objective function) subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). The variables x and y are called decision variables.
Never forget to write x >= 0, y >= 0 when formulating word problems in board exams! In CBSE grading schemes, omitting non-negativity constraints results in an immediate 1-mark deduction even if your objective function and structural constraints are 100% correct.
Open the Half-Plane Interactive Lab. Toggle inequalities from <= to >= and see how constraint boundaries partition the first quadrant into admissible and forbidden half-planes.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Can an objective function in a Linear Programming Problem contain non-linear terms like x^2 or x*y?

Answer: No. In LPP, the objective function and all constraints must be strictly linear.

03

Formulating Linear Constraints: Resource Caps (<=) vs Requirements (>=)

Constraints are linear inequalities expressing restrictions on available resources: availability limits use '<=' (less than or equal to), while minimum quota requirements use '>=' (greater than or equal to).

Key Idea
Sum of (resource consumption per unit * number of units) <= total resource available.
Why It Works
Inequalities model boundary limits; you cannot consume more raw materials than exist in inventory, but you can consume less.
Boundary Trap
Reversing inequality signs: using '>=' for maximum availability or '<=' for minimum dietary requirements.
Application Note
Each table takes 3 hours and each chair takes 1 hour of machine time. With at most 60 hours available: 3x + y <= 60.
Derivation Trace Β· Formulating Linear Constraints: Resource Caps (<=) vs Requirements (>=)
Think of an LPP as running a bakery. You want to make cakes (x) and cookies (y) to make maximum money (Z = 50x + 20y). But you only have so much flour and sugar (constraints). Because you cannot bake negative cakes, x >= 0 and y >= 0. The goal is to find the exact pair (x, y) that extracts the maximum possible cash from your limited ingredients.
A linear programming problem is one that is concerned with finding the optimal value (maximum or minimum) of a linear function of several variables (called objective function) subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). The variables x and y are called decision variables.
Never forget to write x >= 0, y >= 0 when formulating word problems in board exams! In CBSE grading schemes, omitting non-negativity constraints results in an immediate 1-mark deduction even if your objective function and structural constraints are 100% correct.
Open the Half-Plane Interactive Lab. Toggle inequalities from <= to >= and see how constraint boundaries partition the first quadrant into admissible and forbidden half-planes.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If a diet must contain at least 80 units of vitamin A, and foods X and Y provide 2 and 4 units per kg, what is the constraint?

Answer: 2x + 4y >= 80.

02

Feasible Region Geometry, Convexity & The Corner Point Theorem (Theorem 1)

3 concepts Β· Core
3 nodes

Why does the optimal value of a linear program always reside at an extreme corner point (vertex) of the convex feasible region?

The common region determined by all constraints (including non-negativity) is called the feasible region R. It is always a convex polygonal set. NCERT Theorem 1 states that if R is bounded, the objective function Z = ax + by attains both its maximum and minimum values at corner points (vertices) of R.

01

Graphing Linear Inequalities and the Origin Test Point Method

To graph an inequality ax + by <= c: (1) draw the boundary line ax + by = c; (2) test the origin (0, 0): if a(0) + b(0) <= c is true, shade the half-plane containing (0,0); otherwise shade the opposite half-plane.

Key Idea
Solid boundary lines represent '<=' or '>=' (points on line included); dashed lines represent strict inequalities (not used in standard LPP).
Why It Works
A straight line divides the 2D plane into two open half-planes; evaluating any single test point not on the line determines the sign of the entire half-plane.
Boundary Trap
Testing (0, 0) when the line passes directly through the origin (e.g., y <= 2x): use (0, 1) or (1, 0) instead!
Application Note
For 2x + 3y <= 12: boundary line has intercepts (6, 0) and (0, 4). Testing (0, 0): 0 <= 12 is TRUE. Shade the half-plane containing (0, 0).
Derivation Trace Β· Graphing Linear Inequalities and the Origin Test Point Method
Imagine holding a flat wooden ruler (the line Z = ax + by) and sliding it parallel across a flat cardboard polygon (the feasible region). Where does it first touch the cardboard as you push it in? At a sharp corner! Where does it leave the cardboard as you pull it out? At another sharp corner! Because the objective function is completely flat (linear), it can never peak in the middle.
Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by be the objective function. When R is bounded, the objective function Z attains both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R. A corner point of a feasible region is a point in the region which is the intersection of two boundary lines.
Do not skip checking (0, 0) as a candidate corner point if the origin lies in the feasible region! Although (0, 0) gives Z = 0 (which is rarely the maximum for positive coefficients), it is frequently the absolute MINIMUM.
Open the Half-Plane Explorer. Construct multiple overlapping inequalities to visually confirm that the resulting feasible region is always convex without inward dents.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Which test point should you use if the boundary line is x - y = 0?

Answer: Use a point not on the line, such as (1, 0) or (0, 1).

02

The Feasible Region as a Convex Set

The Feasible Region (FR) is the common region determined by all constraints including x >= 0, y >= 0. A region is convex if for any two points P and Q in the region, the entire line segment PQ lies within the region.

Key Idea
The intersection of any collection of convex half-planes is always convex; the feasible region cannot have 'dents' or re-entrant angles.
Why It Works
Linear combinations of linear inequalities preserve convexity: if a P + b <= c and a Q + b <= c, then a(t P + (1-t)Q) + b <= c for all t in [0, 1].
Boundary Trap
Shading separate disconnected areas without taking their common mutual intersection.
Application Note
A triangular or quadrilateral region bounded by linear constraints is convex; a crescent-shaped or star-shaped region is non-convex.
Derivation Trace Β· The Feasible Region as a Convex Set
Imagine holding a flat wooden ruler (the line Z = ax + by) and sliding it parallel across a flat cardboard polygon (the feasible region). Where does it first touch the cardboard as you push it in? At a sharp corner! Where does it leave the cardboard as you pull it out? At another sharp corner! Because the objective function is completely flat (linear), it can never peak in the middle.
Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by be the objective function. When R is bounded, the objective function Z attains both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R. A corner point of a feasible region is a point in the region which is the intersection of two boundary lines.
Do not skip checking (0, 0) as a candidate corner point if the origin lies in the feasible region! Although (0, 0) gives Z = 0 (which is rarely the maximum for positive coefficients), it is frequently the absolute MINIMUM.
Open the Half-Plane Explorer. Construct multiple overlapping inequalities to visually confirm that the resulting feasible region is always convex without inward dents.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Can a feasible region defined by linear inequalities be non-convex?

Answer: No. The intersection of linear half-planes is always a convex set.

03

NCERT Theorem 1: The Corner Point Theorem

Theorem 1 states: Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by be the objective function. When R is bounded, Z attains both its maximum and minimum values at corner points (vertices) of R.

Key Idea
You do NOT need to check millions of interior points; checking the finite number of corner points is 100% mathematically sufficient!
Why It Works
The gradient of Z = ax + by is constant. Moving in the gradient direction increases Z linearly; the highest value must be pushed all the way to an extreme boundary vertex.
Boundary Trap
Checking arbitrary points inside the shaded region instead of strictly evaluating vertices.
Application Note
If a bounded feasible region has vertices (0, 0), (4, 0), (2, 3), (0, 4), the maximum of Z = 3x + 2y MUST occur at one of these four points.
Derivation Trace Β· NCERT Theorem 1: The Corner Point Theorem
Imagine holding a flat wooden ruler (the line Z = ax + by) and sliding it parallel across a flat cardboard polygon (the feasible region). Where does it first touch the cardboard as you push it in? At a sharp corner! Where does it leave the cardboard as you pull it out? At another sharp corner! Because the objective function is completely flat (linear), it can never peak in the middle.
Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by be the objective function. When R is bounded, the objective function Z attains both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R. A corner point of a feasible region is a point in the region which is the intersection of two boundary lines.
Do not skip checking (0, 0) as a candidate corner point if the origin lies in the feasible region! Although (0, 0) gives Z = 0 (which is rarely the maximum for positive coefficients), it is frequently the absolute MINIMUM.
Open the Half-Plane Explorer. Construct multiple overlapping inequalities to visually confirm that the resulting feasible region is always convex without inward dents.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If a bounded region has 5 vertices, how many points must you evaluate to find the maximum of Z?

Answer: Exactly 5 points (the 5 corner vertices).

03

Optimization in Bounded Feasible Regions: The Corner Point Method & Vertex Tabulation

3 concepts Β· Core
3 nodes

What is the systematic algorithmic workflow for extracting vertices and tabulating objective values in bounded regions?

For a bounded feasible region, the optimal solution is obtained systematically via the Corner Point Method: (1) Plot constraints to define region R, (2) Solve pairwise intersections to find all vertex coordinates, (3) Evaluate Z = ax + by at each vertex in a tabular format, and (4) Directly read the maximum M and minimum m values.

01

Systematic Vertex Extraction via Simultaneous Equations

To find each corner point of the feasible region, identify the two boundary lines that intersect at that vertex and solve their simultaneous linear equations using algebraic elimination or substitution.

Key Idea
Do not visually estimate vertex coordinates from a graph; always solve the simultaneous equations algebraically to avoid fractional errors.
Why It Works
Graphing lines by hand has inherent pencil-width inaccuracies; exact algebraic solutions guarantee correct vertex coordinates.
Boundary Trap
Reading fractional vertices like (3.33, 1.67) by eye instead of solving 3x + y = 11 and x + 2y = 7 exactly as (15/5, ...).
Application Note
Boundary lines x + y = 50 and 3x + y = 90 intersect where (3x + y) - (x + y) = 90 - 50 => 2x = 40 => x = 20, y = 30. Vertex is (20, 30).
Derivation Trace Β· Systematic Vertex Extraction via Simultaneous Equations
Solving an LPP with a bounded region is a foolproof recipe: you do not need to test millions of points inside the polygon. You literally test only 3 to 5 corner vertices in a small table, calculate Z for each, and circle the largest (or smallest) number. It is impossible to miss the answer if your arithmetic is clean.
Corner Point Method comprises: 1. Find the feasible region of the linear programming problem and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point. 2. Evaluate the objective function Z = ax + by at each corner point. Let M and m respectively be the largest and smallest values of these points. 3. When the feasible region is bounded, M and m are the maximum and minimum values of Z.
Be careful when finding coordinates of intersection points from hand-drawn graphs! Never guess coordinates visually from the grid; always solve the simultaneous algebraic equations (e.g., 5x + y = 100 and x + y = 60 => 4x = 40 => x = 10, y = 50). Visual approximations often lead to wrong fractional coordinates.
Open the Straight Line Explorer. Experiment with varying slope -a/b to watch how the level curves of Z = ax + by touch the boundary vertices.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Find the intersection point of x + 2y = 8 and 2x + y = 7.

Answer: Multiply second by 2: 4x + 2y = 14. Subtract: 3x = 6 => x = 2, y = 3. Point is (2, 3).

02

Vertex Tabulation Protocol: Evaluating Z = ax + by

Construct a two-column table listing every extracted corner point in column 1 and evaluating Z = ax + by in column 2. The greatest value is M (maximum) and the least value is m (minimum).

Key Idea
The corner point table provides clear, auditable documentation required for full credit in board examinations.
Why It Works
Evaluating Z across all vertices directly implements Theorem 1 to identify global extrema over the closed convex polyhedron.
Boundary Trap
Forgetting to evaluate the origin (0, 0) when it is a valid vertex of the feasible region.
Application Note
For Z = 4x + y with vertices (0, 0): Z=0; (3, 0): Z=12; (2, 3): Z=11; (0, 5): Z=5. Maximum is Z = 12 at (3, 0); Minimum is Z = 0 at (0, 0).
Derivation Trace Β· Vertex Tabulation Protocol: Evaluating Z = ax + by
Solving an LPP with a bounded region is a foolproof recipe: you do not need to test millions of points inside the polygon. You literally test only 3 to 5 corner vertices in a small table, calculate Z for each, and circle the largest (or smallest) number. It is impossible to miss the answer if your arithmetic is clean.
Corner Point Method comprises: 1. Find the feasible region of the linear programming problem and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point. 2. Evaluate the objective function Z = ax + by at each corner point. Let M and m respectively be the largest and smallest values of these points. 3. When the feasible region is bounded, M and m are the maximum and minimum values of Z.
Be careful when finding coordinates of intersection points from hand-drawn graphs! Never guess coordinates visually from the grid; always solve the simultaneous algebraic equations (e.g., 5x + y = 100 and x + y = 60 => 4x = 40 => x = 10, y = 50). Visual approximations often lead to wrong fractional coordinates.
Open the Straight Line Explorer. Experiment with varying slope -a/b to watch how the level curves of Z = ax + by touch the boundary vertices.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If vertices are (0, 2), (3, 0), and (2, 4), which vertex maximizes Z = 5x + 10y?

Answer: (0, 2): Z=20; (3, 0): Z=15; (2, 4): Z=10+40=50. Maximum is 50 at (2, 4).

03

Classification of Bounded Regions vs Guarantees of Solutions

A feasible region is bounded if it can be enclosed inside a circle of finite radius R. For any bounded feasible region, both an absolute maximum and an absolute minimum ALWAYS exist.

Key Idea
Bounded region = finite polygon; guaranteed to attain maximum and minimum values without any further half-plane tests.
Why It Works
A continuous linear function on a compact (closed and bounded) domain attains its supremum and infimum by the Weierstrass Extreme Value Theorem.
Boundary Trap
Applying the open half-plane test (Theorem 2) to a bounded region: it is completely unnecessary for bounded regions!
Application Note
A region bounded by x + y <= 4, x >= 0, y >= 0 is a triangle with vertices (0, 0), (4, 0), (0, 4). It is fully bounded.
Derivation Trace Β· Classification of Bounded Regions vs Guarantees of Solutions
Solving an LPP with a bounded region is a foolproof recipe: you do not need to test millions of points inside the polygon. You literally test only 3 to 5 corner vertices in a small table, calculate Z for each, and circle the largest (or smallest) number. It is impossible to miss the answer if your arithmetic is clean.
Corner Point Method comprises: 1. Find the feasible region of the linear programming problem and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point. 2. Evaluate the objective function Z = ax + by at each corner point. Let M and m respectively be the largest and smallest values of these points. 3. When the feasible region is bounded, M and m are the maximum and minimum values of Z.
Be careful when finding coordinates of intersection points from hand-drawn graphs! Never guess coordinates visually from the grid; always solve the simultaneous algebraic equations (e.g., 5x + y = 100 and x + y = 60 => 4x = 40 => x = 10, y = 50). Visual approximations often lead to wrong fractional coordinates.
Open the Straight Line Explorer. Experiment with varying slope -a/b to watch how the level curves of Z = ax + by touch the boundary vertices.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Is the region defined by x + y <= 10, x >= 0, y >= 0 bounded or unbounded?

Answer: Bounded, because all points satisfy x <= 10, y <= 10 and are trapped in a finite triangle.

04

Unbounded Feasible Regions: Open Half-Plane Criterion (NCERT Theorem 2)

3 concepts Β· Core
3 nodes

How does the open half-plane criterion (Theorem 2) determine whether an optimal value exists in unbounded regions?

When the feasible region R extends infinitely (unbounded), an optimal value may or may not exist. NCERT Theorem 2 dictates that M is the maximum of Z = ax + by if and only if the open half-plane ax + by > M has NO point in common with R. Similarly, m is the minimum if the open half-plane ax + by < m has NO point in common with R.

01

Geometry and Characteristics of Unbounded Feasible Regions

An unbounded feasible region cannot be enclosed within any finite circle; it extends indefinitely into the plane (common in minimization diet problems with '>=' constraints).

Key Idea
Unbounded regions typically arise when all constraints specify minimum thresholds: a1 x + b1 y >= c1, a2 x + b2 y >= c2.
Why It Works
As x and y increase toward positive infinity, all '>=' constraints continue to be satisfied, leaving the domain open on the top and right.
Boundary Trap
Assuming that because vertices exist, a maximum must exist: in an unbounded region, Z can often increase toward infinity!
Application Note
Region x + 2y >= 10, 3x + 4y >= 24, x >= 0, y >= 0 extends to infinity in the first quadrant.
Derivation Trace Β· Geometry and Characteristics of Unbounded Feasible Regions
When a region is bounded, the walls of the pen trap the values. But in an unbounded region, the pen is wide open to infinity! If you are trying to maximize profit, you could potentially make infinite profit by heading out to infinity. To verify if your corner point M is truly the absolute peak, you ask: 'Can Z ever exceed M inside the open region?' You graph ax + by > M: if that region never touches your feasible yard, M is safe and valid!
Theorem 2: Let R be an unbounded feasible region and let Z = ax + by. If M is the maximum value of Z among corner points: (a) M is the maximum value of Z if the open half-plane determined by ax + by > M has no point in common with the feasible region. Otherwise, Z has no maximum value. (b) Similarly, m is the minimum value of Z if the open half-plane determined by ax + by < m has no point in common with the feasible region. Otherwise, Z has no minimum value.
In board exams, students often find corner points, circle M, and stop there! In an unbounded region, failure to draw the open half-plane ax + by > M (or ax + by < m) and explicitly state whether it shares common points with R will cost you 2 full marks!
Open the Half-Plane Explorer. Set >= constraints to produce an unbounded region and verify whether the test line ax + by = m intersects the shaded territory.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Can Z = 2x + 3y attain a maximum value in the region x + y >= 4, x >= 0, y >= 0?

Answer: No. As x and y approach infinity, Z approaches infinity, so no finite maximum exists.

02

Minimum Value Criterion: Open Half-Plane ax + by < m

If m is the smallest value of Z = ax + by at the corner points of an unbounded region, m is the minimum value if and only if the open half-plane ax + by < m shares NO points in common with the feasible region.

Key Idea
Draw dashed line ax + by = m. If the open region ax + by < m does NOT overlap the shaded feasible region, m is the valid minimum.
Why It Works
If any point (x0, y0) in the feasible region satisfies ax0 + by0 < m, then m is not the minimum because a strictly smaller value exists.
Boundary Trap
Drawing the boundary line ax + by = m as solid instead of dashed: it is an OPEN inequality (points on the line itself do not count as common points).
Application Note
Min Z = -50x + 20y. Vertices give candidate min m = -300. Plot dashed line -50x + 20y < -300. Check if this half-plane intersects the feasible region.
Derivation Trace Β· Minimum Value Criterion: Open Half-Plane ax + by < m
When a region is bounded, the walls of the pen trap the values. But in an unbounded region, the pen is wide open to infinity! If you are trying to maximize profit, you could potentially make infinite profit by heading out to infinity. To verify if your corner point M is truly the absolute peak, you ask: 'Can Z ever exceed M inside the open region?' You graph ax + by > M: if that region never touches your feasible yard, M is safe and valid!
Theorem 2: Let R be an unbounded feasible region and let Z = ax + by. If M is the maximum value of Z among corner points: (a) M is the maximum value of Z if the open half-plane determined by ax + by > M has no point in common with the feasible region. Otherwise, Z has no maximum value. (b) Similarly, m is the minimum value of Z if the open half-plane determined by ax + by < m has no point in common with the feasible region. Otherwise, Z has no minimum value.
In board exams, students often find corner points, circle M, and stop there! In an unbounded region, failure to draw the open half-plane ax + by > M (or ax + by < m) and explicitly state whether it shares common points with R will cost you 2 full marks!
Open the Half-Plane Explorer. Set >= constraints to produce an unbounded region and verify whether the test line ax + by = m intersects the shaded territory.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If the open half-plane ax + by < m shares a common point with the feasible region, what is the conclusion?

Answer: The objective function Z has no minimum value in that region.

03

Maximum Value Criterion: Open Half-Plane ax + by > M

If M is the greatest value of Z = ax + by at the corner points of an unbounded region, M is the maximum value if and only if the open half-plane ax + by > M has NO points in common with the feasible region.

Key Idea
Draw dashed line ax + by = M. If the open half-plane ax + by > M has zero overlap with the feasible region, M is the true maximum.
Why It Works
Any point in the feasible region falling inside ax + by > M would yield a Z value strictly greater than M, contradicting that M is the maximum.
Boundary Trap
Concluding maximum exists just because the table gave a largest number M: you MUST verify the open half-plane test!
Application Note
For Z = x + y with region x - y >= 0, x <= 4, y >= 0 (bounded on right): test ax + by > M to verify if maximum exists.
Derivation Trace Β· Maximum Value Criterion: Open Half-Plane ax + by > M
When a region is bounded, the walls of the pen trap the values. But in an unbounded region, the pen is wide open to infinity! If you are trying to maximize profit, you could potentially make infinite profit by heading out to infinity. To verify if your corner point M is truly the absolute peak, you ask: 'Can Z ever exceed M inside the open region?' You graph ax + by > M: if that region never touches your feasible yard, M is safe and valid!
Theorem 2: Let R be an unbounded feasible region and let Z = ax + by. If M is the maximum value of Z among corner points: (a) M is the maximum value of Z if the open half-plane determined by ax + by > M has no point in common with the feasible region. Otherwise, Z has no maximum value. (b) Similarly, m is the minimum value of Z if the open half-plane determined by ax + by < m has no point in common with the feasible region. Otherwise, Z has no minimum value.
In board exams, students often find corner points, circle M, and stop there! In an unbounded region, failure to draw the open half-plane ax + by > M (or ax + by < m) and explicitly state whether it shares common points with R will cost you 2 full marks!
Open the Half-Plane Explorer. Set >= constraints to produce an unbounded region and verify whether the test line ax + by = m intersects the shaded territory.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

In an unbounded region, what happens if ax + by > M intersects the feasible region?

Answer: Z has no maximum value.

05

Special Problem Cases: Infeasible Solutions (Empty Region) & Redundant Constraints

3 concepts Β· Core
3 nodes

How do contradictory constraints create infeasible empty sets, and how are redundant constraints identified?

An LPP has no feasible solution (infeasibility) when the system of linear inequalities has no common intersection (feasible region is the empty set R = null). Conversely, a redundant constraint is an inequality whose removal does not alter the feasible polygon; it is inactive and does not affect the optimal solution.

01

Infeasible Solution and Empty Feasible Region

When there is no point in the Cartesian plane that satisfies all constraints and non-negativity conditions simultaneously, the feasible region is empty (Phi). The problem has an infeasible solution.

Key Idea
No common shaded region = No feasible solution exists. Do not evaluate any objective function.
Why It Works
If constraint half-planes face opposite directions with a separation gap, their set intersection is the empty set.
Boundary Trap
Forcing an intersection point between contradictory parallel lines: parallel lines never meet!
Application Note
Constraints x + y <= 1, x + y >= 3, x >= 0, y >= 0 have no common points because a sum of numbers cannot be both <= 1 and >= 3.
Derivation Trace Β· Infeasible Solution and Empty Feasible Region
Infeasibility is like a boss demanding: 'Work at least 10 hours a day, but work at most 5 hours a day!' It is physically impossible to obey both rules, so you have zero options (empty region). A redundant constraint is like a rule saying: 'You must be under 100 feet tall'β€”everyone already satisfies it because of other tighter limits, so ignoring that rule changes nothing.
When there is no common region determined by all the constraints and non-negativity restrictions of an LPP, the feasible region is empty. In such cases, there is no feasible solution to the problem. An inequality is called a redundant constraint if its inclusion does not restrict the feasible region any further than the existing constraints.
Do not confuse an empty feasible region (no feasible solution) with an unbounded region where Z has no maximum! In an unbounded problem, there are infinitely many feasible solutions, but Z has no finite upper bound. In an infeasible problem, there are zero feasible solutions to begin with.
Open the Half-Plane Explorer. Create two contradictory parallel constraints such as x + y <= 2 and x + y >= 5 to witness the disappearance of any overlapping feasible area.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Can an LPP with an empty feasible region have an optimal value?

Answer: No. If there are no feasible points, no optimal solution exists.

02

Identifying and Handling Redundant Constraints

A constraint is redundant if its removal does not alter the feasible region. It is geometrically dominated by stricter constraints in the system.

Key Idea
Redundant lines lie completely outside the feasible polygon or touch it at a single non-active point without restricting it.
Why It Works
If x <= 5 and x <= 10, any point satisfying x <= 5 automatically satisfies x <= 10, making x <= 10 mathematically redundant.
Boundary Trap
Treating redundant line intersections as active corner points of the feasible region.
Application Note
For x + y <= 4, x + y <= 8, x >= 0, y >= 0: the boundary line x + y = 8 lies entirely outside the region bounded by x + y <= 4, so x + y <= 8 is redundant.
Derivation Trace Β· Identifying and Handling Redundant Constraints
Infeasibility is like a boss demanding: 'Work at least 10 hours a day, but work at most 5 hours a day!' It is physically impossible to obey both rules, so you have zero options (empty region). A redundant constraint is like a rule saying: 'You must be under 100 feet tall'β€”everyone already satisfies it because of other tighter limits, so ignoring that rule changes nothing.
When there is no common region determined by all the constraints and non-negativity restrictions of an LPP, the feasible region is empty. In such cases, there is no feasible solution to the problem. An inequality is called a redundant constraint if its inclusion does not restrict the feasible region any further than the existing constraints.
Do not confuse an empty feasible region (no feasible solution) with an unbounded region where Z has no maximum! In an unbounded problem, there are infinitely many feasible solutions, but Z has no finite upper bound. In an infeasible problem, there are zero feasible solutions to begin with.
Open the Half-Plane Explorer. Create two contradictory parallel constraints such as x + y <= 2 and x + y >= 5 to witness the disappearance of any overlapping feasible area.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If constraints are x <= 3 and x <= 6 (with x >= 0), which constraint is redundant?

Answer: x <= 6 is redundant because x <= 3 already guarantees x <= 6.

03

Unbounded Solutions vs Infeasible Solutions

An infeasible problem has NO feasible points at all (empty region). An unbounded problem has infinitely many feasible points, but the objective function can be made arbitrarily large (or small) without bound.

Key Idea
Infeasible = empty region; Unbounded solution = infinite region where Z can grow to +infinity or -infinity.
Why It Works
Distinguishing between structural inconsistency (no solution possible) and lack of resource caps (infinite profit possible).
Boundary Trap
Confusing an unbounded feasible region (which may still have a finite minimum) with an unbounded solution (where no finite optimum exists).
Application Note
Maximize Z = 3x + 2y subject to x >= 1, y >= 1. The region has points, but Z can reach 1,000,000, 10^9, etc. The solution is unbounded.
Derivation Trace Β· Unbounded Solutions vs Infeasible Solutions
Infeasibility is like a boss demanding: 'Work at least 10 hours a day, but work at most 5 hours a day!' It is physically impossible to obey both rules, so you have zero options (empty region). A redundant constraint is like a rule saying: 'You must be under 100 feet tall'β€”everyone already satisfies it because of other tighter limits, so ignoring that rule changes nothing.
When there is no common region determined by all the constraints and non-negativity restrictions of an LPP, the feasible region is empty. In such cases, there is no feasible solution to the problem. An inequality is called a redundant constraint if its inclusion does not restrict the feasible region any further than the existing constraints.
Do not confuse an empty feasible region (no feasible solution) with an unbounded region where Z has no maximum! In an unbounded problem, there are infinitely many feasible solutions, but Z has no finite upper bound. In an infeasible problem, there are zero feasible solutions to begin with.
Open the Half-Plane Explorer. Create two contradictory parallel constraints such as x + y <= 2 and x + y >= 5 to witness the disappearance of any overlapping feasible area.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Can an unbounded feasible region have a unique finite minimum value?

Answer: Yes! Unbounded minimization problems (e.g. diet problems) frequently have well-defined finite minimums.

06

Multiple Optimal Solutions & Standard LPP Applications (Diet, Manufacturing, Transport)

3 concepts Β· Core
3 nodes

Under what geometric conditions do infinite optimal solutions exist, and how are diet, manufacturing, and transport models solved?

If the objective function Z takes the same optimal value at two adjacent corner points, it attains that same optimal value at every single point on the line segment connecting them (infinite alternate optimal solutions). Standard LPP applications encompass manufacturing problems (profit maximization), diet problems (cost minimization under nutrient bounds), and transportation problems.

01

Multiple (Infinite) Optimal Solutions and Parallel Boundary Edges

If the objective function Z = ax + by attains its optimal value at two adjacent corner points A and B, it attains that same optimal value at every point on the line segment joining A and B, giving infinitely many optimal solutions.

Key Idea
Slope of objective line (-a/b) = Slope of boundary edge (-a_i/b_i). The lines are parallel!
Why It Works
Since Z is linear, any convex combination point P = t A + (1 - t) B has value Z(P) = t Z(A) + (1 - t) Z(B) = t M + (1 - t) M = M.
Boundary Trap
Stating that only two optimal solutions exist: there are INFINITELY many optimal solutions along the entire line segment connecting the two vertices!
Application Note
If Z = 3x + 3y and maximum occurs at both (2, 4) where Z=18 and (4, 2) where Z=18, then all points on segment between (2, 4) and (4, 2) yield Z = 18.
Derivation Trace Β· Multiple (Infinite) Optimal Solutions and Parallel Boundary Edges
Usually, when you push a ruler against a polygon, it bumps into just ONE sharp tip first. But what if the ruler is tilted at the EXACT same angle as one of the flat edges of the polygon? The entire flat edge touches the ruler at once! Every single point along that edge gives the exact same maximum profit.
If two corner points of the feasible region are both optimal solutions of the same type (both produce the same maximum or minimum value of Z), then every point on the line segment joining these two points is also an optimal solution. That is, the problem has infinitely many optimal solutions.
If a multiple-choice question asks: 'If Z attains its maximum at two distinct corner points A and B, how many optimal solutions exist?', do NOT answer 'Two'! The correct answer is 'INFINITELY MANY', because every point on the segment AB is optimal.
Open the Straight Line Explorer. Adjust slope m until the objective line is parallel to one of the constraint lines to observe line-segment overlap.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If Z achieves its maximum at (1, 5) and (4, 2) with Z = 30, what is the value of Z at the midpoint (2.5, 3.5)?

Answer: Exactly Z = 30, because the midpoint lies on the segment connecting the two optimal vertices.

02

Manufacturing and Production Allocation Problems

Manufacturing problems formulate optimal production quantities of different products to maximize total profit subject to limited machine capacities, labor hours, and storage space.

Key Idea
Constraints are predominantly '<=' resource caps; objective function is Maximize Profit Z.
Why It Works
Firms operate under short-run fixed capital constraints, requiring mathematical allocation to maximize economic return.
Boundary Trap
Mixing up the units of time (e.g. minutes in one constraint and hours in another): convert all times to uniform units before writing equations!
Application Note
A company produces tennis rackets and cricket bats. Rackets yield Rs 20 profit and take 1.5 hr machine time; bats yield Rs 10 profit and take 3 hr machine time. Maximize Z = 20x + 10y subject to machine hour constraints.
Derivation Trace Β· Manufacturing and Production Allocation Problems
Usually, when you push a ruler against a polygon, it bumps into just ONE sharp tip first. But what if the ruler is tilted at the EXACT same angle as one of the flat edges of the polygon? The entire flat edge touches the ruler at once! Every single point along that edge gives the exact same maximum profit.
If two corner points of the feasible region are both optimal solutions of the same type (both produce the same maximum or minimum value of Z), then every point on the line segment joining these two points is also an optimal solution. That is, the problem has infinitely many optimal solutions.
If a multiple-choice question asks: 'If Z attains its maximum at two distinct corner points A and B, how many optimal solutions exist?', do NOT answer 'Two'! The correct answer is 'INFINITELY MANY', because every point on the segment AB is optimal.
Open the Straight Line Explorer. Adjust slope m until the objective line is parallel to one of the constraint lines to observe line-segment overlap.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

If machine A is available for at most 42 hours, what type of inequality constraint represents this limit?

Answer: A less than or equal to inequality: a1 x + b1 y <= 42.

03

Diet and Nutritional Cost Minimization Problems

Diet problems formulate optimal intake of different food types to minimize total dietary cost while meeting or exceeding minimum daily requirements of essential nutrients (vitamins, proteins, minerals).

Key Idea
Constraints are predominantly '>=' minimum thresholds; objective function is Minimize Cost Z.
Why It Works
Nutritional guidelines prescribe minimum acceptable daily allowances, meaning exceeding the quota is permissible while falling below causes deficiency.
Boundary Trap
Forgetting that diet problems often yield unbounded feasible regions and failing to perform the open half-plane check ax + by < m.
Application Note
Food P costs Rs 60/kg with 3 units of nutrient A; Food Q costs Rs 80/kg with 4 units of nutrient A. Daily requirement is at least 24 units. Constraint: 3x + 4y >= 24. Minimize Z = 60x + 80y.
Derivation Trace Β· Diet and Nutritional Cost Minimization Problems
Usually, when you push a ruler against a polygon, it bumps into just ONE sharp tip first. But what if the ruler is tilted at the EXACT same angle as one of the flat edges of the polygon? The entire flat edge touches the ruler at once! Every single point along that edge gives the exact same maximum profit.
If two corner points of the feasible region are both optimal solutions of the same type (both produce the same maximum or minimum value of Z), then every point on the line segment joining these two points is also an optimal solution. That is, the problem has infinitely many optimal solutions.
If a multiple-choice question asks: 'If Z attains its maximum at two distinct corner points A and B, how many optimal solutions exist?', do NOT answer 'Two'! The correct answer is 'INFINITELY MANY', because every point on the segment AB is optimal.
Open the Straight Line Explorer. Adjust slope m until the objective line is parallel to one of the constraint lines to observe line-segment overlap.
πŸ”¬ VIRTUAL LAB Feasible Region
Full Stage β†—
? Quick Concept Check

Why do diet problems typically involve unbounded feasible regions?

Answer: Because constraints specify minimum nutritional requirements (>=), leaving the region open toward infinite consumption.