Chapter 12: Linear Programming
Optimization, Feasible Regions & Theorems
1. Definitions & Corner Point Theorem
| Objective Function | Linear function $$Z = ax + by$$ which has to be maximized or minimized. |
| Constraints | Linear inequalities (e.g., $$x \ge 0, y \ge 0$$) that restrict the variables. |
| Feasible Region | The common region determined by all constraints (including non-negative restrictions). |
| Optimal Solution | Any point in the feasible region that gives the maximum or minimum value of $$Z$$. |
| Corner Point Theorem | For a bounded feasible region, the optimal value (Max or Min) of $$Z$$ always occurs at one of the vertex (corner) points of the region. |
2. Case of Infinite Optimal Solutions
| Condition | If the optimal value of $$Z$$ occurs at two distinct corner points (say A and B). |
| Result | Then every point on the line segment joining A and B is also an optimal solution. |
| Implication | The problem has infinitely many solutions. |
3. Case of Unbounded Feasible Region
If the feasible region is unbounded, let $$M$$be the maximum value and$$m$$ be the minimum value obtained at corner points.
| Verification for Max $$M$$ | Plot inequality $$ax + by > M$$. If the open half-plane has NO common point with the feasible region, then $$M$$ is the maximum. Otherwise, no maximum exists. |
| Verification for Min $$m$$ | Plot inequality $$ax + by < m$$. If the open half-plane has NO common point with the feasible region, then $$m$$ is the minimum. Otherwise, no minimum exists. |