š ā Feasible Region
š Chapter 17: Linear Programming | NEB Mathematics Notes Class 12
Based on Latest Syllabus 2080 | Graphical Method, Simplex Method, Duality
ā
Updated according to latest syllabus of 2080 | Complete notes with 15 solved problems
š Linear Programming ā This chapter covers the mathematical method of getting the optimal solution (maximum profit or minimum cost) under given constraints. Topics include graphical method, feasible region, corner point method, simplex method, and duality. The notes have been updated according to the latest syllabus of 2080.
š Exercise
š Introduction to Linear Programming
Linear Programming (LP) is a mathematical method for obtaining the optimal solution (maximum profit or minimum cost) under certain constraints when resources are limited.
Components of LPP:
Components of LPP:
- Objective Function: \(Z = ax + by\) (to be maximized or minimized)
- Constraints: Linear inequalities like \(a_1x + b_1y \leq c_1\)
- Non-negativity Restrictions: \(x \geq 0, y \geq 0\)
- Decision Variables: x, y
- Feasible Region: Set of all points satisfying all constraints
- Optimal Solution: Point in feasible region that optimizes objective function
š Mathematical Model of LPP
Standard Form:
Optimize \(Z = a_1x_1 + a_2x_2\)
Subject to:
\(b_{11}x_1 + b_{12}x_2 \leq c_1\)
\(b_{21}x_1 + b_{22}x_2 \leq c_2\)
\(x_1, x_2 \geq 0\) (Non-negativity constraints)
Optimize \(Z = a_1x_1 + a_2x_2\)
Subject to:
\(b_{11}x_1 + b_{12}x_2 \leq c_1\)
\(b_{21}x_1 + b_{22}x_2 \leq c_2\)
\(x_1, x_2 \geq 0\) (Non-negativity constraints)
š Graphical Method (For 2 Variables)
Step 1: Convert inequalities into equations
Step 2: Plot lines on graph
Step 3: Identify feasible region (common area)
Step 4: Find corner points
Step 5: Evaluate objective function at each corner
Step 6: Select optimal (max/min) value
š Simplex Method
The Simplex Method is an iterative method used for solving LPP with two or more decision variables. It starts with a basic feasible solution and improves it in each iteration until optimality is reached.
Key Terms: Slack variables, basic variables, non-basic variables, pivot element, optimality condition.
Key Terms: Slack variables, basic variables, non-basic variables, pivot element, optimality condition.
āļø Duality in Linear Programming
Every LPP has a corresponding dual problem. The original problem is the primal and the associated problem is the dual.
Principle of Duality: If either the primal or dual has a finite optimal solution, then the other also has a finite optimal solution, and:
\[ \text{Max Z (Primal)} = \text{Min W (Dual)} \]
Rules for forming Dual:
Principle of Duality: If either the primal or dual has a finite optimal solution, then the other also has a finite optimal solution, and:
\[ \text{Max Z (Primal)} = \text{Min W (Dual)} \]
Rules for forming Dual:
- Maximization primal ā Minimization dual
- Constraints of primal become variables of dual
š Solved Problems (15 Important Questions)
Q1 Maximize \(Z = 3x + 5y\) subject to \(x + y \leq 4\), \(x \geq 0\), \(y \geq 0\).
Corner points: (0,0) ā Z=0; (4,0) ā Z=12; (0,4) ā Z=20
ā
Maximum Z = 20 at (0,4)
Q2 Maximize \(Z = 4x + 3y\) subject to \(x + 2y \leq 10\), \(2x + y \leq 8\), \(x, y \geq 0\).
Corner points: (0,0) ā 0; (0,5) ā 15; (4,0) ā 16; Intersection: solving \(x+2y=10\), \(2x+y=8\) gives \(x=2, y=4\) ā Z = 8+12=20
ā
Maximum Z = 20 at (2,4)
Q3 Minimize \(Z = 2x + 3y\) subject to \(x + y \geq 4\), \(2x + y \geq 5\), \(x, y \geq 0\).
Corner points: Intersection of \(x+y=4\) and \(2x+y=5\) gives \(x=1, y=3\) ā Z=2+9=11
Also (0,5) ā Z=15; (4,0) ā Z=8
Feasible region unbounded, but (4,0) gives Z=8 (check constraints: 4ā„4, 8ā„5 OK)
Also (0,5) ā Z=15; (4,0) ā Z=8
Feasible region unbounded, but (4,0) gives Z=8 (check constraints: 4ā„4, 8ā„5 OK)
ā
Minimum Z = 8 at (4,0)
Q4 A factory produces two products A and B. Profit from A is Rs 40, from B is Rs 30. Each product requires machine time: A requires 2 hours, B requires 1 hour. Total machine hours available = 100. Market demand: at most 60 units of A. Find optimal production.
Let x = number of A, y = number of B
Maximize Z = 40x + 30y
Constraints: \(2x + y \leq 100\), \(x \leq 60\), \(x, y \geq 0\)
Corner points: (0,0)ā0; (60,0)ā2400; (0,100)ā3000; Intersection: \(2(60)+y=100\) ā y=-20 (not feasible). Also check (50,0) is on line? Actually intersection of 2x+y=100 and x=60 gives x=60, y=-20 invalid. So test (0,100) gives 3000, but check xā¤60? 0ā¤60 OK. Also check where 2x+y=100 meets x=60 gives y=-20 not valid. So feasible region includes (0,100) because 2(0)+100=100 ā¤100. Also need to check (50,0) not needed. Actually (0,100) gives Z=3000.
Maximize Z = 40x + 30y
Constraints: \(2x + y \leq 100\), \(x \leq 60\), \(x, y \geq 0\)
Corner points: (0,0)ā0; (60,0)ā2400; (0,100)ā3000; Intersection: \(2(60)+y=100\) ā y=-20 (not feasible). Also check (50,0) is on line? Actually intersection of 2x+y=100 and x=60 gives x=60, y=-20 invalid. So test (0,100) gives 3000, but check xā¤60? 0ā¤60 OK. Also check where 2x+y=100 meets x=60 gives y=-20 not valid. So feasible region includes (0,100) because 2(0)+100=100 ā¤100. Also need to check (50,0) not needed. Actually (0,100) gives Z=3000.
ā
Produce 0 units of A, 100 units of B ā Profit = Rs 3000
Q5 Solve graphically: Maximize Z = 2x + 3y subject to \(x + y \leq 6\), \(x \leq 4\), \(y \leq 4\), \(x, y \geq 0\).
Corners: (0,0)ā0; (4,0)ā8; (0,4)ā12; (4,2)ā8+6=14; (2,4)ā4+12=16
Intersection of x=4 and x+y=6 ā y=2; intersection of y=4 and x+y=6 ā x=2
Intersection of x=4 and x+y=6 ā y=2; intersection of y=4 and x+y=6 ā x=2
ā
Maximum Z = 16 at (2,4)
Q6 Minimize Z = 5x + 4y subject to \(x + y \geq 6\), \(2x + y \geq 8\), \(x \geq 0\), \(y \geq 0\).
Intersection of x+y=6 and 2x+y=8 ā x=2, y=4 ā Z=10+16=26
(0,8)āZ=32; (6,0)āZ=30
Minimum = 26 at (2,4)
(0,8)āZ=32; (6,0)āZ=30
Minimum = 26 at (2,4)
ā
Minimum Z = 26 at (2,4)
Q7 Maximize Z = 3x + 2y subject to \(x + 2y \leq 10\), \(3x + y \leq 15\), \(x, y \geq 0\).
Intersection: x+2y=10 and 3x+y=15 ā solve: multiply second by 2: 6x+2y=30, subtract first: 5x=20 ā x=4, y=3 ā Z=12+6=18
(0,5)āZ=10; (5,0)āZ=15
(0,5)āZ=10; (5,0)āZ=15
ā
Maximum Z = 18 at (4,3)
Q8 Find dual of: Maximize Z = 2x + 3y subject to \(x + y \leq 4\), \(2x + y \leq 5\), \(x, y \geq 0\).
Primal: Max Z = 2xā + 3xā
Constraints: xā + xā ā¤ 4, 2xā + xā ā¤ 5, xā, xā ā„ 0
Dual: Minimize W = 4yā + 5yā
Constraints: yā + 2yā ā„ 2, yā + yā ā„ 3, yā, yā ā„ 0
Constraints: xā + xā ā¤ 4, 2xā + xā ā¤ 5, xā, xā ā„ 0
Dual: Minimize W = 4yā + 5yā
Constraints: yā + 2yā ā„ 2, yā + yā ā„ 3, yā, yā ā„ 0
ā
Min W = 4yā + 5yā subject to yā+2yāā„2, yā+yāā„3, yā,yāā„0
Q9 A company produces two products. Each unit of product P requires 2 hours of labor and 3 kg of material; each unit of Q requires 3 hours of labor and 2 kg of material. Available: 60 hours labor, 50 kg material. Profit: P = Rs 50, Q = Rs 40. Find optimal production.
Maximize Z = 50x + 40y
Constraints: 2x + 3y ā¤ 60 (labor), 3x + 2y ā¤ 50 (material), x, y ā„ 0
Intersection: 2x+3y=60 and 3x+2y=50 ā multiply first by 2: 4x+6y=120, second by 3: 9x+6y=150 ā subtract: 5x=30 ā x=6, y=16 ā Z=300+640=940
(0,20)āZ=800; (16.67,0)āZā833
Constraints: 2x + 3y ā¤ 60 (labor), 3x + 2y ā¤ 50 (material), x, y ā„ 0
Intersection: 2x+3y=60 and 3x+2y=50 ā multiply first by 2: 4x+6y=120, second by 3: 9x+6y=150 ā subtract: 5x=30 ā x=6, y=16 ā Z=300+640=940
(0,20)āZ=800; (16.67,0)āZā833
ā
Optimal: x=6, y=16, Profit = Rs 940
Q10 Maximize Z = 5x + 7y subject to \(x + y \leq 8\), \(x \leq 5\), \(y \leq 6\), \(x, y \geq 0\).
Corners: (0,0)ā0; (5,0)ā25; (0,6)ā42; (5,3)ā25+21=46; (2,6)ā10+42=52
Intersection of x=5 and x+y=8 ā y=3; intersection of y=6 and x+y=8 ā x=2
Intersection of x=5 and x+y=8 ā y=3; intersection of y=6 and x+y=8 ā x=2
ā
Maximum Z = 52 at (2,6)
Q11 Minimize Z = x + 2y subject to \(2x + y \geq 8\), \(x + 2y \geq 10\), \(x, y \geq 0\).
Intersection: 2x+y=8 and x+2y=10 ā multiply first by 2: 4x+2y=16, subtract: 3x=6 ā x=2, y=4 ā Z=2+8=10
(0,8)āZ=16; (10,0)āZ=10
Minimum Z=10 at (2,4) and (10,0)
(0,8)āZ=16; (10,0)āZ=10
Minimum Z=10 at (2,4) and (10,0)
ā
Minimum Z = 10 at multiple points
Q12 A diet requires at least 8 units of vitamin A and 10 units of vitamin B. Food P has 2 units of A and 1 unit of B per gram, costs Rs 3. Food Q has 1 unit of A and 2 units of B per gram, costs Rs 4. Find minimum cost.
Minimize Z = 3x + 4y
Constraints: 2x + y ā„ 8 (vitamin A), x + 2y ā„ 10 (vitamin B), x, y ā„ 0
Intersection: 2x+y=8, x+2y=10 ā solve: multiply first by 2: 4x+2y=16, subtract second: 3x=6 ā x=2, y=4 ā Z=6+16=22
(0,8)āZ=32; (10,0)āZ=30
Minimum Z=22 at (2,4)
Constraints: 2x + y ā„ 8 (vitamin A), x + 2y ā„ 10 (vitamin B), x, y ā„ 0
Intersection: 2x+y=8, x+2y=10 ā solve: multiply first by 2: 4x+2y=16, subtract second: 3x=6 ā x=2, y=4 ā Z=6+16=22
(0,8)āZ=32; (10,0)āZ=30
Minimum Z=22 at (2,4)
ā
Minimum cost = Rs 22 with 2g of P and 4g of Q
Q13 Write the dual of: Minimize Z = 5x + 3y subject to \(2x + y \geq 6\), \(x + 2y \geq 8\), \(x, y \geq 0\).
Primal: Min Z = 5xā + 3xā
Constraints: 2xā + xā ā„ 6, xā + 2xā ā„ 8, xā, xā ā„ 0
Dual: Maximize W = 6yā + 8yā
Constraints: 2yā + yā ā¤ 5, yā + 2yā ā¤ 3, yā, yā ā„ 0
Constraints: 2xā + xā ā„ 6, xā + 2xā ā„ 8, xā, xā ā„ 0
Dual: Maximize W = 6yā + 8yā
Constraints: 2yā + yā ā¤ 5, yā + 2yā ā¤ 3, yā, yā ā„ 0
ā
Max W = 6yā + 8yā subject to 2yā+yāā¤5, yā+2yāā¤3, yā,yāā„0
Q14 Maximize Z = 4x + 6y subject to \(x + y \leq 5\), \(2x + 3y \leq 12\), \(x \geq 0\), \(y \geq 0\).
Intersection: x+y=5 and 2x+3y=12 ā multiply first by 2: 2x+2y=10, subtract: y=2, x=3 ā Z=12+12=24
(0,5)āZ=30; (5,0)āZ=20; (0,4)āZ=24; (6,0)āZ=24
(0,5)āZ=30; (5,0)āZ=20; (0,4)āZ=24; (6,0)āZ=24
ā
Maximum Z = 30 at (0,5)
Q15 A manufacturer produces two types of products. Type A requires 2 hours on machine M1 and 1 hour on M2. Type B requires 1 hour on M1 and 2 hours on M2. Available: M1 = 100 hours, M2 = 80 hours. Profit: A = Rs 40, B = Rs 50. Find maximum profit.
Maximize Z = 40x + 50y
Constraints: 2x + y ā¤ 100, x + 2y ā¤ 80, x, y ā„ 0
Intersection: 2x+y=100, x+2y=80 ā multiply second by 2: 2x+4y=160, subtract first: 3y=60 ā y=20, x=40 ā Z=1600+1000=2600
(0,40)āZ=2000; (50,0)āZ=2000
Constraints: 2x + y ā¤ 100, x + 2y ā¤ 80, x, y ā„ 0
Intersection: 2x+y=100, x+2y=80 ā multiply second by 2: 2x+4y=160, subtract first: 3y=60 ā y=20, x=40 ā Z=1600+1000=2600
(0,40)āZ=2000; (50,0)āZ=2000
ā
Maximum Profit = Rs 2600 at x=40, y=20
āļø Practice Questions
P1 Maximize Z = 2x + 4y subject to x + y ā¤ 5, 2x + y ā¤ 8, x, y ā„ 0
ā
Answer: Z = 16 at (0,4)
P2 Minimize Z = 4x + 5y subject to x + 2y ā„ 10, 2x + y ā„ 10, x, y ā„ 0
ā
Answer: Z = 30 at (5,0) or (0,5)
P3 Find the feasible region for: x + y ā¤ 6, x ā¤ 4, y ā¤ 5, x, y ā„ 0
ā
Answer: Polygon with vertices (0,0), (4,0), (4,2), (1,5), (0,5)
P4 Write the dual of: Maximize Z = 3x + 4y subject to 2x + y ā¤ 10, x + 2y ā¤ 8, x, y ā„ 0
ā
Answer: Minimize W = 10u + 8v subject to 2u+vā„3, u+2vā„4, u,vā„0
P5 A company produces x units of product P and y units of Q with profit 20x+30y. Constraints: x+yā¤50, xā¤30, yā¤25. Find optimal.
ā
Answer: x=25, y=25, Z=1250
š Multiple Choice Questions (HSEB Pattern)
MCQ 1 In Linear Programming, the objective function is:
A) A linear expression to be optimized B) A constraint C) A non-linear equation D) None
ā
Answer: A) A linear expression to be optimized
MCQ 2 The feasible region in a LPP is always:
A) Concave B) Convex C) Circular D) Linear
ā
Answer: B) Convex
MCQ 3 The optimal solution of an LPP lies at:
A) Interior of feasible region B) Boundary C) Corner point D) Any point
ā
Answer: C) Corner point
MCQ 4 The dual of a maximization problem is a:
A) Maximization problem B) Minimization problem C) Equality problem D) None
ā
Answer: B) Minimization problem
MCQ 5 A constraint in LPP is written as:
A) Equation with = B) ā¤ or ā„ C) Only ā¤ D) Only ā„
ā
Answer: B) ā¤ or ā„
MCQ 6 The variables that are ā„ 0 in LPP are called:
A) Slack variables B) Decision variables C) Surplus variables D) None
ā
Answer: B) Decision variables
MCQ 7 If the feasible region is empty, the LPP has:
A) Unique solution B) Infinite solutions C) No solution D) None
ā
Answer: C) No solution
MCQ 8 In the simplex method, the objective function coefficient of the entering variable should be:
A) Most negative (for maximization) B) Most positive (for maximization) C) Zero D) None
ā
Answer: A) Most negative (for maximization)
ā ļø Please do not repost this PDF on any website or social platform without permission.
This PDF provides the solutions of every question from the 1st exercise of class 12 linear programming chapter. If you want the notes of other chapters then you can search them in our site.
This PDF provides the solutions of every question from the 1st exercise of class 12 linear programming chapter. If you want the notes of other chapters then you can search them in our site.
š More Read
Class 12 Nepali Important Questions
NEB Class 12 English Important Questions
NEB Class 12 Biology Important Questions
NEB Class 12 Chemistry Important Questions
š Key Linear Programming Summary:
ā¢ Objective Function: \(Z = ax + by\) (Maximize or Minimize)
ā¢ Corner Point Theorem: Optimal solution occurs at a corner point of feasible region
ā¢ Duality: Max Z = Min W (subject to proper conversion)
ā¢ Feasible Region: Convex polygon satisfying all constraints
ā¢ Simplex Method: Iterative method for higher-dimensional LPPs
ā¢ Objective Function: \(Z = ax + by\) (Maximize or Minimize)
ā¢ Corner Point Theorem: Optimal solution occurs at a corner point of feasible region
ā¢ Duality: Max Z = Min W (subject to proper conversion)
ā¢ Feasible Region: Convex polygon satisfying all constraints
ā¢ Simplex Method: Iterative method for higher-dimensional LPPs