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
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
The optimum lies at a corner point of the feasible region; compare Z at (0,0)=0, (50,0)=150, (50,30)=210, (20,60)=180, (0,60)=120
- 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
The simplex method moves from one corner (basic feasible) solution to a better adjacent one until no further improvement is possible. The Big-M method handles ≥ and = constraints by adding artificial variables with a very large penalty M in the objective function.
- 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.
Example
Choosing the pivot: in a maximisation tableau, the variable with the largest positive Cj − Zj enters. The leaving variable is the one with the smallest non-negative ratio of the solution value to the pivot-column value — this keeps the solution feasible.
Exam tip
Write the steps: standard form → initial tableau → entering variable → leaving variable → pivot → repeat until optimal.
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.
Example
A minimisation problem: a feed company mixes two ingredients to meet minimum protein and fibre requirements at the lowest cost. Each ≥ constraint needs a surplus and an artificial variable, and the optimum is reached when all Cj − Zj ≥ 0.
Exam tip
A minimisation problem can also be solved by maximising the negative of the objective function.
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.
Example
Why two phases: in Phase I, the method minimises the sum of artificial variables. If this minimum is zero, a feasible solution exists and Phase II optimises the original objective from there. If it is above zero, the problem has no feasible solution.
Exam tip
The two-phase method avoids rounding errors from using a very large M in computers.
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.
