Unit 4: Network and non-linear models
Operation Research Applications notes · PTU syllabus (MBA 952-18)
On this page
Unit summary
Networks model routes and projects, and some business relationships are non-linear. This unit covers the shortest route and travelling salesman problems, PERT and CPM — network construction, critical path, slack and float, crashing for cost reduction — and graphical illustration of non-linear programming problems.
After this unit you can
- Solve shortest route and travelling salesman problems
- Construct project networks and identify the critical path
- Compute slack and float and crash a project
- Solve simple non-linear programming problems graphically
PTU syllabus topics
- Shortest route and traveling salesman problems
- PERT and CPM
- network construction
- critical path identification
- slack and float
- crashing for cost reduction
- graphical illustration of non-linear programming problems
Topic 1
The shortest route problem
Find the shortest path from a source node to a destination node in a network — delivery routes, network cabling, project paths.
- 1Label the source 0 and all other nodes infinity
- 2Select the unvisited node with the smallest label
- 3Update labels of its neighbours
New label = min(current, node label + arc length)
- 4Mark the node permanent
- 5Repeat until the destination is permanent; trace back the path
Example
From A: A–B 4, A–C 2, C–B 1, B–D 5, C–D 8. Labels: C = 2, B = min(4, 2 + 1) = 3, D = min(3 + 5, 2 + 8) = 8. Shortest route A–C–B–D = 8.
Topic 2
The travelling salesman problem
- TSP: find the shortest tour that visits each city exactly once and returns to the start.
- Formulation: like an assignment problem with the extra condition that no sub-tours are allowed; cost of going from a city to itself is infinite.
- Solution approaches: Hungarian method with sub-tour checks (small problems), branch and bound, nearest-neighbour heuristic, metaheuristics for large problems.
- Applications: delivery routing, sales visits, machine sequencing to minimise set-up times, PCB drilling.
Example
A delivery route: a courier must visit four shops and return to the depot. With 4 shops there are (4 − 1)! = 6 possible tours (3 when direction is ignored). OR methods compare the total distances and choose the shortest. With 20 shops the number of tours explodes, so heuristics are used.
Exam tip
The TSP can be solved like an assignment problem with the extra condition that the route forms one complete tour.
Topic 3
PERT, CPM and network construction
Both PERT and CPM represent a project as a network of activities and events, and identify the critical path — the longest path, which determines the minimum project duration. PERT uses three time estimates; CPM uses one.
Origin
US Navy Polaris project (1958)
DuPont and Remington Rand (1957)
Activity times
Probabilistic — three estimates
Deterministic — one estimate
Orientation
Event-oriented
Activity-oriented
Used for
R&D, new projects with uncertainty
Construction, repetitive projects
Cost
Time-focused
Time–cost trade-off (crashing)
Construction of networks
- Activity (arrow), event (node), dummy activity (dashed — shows dependency without time).
- Rules: each activity has one arrow; no loops; no dangling events; only one start and one end node; dummies to avoid two activities with the same start and end nodes.
- 1Forward pass
Earliest start (ES) and earliest finish (EF)
- 2Backward pass
Latest finish (LF) and latest start (LS)
- 3Compute floats
- 4Critical activities have zero total float
- 5Critical path = longest path = project duration
Example
PERT expected time: an activity has optimistic time 4 days, most likely 6 days and pessimistic time 14 days. Expected time = (4 + 4 × 6 + 14) ÷ 6 = 42 ÷ 6 = 7 days.
Exam tip
Remember te = (a + 4m + b) ÷ 6. Activities on the critical path have zero slack.
Topic 4
Critical path, slack and float
Critical path A–C–E = 10 days; path B–D–E = 8 days, so B–D has 2 days of float
Total float
LS − ES (or LF − EF)
Free float
ES of successor − EF of the activity
Independent float
ES of successor − LF of predecessor − duration
Event slack
Latest event time − Earliest event time
PERT expected time
te = (to + 4tm + tp) ÷ 6
Activity variance
σ² = [(tp − to) ÷ 6]²
Probability of completion
Z = (Scheduled time − Expected project time) ÷ √(Sum of critical variances)
Example
Activity estimates: optimistic 4, most likely 7, pessimistic 16 days → te = (4 + 28 + 16) ÷ 6 = 8 days; σ² = (12 ÷ 6)² = 4. If the critical path expected time is 40 days with total variance 16 (σ = 4), the probability of finishing in 44 days: Z = (44 − 40) ÷ 4 = 1 → about 84%.
Topic 5
Crashing a network for cost reduction
Crashing shortens project duration by adding resources to critical activities at extra (direct) cost, while indirect costs (overheads, penalties) fall.
Cost slope
(Crash cost − Normal cost) ÷ (Normal time − Crash time)
- 1
Find the critical path and total cost at normal times
- 2
Choose the critical activity with the lowest cost slope
- 3
Crash it by one unit (or as far as possible without creating a new critical path)
- 4
Recompute paths and total cost (direct + indirect)
- 5
Repeat while total cost falls
- 6
Optimal duration = minimum total cost
Example
Activity normal 8 days ₹6,000; crash 5 days ₹9,000 → cost slope = 3,000 ÷ 3 = ₹1,000 per day. If indirect cost is ₹1,500 per day, crashing this activity saves ₹500 per day.
Topic 6
Graphical solution of non-linear programming problems
- Non-linear programming (NLP): the objective function or some constraints are non-linear — e.g., profit with volume discounts, revenue = price × quantity where price falls with quantity.
- Graphical method (two variables): plot the constraints to get the feasible region; draw iso-profit or iso-cost curves (circles, parabolas) of the objective; the optimum is where a curve is tangent to the feasible region — it may lie on the boundary but not necessarily at a corner point, or in the interior.
Example
Minimise Z = (x − 4)² + (y − 3)² subject to x + y ≤ 5. The unconstrained optimum (4, 3) is infeasible; the closest feasible point lies on x + y = 5 at (3, 2), giving Z = 2.
- Kuhn–Tucker conditions give necessary conditions for optimality with inequality constraints (for larger problems).
Key terms
- Shortest route problem
- Finding the minimum-distance path in a network
- Travelling salesman problem
- Shortest tour visiting each city once
- Critical path
- Longest path determining project duration
- Crashing
- Shortening activities at extra cost
- Non-linear programming
- Optimisation with non-linear objective or constraints
Quick revision
- Dijkstra's labelling algorithm for shortest routes.
- TSP: assignment structure with no sub-tours; heuristics.
- PERT (three time estimates) and CPM (one estimate); network rules.
- EST, EFT, LST, LFT; total, free and independent float; critical path.
- Crashing: cost slope; NLP graphical — optimum at tangency, not necessarily a corner.
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.What is the shortest route problem?
- Q2.How does the TSP differ from the assignment problem?
- Q3.Distinguish PERT and CPM.
- Q4.What is total float?
- Q5.What is the cost slope in crashing?
- Q6.Why may the NLP optimum not lie at a corner point?
Long-answer questions
- Q1.Solve a shortest route problem using Dijkstra's algorithm (numerical).
- Q2.Explain the travelling salesman problem and its solution.
- Q3.Draw a project network, find the critical path and compute floats (numerical).
- Q4.Explain crashing and the graphical solution of non-linear programming problems.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research Applications, or to ask about studying MBA at Synetic.
