Class 12 : Maths (English) – Chapter 12: Linear Programming
EXPLANATION & SUMMARY
🔷 Explanation
🔹 Introduction
Linear Programming (LP) is a branch of mathematics that deals with the optimization (maximization or minimization) of a linear objective function, subject to a set of linear constraints (inequalities or equations).
It is a key topic in Operations Research and is widely used in economics, business, engineering, and management for resource optimization.
💡 Concept:
A Linear Programming Problem (LPP) involves finding the maximum or minimum value of a linear expression called the objective function, under certain linear constraints.
🔹 1. Basic Terminology
🟢 Objective Function:
A linear function of the form
➡️ Z = ax + by
where a and b are constants, and x, y are variables.
We aim to either maximize or minimize Z.
🟢 Constraints:
Conditions or restrictions expressed as linear inequalities or equations, e.g.:
➡️ 2x + y ≤ 10, x + y ≥ 5
🟢 Decision Variables:
The variables (x, y) whose values determine the value of Z.
🟢 Feasible Region:
The common region in the graph that satisfies all constraints simultaneously.
🟢 Feasible Solution:
Any point (x, y) within or on the boundary of the feasible region.
🟢 Optimal Solution:
A feasible solution that gives the maximum or minimum value of the objective function.
🟢 Corner Point Theorem:
If the feasible region is bounded, the optimal value occurs at one of the corner points (vertices) of the feasible region.
🔹 2. Formulation of Linear Programming Problem
The first step is to convert the word problem into mathematical form:
1️⃣ Identify decision variables (x, y).
2️⃣ Express the objective function (Z = ax + by).
3️⃣ Write down the constraints as linear inequalities.
4️⃣ Include non-negativity conditions: x ≥ 0, y ≥ 0.
🔹 3. Graphical Method of Solution
The graphical method is used for two-variable problems.
🧭 Steps:
1️⃣ Plot each linear inequality on a graph.
2️⃣ Shade the region satisfying each inequality.
3️⃣ The common shaded area is the feasible region.
4️⃣ Identify the corner points (vertices) of the feasible region.
5️⃣ Evaluate Z = ax + by at each corner point.
6️⃣ The maximum or minimum value occurs at one of these points.
✏️ Note: If feasible region is unbounded, you must check whether optimum value is finite.
🔹 4. Types of Linear Programming Problems
🟢 Maximization Problem:
Objective is to maximize Z = ax + by.
Example: Profit maximization.
🟢 Minimization Problem:
Objective is to minimize Z = ax + by.
Example: Cost minimization.
🟢 Feasible Region:
Bounded → Optimal value always exists.
Unbounded → May or may not exist; check using test line.
🔹 5. Example (Maximization)
Problem:
Maximize Z = 3x + 2y
Subject to:
x + y ≤ 4
x ≥ 0, y ≥ 0
Solution:
Plot lines x + y = 4
Shade feasible region in first quadrant (bounded triangle).
Corner points: (0,0), (4,0), (0,4)
Evaluate Z:
Z(0,0) = 0
Z(4,0) = 12
Z(0,4) = 8
✅ Maximum Z = 12 at (4,0)
🔹 6. Example (Minimization)
Problem:
Minimize Z = 2x + 3y
Subject to:
x + 2y ≥ 4
3x + y ≥ 3
x ≥ 0, y ≥ 0
By plotting the inequalities, feasible region is obtained and corner points are found.
Evaluate Z at each corner point → the smallest value is minimum Z.
🔹 7. Corner Point Method
💡 Corner Point Theorem:
If an LP problem has an optimal solution, it occurs at a vertex (corner point) of the feasible region.
🧭 Steps:
Determine feasible region.
Find corner points.
Evaluate objective function at each corner.
Choose maximum/minimum value.
🔹 8. Important Observations
✔️ If feasible region is bounded, optimal solution always exists at a vertex.
✔️ If feasible region is unbounded, optimal value may not exist.
✔️ If two or more vertices give the same Z, there are infinite optimal solutions.
🔹 9. Real-Life Applications
🔸 Manufacturing: Maximize profit by allocating resources optimally.
🔸 Diet Problems: Minimize cost while meeting nutritional needs.
🔸 Transportation: Minimize travel cost or distance.
🔸 Finance: Maximize returns under given constraints.
🔹 10. Key Formulae
Objective Function: Z = ax + by
Corner Point Evaluation
Distance between two lines if needed for geometric analysis
Feasibility check via inequalities
✏️ Non-negativity Conditions:
x ≥ 0, y ≥ 0 are mandatory.
🔹 11. Graphical Insights
🧠 Feasible region = polygon or half-plane intersection.
🧠 Vertices = intersection points of boundary lines.
🧠 Optimum value always at vertex.
🔹 12. Special Cases
🟡 No Solution: If feasible region is empty (inconsistent constraints).
🟡 Multiple Solutions: Two vertices give same Z → infinite optimal solutions.
🟡 Unbounded Solution: Region not closed; optimum may not exist.
🔹 13. NCERT Example Summary
Example 1: Maximize Z = 3x + 2y with x + y ≤ 4.
→ Maximum at (4,0), Z = 12.
Example 2: Minimize Z = x + y, subject to linear constraints.
→ Minimum at intersection point satisfying all inequalities.
🔹 14. Summary of Steps to Solve LPP
➡️ Step 1: Define variables x, y.
➡️ Step 2: Write objective function Z.
➡️ Step 3: Write all constraints.
➡️ Step 4: Plot constraints on graph.
➡️ Step 5: Determine feasible region.
➡️ Step 6: Identify corner points.
➡️ Step 7: Evaluate Z at each point.
➡️ Step 8: Choose maximum/minimum.
🔹 15. Non-Negativity Condition
Always include x ≥ 0 and y ≥ 0, as negative quantities often have no practical meaning.
🔹 16. Theoretical Basis
🧠 The LP feasible region is a convex polygon.
🧠 The objective function has linear level lines (iso-profit or iso-cost lines).
🧠 Optimal value occurs at vertex due to convexity.
🔹 17. Use in Economics & Business
🔸 Production Planning: Allocate machines and labor.
🔸 Diet Problems: Balanced diet with minimum cost.
🔸 Transportation Problems: Minimize logistics cost.
🔸 Portfolio Management: Optimize returns.
🔹 18. Limitations
⚠️ Assumes linearity of constraints and objective function.
⚠️ Only handles continuous variables.
⚠️ Ignores uncertainties and integer constraints.
🔷 Summary (~300 words)
🔹 Linear Programming aims to optimize (maximize or minimize) a linear objective function under linear constraints.
🔹 Objective Function: Z = ax + by
🔹 Constraints: Linear inequalities involving x, y.
🔹 Decision Variables: x, y
🔹 Feasible Region: Common region satisfying all inequalities.
🔹 Feasible Solution: Any point in feasible region.
🔹 Optimal Solution: Point giving maximum or minimum Z.
💡 Corner Point Theorem:
For bounded feasible region, optimal value occurs at a vertex.
🧭 Steps:
1️⃣ Define variables
2️⃣ Write objective function
3️⃣ Write constraints
4️⃣ Plot graph
5️⃣ Identify feasible region
6️⃣ Find corner points
7️⃣ Evaluate Z
8️⃣ Pick optimum
🟢 Bounded Region: Always optimum.
🟡 Unbounded Region: Check if optimum exists.
🔴 Infeasible: No common region → no solution.
Applications:
Production & resource allocation
Diet & nutrition
Transportation & logistics
Financial planning
Limitations:
Assumes linearity
Cannot handle integer constraints
No stochastic variables
📝 Quick Recap
✔️ Linear Programming = Optimization under constraints
✔️ Objective Function: Z = ax + by
✔️ Constraints: Linear inequalities
✔️ Feasible region = intersection
✔️ Optimum at corner point
✔️ Bounded → always solution
✔️ Unbounded → test line needed
🎯 Use: Maximize profit or minimize cost within given limits.
————————————————————————————————————————————————————————————————————————————
QUESTIONS FROM TEXTBOOK
🔵 Exercise 12.1
🔵 Question 1:
Maximise Z = 3x + 4y subject to the constraints: x + y ≤ 4, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Feasible region in first quadrant bounded by x + y = 4 and axes.
➡️ Corner points: (0,0), (4,0), (0,4).
✳️ Z(0,0) = 0.
✳️ Z(4,0) = 3×4 + 4×0 = 12.
✳️ Z(0,4) = 3×0 + 4×4 = 16.
✔️ Maximum Z = 16 at (x, y) = (0, 4).
🔵 Question 2:
Minimise Z = −3x + 4y subject to x + 2y ≤ 8, 3x + 2y ≤ 12, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Lines: x + 2y = 8 and 3x + 2y = 12.
➡️ Intersections with axes give candidate points; also solve for common point.
✳️ Intersection:
x + 2y = 8
3x + 2y = 12 ⇒ subtract ⇒ 2x = 4 ⇒ x = 2 ⇒ y = 3.
➡️ Feasible corner points: (0,0), (4,0), (2,3), (0,4).
✳️ Z(0,0) = 0.
✳️ Z(4,0) = −12.
✳️ Z(2,3) = −6 + 12 = 6.
✳️ Z(0,4) = 16.
✔️ Minimum Z = −12 at (x, y) = (4, 0).
🔵 Question 3:
Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Find intersection of the two boundary lines.
✳️ Solve:
3x + 5y = 15
5x + 2y = 10
⇒ 6x + 10y = 30, 25x + 10y = 50 ⇒ 19x = 20 ⇒ x = 20/19, y = 45/19.
➡️ Feasible corner points: (0,0), (2,0), (0,3), (20/19, 45/19).
✳️ Z(0,0) = 0.
✳️ Z(2,0) = 10.
✳️ Z(0,3) = 9.
✳️ Z(20/19, 45/19) = 5×(20/19) + 3×(45/19) = 235/19.
✔️ Maximum Z = 235/19 at (x, y) = (20/19, 45/19).
🔵 Question 4:
Minimise Z = 3x + 5y such that x + 3y ≥ 3, x + y ≥ 2, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ For “≥” constraints, feasible region is above both lines in first quadrant.
➡️ Intersection of boundaries gives likely minimum.
✳️ Solve:
x + 3y = 3
x + y = 2 ⇒ subtract ⇒ 2y = 1 ⇒ y = 1/2 ⇒ x = 3 − 3(1/2) = 3/2.
➡️ Check other boundary points that satisfy both: (3,0) and (0,2).
✳️ Z(3/2, 1/2) = 3×(3/2) + 5×(1/2) = 9/2 + 5/2 = 7.
✳️ Z(3,0) = 9.
✳️ Z(0,2) = 10.
✔️ Minimum Z = 7 at (x, y) = (3/2, 1/2).
🔵 Question 5:
Maximise Z = 3x + 2y subject to x + 2y ≤ 10, 3x + y ≤ 15, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Intersection of boundaries:
x + 2y = 10
3x + y = 15 ⇒ 3x + 6y = 30 ⇒ 5y = 15 ⇒ y = 3 ⇒ x = 4.
➡️ Feasible corner points: (0,0), (5,0), (0,5), (4,3).
✳️ Z(0,0) = 0.
✳️ Z(5,0) = 15.
✳️ Z(0,5) = 10.
✳️ Z(4,3) = 3×4 + 2×3 = 18.
✔️ Maximum Z = 18 at (x, y) = (4, 3).
🔵 Question 6:
Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Boundary lines: L₁: 2x + y = 3, L₂: x + 2y = 6.
➡️ Intersection:
✳️ From L₁: y = 3 − 2x.
✳️ Put in L₂: x + 2(3 − 2x) = 6 ⇒ −3x = 0 ⇒ x = 0, y = 3 ⇒ (0, 3).
➡️ Axis hits of L₂: (6, 0) and (0, 3).
➡️ Feasible region is above both lines (because “≥”).
➡️ Corner candidates: (0, 3) and (6, 0).
✳️ Z(0, 3) = 0 + 2×3 = 6.
✳️ Z(6, 0) = 6 + 0 = 6.
✔️ Minimum Z = 6.
💡 Since on L₂ (x + 2y = 6), Z = 6 for every point of the segment from (6, 0) to (0, 3) that also satisfies 2x + y ≥ 3 (true for 0 ≤ y ≤ 3).
✔️ Hence the minimum occurs at infinitely many points (all points on that segment).
🔵 Question 7:
Minimise and Maximise Z = 5x + 10y
subject to x + 2y ≤ 120, x + y ≥ 60, x − 2y ≥ 0, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Lines: L₁: x + 2y = 120, L₂: x + y = 60, L₃: x − 2y = 0 (i.e., x = 2y).
➡️ Vertices of feasible region:
✳️ A = L₂ ∩ L₃: 2y + y = 60 ⇒ y = 20, x = 40 ⇒ A(40, 20).
✳️ B = L₁ ∩ L₃: 2y + 2y = 120 ⇒ y = 30, x = 60 ⇒ B(60, 30).
✳️ C = L₁ ∩ x-axis: y = 0 ⇒ x = 120 ⇒ C(120, 0).
✳️ D = L₂ ∩ x-axis: y = 0 ⇒ x = 60 ⇒ D(60, 0).
➡️ Evaluate Z = 5x + 10y:
✳️ Z(D) = 5×60 + 10×0 = 300.
✳️ Z(C) = 5×120 + 10×0 = 600.
✳️ Z(B) = 5×60 + 10×30 = 600.
✳️ Z(A) = 5×40 + 10×20 = 400.
✔️ Minimum Z = 300 at (60, 0).
✔️ Maximum Z = 600 at every point on the segment of L₁ from (120, 0) to (60, 30) (including those endpoints) since on x + 2y = 120, Z = 5(x + 2y) = 600 (constant).
🔵 Question 8:
Minimise and Maximise Z = x + 2y
subject to x + 2y ≥ 100, 2x − y ≤ 0 (i.e., y ≥ 2x), 2x + y ≤ 200, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Lines: L₁: x + 2y = 100, L₂: y = 2x, L₃: 2x + y = 200.
➡️ Vertices of feasible region:
✳️ Q = L₁ ∩ L₂: x + 2(2x) = 100 ⇒ 5x = 100 ⇒ (20, 40).
✳️ P = L₂ ∩ L₃: 2x + 2x = 200 ⇒ x = 50, y = 100 ⇒ (50, 100).
✳️ E = L₁ ∩ y-axis: (0, 50).
✳️ F = L₃ ∩ y-axis: (0, 200).
➡️ Evaluate Z = x + 2y:
✳️ Z(E) = 0 + 100 = 100.
✳️ Z(Q) = 20 + 80 = 100.
✳️ Z(P) = 50 + 200 = 250.
✳️ Z(F) = 0 + 400 = 400.
✔️ Minimum Z = 100 at every point on L₁ between (0, 50) and (20, 40).
✔️ Maximum Z = 400 at (0, 200).
🔵 Question 9:
Maximise Z = −x + 2y
subject to x ≥ 3, x + y ≥ 5, x + 2y ≥ 6, y ≥ 0.
🟢 Answer:
➡️ Feasible region is to the right of x = 3 and above both lines x + y = 5 and x + 2y = 6 in first quadrant.
➡️ Along the vertical line x = 3, choose y → ∞ (and constraints remain satisfied).
✳️ Z(3, y) = −3 + 2y → unbounded above as y increases.
✔️ Conclusion: No maximum value (Z is unbounded on the feasible region).
🔵 Question 10:
Maximise Z = x + y
subject to x − y ≤ −1, −x + y ≤ 0, x ≥ 0, y ≥ 0.
🟢 Answer:
➡️ Inequalities:
✳️ x − y ≤ −1 ⇒ x ≤ y − 1.
✳️ −x + y ≤ 0 ⇒ y ≤ x.
➡️ Combining gives y ≤ x and x ≤ y − 1 ⇒ x ≤ x − 1, which is impossible.
✔️ Conclusion: No feasible solution (feasible region is empty), so no maximum exists.
————————————————————————————————————————————————————————————————————————————
OTHER IMPORTANT QUESTIONS FOR EXAMS
🔷 Section A – Multiple Choice Questions (1 mark each)
🔵 Question 1:
Linear Programming is used to
🔵 (A) Solve equations
🟢 (B) Optimize objective functions
🟠 (C) Solve quadratic equations
🔴 (D) Find derivatives
Answer: (B) Optimize objective functions
🔵 Question 2:
The function to be optimized is called
🔵 (A) Feasible function
🟢 (B) Objective function
🟠 (C) Constraint function
🔴 (D) Boundary function
Answer: (B) Objective function
🔵 Question 3:
A feasible region is
🔵 (A) Entire plane
🟢 (B) Common region satisfying all constraints
🟠 (C) Any single inequality region
🔴 (D) Unbounded line
Answer: (B) Common region satisfying all constraints
🔵 Question 4:
Which of the following is not a property of LPP?
🔵 (A) Linear objective function
🟢 (B) Linear constraints
🟠 (C) Nonlinear variables
🔴 (D) Non-negativity conditions
Answer: (C) Nonlinear variables
🔵 Question 5:
If Z = 3x + 2y is to be maximized, it is called
🔵 (A) Objective function
🟢 (B) Constraint
🟠 (C) Solution
🔴 (D) Feasible point
Answer: (A) Objective function
🔵 Question 6:
Feasible solution means
🔵 (A) Any solution
🟢 (B) Solution satisfying all constraints
🟠 (C) Solution giving maximum value
🔴 (D) Solution giving minimum value
Answer: (B) Solution satisfying all constraints
🔵 Question 7:
The optimal solution of a Linear Programming Problem, if it exists, occurs at
🔵 (A) Any point
🟢 (B) Corner point of feasible region
🟠 (C) Midpoint
🔴 (D) Axis intersection
Answer: (B) Corner point of feasible region
🔵 Question 8:
Non-negativity constraint means
🔵 (A) x < 0
🟢 (B) x ≥ 0
🟠 (C) x ≤ 0
🔴 (D) x ≠ 0
Answer: (B) x ≥ 0
🔵 Question 9:
If feasible region is bounded, then
🔵 (A) No optimum exists
🟢 (B) Optimum value exists at vertex
🟠 (C) Infinite solutions
🔴 (D) None of these
Answer: (B) Optimum value exists at vertex
🔵 Question 10:
Which of these is an example of LP application?
🔵 (A) Solving integral equations
🟢 (B) Profit maximization
🟠 (C) Curve fitting
🔴 (D) Differential equations
Answer: (B) Profit maximization
🔵 Question 11:
Corner Point Theorem applies to
🔵 (A) Non-linear programming
🟢 (B) Linear Programming
🟠 (C) Geometry
🔴 (D) Calculus
Answer: (B) Linear Programming
🔵 Question 12:
If two corner points give same value of Z,
🔵 (A) One is optimum
🟢 (B) Infinite optimal solutions exist
🟠 (C) No solution
🔴 (D) Unique solution
Answer: (B) Infinite optimal solutions exist
🔵 Question 13:
A problem having no feasible region is
🔵 (A) Infeasible
🟢 (B) Feasible
🟠 (C) Unbounded
🔴 (D) Multiple
Answer: (A) Infeasible
🔵 Question 14:
Graphical method applies to
🔵 (A) 1 variable
🟢 (B) 2 variables
🟠 (C) 3 variables
🔴 (D) More than 3 variables
Answer: (B) 2 variables
🔵 Question 15:
Which is not an LP constraint form?
🔵 (A) ax + by ≤ c
🟢 (B) ax + by ≥ c
🟠 (C) ax + by = c
🔴 (D) ax² + by = c
Answer: (D) ax² + by = c
🔵 Question 16:
The feasible region of LP problem is always
🔵 (A) Convex
🟢 (B) Concave
🟠 (C) Straight line
🔴 (D) Ellipse
Answer: (A) Convex
🔵 Question 17:
The set of all points satisfying constraints is called
🔵 (A) Solution set
🟢 (B) Feasible region
🟠 (C) Line
🔴 (D) Curve
Answer: (B) Feasible region
🔵 Question 18:
If feasible region is unbounded, optimum value
🔵 (A) Always exists
🟢 (B) May or may not exist
🟠 (C) Never exists
🔴 (D) Is infinite
Answer: (B) May or may not exist
🔶 Section B – Very Short / Short Answer Questions (2–3 marks each)
🔵 Question 19:
Define a Linear Programming Problem (LPP). Write its standard form.
🟢 Answer:
➡️ A Linear Programming Problem (LPP) is a problem that seeks to optimize (maximize or minimize) a linear objective function subject to a set of linear inequalities or equations known as constraints.
💡 Standard Form:
Maximize or Minimize: Z = a₁x₁ + a₂x₂
Subject to:
🔹 c₁₁x₁ + c₁₂x₂ ≤ b₁
🔹 c₂₁x₁ + c₂₂x₂ ≤ b₂
🔹 x₁ ≥ 0, x₂ ≥ 0
✔️ The standard form must contain all inequalities in ≤ form and variables non-negative.
🔵 Question 20:
What is the feasible region? How is the optimal solution determined graphically?
🟢 Answer:
➡️ The feasible region is the common shaded area on the graph that satisfies all the constraints simultaneously, including non-negativity conditions.
➡️ To find the optimal solution, we:
1️⃣ Identify all corner points (vertices) of the feasible region.
2️⃣ Compute Z = ax + by at each corner point.
3️⃣ The maximum or minimum value of Z gives the optimal solution.
🔵 Question 21:
What are the possible types of solutions in Linear Programming?
🟢 Answer:
There are four types of possible outcomes:
1️⃣ Unique Optimal Solution: One corner point gives the best value.
2️⃣ Multiple Optimal Solutions: Two or more corner points give the same optimal value.
3️⃣ Unbounded Solution: Feasible region extends infinitely; optimum may not exist.
4️⃣ Infeasible Solution: No common feasible region, hence no solution.
🔵 Question 22:
Explain the Corner Point Method used in solving LPP graphically.
🟢 Answer:
💡 Corner Point Method Steps:
1️⃣ Plot all constraints on coordinate axes.
2️⃣ Shade feasible region.
3️⃣ Identify vertices (corner points).
4️⃣ Evaluate objective function Z = ax + by at each vertex.
5️⃣ Select maximum or minimum value as per question.
✔️ According to Corner Point Theorem, the optimum solution occurs at a vertex.
🔵 Question 23:
Solve graphically:
Maximize Z = 3x + 2y
Subject to:
x + y ≤ 4
x ≥ 0, y ≥ 0
🟢 Answer:
➡️ Step 1: Plot line x + y = 4
Intercepts: (4, 0) and (0, 4)
➡️ Step 2: Feasible region = below the line, first quadrant.
➡️ Step 3: Corner points: (0,0), (4,0), (0,4)
➡️ Step 4: Evaluate Z = 3x + 2y
🔹 Z(0,0) = 0
🔹 Z(4,0) = 12
🔹 Z(0,4) = 8
✅ Maximum Z = 12 at (4, 0)
🔵 Question 24:
Write conditions for existence of optimal solution of an LPP.
🟢 Answer:
Optimal solution exists when:
1️⃣ The feasible region is non-empty.
2️⃣ The feasible region is bounded.
3️⃣ Objective function is continuous and linear.
Then the optimum value occurs at one of the corner points.
🔵 Question 25:
What is the difference between feasible solution and optimal solution?
🟢 Answer:
Feature
Feasible Solution
Optimal Solution
Definition
Satisfies all constraints
Gives best (max/min) Z value
Requirement
Lies in feasible region
Must be a feasible solution
Quantity
Many possible
Usually one or few
✔️ Every optimal solution is feasible, but not every feasible solution is optimal.
🔵 Question 26:
Explain unbounded feasible region and its significance.
🟢 Answer:
➡️ A feasible region that extends infinitely in some direction is called unbounded.
➡️ In such cases, the maximum or minimum value may or may not exist.
✔️ We must test corner points and check direction of increasing Z.
🔵 Question 27:
State any two real-life applications of Linear Programming.
🟢 Answer:
1️⃣ Manufacturing: Maximize profit by allocating limited resources (machines, labor).
2️⃣ Diet Problem: Minimize cost while meeting nutritional requirements.
3️⃣ Transportation: Minimize cost of shipping goods.
4️⃣ Finance: Optimize investment under constraints.
✔️ Linear Programming helps in decision-making for optimization.
🔷 Section C & D – Long Answer / Case-Based Questions (5 marks each)
🔵 Question 28:
Solve graphically the following LPP:
Maximize Z = 5x + 3y
Subject to:
x + y ≤ 6
x + 3y ≤ 9
x ≥ 0, y ≥ 0
🟢 Answer:
➡️ Step 1: Plot constraints
• x + y = 6 → intercepts (6, 0), (0, 6)
• x + 3y = 9 → intercepts (9, 0), (0, 3)
➡️ Step 2: Feasible region
Common region in first quadrant satisfying both inequalities.
Vertices (corner points): (0, 0), (0, 3), (3, 2), (6, 0)
➡️ Step 3: Evaluate Z = 5x + 3y
• Z(0,0) = 0
• Z(0,3) = 9
• Z(3,2) = 5×3 + 3×2 = 15 + 6 = 21
• Z(6,0) = 30
✅ Maximum Z = 30 at (6, 0)
Hence, optimal solution: x = 6, y = 0, Zₘₐₓ = 30.
🔵 Question 29:
Solve graphically the LPP:
Minimize Z = x + 2y
Subject to:
x + y ≥ 4
x + 2y ≥ 5
x, y ≥ 0
🟢 Answer:
➡️ Step 1: Plot constraints
• x + y = 4 → (4,0), (0,4)
• x + 2y = 5 → (5,0), (0,2.5)
➡️ Step 2: Feasible region
Above both lines in first quadrant.
Vertices: Intersection of lines + axis points → (5,0), (0,4), (3,1)
➡️ Step 3: Evaluate Z = x + 2y
• Z(5,0) = 5
• Z(0,4) = 8
• Z(3,1) = 3 + 2 = 5
✅ Minimum Z = 5 at (5,0) and (3,1)
Hence, multiple optimal solutions.
🔵 Question 30:
Define and explain the corner point theorem with justification.
🟢 Answer:
💡 Corner Point Theorem:
If a Linear Programming Problem has an optimal solution (maximum or minimum), it occurs at a vertex (corner point) of the feasible region.
🧠 Justification:
Feasible region = convex polygon formed by linear constraints.
Objective function Z = ax + by represents a family of parallel lines.
As Z shifts parallelly, the extreme value touches boundary at a vertex.
✔️ Hence, only corner points need to be checked to find optimum.
✏️ Note: If two or more vertices yield same Z, there are infinite optimal solutions.
🔵 Question 31:
Formulate the following problem as an LPP:
A company manufactures two products A and B. Each A requires 1 hour on machine I and 2 hours on machine II. Each B requires 2 hours on machine I and 1 hour on machine II. Machine I can work 8 hours, and Machine II can work 6 hours. Profit is ₹30 on each A and ₹20 on each B.
Formulate the LPP to maximize profit.
🟢 Answer:
Let x = number of A units
Let y = number of B units
➡️ Objective Function:
Maximize Z = 30x + 20y
➡️ Constraints:
• Machine I: 1x + 2y ≤ 8
• Machine II: 2x + 1y ≤ 6
• Non-negativity: x ≥ 0, y ≥ 0
✔️ LPP:
Maximize Z = 30x + 20y
Subject to:
x + 2y ≤ 8
2x + y ≤ 6
x ≥ 0, y ≥ 0
🔵 Question 32 (Case-Based):
A dietitian wishes to mix two foods A and B to obtain at least 8 units of protein and 12 units of vitamins. Each kg of food A contains 2 units of protein and 3 units of vitamins, and costs ₹40. Each kg of food B contains 4 units of protein and 2 units of vitamins, and costs ₹60.
Find the least cost mixture satisfying requirements.
🟢 Answer:
Let x = kg of food A, y = kg of food B
➡️ Objective Function:
Minimize Z = 40x + 60y
➡️ Constraints:
• Protein: 2x + 4y ≥ 8
• Vitamins: 3x + 2y ≥ 12
• x ≥ 0, y ≥ 0
Solve graphically:
Vertices found → (0,6), (4,0), (2,3)
Evaluate Z:
• Z(0,6) = 360
• Z(4,0) = 160
• Z(2,3) = 40×2 + 60×3 = 80 + 180 = 260
✅ Minimum Z = 160 at (4, 0)
Hence, least cost ₹160 when x = 4 kg (A), y = 0 kg (B).
🔵 Question 33 (Case-Based):
A factory produces two products P and Q. Each unit of P requires 1 hour of labor and 3 units of material. Each unit of Q requires 2 hours of labor and 2 units of material.
Maximum available: 8 hours labor, 8 units material.
Profit: ₹50 on P, ₹40 on Q.
Find number of units to produce to maximize profit.
🟢 Answer:
Let x = units of P, y = units of Q
➡️ Objective Function:
Maximize Z = 50x + 40y
➡️ Constraints:
• Labor: 1x + 2y ≤ 8
• Material: 3x + 2y ≤ 8
• Non-negativity: x ≥ 0, y ≥ 0
Graphical solution → vertices: (0,0), (0,4), (2,2), (8/3,0)
Evaluate Z:
• (0,0): 0
• (0,4): 160
• (2,2): 50×2 + 40×2 = 100 + 80 = 180
• (8/3,0): 50×8/3 ≈ 133.3
✅ Maximum Z = 180 at (2, 2)
Hence, produce 2 units of P and 2 units of Q, profit ₹180.
————————————————————————————————————————————————————————————————————————————