Network, Flow, and Constraint Systems

The Central Idea

A network consists of connected locations, often called nodes, joined by routes or links.

A variable may represent the amount of flow along each route.

At an ordinary intermediate node, conservation gives

Additional inequalities may restrict each flow:

Nodes and Links

A node is a location where flow may enter, leave, split, or combine.

A link connects two nodes and carries some flow.

In algebraic models, each link can be assigned a variable such as

The diagram becomes a system of equations once the node balances are written.

Flow Direction

A link should be given a stated direction before its variable is used.

For example,

may represent flow from node \(A\) to node \(B\).

Clear direction prevents sign and bookkeeping errors.

Conservation at an Intermediate Node

Suppose \(x_1\) and \(x_2\) enter a node, while \(x_3\) and \(x_4\) leave.

Conservation gives

Example: One Unknown Outflow

A junction receives flows of \(40\) and \(25\) units per minute. One outgoing route carries \(30\) units per minute. Find the other outgoing flow \(x\).

Therefore,

Sources

A source introduces flow into the modeled network.

If a source supplies \(S\) units and sends them along routes \(x_1\) and \(x_2\), then

Sinks

A sink receives or removes flow from the network.

If routes \(x_1\) and \(x_2\) feed a sink that receives total amount \(D\), then

Example: Source Split

A source provides \(100\) units per hour.

One route carries \(x\) units and another carries \(y\).

Then

If

then

Flow Can Split

If flow \(x\) enters a node and leaves along routes \(y\) and \(z\), then

A split does not create or destroy flow.

Flow Can Merge

If routes \(x\) and \(y\) merge into one outgoing route \(z\), then

A Small Network System

Suppose source flow \(120\) splits into \(x\) and \(y\):

Later, route \(x\) contributes \(20\) units to another branch and sends the remainder \(z\) forward:

If \(y\) and \(z\) merge at the sink,

The network is described by a system of linear equations.

Redundant Balance Equations

In a fully connected conservation system, not every node equation is always algebraically independent.

One balance may follow from the others together with total source and sink information.

A redundant equation is not wrong; it simply does not add new information.

Underdetermined Networks

A network may have more unknown flows than independent equations.

Then there may be infinitely many feasible flow assignments.

One or more variables can be treated as parameters.

Example: A Parameterized Flow Family

Suppose

Let

Then

Therefore, the solution family is

Nonnegative Flow

If \(x\) and \(y\) represent ordinary directed flows, they are usually required to satisfy

For

nonnegativity implies

Capacity Constraints

A route may have a maximum capacity \(C\).

If route flow is \(x\), then

Capacity turns a conservation problem into a system containing both equations and inequalities.

Example: Apply a Capacity

Suppose

and route \(x\) can carry at most \(60\) units.

Then

Since

at least

units must travel through route \(y\).

Lower-Bound Constraints

A route may also require a minimum flow.

If at least \(L\) units must travel through route \(x\), then

Combined Bounds

A route with minimum \(20\) and capacity \(75\) satisfies

Feasible Solutions

A feasible solution satisfies every equation and every inequality in the model.

Solving one equation correctly is not enough if the result violates a capacity, nonnegativity condition, or another required constraint.

Example: Test Feasibility

Suppose

and

Test

The total is

and both capacity constraints are satisfied.

Therefore,

Example: An Infeasible Assignment

Using the same system, test

Although

the capacity

is violated.

Therefore,

Resource Constraints

Not every constraint system describes literal movement through pipes or roads.

Production problems often use the same mathematics.

If product A uses \(a_1\) units of a resource and product B uses \(a_2\) units, while at most \(R\) units are available, then

Example: Material Constraint

Product A uses \(3\) kg of material and product B uses \(5\) kg. At most \(120\) kg are available.

If \(x\) and \(y\) are production quantities, then

Labor Constraint

Suppose product A requires \(2\) labor hours and product B requires \(4\) hours, with at most \(80\) labor hours available.

Then

Nonnegativity in Production Models

Production quantities usually satisfy

If only whole products can be made, integer restrictions may also apply.

A Basic Constraint System

Combining the material and labor examples gives

Every feasible production plan must satisfy all four conditions.

Boundary Lines

To understand an inequality such as

first study the boundary equation

The inequality selects one side of that line.

Intercepts of a Constraint Boundary

For

set \(y=0\):

Set \(x=0\):

Thus the boundary passes through

Feasible Region

The feasible region is the set of all points satisfying every constraint simultaneously.

For two variables, it can be visualized as the overlap of several half-planes.

Algebraically, it is the common solution set of the inequality system.

Test a Production Plan

Using

and

test

Material:

Labor:

Therefore,

Another Production Plan

Test

Material:

Since

the material constraint is violated.

Therefore,

Equality versus Inequality Constraints

An equality such as

requires an exact balance.

An inequality such as

imposes a maximum.

An inequality such as

imposes a minimum.

Capacity at a Node

A node itself may have a processing limit.

If total flow through a node cannot exceed \(C\), then

Example: Processing Capacity

A station receives flows \(x\) and \(y\), but can process at most \(150\) units per hour.

Then

Demand Constraints

A destination may require at least a specified amount.

If routes \(x\) and \(y\) deliver to a destination requiring at least \(90\) units, then

Exact Demand

If the destination must receive exactly \(90\) units, then the constraint becomes

Balance with Storage

Conservation can be extended when some flow is stored.

A useful balance form is

Ordinary flow conservation is the special case where storage does not change.

Example: Inventory Accumulation

A warehouse receives \(120\) units per day and ships \(95\) units per day.

Net inventory change is

Therefore, inventory increases by

Balance with Loss

If some material is lost during a process, conservation must account for the loss explicitly.

For example,

Example: Process Loss

A process receives \(200\) kg of material. If \(8\%\) is lost, useful output is

Therefore,

Network Flow with a Loss Factor

If route input is \(x\) and only fraction \(e\) reaches the next node, then delivered flow is

A downstream node balance must use the delivered amount, not the original upstream amount.

Example: Transmission Efficiency

A route carries \(100\) units with efficiency

Delivered amount is

Therefore,

Multiple Resource Constraints

A production plan may be limited by material, labor, machine time, budget, storage, or demand simultaneously.

Each restriction becomes another equation or inequality.

Feasibility means satisfying all of them at once.

Example: Three Constraints

Suppose products \(x\) and \(y\) must satisfy

and

Together with

these inequalities define the feasible production plans.

Constraint Intersections

Boundary lines can intersect.

Their intersection points often matter because several constraints are active there at once.

Algebraically, find such points by solving the corresponding boundary equations as a system.

Example: Intersection of Two Boundaries

Solve

and

From the first equation,

Substitute:

Then

Therefore,

Active Constraints

A constraint is active at a point if it holds with equality.

For example, at a point satisfying

the resource represented by

is fully used.

Slack

For a maximum constraint

the unused amount is

This unused amount is often called slack.

Example: Compute Slack

Suppose

and the plan is

Resource use is

Slack is

Therefore,

Bottlenecks

A bottleneck is a capacity that restricts overall flow or production.

In a simple chain of routes, the smallest route capacity can limit the maximum possible through-flow.

Example: Simple Chain Bottleneck

A path contains consecutive links with capacities

Every unit must traverse all three links.

Therefore, the path cannot carry more than

at one time under this simplified model.

Parallel Routes

If two independent parallel routes connect the same source and destination, their capacities can combine.

If the capacities are

and

then total possible flow across those two routes cannot exceed

Example: Parallel Capacity

Two parallel routes have capacities \(40\) and \(65\).

Their combined capacity is

Therefore,

Path Variables

Instead of assigning variables to individual links, some models assign variables to entire routes.

If \(x\) units use path 1 and \(y\) units use path 2, then a shared link may carry

Its capacity constraint becomes

Example: Shared-Link Capacity

Two routes share a bridge that can carry at most \(90\) vehicles per time interval.

If route flows are \(x\) and \(y\), then

Transportation Allocation

Suppose two warehouses send goods to two destinations.

Variables can represent each shipment:

Supply constraints describe what leaves each warehouse, while demand constraints describe what reaches each destination.

Example: Warehouse Supply Equations

Warehouse 1 has \(70\) units available:

Warehouse 2 has \(50\) units:

Example: Destination Demand Equations

Destination 1 requires \(60\) units:

Destination 2 requires \(60\) units:

Total supply and total demand both equal \(120\), so an exactly balanced shipment system is possible in principle.

Parameterized Transportation Solution

From

and

let

Then

and the remaining equation gives

Thus,

Feasible Parameter Range

Shipment quantities must be nonnegative.

Therefore,

and

Combining these gives

Cost Can Be Added to a Flow Model

If shipping one unit along route \(i\) costs \(c_i\), total cost may be

This creates an objective that can later be compared across feasible solutions.

Full optimization methods are developed more deeply elsewhere.

Example: Evaluate a Feasible Shipping Cost

Suppose a plan ships \(30\) units on route A at \(\$4\) per unit and \(50\) units on route B at \(\$6\) per unit.

Therefore,

Objective versus Constraint

A constraint states what solutions are allowed.

An objective measures how desirable a feasible solution is.

For example,

may be a material constraint, while

may measure profit.

This lesson emphasizes building the feasible system; optimization is a later step.

Integer Constraints

Some variables represent indivisible objects.

Then a model may require

A fractional point can satisfy the linear inequalities but still be infeasible when whole units are required.

Example: Fractional but Infeasible

Suppose a production model allows

algebraically, but \(x\) counts complete machines.

Then the value violates the integer requirement.

Context matters in addition to the inequalities.

Checking a Node Balance

Add every incoming flow and every outgoing flow separately.

At a conservative intermediate node, verify

Checking Network Totals

In a lossless network with no accumulation, total source flow should equal total sink flow.

This global check can reveal an omitted route or incorrect sign even when individual equations appear plausible.

Checking Capacities

After solving for flows, compare each one with its permitted range.

A solution that violates even one capacity is infeasible.

Checking Units

All terms in one balance equation must use compatible flow units.

Do not add

directly to

without conversion.

Common Error: Reversing Inflow and Outflow

Choose a consistent node equation.

Either write

or write

Mixing sign conventions mid-problem creates errors.

Common Error: Ignoring a Branch

If flow splits along three outgoing routes, all three must appear in the node balance.

Omitting one route makes the network appear to create or destroy flow.

Common Error: Solving Equations but Ignoring Inequalities

Conservation equations describe balance.

Capacity inequalities determine whether the balanced assignment is feasible.

Both parts of the model must be checked.

Common Error: Accepting Negative Flow Automatically

A negative result may indicate that the assumed direction was opposite the actual direction, or it may indicate an infeasible model.

If variables are explicitly defined as nonnegative directed flows, negative values are not allowed.

Common Error: Confusing Capacity with Actual Flow

A route capacity of \(80\) does not mean the route must carry \(80\).

It means

Common Error: Treating a Maximum as an Equality

If at most \(100\) units of a resource are available, use

not automatically

Common Error: Forgetting Nonnegativity

A system of resource inequalities may include algebraic points with negative coordinates.

Production and flow quantities generally also require

Common Error: Counting Shared Capacity Twice

If two route variables share the same physical link, that link's capacity applies to their combined flow.

Use

not separate constraints that each allow the full capacity simultaneously.

Common Error: Ignoring Storage or Loss

Inflow need not equal outflow if material accumulates or is lost.

Modify the balance equation to include the missing term explicitly.

A Reliable Procedure for Flow Networks

1. Label every node and directed link.
2. Assign a variable to each unknown flow.
3. Write one conservation equation for each relevant node.
4. Add source, sink, storage, or loss terms where needed.
5. Write nonnegativity conditions.
6. Write route and node capacities.
7. Solve the resulting system or parameterize the solution family.
8. Check every balance and every constraint.

A Reliable Procedure for Resource Constraints

1. Define the decision variables.
2. List each limited resource.
3. Determine how much of each resource each variable uses.
4. Write one inequality per resource.
5. Add nonnegativity and whole-number restrictions if required.
6. Test or graph the common solution set.
7. Separate feasibility from any later objective such as profit or cost.

A Reliable Procedure for Feasibility Checks

1. Substitute the proposed values into every equality.
2. Substitute them into every inequality.
3. Check nonnegativity.
4. Check units.
5. Check integer restrictions if applicable.
6. Declare the point feasible only if every condition is satisfied.

Practice 1: Node Balance

A node receives \(45\) and \(30\) units per minute and sends \(50\) units along one route. Find the other outgoing flow.

Practice 2: Source Split

A source sends \(140\) units through routes \(x\) and \(y\). If \(x=85\), find \(y\).

Practice 3: Parameterized Split

Solve

by setting \(x=t\). State the nonnegative range of \(t\).

Practice 4: Capacity Constraint

A route can carry at most \(65\) units per hour. Write the capacity constraint for flow \(x\).

Practice 5: Feasibility

Determine whether

is feasible for

Practice 6: Infeasibility

Determine whether

is feasible for the same system.

Practice 7: Resource Constraint

Product A uses \(4\) kg of material and product B uses \(3\) kg. At most \(120\) kg are available. Write the constraint.

Practice 8: Test a Production Plan

Determine whether

satisfies

Practice 9: Slack

For the plan in Practice 8, how much material remains unused?

Practice 10: Boundary Intersection

Solve

and

Practice 11: Chain Bottleneck

A path has consecutive capacities \(90\), \(70\), and \(85\). What is the largest possible through-flow along that single path?

Practice 12: Parallel Capacity

Two independent parallel routes have capacities \(55\) and \(45\). What is their combined capacity?

Practice 13: Inventory Balance

A warehouse receives \(160\) units per day and ships \(135\). Find the daily change in inventory.

Practice 14: Transportation Parameter

A warehouse sends \(80\) units to destinations A and B:

Destination A must receive at least \(30\) units, while destination B can receive at most \(60\). State the feasible range of \(x\).

Practice 15: Identify the Error

Two path flows \(x\) and \(y\) share a bridge of capacity \(100\). A student writes

and concludes that \(x=y=100\) is feasible.

Explain the error and write the correct shared-capacity constraint.

Practice Answers

Practice 1

Practice 2

Practice 3

Let

Then

Nonnegativity requires

and

Therefore,

Practice 4

Practice 5

Total:

Capacities:

Both values are nonnegative.

Therefore,

Practice 6

The total is correct:

But

Therefore,

Practice 7

Practice 8

Since

the plan satisfies the material constraint.

Practice 9

Therefore,

Practice 10

Subtract the first equation from the second:

Then

Therefore,

Practice 11

Every unit must pass through all three links, so the smallest capacity is the bottleneck:

Therefore,

Practice 12

Therefore,

Practice 13

Therefore,

Practice 14

Since

we have

Destination A requires

Destination B has

Therefore,

The stronger lower bound is \(x\ge30\).

Nonnegativity of \(y\) gives

Therefore,

Practice 15

The two flows share one bridge, so they cannot each use the full bridge capacity independently.

Their combined flow must satisfy

The assignment

would require

units of shared capacity and is therefore infeasible.

What to Remember

At a conservative intermediate node,

A route capacity is modeled by

Resource constraints often have form

A feasible solution must satisfy every equality, every inequality, and every domain restriction simultaneously.

The most important habit is to separate three questions:

1. Does the flow balance?
2. Does it respect every capacity or resource limit?
3. Does the solution make sense in the stated context?

Where We Go Next

The applied problem families in this section have used many different equations, tables, rates, percentages, systems, and constraints. Their surface details differ, but they all rely on the same underlying habit: translate a situation into variables and relationships, solve the model, and then test whether the result answers the original question.

The next lesson, The Algebraic Modeling Process, brings those habits together into one general workflow for applied algebra.