Unit 2: Linear programming applications
Operation Research Applications notes · PTU syllabus (MBA 952-18)
On this page
Unit summary
Linear programming allocates scarce resources to competing uses in the best way. This unit covers the formulation of linear models, graphical and simplex solutions, the simplex algorithm and tableau, maximisation vs minimisation, the Big-M and two-phase methods, duality theory and sensitivity analysis.
After this unit you can
- Formulate linear programming models
- Solve LP problems graphically and by the simplex method
- Apply the Big-M and two-phase methods
- Explain duality and sensitivity analysis
PTU syllabus topics
- Formulation of linear mathematical models
- graphical and simplex techniques
- simplex algorithm and tableau construction
- minimization vs maximization
- Big-M and two-phase methods
- duality theory and sensitivity analysis
Objective
Maximise
Minimise (and vice versa)
Constraints
m constraints
m dual variables
Variables
n variables
n dual constraints
Optimal value
Max Z
Min W: equal at the optimum (Z* = W*)
Topic 1
Formulation of linear programming models
Linear programming (LP) optimises (maximises or minimises) a linear objective function subject to linear constraints. Characteristics: objective function, decision variables, constraints, non-negativity, linearity, divisibility and certainty.
Example
A firm makes chairs (x) and tables (y): profit ₹40 and ₹60. Wood: 2x + 3y ≤ 120; labour: 2x + y ≤ 60. Maximise Z = 40x + 60y, with x, y ≥ 0.
Topic 2
Graphical method
- 1Plot each constraint as a line
- 2Shade the feasible region
- 3Find the corner points
- 4Evaluate Z at each corner
- 5Choose the best value
Example
For the example, corners are (0,0), (30,0), (0,40) and (15,30). Z = 0, 1,200, 2,400 and 2,400. Both (0,40) and (15,30) give Z = 2,400 — multiple optimal solutions.
Topic 3
The simplex algorithm, tableau and Big-M method
- Convert inequalities to equations: add slack (≤), subtract surplus and add artificial variables (≥ or =).
- 1
Standard form with slack/surplus/artificial variables
- 2
Initial basic feasible solution table
- 3
Compute Cj − Zj (net evaluation)
- 4
Entering variable
Most positive Cj − Zj (maximisation)
- 5
Leaving variable
Minimum ratio (b ÷ key column, positive only)
- 6
Pivot and update the table
- 7
Repeat until all Cj − Zj ≤ 0 (maximisation)
- Big-M method: artificial variables are given a very large penalty −M in a maximisation objective (+M for minimisation) so they leave the basis; if an artificial variable remains positive in the final table, the problem is infeasible.
- Two-phase method: alternative to Big-M — first minimise the sum of artificial variables.
- Duality: every LP (primal) has a dual; optimal values are equal; dual values give shadow prices of resources.
Topic 4
Maximisation vs minimisation problems
- Maximisation: the variable with the largest positive Cj − Zj enters the basis; the solution is optimal when every Cj − Zj is zero or negative. Artificial variables carry a cost of −M.
- Minimisation: the variable with the most negative Cj − Zj enters; optimal when every Cj − Zj is zero or positive. Artificial variables carry a cost of +M. Alternatively, minimise Z by maximising −Z.
- Constraint types: ≤ needs a slack variable; ≥ needs a surplus and an artificial variable; = needs an artificial variable.
Topic 5
The two-phase method
An alternative to Big-M that avoids choosing a large M.
- 1Phase I
Minimise the sum of artificial variables subject to the constraints
- 2Check
If the minimum is zero, a feasible solution exists; if positive, the problem is infeasible
- 3Phase II
Drop artificial variables, restore the original objective and continue simplex to optimality
- Advantage: avoids rounding errors from very large M values in computer solutions.
Topic 6
Duality theory and sensitivity analysis
- Degeneracy: a basic variable takes the value zero — ties in the minimum ratio; may cause cycling (resolved by perturbation or Bland's rule).
- Duality: every primal LP has a dual; if the primal maximises with ≤ constraints, the dual minimises with ≥ constraints; the objective values are equal at the optimum; dual variables = shadow prices (value of one more unit of a resource).
Variables
n decision variables
m dual variables (one per constraint)
Constraints
m constraints (≤)
n constraints (≥)
Objective coefficients
Become right-hand sides of the dual
Right-hand sides of the primal
Optimum
Max Z
Min W = Max Z
- Post-optimality (sensitivity) analysis: how the optimal solution changes with changes in objective coefficients, right-hand-side values (resources) or constraint coefficients — ranges of optimality and feasibility.
Example
If the shadow price of machine hours is ₹30, buying an extra hour for less than ₹30 increases profit — useful for capacity decisions.
Key terms
- Feasible region
- Set of points satisfying all constraints
- Slack variable
- Unused resource in a ≤ constraint
- Artificial variable
- Temporary variable to start the simplex with ≥ or = constraints
- Two-phase method
- Simplex variant that first finds a feasible solution
- Shadow price
- Change in the objective per unit increase in a resource
Quick revision
- Formulation: decision variables, objective, constraints, non-negativity.
- Graphical method: corner points; special cases.
- Simplex: tableau, entering and leaving variables, optimality test.
- Big-M and two-phase methods for ≥ and = constraints.
- Duality: primal–dual relations; shadow prices; sensitivity analysis.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State the components of an LP model.
- Q2.What is a slack variable?
- Q3.When is an artificial variable used?
- Q4.State the purpose of Phase I in the two-phase method.
- Q5.What is a shadow price?
- Q6.What is sensitivity analysis?
Long-answer questions
- Q1.Formulate and solve an LP problem graphically (numerical).
- Q2.Solve an LP problem by the simplex method (numerical).
- Q3.Explain the Big-M and two-phase methods with an example.
- Q4.Explain duality theory and sensitivity analysis in linear programming.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research Applications, or to ask about studying MBA at Synetic.