12M12
Linear Programming
Introduction
Why Linear Programming ???
Rs. 50,000
Price :
Profit :
2500
500
250
75
Storage space of Max. 60 items
Maximum Profit
12M12.1
Linear Programming & its Mathematical Formulation
12M12.1 – Linear Programming & its Mathematical Formulation
Learning Objectives
Graphical Method of Solving Linear Programming Problems
Mathematical Formulation of the Problems
Finding Optimum value of Objective function For Bounded Feasible Region
12M12.1
CV1
Mathematical Formulation of the Problems
Rs. 50,000
Quantity :
Maximum Profit
(Non-negative
Constraints)
Price :
Profit :
2500
500
250
75
Storage space of Max. 60 items
Simplify :
(Investment Constraint)
Rs. 50,000
Quantity :
Maximum Profit
(Non-negative
Constraints)
Price :
Profit :
2500
500
250
75
Storage space of Max. 60 items
Simplify :
(Investment Constraint)
(Storage Constraint)
Rs. 50,000
Quantity :
(Non-negative
Constraints)
Price :
Profit :
2500
500
250
75
Storage space of Max. 60 items
Simplify :
(Investment Constraint)
(Storage Constraint)
Maximum Profit
Let profit = Z
Z =
(Objective Function)
Objective Function :
Function or a Quantity that needs to be maximised or minimised.
Constraints :
Boundation / conditions applied on decision variables.
Some Basic Terminology
12M12.1
CV2
Graphical Method of Solving Linear Programming Problems
Rs. 50,000
Quantity :
(Non-negative
Constraints)
Price :
Profit :
2500
500
250
75
Storage space of Max. 60 items
Simplify :
(Investment Constraint)
(Storage Constraint)
Maximum Profit
Let profit = Z
Z =
(Objective Function)
Constraints :
Constraints :
Constraints :
| |
| |
| |
Constraints :
| |
| |
| |
Constraints :
Feasible Region :
A common region which satisfy all the constraints.
Feasible Solution :
Any point in the feasible region.
Optimum Solution :
Any point in the feasible region that gives optimum value (min. / max.) of Objective function.
Some Basic Terminology
12M12.1
CV3
Finding Optimum Value of Objective
Function for Bounded Feasible Region
Constraints :
Theorem 1 :
Feasible Region(R)
& R be the feasible region (convex polygon)
Constraints :
12M12.1
PSV 1
subject to the constraints :
Q.
(NCERT Ex. 12.1, Q2)
subject to the constraints :
Q.
| |
| |
| |
subject to the constraints :
Q.
| |
| |
| |
subject to the constraints :
Q.
subject to the constraints :
Q.
12M12.1
PSV 2
Q.
subject to the constraints :
| |
0 | 20 |
60 | 0 |
Q.
subject to the constraints :
| |
0 | 10 |
10 | 0 |
Q.
subject to the constraints :
| |
0 | 0 |
20 | 20 |
Q.
subject to the constraints :
Q.
subject to the constraints :
Q.
subject to the constraints :
Q.
subject to the constraints :
Note :
Feasible Region(R)
A
B
C
D
E
Q.
subject to the constraints :
12M12.1
PSV 3
subject to the constraints :
Q.
subject to the constraints :
Q.
| |
| |
| |
subject to the constraints :
Q.
| |
| |
| |
subject to the constraints :
Q.
subject to the constraints :
Q.
Unbounded
Note :
If feasible region is unbounded, then optimal value of objective function may not exist.
Case 1 :
No common point.
Note :
If feasible region is unbounded, then optimal value of objective function may not exist.
Case 2 :
Common point exist b/w feasible region and open half plane.
subject to the constraints :
Q.
Unbounded
| |
| |
| |
No Common point
ConcepTest 1
subject to the constraints :
Q.
(NCERT Ex. 12.1, Q9)
subject to the constraints :
Q.
| |
| |
| |
subject to the constraints :
Q.
| |
| |
| |
subject to the constraints :
Q.
subject to the constraints :
Q.
subject to the constraints :
Q.
Unbounded
subject to the constraints :
Q.
Unbounded
| |
| |
| |
Steps to solve Linear Programming Problem
Linear Programming
Summary
Reference Questions
NCERT (Ex. 12.1)
:
1, 3, 4,5,6, 7,8, 10
Work Book
:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
12M12.2
Different Types of Linear Programming Problems
12M12.2 –Different types of Linear Programming Problem
Learning Objectives
Diet Problems
Introduction to the Problems
Transportation Problem
Manufacturing Problem
12M12.2
CV1
Introduction to the Problems
Diet Problem
2 units/kg
1 unit/kg
1 unit/kg
2 units/kg
50 Rs/kg
70 Rs/kg
8 units/day
10 units/day
Minimum Expenditure on Proper Diet
A
Transportation Problem
Factory P
Cap. = 8 units
Location A
Req. = 5 units
Location B
Req. = 5 units
Location C
Req. = 4 units
Factory Q
Cap. = 6 units
Rs. 120
Rs. 100
Rs. 100
Rs. 100
Rs. 160
Rs. 150
Minimum
Transportation
cost
Manufacturing Problem
Finishing :
Fabricating :
Profit :
9 hours
1 hours
3 hours
12 hours
8000
12000
Model A
Model B
Max. 180 hour
Max. 30 hour
Maximum??
12M12.2
CV2
Diet Problems
Ex. :
Requirement
Food Q
Food P
Vit. A
Vit. B
Cost
Objective Function
Vit. A constraint :
Vit. B constraint :
Non negative constraint :
subject to the constraints :
subject to the constraints :
| |
| |
| |
subject to the constraints :
| |
| |
| |
subject to the constraints :
subject to the constraints :
Unbounded
subject to the constraints :
Unbounded
| |
| |
| |
No Common point
subject to the constraints :
Unbounded
| |
| |
| |
No Common point
ConcepTest 1
Requirement
Vit. A
Minerals
Cost
Objective
Function
Vit. A constraint :
Vit. B constraint :
Non negative constraint :
Pause the Video
(Time Duration : 4 Minutes)
subject to the constraints :
subject to the constraints :
| |
| |
| |
subject to the constraints :
| |
| |
| |
subject to the constraints :
subject to the constraints :
Unbounded
subject to the constraints :
Unbounded
| |
| |
| |
No Common Point
subject to the constraints :
Unbounded
| |
| |
| |
No Common Point
12M12.2
CV3
Transportation Problems
How should the supplies be transported in order that the transportation cost is minimum?
What is the minimum cost?
Ex. Two godowns A and B have grain capacity of 100 quintals and 50 quintals respectively. They supply to 3 ration shops, D, E and F whose requirements are 60, 50 and 40 quintals respectively. The cost of transportation per quintal from the godowns to the shops are given in the following table:
A
Transportation cost per quintal (in Rs)
From/To
B
D
F
E
Shop D
60 quintal
Shop F
40 quintal
Shop E
50 quintal
Godown B
50 quintal
Godown A
100 quintal
Ex.
Shop D
60 quintal
Shop F
40 quintal
Shop E
50 quintal
Godown B
50 quintal
Godown A
100 quintal
Constraints :
subject to the constraints :
subject to the constraints :
subject to the constraints :
| |
| |
| |
subject to the constraints :
| |
| |
| |
subject to the constraints :
subject to the constraints :
subject to the constraints :
subject to the constraints :
Ex.
Shop D
60 quintal
Shop F
40 quintal
Shop E
50 quintal
Godown B
50 quintal
Godown A
100 quintal
Constraints :
ConcepTest 2
A
Distance in (Km.)
From/To
B
D
F
E
Pause the Video
(Time Duration : 4 Minutes)
Q. An oil company has two depots A and B with capacities of 7000 L and 4000 L respectively. The company is to supply oil to three petrol pumps, D, E and F whose requirements are 4500L, 3000L and 3500L respectively. The distances (in km) between the depots and the petrol pumps is given in the following table:
Assuming that the transportation cost of 10 litres of oil is Re 1 per km, how should the delivery be scheduled in order that the transportation cost is minimum?
Q.
Constraints :
Minimise
subject to the constraints :
Minimise
subject to the constraints :
Minimise
subject to the constraints :
| |
| |
| |
Minimise
subject to the constraints :
| |
| |
| |
Minimise
subject to the constraints :
Minimise
subject to the constraints :
Minimise
subject to the constraints :
Minimise
subject to the constraints :
Minimise
subject to the constraints :
Q.
Constraints :
12M12.2
CV4
Manufacturing Problems
Ex. 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. It takes 3 hours on machine A and 1 hour on machine B to produce a package of bolts. He earns a profit of Rs17.50 per package on nuts and Rs 7.00 per package on bolts. How many packages of each should be produced each day so as to maximise his profit, if he operates his machines for at the most 12 hours a day?
Nuts
Bolts
Machine A
Machine B
Profit
Let
Max Hours
Ex.
Nuts
Bolts
Machine A
Machine B
Profit
Let
Max Hours
Constraints :
Ex.
Maximise
subject to the constraints :
Ex.
Maximise
subject to the constraints :
| |
| |
| |
Ex.
Maximise
subject to the constraints :
| |
| |
| |
Ex.
Maximise
subject to the constraints :
Ex.
Maximise
subject to the constraints :
Ex.
Maximise
subject to the constraints :
ConcepTest 3
A
Types of Toys
Machine
B
D
F
E
Let
Total profit :
Profit
Constraints :
Objective
Function
Pause the Video
(Time Duration : 4 Minutes)
Q. A manufacturer makes two types of toys A and B. Three machines are needed for this purpose and the time (in minutes) required for each toy on the machines is given below:
Each machine is available for a maximum of 6 hours per day. If the profit on each toy of type A is Rs 7.50 and that on each toy of type B is Rs 5, show that 15 toys of type A and 30 of type B should be manufactured in a day to get maximum profit.
Maximise
subject to the constraints :
Maximise
subject to the constraints :
Maximise
subject to the constraints :
| |
| |
| |
Maximise
subject to the constraints :
| |
| |
| |
Maximise
subject to the constraints :
Maximise
subject to the constraints :
Maximise
subject to the constraints :
Ex.
Maximise
subject to the constraints :
Steps to solve different Linear Programming Problems
Linear Programming
Summary
Reference Questions
NCERT (Ex. 12.2)
:
2, 3, 5, 6, 7, 8, 10, 11
Work Book
:
11, 12, 13, 14, 15, 16, 17, 18, 19, 20