Definitions [6]
An equation which contains two variables and the degree of each term containing a variable is one is called a linear equation in two variables.
General Form:
ax + by + c = 0
A set of points in a plane is called a convex set if the line segment joining any two points in the set lies entirely within the set.
If the line segment joining any two points in the set does not completely lie in the set, then it is a non-convex set.
A linear inequality or inequation, which has only one variable, is called a linear inequality or inequation in one variable.
e.g. ax + b < 0, where a ≠ 0, 3x + 4 > 0
An inequality or inequation is said to be linear if each variable occurs in the first degree only and there is no term involving the product of the variables.
e.g. ax + b ≤ 0, ax + by + c > 0, x ≤ 4
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
| 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 |
| 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 |
