Unit 18
Computational Method
Class 12 Mathematics
Linear Programming Problems
Class 12 Mathematics – Linear Programming Problems Notes PDF
On mobile, swipe inside the PDF to read all pages and pinch to zoom.
Contents / Quick Navigation
NEB / CDC Focus
The Grade 12 computational-method outcome is to solve linear programming problems of two variables by the simplex method. The formulation, standard form, slack variables, feasible/basic solutions and tableau steps below are included because they are necessary to execute the simplex method correctly.
1. Linear Programming Problem (LPP)
Linear programming optimizes a linear objective function subject to linear equality/inequality constraints and non-negativity restrictions.
A typical problem asks to maximize profit or minimize cost, time, material use, or another linear quantity.
2. Formulating a Linear Programming Problem
- Define the decision variables.
- Translate the goal into a linear objective function.
- Translate resource/requirement statements into linear constraints.
- Add non-negativity restrictions.
A workshop makes products A and B. Each A gives profit 3 units and each B gives profit 5 units. Resource limits are:
x+2y≤8, 3x+2y≤12, x,y≥0.
Objective:
Maximize Z=3x+5y.
Every coefficient in a resource constraint should represent resource used per unit of the corresponding decision variable. Mixing units is a common modeling error.
3. Key Terms
| Term | Meaning |
|---|---|
| Feasible solution | Satisfies every constraint including non-negativity. |
| Feasible region | Set of all feasible solutions. |
| Optimal solution | A feasible solution giving the best objective value. |
| Basic solution | A solution associated with selecting basic variables. |
| Basic feasible solution | A basic solution that is also feasible. |
| Slack variable | Non-negative variable added to a ≤ constraint to convert it to equality. |
4. Standard Form and Slack Variables
For simplex calculations, inequalities are converted to equations. For a maximization problem with ≤ constraints:
The slack variables measure unused resources.
x+2y≤8 becomes x+2y+s₁=8.
3x+2y≤12 becomes 3x+2y+s₂=12.
5. Basic Idea of the Simplex Method
The simplex method starts from a basic feasible solution and systematically changes the basis to improve the objective value until no further improvement is possible under the chosen optimality convention.
- Convert the LPP to standard form.
- Construct the initial simplex tableau.
- Identify the entering variable (pivot column).
- Use the minimum positive ratio test to identify the leaving variable (pivot row).
- Pivot so the pivot element becomes 1 and other entries in its column become 0.
- Repeat until the optimality condition is met.
- Read the basic variables and objective value.
6. Simplex Tableau
One common classroom tableau for a maximization problem lists the basic variable, coefficients of decision/slack variables, right-hand-side values, and the objective-row information.
| Basis | x | y | s₁ | s₂ | RHS |
|---|---|---|---|---|---|
| s₁ | 1 | 2 | 1 | 0 | 8 |
| s₂ | 3 | 2 | 0 | 1 | 12 |
| Z row / reduced-cost row | written according to the sign convention used by your textbook | ||||
Different textbooks write the objective row as Z−3x−5y=0, Cj−Zj, or Zj−Cj. The entering-variable sign rule changes with the convention. Use one convention consistently throughout a problem.
7. Pivot Column, Pivot Row and Row Operations
7.1 Entering Variable
For a maximization tableau, choose the variable that most improves the objective according to the tableau’s reduced-cost convention.
7.2 Leaving Variable
For positive entries in the pivot column, compute
The smallest non-negative/positive admissible ratio selects the pivot row.
7.3 Pivot Operation
Scale the pivot row to make the pivot element 1, then eliminate the other entries in the pivot column using elementary row operations.
8. Worked Simplex Example
Maximize Z=3x+5y
subject to
x+2y≤8,
3x+2y≤12,
x,y≥0.
Add slack variables:
x+2y+s₁=8,
3x+2y+s₂=12.
Initial basic solution is x=y=0, s₁=8, s₂=12, giving Z=0.
Using the usual maximization logic, y is a natural first entering variable because its objective coefficient 5 exceeds 3. Ratio test:
8/2=4, 12/2=6.
So the first row leaves and the pivot element is 2. After pivoting, continue until no improving reduced cost remains. The optimal corner for this model is
Check constraints:
2+2(3)=8, 3(2)+2(3)=12.
9. Special Situations to Recognize
| Situation | Signal / interpretation |
|---|---|
| Unbounded solution | Objective can improve without a finite bound; a valid leaving row may be unavailable for an improving entering column. |
| Multiple optimum | At optimum, a non-basic variable can have zero reduced cost under the relevant convention. |
| Degeneracy | A basic variable may be zero; ratio tests can tie. |
| Infeasibility | No point satisfies all constraints. More advanced simplex variants handle problems lacking an obvious initial basic feasible solution. |
At Grade 12 level, focus first on correctly solving the standard two-variable cases presented in the prescribed exercises.
10. Real-Life Applications
- Production planning under labor and material limits.
- Allocation of land, feed, transport capacity or machine time.
- Profit maximization and cost minimization.
- Blending and resource-allocation problems.
The simplex method solves the mathematical model. A good solution still depends on defining meaningful decision variables, objective coefficients and realistic linear constraints.
11. Common Mistakes
Do not maximize a quantity the problem asks you to minimize, or vice versa.
Write x,y≥0 when quantities cannot be negative.
For a ≤ constraint, add a non-negative slack variable.
The ordinary minimum-ratio test uses admissible positive pivot-column entries.
Update the entire row, including RHS and all variable columns.
Keep one reduced-cost sign convention from start to finish.
12. Formula / Procedure Sheet
13. Important Exam Questions
Short
- Define LPP, objective function, constraint and feasible solution.
- Define slack variable and basic feasible solution.
- Explain pivot column, pivot row and pivot element.
- State the role of the minimum-ratio test.
Long / Numerical
- Formulate a two-variable real-life LPP.
- Convert an LPP to standard form using slack variables.
- Construct the initial simplex tableau.
- Solve a maximization LPP by simplex method.
- Interpret the final values of decision and slack variables.
14. One-Minute Revision
- LPP optimizes a linear objective under linear constraints.
- Decision variables must be clearly defined.
- Include non-negativity restrictions.
- For ≤ constraints, add slack variables.
- The initial slack-variable basis often gives a basic feasible solution.
- Choose an entering variable using the objective-row convention.
- Choose the leaving row by the minimum positive ratio test.
- Pivot to create a unit column for the entering basic variable.
- Repeat until the tableau satisfies optimality conditions.
- Always verify the final solution satisfies all original constraints.
15. Diagram Practice
- LPP structure diagram.
- Feasible region sketch.
- Slack-variable conversion diagram.
- Simplex iteration cycle.
- Pivot-column and pivot-row diagram.
- Geometric check of an optimum.
Also Visit
Original Nepal eNotes page: Linear Programming Problems Notes.
Discussion
Share a helpful question, idea, or explanation with other students.