Linear Programming
📊 Chapter 12: Linear Programming
1. Introduction
Linear Programming (LP) is a mathematical technique used to find the optimum (maximum or minimum) value of a linear function, subject to certain linear conditions called constraints. It has wide applications in business, industry, transportation, and resource allocation — helping decide the best possible outcome (like maximum profit or minimum cost) under given restrictions.
2. Key Terminology
Objective function: A linear function Z = ax + by, where a and b are constants, that is to be maximised or minimised.
Decision variables: The variables x and y in the objective function whose values determine the outcome.
Constraints: Linear inequalities or equations on the decision variables that restrict their values.
Non-negative restrictions: The conditions x ≥ 0 and y ≥ 0, since decision variables usually represent real-world quantities.
Optimisation problem: A problem that seeks to maximise or minimise a linear function subject to given constraints.
3. Mathematical Formulation of an LPP
A Linear Programming Problem (LPP) typically has three components:
- Objective function: Z = ax + by (to be maximised or minimised)
- Constraints: A set of linear inequalities in x and y
- Non-negativity restrictions: x ≥ 0, y ≥ 0
4. Important Definitions
| Term | Meaning |
|---|---|
| Solution | Any point (x, y) satisfying all the constraints of an LPP. |
| Feasible solution | A point satisfying all constraints, including non-negativity restrictions. |
| Feasible region | The common region determined by all constraints of an LPP; every point in it is a feasible solution. |
| Infeasible region | The region outside the feasible region. |
| Optimal (feasible) solution | A feasible solution that optimises (maximises or minimises) the objective function. |
| Corner point | A vertex of the feasible region. |
| Bounded region | A feasible region that can be enclosed within a circle (finite area). |
| Unbounded region | A feasible region that extends indefinitely in some direction. |
5. Corner Point Method (Solving an LPP Graphically)
This is the standard method used to solve an LPP with two variables graphically. Steps:
- Formulate the LPP: write the objective function and constraints.
- Graph each constraint as a straight line and shade the feasible region satisfying all constraints and x ≥ 0, y ≥ 0.
- Identify the feasible region — it will be a convex polygon (bounded or unbounded).
- Find the coordinates of all corner points (vertices) of the feasible region.
- Evaluate the objective function Z = ax + by at each corner point.
- If the region is bounded: The maximum and minimum values of Z among the corner points are the optimal values.
- If the region is unbounded: A maximum or minimum may not exist. Check by plotting the inequality ax + by > M (or < m) — if this open half-plane has no point in common with the feasible region, then M (or m) is the optimal value; otherwise no such optimal value exists.
6. Key Theorems
Theorem 1: Let R be the feasible region (convex polygon) for an LPP and let Z = ax + by be the objective function. When Z has an optimal value (maximum or minimum), it must occur at a corner point (vertex) of R.
Theorem 2: Let R be the feasible region and Z = ax + by the objective function. If R is bounded, then Z attains both a maximum and a minimum value in R, and each occurs at a corner point of R.
7. Types of Linear Programming Problems
- Manufacturing problems: Determine number of units of products to maximise profit, given constraints like labour, raw material, and machine hours.
- Diet problems: Determine quantities of food items to minimise cost while meeting minimum nutritional requirements.
- Transportation problems: Determine transportation schedules to minimise cost of shipping goods from sources to destinations.
8. Solved Examples
✏️ Example 1: Maximise Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.
Solution: The feasible region is bounded by x + y = 4 in the first quadrant.
Corner points: (0,0), (4,0), (0,4)
Z(0,0) = 0; Z(4,0) = 12; Z(0,4) = 16
Maximum value of Z = 16 at (0, 4)
✏️ Example 2: Minimise Z = 200x + 500y subject to x + 2y ≥ 10, 3x + 4y ≤ 24, x ≥ 0, y ≥ 0.
Solution: Solving x + 2y = 10 and 3x + 4y = 24 simultaneously gives x = 4, y = 3.
Corner points of feasible region: (0,5), (4,3), (0,6)
Z(0,5) = 2500; Z(4,3) = 800+1500 = 2300; Z(0,6) = 3000
Minimum value of Z = 2300 at (4, 3)
9. Quick Revision Points
- Objective function is always linear: Z = ax + by.
- Feasible region is always a convex polygon (or unbounded convex region).
- Optimal value of Z always occurs at a corner point of the feasible region — never inside it.
- For a bounded feasible region, both maximum and minimum values definitely exist.
- For an unbounded feasible region, always verify by checking the open half-plane condition before concluding an optimal value exists.
- Always draw graphs neatly and label corner points clearly — GTU exams award marks for correct graphical representation.
Post a Comment