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.
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
| 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 |
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 [15]
- Find the feasible solution of the following inequation: 2x + 3y ≤ 6, x + y ≥ 2, x ≥ 0, y ≥ 0
- 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 ______.
- A firm manufactures two products A and B on which profit earned per unit are ₹ 3 and ₹ 4 respectively. Each product is processed on two machines M1 and M2.
- Solve the Linear Programming problem graphically: Maximize z = 3x + 5y subject to x + 4y ≤ 24, 3x + y ≤ 21, x + y ≤ 9, x ≥ 0, y ≥ 0 also find the maximum value of z
- A company manufactures bicycles and tricycles each of which must be processed through machines A and B. Machine A has maximum of 120 hours available and machine B has maximum of 180 hours available.
- Solve the following LPP by graphical method: Maximize: z = 3x + 5ySubject to: x + 4y ≤ 24 3x + y ≤ 21 x + y ≤ 9 x ≥ 0, y ≥ 0 Also find maximum value of z.
- Minimize z=4x+5y subject to 2x+y>=7, 2x+3y<=15, x<=3,x>=0, y>=0 solve using graphical method.
- Solve the following LPP by graphical method: Minimize Z = 7x + y subject to 5x + y ≥ 5, x + y ≥ 3, x ≥ 0, y ≥ 0
- Maximize: 3 5 Subjectto
- Solve the Following Linear Programming L. P. P. Graphically Minimize Z = 6x + 2y Subject to 5x + 9y ≤ 90
- Minimize: Z = 6x + 4y Subject to the conditions: 3x + 2y ≥ 12, x + y ≥ 5, 0 ≤ x ≤ 4, 0 ≤ y ≤ 4
- Solve the following LPP by using graphical method. Maximize : Z = 6x + 4y
- Solve the following L.P.P graphically: Maximize :Z = 10x + 25y Subject to : x ≤ 3, y ≤ 3, x + y ≤ 5, x ≥ 0, y ≥ 0
- Minimize :Z=6x+4y, Subject to : 3x+2y ≥12
