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 [33]
- A Company Produces Two Types of Goods a and B, that Require Gold and Silver. Each Unit of Type a Requires 3 G of Silver and 1 G of Golds While that of Type B Requires 1 G of Silver and 2 G of Gold.
- The Postmaster of a Local Post Office Wishes to Hire Extra Helpers During the Deepawali Season, Because of a Large Increase in the Volume of Mail Handling and Delivery. Because of the Limited Office Space and the Budgetary Conditions, the Number of Temporary Helpers Must Not Exceed 10.
- A Factory Manufactures Two Types of Screws a and B, Each Type Requiring the Use of Two Machines, an Automatic and a Hand-operated. Assuming that He Can Sell All the Screws He Manufactures, How Many Packets of Each Type Should the Factory Owner Produce in a Day in Order to Maximize His Profit? Formulate the Above Lpp and Solve It Graphically and Find the Maximum Profit.
- A manufacturer produces nuts and bolts. It takes 1 hour of work on machine A and 3 hours on machine B to produce a package of nuts.
- A Cottage Industry Manufactures Pedestal Lamps and Wooden Shades, Each Requiring the Use of a Grinding/Cutting Machine and a Sprayer. It Takes 2 Hours on the Grinding/Cutting Machine
- 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
- 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.
- 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:
- 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.
- 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.
- 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?
- 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
