Definitions [1]
Defintion: Linear Programming Problem (L.P.P.)
A linear programming problem (LPP) is one that is concerned with finding the optimal value (maximum or minimum) of a linear function of several variables, subject to constraints that the variables are non-negative and satisfy a set of linear inequalities.
Maximise / Minimise:
z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to constraints:
a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ (≤, =, ≥) b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ (≤, =, ≥) b₂
.
.
.
... aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ (≤, =, ≥) bₘ
x₁, x₂, x₃, ..., xₙ ≥ 0
Objective function:
The function z = c₁x₁ + c₂x₂ + ... + cₙxₙ is called the objective function.
Key Points
Key Points: Linear Programming Problem (L.P.P.)
| Term | Meaning |
|---|---|
| Decision Variables | Variables we need to find (like x, y) |
| Objective Function | Function to maximise or minimise (z = c₁x + c₂y) |
| Constraints | Conditions/restrictions given (inequalities like ax + by ≤ c) |
| Non-negativity Constraints | Variables cannot be negative (x ≥ 0, y ≥ 0) |
| Feasible Solution | Any solution that satisfies all constraints |
| Infeasible Solution | Does NOT satisfy constraints |
| Feasible Region | Area containing all feasible solutions |
| Optimal Solution | Best solution (max or min value) |
| Optimum Value | Value of the objective function at the optimal solution |
| Bounded Region | Region that is closed (limited area) |
| Unbounded Region | A region that extends infinitely |
| Corner Point (Extreme Point) | Intersection points of boundary lines |
| Optimal Feasible Solution | Feasible solution giving the best value of z |
Key points: Methods to Solve LPP (Graphical / Corner Point Method)
| Case | Result |
|---|---|
| Bounded region | Max & Min exist |
| Unbounded region | Max/Min may not exist |
| Parallel lines | Infinite solutions |
| Same value at 2 points | All points on the line segment are optimal |
