Linear Programming — Types of Problems and Edge Cases

• Distinguish bounded from unbounded feasible regions and their implications for optimality
• Identify infeasible LP problems where no feasible point exists
• Recognise multiple optimal solutions when the objective function is parallel to a constraint boundary
• Verify whether a minimum exists for an unbounded region using the isocost line method
• Understand alternate optimal solutions and their practical significance
• Apply careful corner-point verification when the feasible region is unbounded

Level 1 — Foundations

Types of feasible regions:

Infeasible problem: constraints are contradictory — their intersection is empty. For example, $x + y \geq 6$ AND $x + y \leq 4$ cannot both be satisfied.

Multiple optimal solutions: If the slope of the objective function $Z = ax + by$ equals the slope of an edge of the feasible polygon, then every point on that edge gives the same (optimal) value of $Z$. There are infinitely many optimal solutions.

Slope of $Z = ax + by$: rewrite as $y = -\frac{a}{b}x + \frac{Z}{b}$. Slope $= -a/b$. Slope of constraint $px + qy = r$: slope $= -p/q$. If $a/b = p/q$, i.e., $aq = bp$, objective is parallel to that boundary.

Level 2 — JEE Depth

Unbounded region — when does the minimum exist?

For a minimisation problem with an unbounded feasible region:

1. Find the minimum value $Z^*$ at a corner point.
2. Draw the line $Z = Z^*$ (the isocost line).
3. If there is NO feasible point on the side of this line where $Z < Z^*$, then $Z^*$ is indeed the minimum.
4. If there ARE feasible points giving $Z < Z^*$, there is no finite minimum.

For maximisation with an unbounded region: the maximum may not exist (the objective can grow without bound). Always check by drawing the isoprofit line — if you can always find a feasible point further out, no maximum exists.

Practical significance of multiple optima: If two corner points give the same maximum profit, ALL points on the line segment between them also give that profit. Practically, the decision-maker has flexibility — choose the mix that satisfies secondary objectives (e.g., fewest resources used, easier to implement).

Systematic approach for edge cases:

Step 1: Check feasibility — do the constraints have a common intersection? Step 2: Check boundedness — does the feasible region extend to infinity? Step 3: For unbounded maximisation — no finite maximum; state this. Step 4: For unbounded minimisation — find corner-point minimum, then verify with isocost line. Step 5: After finding corner-point optimal, check if slope of objective = slope of any edge → multiple optima.

Example 1: Maximise $Z = x + y$ subject to $x + y \leq 1$, $x - y \leq 1$, $x \geq 0$, $y \geq 0$. Find all corner points and the optimal value. Then change the objective to $Z = x$ and identify multiple optimal solutions.

Part (a): Maximise Z = x + y.

Step 1 — Boundaries.
L1: x + y = 1  →  (1,0), (0,1).
L2: x − y = 1  →  (1,0), (0,−1). But y ≥ 0, so the relevant part is from (1,0) rightward.

Step 2 — Feasible region with x ≥ 0, y ≥ 0:
Intersection of x+y ≤ 1, x−y ≤ 1, x ≥ 0, y ≥ 0.
At (0,0): 0 ≤ 1 ✓, 0 ≤ 1 ✓. Feasible.
At (1,0): 1 ≤ 1 ✓, 0 ≤ 1 ✓. Feasible.
At (0,1): 1 ≤ 1 ✓, −1 ≤ 1 ✓. Feasible.
Intersection of L1 and L2: x+y=1, x−y=1 → 2x=2 → x=1, y=0 → (1,0).

Corner points: O=(0,0), A=(1,0), B=(0,1).

Step 3 — Evaluate Z = x + y.
O: Z = 0
A: Z = 1
B: Z = 1

Maximum Z = 1, attained at BOTH A=(1,0) and B=(0,1).

Step 4 — Since two corner points give the same Z, the entire edge AB is optimal.
Every point on the segment from (1,0) to (0,1) gives Z = x + y = 1.
→ Infinitely many optimal solutions.

Part (b): Change objective to Z = x.

Evaluate at corners:
O=(0,0): Z = 0
A=(1,0): Z = 1
B=(0,1): Z = 0

Maximum Z = 1 at A=(1,0) only → unique optimal solution.
Note: slope of Z=x is: y = 0 (horizontal) — not parallel to any edge here, so unique maximum.

Example 2: Check feasibility for the system $x + y \geq 6$, $2x + y \leq 4$, $x \geq 0$, $y \geq 0$.

Step 1 — Find the feasible region of each pair of constraints.

Constraint 1: x + y ≥ 6 → feasible region is above/on the line x + y = 6.
The line x + y = 6 has intercepts (6,0) and (0,6).

Constraint 2: 2x + y ≤ 4 → feasible region is below/on the line 2x + y = 4.
The line 2x + y = 4 has intercepts (2,0) and (0,4).

Step 2 — Check the relative positions of these regions.

From constraint 2: y ≤ 4 − 2x. Since x ≥ 0, the maximum y achievable is 4 (at x=0).
Then x + y ≤ x + (4 − 2x) = 4 − x ≤ 4 (since x ≥ 0).

But constraint 1 requires x + y ≥ 6.
Since x + y ≤ 4 for any point satisfying constraint 2 with x ≥ 0, y ≥ 0,
it is impossible to have x + y ≥ 6 simultaneously.

Step 3 — Conclusion.
The feasible region is EMPTY. The problem is INFEASIBLE — no solution exists.

Geometric interpretation: The line x+y=6 lies entirely above the region where 2x+y ≤ 4 
and x,y ≥ 0. The two half-planes do not intersect in the first quadrant.

• Q1: For the feasible region defined by $x \geq 0$, $y \geq 0$, $x + y \leq 4$, $x + y \geq 2$: is the region bounded or unbounded? List its corner points.
• Q2: Maximise $Z = 3x + 3y$ over the feasible region in Q1. What type of optimal solution occurs?
• Q3: Show that the system $x + 2y \leq 3$, $3x + y \leq 4$, $x + y \geq 5$, $x \geq 0$, $y \geq 0$ is infeasible.
• Q4: For an unbounded feasible region with corner point $(2, 1)$ giving $Z = 7$ (minimise $Z = 3x + 2y$), draw the isocost line $Z = 7$ and describe how to verify this is the minimum.
• Stretch: Q5: For what values of $k$ does $Z = kx + y$ have multiple optimal solutions over the feasible region with vertices $(0,0)$, $(4,0)$, $(2,3)$, $(0,4)$? (Find all edges and match slopes.)

NCERT Chapter 12 link: Section 12.3 (Cases — bounded, unbounded, infeasible, multiple optima); worked examples 12.5–12.8; important note at the end of 12.3 on unbounded regions.

Exam connections: JEE Main: direct questions on identifying bounded/unbounded regions and reading multiple optima from a graph (1 Q/year). JEE Advanced: problems that require checking infeasibility or finding conditions for multiple optima.

Study strategy: When the feasible region is unbounded, always draw the isocost/isoprofit line after finding the corner-point optimum — this one extra step prevents wrong answers. Practice one example of each edge case (infeasible, multiple optima, unbounded max) before the exam.

• Edge-case explorer: three modes — infeasible, multiple optima, unbounded. Students toggle constraint parameters and watch which case emerges; the system labels the case and explains why.
• Isocost line verifier for unbounded regions: after finding the corner minimum, slide the line inward/outward and watch whether any feasible point dips below it.
• AI mentor reflection: "Create your own LP problem that is infeasible by choosing two constraints that contradict each other. What is the geometric signature of infeasibility on the graph?"

• "In a bounded feasible region, both the maximum and minimum always exist. Why does this guarantee break down when the region is unbounded?"
• "If a business finds it has multiple optimal production plans, is this good news or bad news? What secondary criteria could the manager use to choose between them?"
• Stretch: "Design constraints on $x$ and $y$ (with $x,y \geq 0$) such that the feasible region is unbounded AND the objective $Z = x + 2y$ has no maximum but DOES have a minimum. State the minimum."

• Complete the core practice + one extension activity (photo, table, short reflection, or mini-project) for base XP + topic badge.
• 5-7 day streak or family discussion note = multiplier + visible artifact in parent/principal dashboard.
• Best real-world application stories (anonymised) featured on class or national leaderboard.

• Simulate a robot path-planning scenario: the robot must reach a goal region (defined by inequality constraints) while a constraint becomes infeasible (obstacle appears); model this as an LP feasibility check and re-plan.
• Future Skill track: AI Mastery — Infeasibility detection is critical in AI scheduling and resource allocation systems; connect LP infeasibility to why AI systems need fallback plans when constraints cannot all be met simultaneously.
• Coding extension: Write a Python function using scipy.optimize.linprog that detects infeasibility (checks the status field of the result) for any given LP, and test it on Example 2; print a clear message "Infeasible: no solution exists" when status == 2.

This material emphasises experiential "learning by doing", competency (apply/create/analyse), vocational exposure, critical thinking, and multidisciplinary connections. Designed to feed live worlds, AI Mentor (with memory), gamification, robotics, parent analytics, and future skills — not just exam prep.

Portfolio Evidence Idea: Your photo/table/reflection/project + one sentence on "How this helps me in real life or a possible future path."

Open the Practice tab for aligned questions (easy/medium/hard + case-based) with full AI scaffolding.

See curriculum for cross-links and the full future-skills/robotics chapters.