Learning Objectives
- Understand linear programming problems (LPP) and their formulation
- Learn the graphical method for solving LPPs
- Study feasible region, corner points, and optimal solutions
- Apply LPP to real-world optimization problems
Key Concepts
Linear Programming Problem
Optimization of a linear objective function Z = ax + by subject to linear constraints (inequalities) and non-negativity restrictions (x ≥ 0, y ≥ 0). Goal: Find values of x, y that maximize or minimize Z.
Key Terminology
Objective function: Linear function to be optimized (Z = cx + dy). Decision variables: x, y whose values are to be determined. Constraints: Linear inequalities representing restrictions. Feasible region: Set of all points satisfying all constraints. Feasible solution: Any point in the feasible region. Optimal solution: Feasible solution that optimizes the objective function. Corner point (Vertex): Point of intersection of boundary lines.
Graphical Method
Steps: (1) Formulate the problem (identify objective function and constraints). (2) Graph all constraints as lines; shade feasible region (intersection of all half-planes). (3) Identify corner points of the feasible region. (4) Evaluate Z at each corner point. (5) Optimal value is at the corner point giving maximum/minimum Z.
Corner Point Theorem: The optimal value of Z (if it exists) occurs at a corner point of the feasible region. If Z has the same optimal value at two adjacent corner points, then every point on the line segment joining them is also optimal.
Types of Feasible Regions
Bounded feasible region: Both maximum and minimum of Z exist (at corner points). Unbounded feasible region: Maximum or minimum may or may not exist. To check: draw the line Z = c (for the candidate optimal value); if the open half-plane (opposite to optimization direction) has no point in common with the feasible region, then the optimal value exists.
Types of LPP
Manufacturing problems: Maximize profit given resource constraints. Diet problems: Minimize cost subject to nutritional requirements. Transportation problems: Minimize shipping costs. An LPP may have: a unique optimal solution, infinitely many optimal solutions, or no solution (if feasible region is empty).
Summary
Linear programming optimizes a linear objective function subject to linear constraints. The graphical method identifies the feasible region and evaluates the objective function at corner points. The optimal solution always occurs at a corner point (Corner Point Theorem). Problems can be bounded or unbounded.
Important Terms
- Objective function: The linear function to be maximized or minimized
- Feasible region: Set of all points satisfying all constraints
- Corner point: Vertex of the feasible region polygon
- Optimal solution: Point giving the best value of objective function
- Infeasible problem: No feasible region exists (constraints are contradictory)
Quick Revision
- Z = ax + by (objective function); subject to constraints + non-negativity
- Graph constraints → shade feasible region → find corner points → evaluate Z
- Optimal value occurs at a corner point (Corner Point Theorem)
- Bounded region: both max and min exist
- Unbounded region: may not have optimal value (check further)
- Same Z at two corners → infinite solutions on segment joining them
- No feasible region → no solution