Chapter Overview
What is Linear Programming?
Linear Programming is a mathematical technique used to obtain the best possible value of a linear objective function subject to a set of linear restrictions or constraints.
The best value may represent maximum profit, maximum production, minimum cost, minimum time, optimum utilization of resources or another measurable quantity.
Linear Programming Workflow
Core Concepts
Basic Terminology
Decision Variables
The unknown quantities whose values have to be determined are called decision variables.
\(y\) = units of Product B
Objective Function
The linear function that is required to be maximized or minimized.
Constraints
Linear inequalities that represent limitations on available resources.
\(a_2x+b_2y\le c_2\)
Feasible Solution
Any point satisfying all constraints, including non-negativity restrictions, is called a feasible solution.
Feasible Region
The common region satisfying all the constraints and non-negativity restrictions.
Optimal Solution
A feasible solution giving the required maximum or minimum value of the objective function.
Optimization
Objective Function
The objective function represents the quantity whose value is to be optimized.
Maximization
Find the largest possible value of \(Z\).
Minimization
Find the smallest possible value of \(Z\).
Restrictions
Constraints and Non-Negativity
Constraints represent the limitations imposed by resources such as raw material, labour, machine hours, capital, storage capacity or production requirements.
\(a_2x+b_2y\le c_2\)
\(a_3x+b_3y\ge c_3\)
\(x\ge0,\quad y\ge0\)
Represents an upper limit.
Represents a lower limit.
\(x,y\) are generally non-negative quantities.
Graphical Interpretation
Linear Inequalities and Half-Planes
A linear inequality such as \(2x+y\le6\) divides the coordinate plane into two half-planes. The boundary line is obtained by replacing the inequality sign with equality.
Boundary Equation
Test Point Method
Choose a convenient point, commonly \((0,0)\), and substitute it into the inequality to identify the required side.
Important Graphing Rule
Boundary line is included.
Boundary line is not included.
Visual Learning
Feasible Region
The feasible region is the common region satisfying all the constraints. Every point inside this region represents a feasible solution.
Draw all boundary lines.
Identify the correct half-plane.
Take the common region.
Problem Solving
Graphical Method
Define Decision Variables
Let \(x\) and \(y\) represent the quantities to be determined.
Write the Objective Function
Write the quantity to be maximized or minimized.
Write the Constraints
Translate the resource limitations into linear inequalities.
Apply Non-Negativity
Draw the Graph
Draw the boundary lines and shade the appropriate half-planes.
Find Corner Points
Identify all vertices of the feasible region.
Evaluate \(Z\)
Substitute each corner point into the objective function and compare the values.
Most Important Method
Corner Point Method
Once the feasible region has been identified, the objective function is evaluated at the corner points of the feasible region.
Key Principle
For a linear programming problem with a non-empty bounded feasible region, an optimum value occurs at a corner point of the feasible region.
| Corner Point | \(x\) | \(y\) | \(Z=ax+by\) |
|---|---|---|---|
| A | \(x_1\) | \(y_1\) | \(Z_1\) |
| B | \(x_2\) | \(y_2\) | \(Z_2\) |
| C | \(x_3\) | \(y_3\) | \(Z_3\) |
| D | \(x_4\) | \(y_4\) | \(Z_4\) |
Important Cases
Special Cases in LPP
Bounded Feasible Region
The feasible region is enclosed and has finite extent.
Unbounded Feasible Region
The feasible region extends indefinitely in one or more directions.
Multiple Optimal Solutions
The same optimum value may occur at more than one feasible point, particularly along an edge of the feasible region.
No Feasible Solution
If the constraints have no common region, the LPP has no feasible solution.
CBSE Preparation
Detailed Solved Examples
Maximization Problem
Solution
- Draw the boundary lines \(x+y=4\), \(x=2\) and \(y=3\).
- Identify the common feasible region in the first quadrant.
- Determine the corner points.
\[ (0,0),\quad (2,0),\quad (2,2),\quad (1,3),\quad (0,3) \]
| Point | \(x\) | \(y\) | \(Z=3x+5y\) |
|---|---|---|---|
| (0,0) | 0 | 0 | 0 |
| (2,0) | 2 | 0 | 6 |
| (2,2) | 2 | 2 | 16 |
| (1,3) | 1 | 3 | 18 |
| (0,3) | 0 | 3 | 15 |
Answer
Maximum value of the objective function is
at \((x,y)=(1,3)\).
Formulation of an LPP
A manufacturer produces two products \(A\) and \(B\). Product \(A\) gives a profit of ₹40 per unit and Product \(B\) gives a profit of ₹30 per unit. The production restrictions are represented by:
\(x+2y\le80\)
\(x\ge0,\quad y\ge0\)
Mathematical Model
The objective function represents total profit, while the inequalities represent limitations on production resources.
Minimization Problem
The boundary equations are drawn first. The appropriate half-planes are then identified using a test point. The corner points of the common feasible region are evaluated in the objective function to obtain the minimum value.
Real-World Connection
Applications of Linear Programming
Production Planning
Determine an efficient combination of products while considering resource limitations.
Profit Maximization
Select production quantities to maximize a specified profit objective.
Cost Minimization
Determine a combination of resources that minimizes a specified cost.
Transportation
Mathematical optimization can help allocate resources among locations subject to constraints.
Agriculture
Land, labour and resource allocation can be represented using mathematical constraints.
Resource Allocation
Limited resources can be allocated among competing activities using an optimization model.
Practice
Practice Questions
subject to \(x+y\le4\), \(x\le2\), \(y\le3\), \(x,y\ge0\).
subject to \(x+y\ge5\), \(2x+y\ge6\), \(x,y\ge0\).
Explain the difference between a feasible solution, feasible region and optimal solution.
Explain the role of non-negativity restrictions in a Linear Programming Problem.
Formulate an LPP representing a production problem involving two products and two limited resources.
Explain graphically how multiple optimal solutions can occur.
Higher Order Thinking Skills
HOTS Questions
HOTS 1
A feasible region is unbounded. Explain why evaluating a few corner points does not automatically establish the existence of a finite maximum or minimum.
HOTS 2
Explain geometrically why an objective function may have the same optimum value at every point of a line segment.
HOTS 3
Can two different sets of constraints produce the same feasible region? Explain with mathematical reasoning.
HOTS 4
Construct an LPP whose feasible region has exactly four corner points. Explain how the optimum would be determined.
Concept Check
Assertion–Reason Questions
Assertion:
Every corner point of a feasible region is a feasible solution.
Reason:
Corner points belong to the feasible region.
Assertion:
The conditions \(x\ge0\) and \(y\ge0\) restrict the solution to the first quadrant.
Reason:
Points in the first quadrant have non-negative coordinates.
Assertion:
A linear programming problem may have multiple optimal solutions.
Reason:
An objective function can remain constant along a line segment forming part of the feasible region.
Last-Minute Revision
Quick Revision Sheet
| Term | Key Point |
|---|---|
| Decision Variables | Unknown quantities to be determined. |
| Objective Function | Linear expression to maximize or minimize. |
| Constraints | Restrictions represented by inequalities. |
| Feasible Solution | Satisfies all constraints. |
| Feasible Region | Common region satisfying all restrictions. |
| Corner Point | Vertex of the feasible region. |
| Optimal Solution | Feasible solution producing the required optimum value. |
Essential Formula
Evaluate \(Z\) at the corner points of the feasible region.
CBSE Examination
Exam Tips
Clearly state what \(x\) and \(y\) represent.
Check whether the problem requires maximum or minimum.
Usually write \(x\ge0,\ y\ge0\).
Label axes, boundary lines and corner points.
Evaluate \(Z\) at every relevant corner point.
Mention both the optimum value and the corresponding values of the variables.
Chapter Checklist
Linear Programming – Exam Ready
Class XII Mathematics • Chapter 12
Linear Programming
Complete notes, graphical illustrations, solved examples, practice questions and examination revision.