Definitions [13]
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.
To optimise means to maximise or minimise.
The common region satisfying all the constraints of an LPP is called the feasible region, and every point in this region is called a feasible solution.
-
A feasible region is always convex.
A solution which does not satisfy all the constraints and non-negativity restrictions is called an infeasible solution.
A Linear Programming Problem involves maximising or minimising a linear function subject to linear constraints and non-negativity restrictions.
The conditions represented by a system of linear inequalities, which the variables of a Linear Programming Problem must satisfy, are called constraints.
The common region satisfying all the given inequalities is called the solution set.
A Linear Programming Problem (LPP) involves a linear function of variables subject to a set of linear constraints, where the objective is to maximise or minimise the function.
Linear Programming is a method of solving problems in which a linear objective function is maximised or minimised subject to conditions expressed as a system of linear inequalities.
The linear function whose maximum or minimum value is to be determined is called the objective function.
The constraints which imply that the decision variables of an LPP are non-negative are called non-negativity restrictions.
A region is said to be convex if the line segment joining any two points in the region lies entirely within the region.
The equation ax + by = c is called the associated equation of the inequality.
Theorems and Laws [1]
Statement:
If a linear objective function has a maximum or minimum value over a feasible region, then the maximum or minimum occurs at one of the corner points of the feasible region.
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 |
This method is based on the fundamental extreme point theorem.
- Step 1: Draw the feasible region and find all corner points (vertices).
- Step 2: Evaluate the objective function Z = ax + by at each corner point.
Feasible Region is Bounded
Maximum value of Z = the largest value at a corner
Minimum value of Z = the smallest value at a corner
If the Feasible Region is Unbounded
If a maximum (or minimum) exists, it must occur at a corner point.
But maximum or minimum may not exist.
Extreme point theorem:
An optimum solution to a linear programming problem, if it exists, occurs at one of the corners (or extreme) points of the feasible region.
| Condition | Region represented |
|---|---|
| ( x > 0 ) | Right of the y-axis |
| ( x < 0 ) | Left of the y-axis |
| ( y > 0 ) | Above x-axis |
| ( y < 0 ) | Below x-axis |
| ( x ≥ 0 ) | Includes y-axis |
| ( y ≥ 0 ) | Includes x-axis |
Important Questions [17]
- State whether the following is True or False: The optimum value of the objective function of LPP occurs at the centre of the feasible region.
- Solve the following L.P.P. by graphical method: Minimize: z = 8x + 10y Subject to: 2x + y ≥ 7, 2x + 3y ≥ 15, y ≥ 2, x ≥ 0, y ≥ 0.
- If the corner points of the feasible solution are (0, 10), (2, 2) and (4, 0), then the point of minimum z = 3x + 2y is ______.
- Solve the following LPP: Minimize z = 4x + 2y Subject to 3x + y ≥ 27, x + y ≥ 21, x + 2y ≥ 30, x ≥ 0, y ≥ 0
- In a cattle breeding firm, it is prescribed that the food ration for one animal must contain 14, 22 and 1 unit of nutrients A, B and C respectively. Two different kinds of fodder are available. Each
- Solve the following L.P.P. by graphical method: Maximize: Z = 4x + 6y Subject to 3x + 2y ≤ 12, x + y ≥ 4, x, y ≥ 0.
- Objective function of LPP is ______.
- If the corner points of the feasible region are (0, 0), (3, 0), (2, 1) and (0,73) the maximum value of z = 4x + 5y is ______.
- The optimal value of the objective function is attained at the ______ points of the feasible region.
- The company makes concrete bricks made up of cement and sand. The weight of a concrete brick has to be at least 5 kg. Cement costs ₹ 20 per kg and sand costs of ₹ 6 per kg. Strength consideration dic
- A train carries at least twice as many first class passengers (y) as second class passengers (x). The constraint is given by ______.
- Minimize z = 7x + y subjected to 5x + y ≥ 5, x + y ≥ 3, x ≥ 0, y ≥ 0.
- Solve the following LP.P. Maximize z = 13x + 9y, Subject to 3x + 2y ≤ 12, x + y ≥ 4, x ≥ 0, y ≥ 0.
- Maximize Z = 60x + 50y Subject to x + 2y ≤ 40, 3x + 2y ≤ 60, x ≥ 0, y ≥ 0
- The region represented by the inequality y ≤ 0 lies in _______ quadrants.
- Graphical solution set of the inequations x ≥ 0 and y ≤ 0 lies in ______ quadrant.
- Solve the following L.P.P. by graphical method: Minimize: Z = 6x + 2y subject to x + 2y ≥ 3, x + 4y ≥ 4, 3x + y ≥ 3, x ≥ 0, y ≥ 0.
