Network Models

A network model represents a system as a set of nodes (vertices) connected by arcs (edges), where each arc carries a flow, cost, time, or capacity. Networks are used to model transportation routes, communication links, pipeline systems, project activities, and supply chains. A directed arc (i, j) has a direction of flow, while an undirected edge can be traversed in either direction. Each arc typically has a capacity u_ij (the maximum flow it can carry), a cost c_ij per unit of flow, and a traversal time t_ij. The most common network problems are: the shortest path problem, which finds the minimum-cost or minimum-time route from a source to a destination; the maximum flow problem, which finds the largest flow that can be sent from a source s to a sink t without exceeding arc capacities; the minimum-cost flow problem, which sends a required flow at minimum total cost; the transportation and assignment problems, which distribute goods from sources to destinations; and the critical path method (CPM) and PERT, which schedule project activities represented as a network of precedence relationships. The shortest path problem is solved by Dijkstra's algorithm when all arc costs are non-negative, or by Bellman-Ford when negative costs are present. Maximum flow is solved by the Ford-Fulkerson method and its variants (Edmonds-Karp, Dinic). The max-flow min-cut theorem states that the maximum flow from s to t equals the capacity of the minimum s-t cut, which separates the network into two parts with the smallest total capacity. In project networks, the critical path is the longest path through the network; any delay on a critical activity delays the entire project, while non-critical activities have float or slack. Network models assume that arc parameters are known and deterministic; when travel times or demands are uncertain, stochastic or robust versions are used. The main limitations are the assumption of linear, additive costs and the difficulty of representing complex real-world constraints such as vehicle routing with time windows.