Definitions [8]
An optimisation problem is a problem in which the value of one quantity has to be made as large as possible or as small as possible under given restrictions. If the quantity and restrictions are linear, the problem becomes a Linear Programming Problem (LPP).
A Linear Programming Problem (LPP) is a problem in which a linear objective function is to be maximised or minimised subject to a set of linear constraints and non-negative conditions on the variables.
| Term | Definition |
| Feasible Solution | A feasible solution is any solution that satisfies all the constraints of the LPP, including non-negativity restrictions. |
| Feasible Region | The common region that satisfies all the constraints on the graph is called the feasible region. Every point inside or on this region represents a feasible solution. |
| Infeasible Solution | Any point that does not satisfy all the given constraints is an infeasible solution. |
| Optimal Solution | A feasible solution that gives the maximum or minimum value of the objective function is called the optimal solution. |
| Corner Point | A corner point is a vertex of the feasible region formed by the intersection of boundary lines. In the graphical method, these points are checked first to find the optimum value. |
| Bounded Region |
A feasible region that is enclosed within finite boundaries and does not extend indefinitely in any direction. |
| Unbounded Region |
A feasible region that extends indefinitely in one or more directions and is not completely enclosed by boundaries. |
The linear function whose maximum or minimum value is to be determined is called the objective function.
The common region satisfying all the given inequalities is called the solution set.
The equation ax + by = c is called the associated equation of the inequality.
To optimise means to maximise or minimise.
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
-
Linear Programming is a method of optimisation under linear constraints.
-
The quantity to be optimised is called the objective function.
-
The unknown quantities are called decision variables.
-
Restrictions are called constraints.
-
Non-negative restrictions must always be included.
-
An LPP is solved graphically when there are two variables.
-
The feasible region is formed by the common solution of all constraints.
-
The optimum value is found by evaluating the objective function at corner points.
-
If two corner points give the same optimum value, then all points on the joining segment are also optimal.
-
In an unbounded region, the required maximum or minimum may fail to exist.
-
If no feasible region exists, the LPP has no feasible solution.
| 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 [28]
- Two Tailors, a and B, Earn Rs 300 and Rs 400 per Day Respectively. a Can Stitch 6 Shirts and 4 Pairs of Trousers While B Can Stitch 10 Shirts and 4 Pairs of Trousers per Day. to Find How Many Days Should Each of Them Work and If It is Desired to Produce at Least 60 Shirts and 32 Pairs of Trousers at a Minimum Labour Cost, Formulate this as an Lpp
- A Small Firm Manufactures Necklaces and Bracelets. the Total Number of Necklaces and Bracelets that It Can Handle per Day is at Most 24 Formulate on L.P.P. for Finding How Many of Each Should Be Produced Daily to Maximize the Profit?
- There are two types of fertilisers 'A' and 'B'. 'A' consists of 12% nitrogen and 5% phosphoric acid whereas 'B' consists of 4% nitrogen and 5% phosphoric acid. After testing the soil conditions, farmer finds that he needs at least 12 kg of nitrogen and 12 kg of phosphoric acid for his crops. If 'A' costs Rs 10 per kg and 'B' cost Rs 8 per kg, then graphically determine how much of each type of fertiliser should be used so that nutrient requirements are met at a minimum cost
- A retired person wants to invest an amount of Rs. 50, 000. His broker recommends investing in two type of bonds ‘A’ and ‘B’ yielding 10% and 9% return respectively on the invested amount.
- Minimum and Maximum Z = 5x + 2y Subject to the Following Constraints:
- A manufacturer produces two products A and B. Both the products are processed on two differeavailable capacity of first machine is 12 hours and that of second machine is 9 hours per day.
- Find Graphically, the Maximum Value of Z = 2x + 5y, Subject to Constraints Given Below
- A manufacturing company makes two types of teaching aids A and B of Mathematics for class XII. Each type of A requires 9 labour hours for fabricating and 1 labour hour for finishing. Each type of B requires 12 labour hours for fabricating and 3 labour hours for finishing.
- Maximise Z = X + 2y Subject to the Constraints X + 2y >= 10 2x - Y <= 0 and 2x + Y <= 20 Solve the Above Lpp Graphically
- Solve the Following Linear Programming Problem Graphically : Maximise Z = 7x + 10y Subject to the Constraints 4x + 6y ≤ 240 6x + 3y ≤ 240
- Solve the Following L.P.P. Graphically: Minimise Z = 5x + 10y Subject to X + 2y ≤ 120 Constraints X + Y
- Solve the Following L.P.P. Graphically Maximise Z = 4x + Y Subject to Following Constraints X + Y ≤ 50 3x + Y ≤ 90, X ≥ 10 X, Y ≥ 0
- Solve the Following L.P.P Graphically: Maximise Z = 20x + 10y Subject to the Following Constraints X + 2y ≤ 28,
- Solve the Following Lpp Graphically : Maximise Z = 105x + 90y Subject to the Constraints X + Y ≤ 50 2x + Y ≤ 80 X ≥ 0, Y ≥ 0.
- In Order to Supplement Daily Diet, a Person Wishes to Take X and Y Tablets. the Contents (In Milligrams per Tablet) of Iron, Calcium and Vitamins in X and Y Are Given as Below :
- Maximise Z = 8x + 9y Subject to the Constraints Given Below : 2x + 3y ≤ 6 3x − 2y ≤6 Y ≤ 1 X, Y ≥ 0
- A Company Manufactures Two Types of Novelty Souvenirs Made of Plywood. Souvenirs of Type a Require 5 Minutes Each for Cutting and 10 Minutes Each for Assembling.
- A Manufacturer Has Employed 5 Skilled Men and 10 Semi-skilled Men and Makes Two Models a and B of an Article. the Making of One Item of Model a Requires 2 Hours Work by a Skilled Man
- A Company Manufactures Two Types of Cardigans: Type a and Type B. It Costs ₹ 360 to Make a Type a Cardigan and ₹ 120 to Make a Type B Cardigan. the Company Can Make at Most 300 Cardigans
- The objective function Z = ax + by of an LPP has maximum vaiue 42 at (4, 6) and minimum value 19 at (3, 2). Which of the following is true?
- The corner points of the feasible region of a linear programming problem are (0, 4), (8, 0) and (203,43). If Z = 30x + 24y is the objective function, then (maximum value of Z – minimum value of Z)
- Solve the following linear programming problem graphically: Minimize: Z = 5x + 10y Subject to constraints: x + 2y ≤ 120, x + y ≥ 60, x – 2y ≥ 0, x ≥ 0, y ≥ 0.
- Solve the following linear programming problem graphically: Maximize: Z = x + 2y Subject to constraints: x + 2y ≥ 100, 2x – y ≤ 0 2x + y ≤ 200, x ≥ 0, y ≥ 0.
- Solve the following Linear Programming problem graphically: Maximize: Z = 3x + 3.5y Subject to constraints: x + 2y ≥ 240, 3x + 1.5y ≥ 270, 1.5x + 2y ≤ 310, x ≥ 0, y ≥ 0.
- Solve the following Linear Programming Problem graphically: Maximize: P = 70x + 40y Subject to: 3x + 2y ≤ 9, 3x + y ≤ 9, x ≥ 0,y ≥ 0.
- A dealer in rural area wishes to purchase a number of sewing machines. He has only Rs 5,760 to invest and has space for at most 20 items for storage.
- Solve the following Linear Programming Problem graphically: Minimize: Z = 60x + 80y Subject to constraints: 3x + 4y ≥ 8 5x + 2y ≥ 11 x, y ≥ 0
- A cooperative society of farmers has 50 hectares of land to grow two crops A and B. The profits from crops A and B per hectare are estimated as Rs 10,500 and Rs 9,000 respectively.
