Synetic College Logo
Unit 4 of 4 · MBA Sem 3

Unit 4: Network and non-linear models

Operation Research Applications notes · PTU syllabus (MBA 952-18)

3 min read6 topics10 exam questions
On this page
  1. Unit summary
  2. The shortest route problem
  3. The travelling salesman problem
  4. PERT, CPM and network construction
  5. Critical path, slack and float
  6. Crashing a network for cost reduction
  7. Graphical solution of non-linear programming problems
  8. Key terms
  9. Quick revision
  10. Important questions

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
ProcessProject crashing
  1. 1Find the critical path
  2. 2List crash cost per day for critical activities
  3. 3Crash the cheapest activity by one day
  4. 4Recheck for new critical paths
  5. 5Stop when total cost starts rising

    Or the deadline is met

1

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.

ProcessDijkstra's algorithm
  1. 1Label the source 0 and all other nodes infinity
  2. 2Select the unvisited node with the smallest label
  3. 3Update labels of its neighbours

    New label = min(current, node label + arc length)

  4. 4Mark the node permanent
  5. 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.

2

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.
3

Topic 3

PERT, CPM and network construction

ComparisonPERT vs CPM
PERT
CPM

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.
ProcessCritical path computation
  1. 1Forward pass

    Earliest start (ES) and earliest finish (EF)

  2. 2Backward pass

    Latest finish (LF) and latest start (LS)

  3. 3Compute floats
  4. 4Critical activities have zero total float
  5. 5Critical path = longest path = project duration
4

Topic 4

Critical path, slack and float

Key formulasFloat and PERT formulas

  • 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%.

5

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.

Key formulasCrashing

  • Cost slope

    (Crash cost − Normal cost) ÷ (Normal time − Crash time)

ProcessCrashing procedure
  1. 1

    Find the critical path and total cost at normal times

  2. 2

    Choose the critical activity with the lowest cost slope

  3. 3

    Crash it by one unit (or as far as possible without creating a new critical path)

  4. 4

    Recompute paths and total cost (direct + indirect)

  5. 5

    Repeat while total cost falls

  6. 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.

6

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

  1. Q1.What is the shortest route problem?
  2. Q2.How does the TSP differ from the assignment problem?
  3. Q3.Distinguish PERT and CPM.
  4. Q4.What is total float?
  5. Q5.What is the cost slope in crashing?
  6. Q6.Why may the NLP optimum not lie at a corner point?

Long-answer questions

  1. Q1.Solve a shortest route problem using Dijkstra's algorithm (numerical).
  2. Q2.Explain the travelling salesman problem and its solution.
  3. Q3.Draw a project network, find the critical path and compute floats (numerical).
  4. 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.

WhatsApp us