AL6, AN13 - Network problems as linear programs | OCR A-Level Further Mathematics B (MEI)

Express paths, flows, project durations, matchings, allocations and transportation as linear models suitable for a computer. The network picture remains useful, but the decision variables and constraints tell the software what its arrows mean.

Shortest paths as binary decisions

The same three arrows can describe a journey, a pipe system or a project. Why cannot one optimisation model solve all three just by changing the numbers?

Their decisions differ. A path selects arcs, a flow sends quantities, and a schedule assigns times. The objective and constraints must describe the intended problem.

You already know

Use Dijkstra's algorithm for suitable shortest-path problems, conservation and capacities for flows, and a directed activity network for critical paths. An LP needs a numerical objective, all constraints and the correct variable domains.

For each model below, a symbol such as $SA$ denotes one numerical arc variable, not a product of two numbers or the arc's fixed length.

Binary arc selection

For a path, set each arc variable to $1$ if the arc is selected and $0$ otherwise. Send one unit out of the start, conserve that unit at intermediate vertices, and receive one unit at the finish.

We use a directed acyclic network, so those balance equations cannot add a disconnected directed cycle. Positive costs also discourage cycles in a shortest-path objective, but they must not be relied on to repair every possible network model.

[DIAGRAM: asset_name: The same arrows can represent different network problems; asset_slug: network_lp_roles; caption: Arc lengths, capacities and activity durations lead to different variables and objectives; description: Three separate triangular directed networks each have S at the left, A above the centre and T at the right, with arcs S to A, A to T and S to T. The shortest-path panel labels the arcs 2, 3 and 7 as costs. The flow panel labels the arcs 4, 3 and 2 as capacities. The project panel labels the arcs 2, 3 and 4 as durations. Each panel explicitly labels what its numbers represent, and no arrows are drawn in reverse.]
Arc lengths, capacities and activity durations lead to different variables and objectives

Worked example 1: selecting a shortest route

Question. The arcs $S\to A$ , $A\to T$ , $S\to T$ have lengths $2,3,7$ . Formulate a shortest-path model.

Plan. Use binary selections, enforce a single start-to-finish path and minimise total selected length.

\begin{aligned} \text{Minimise }L&=2SA+3AT+7ST&&\text{total path length}\\ SA+ST&=1&&\text{one unit leaves }S\\ SA-AT&=0&&\text{balance at }A\\ AT+ST&=1&&\text{one unit reaches }T \end{aligned}

Require $SA,AT,ST\in\{0,1\}$ .

Why this step? Capacities such as $SA\le2$ would confuse a length with an upper bound on a quantity.

Answer. The displayed binary linear model selects a shortest path.

Check. $SA=AT=1,ST=0$ gives length $5$ ; the direct path gives length $7$ . The model prefers $S\to A\to T$ .

Change only the direct arc's length.

Worked example 2: a cheaper direct arc

Question. Replace the length of $S\to T$ by $4$ . Formulate the revised model and identify its preferred route.

Plan. Change the objective coefficient, retaining the selection and balance constraints.

\begin{aligned} \text{Minimise }L&=2SA+3AT+4ST&&\text{new direct length}\\ SA+ST&=1,\quad SA=AT&&\text{same route structure}\\ AT+ST&=1&&\text{same destination} \end{aligned}

All three variables remain binary.

Why this step? Changing an arc's length changes its cost, not whether flow is conserved at a vertex.

Answer. Choose $ST=1$ , $SA=AT=0$ ; the shortest route is now the direct arc, of length $4$ .

Check. The alternative route still has length $2+3=5$ .

The balance equalities include a redundant equation in this tiny network. Keeping it makes the start and finish meanings explicit; it does not change the feasible paths.

Watch out

Wrong: say only that all variables are non-negative. Right: for this selected-path formulation, state their binary domains as well.

Change the direct length again.

Maximum flow with capacities

For a pipe network, the arc variables now represent amounts per unit time. They are not yes/no decisions and their coefficients are not travel costs.

Flow formulation

For each directed arc, use a non-negative flow variable bounded above by its capacity. At every intermediate vertex, inflow equals outflow. Maximise the total flow out of the source, or equivalently into the sink.

All relationships in these network formulations come from the model; no network-LP formulae are supplied in the formula booklet.

Worked example 3: a bottleneck on the indirect route

Question. The network $S\to A$ , $A\to T$ , $S\to T$ has capacities $4,3,2$ units per minute. Formulate a maximum-flow LP.

Plan. Define continuous arc flows, conserve flow at $A$ , impose capacity bounds and maximise source outflow.

\begin{aligned} \text{Maximise }F&=SA+ST&&\text{source outflow}\\ SA&=AT&&\text{conservation at }A\\ 0\le SA&\le4&&\text{first capacity}\\ 0\le AT&\le3&&\text{second capacity}\\ 0\le ST&\le2&&\text{direct capacity} \end{aligned}

Why this step? Flow on the indirect route is limited by its smaller capacity, not by adding the two capacities.

Answer. The displayed continuous LP models maximum flow.

Check. $SA=AT=3,ST=2$ is feasible and gives $F=5$ , matching total capacity $3+2$ entering $T$ .

Change only the capacity of $A\to T$ .

Worked example 4: the bottleneck moves

Question. Increase the capacity of $A\to T$ to $6$ , leaving $SA\le4$ , $ST\le2$ . State the revised model and its maximum flow.

Plan. Change the single capacity bound and check what now limits the indirect route.

\begin{aligned} \text{Maximise }F&=SA+ST&&\text{unchanged objective}\\ SA&=AT&&\text{unchanged conservation}\\ 0\le SA&\le4,\quad 0\le AT\le6&&\text{revised bounds}\\ 0\le ST&\le2&&\text{direct capacity} \end{aligned}

Why this step? Increasing one pipe's capacity need not increase the route's capacity by the same amount: another pipe may become limiting.

Answer. $SA=AT=4,ST=2$ gives maximum flow $6$ units per minute.

Check. The source cut has capacity $4+2=6$ , proving that this feasible flow is maximal.

In a more complicated graph, write a separate conservation equation at each intermediate vertex. Follow each arrow's direction, especially after an arc is reversed.

Watch out

Wrong: impose equality between an arc's flow and capacity. Right: $0\le f\le c$ ; unused capacity is allowed, while conservation applies at vertices.

Use fresh capacity values.

Critical paths and event times

A project's completion time is governed by the longest required chain of activities in its acyclic precedence network. Activities on different branches can overlap.

There are two useful formulations: maximise the duration of a selected start-to-finish path, or minimise the finish event time subject to every precedence lower bound.

Worked example 5: selecting a longest activity path

Question. A directed acyclic project network has activities $S\to A$ , $A\to T$ , $S\to T$ of durations $2,3,4$ days. Formulate a longest-path model for its critical duration.

Plan. Use the path-selection balances, but maximise the sum of selected durations.

\begin{aligned} \text{Maximise }D&=2SA+3AT+4ST&&\text{duration of selected chain}\\ SA+ST&=1,\quad SA=AT&&\text{one path through the network}\\ AT+ST&=1&&\text{finish balance}\\ SA,\ AT,\ ST&\in\{0,1\}&&\text{activity selection} \end{aligned}

Why this step? The longest chain constrains the whole project's earliest finish. Minimising a selected path would ignore a slower necessary branch.

Answer. The critical path is $S\to A\to T$ , of duration $5$ days.

Check. Its $2+3=5$ days exceed the direct activity's $4$ days.

Change only the representation: use event times for this same project.

Worked example 6: minimising the earliest finish

Question. Formulate the same critical-duration problem using event times $t_S,t_A,t_T$ , rather than path selections.

Plan. Fix the start time and require each finishing event to occur after its incoming activity has had time to finish.

\begin{aligned} \text{Minimise }t_T&&&\text{earliest project finish}\\ t_S&=0&&\text{chosen time origin}\\ t_A-t_S&\ge2&&\text{activity }S\to A\\ t_T-t_A&\ge3&&\text{activity }A\to T\\ t_T-t_S&\ge4&&\text{direct activity} \end{aligned}

The event times are non-negative continuous variables, measured in days.

Why this step? These are lower bounds on event times, so minimisation finds the earliest schedule that respects every activity.

Answer. The minimum finish time is $t_T=5$ , achieved with $t_A=2$ .

Check. The inequalities imply $t_T\ge t_A+3\ge5$ ; $(t_S,t_A,t_T)=(0,2,5)$ meets them all.

This is a useful reversal: a longest-path duration can be obtained by minimising a feasible finish time. The variables and constraints explain why the two objectives represent the same project quantity.

Watch out

Wrong: apply a binary longest-path model to an arbitrary cyclic graph and assume the balances select only a simple path. Right: critical-path networks are acyclic; added cycles can invalidate that interpretation.

Change one activity's duration.

Matching as a maximum number of links

A matching selects compatible pairs while using each member of either set at most once. Its aim here is to match as many pairs as possible.

Matching variables

For an allowed pairing such as applicant $A$ with task $1$ , let $A1=1$ if that pair is selected and $0$ otherwise. A member's incident selected variables sum to at most $1$ . Disallowed pairs have no variable, or are fixed at zero.

Unlike a flow amount, each selected variable counts one whole link.

Worked example 7: a small compatibility network

Question. The allowed applicant-task pairings are $A1,A2,B1$ . Formulate a model for a matching with the greatest possible number of pairs.

Plan. Maximise the number of selected links and restrict each applicant and task to at most one.

\begin{aligned} \text{Maximise }M&=A1+A2+B1&&\text{number of matched pairs}\\ A1+A2&\le1,\quad B1\le1&&\text{applicants}\\ A1+B1&\le1,\quad A2\le1&&\text{tasks}\\ A1,\ A2,\ B1&\in\{0,1\}&&\text{yes/no pairings} \end{aligned}

Why this step? Applicant $A$ cannot take both tasks, and task $1$ cannot be assigned to both applicants.

Answer. The displayed binary model gives a largest matching.

Check. $A2=B1=1,A1=0$ matches both applicants, giving $M=2$ .

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AL6, AN13 - Network problems as linear programs

Shortest paths as binary decisions

Maximum flow with capacities

Critical paths and event times

Matching as a maximum number of links

Continue this lesson.

Learn faster with Nova