Definitions [12]
The common region satisfying all the given inequalities is called the solution set.
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 equation ax + by = c is called the associated equation of the inequality.
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.
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
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]
- The optimum value of the objective function of LPP occurs at the center 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.
