Network model (operations research)
Network models (in operations research) are a class of mathematical models that represent a problem in the form of a graph (or network), where vertices (nodes) denote objects or states, and edges (arcs) represent connections or processes between them[1]. In the context of optimization, a network is often understood as a directed graph, which in operations research is directly called a "network"; the vertices of such a network are called nodes, and the edges are called arcs.
Network models are a powerful tool for analyzing and optimizing complex systems in fields such as logistics, telecommunications, project management, and finance. Their strength lies in their high level of abstraction: a node can represent a city, a computer router, or a project stage, while an arc can represent a road, a communication channel, or a technological operation.
Definition and Terminology
The foundation of network models is graph theory. Key concepts include:
- Flow network: a directed graph in which each edge has a capacity and a flow. The graph has two special vertices: a source, from which the flow originates, and a sink, into which it flows[1].
- Flow conservation law: For any vertex other than the source or sink, the total incoming flow must equal the total outgoing flow. This condition is a discrete analog of physical conservation laws.
- Network scheduling: A model representing a project as a set of interconnected operations (arcs) and events (nodes). Such networks are directed acyclic graphs, reflecting the sequence of work execution.
Key Properties and Theorems
Network models have a number of special properties that allow for the application of highly efficient algorithms to solve them.
- Integrality of solutions: Many network optimization problems (e.g., maximum flow or shortest path) have the property of total unimodularity of the constraint matrix. Due to this, if the problem parameters (capacities, lengths) are integers, the optimal solution found by linear programming methods will also be an integer, without the need for additional constraints[2].
- Max-flow min-cut theorem: A central result in flow theory. It states that the maximum flow value from a source to a sink is equal to the minimum capacity of any cut separating the source and the sink. This theorem establishes the optimality criterion for a flow and is the basis for many algorithms[3].
- Optimality principle for shortest paths: If a path from point A to point C is the shortest, then any of its subpaths (e.g., from an intermediate point B to C) is also the shortest path between the respective vertices. This property, which underlies dynamic programming, ensures the correctness of algorithms such as Dijkstra's algorithm.
- Properties of the minimum spanning tree (MST):
- Cut property: For any cut in the graph, the edge with the minimum weight that crosses the cut belongs to at least one MST.
- Cycle property: In any cycle of the graph, the edge with the maximum weight does not belong to any MST.
The correctness of "greedy" algorithms like Prim's and Kruskal's is based on these properties.
Main Network Optimization Problems
- Shortest path problem: Find a path of minimum total length (weight) between two given nodes. Solved by Dijkstra's algorithm (for non-negative weights) or the Bellman-Ford algorithm (for arbitrary weights).
- Maximum flow problem: Determine the maximum possible flow from a source to a sink, given the capacities of the arcs. A classic solution method is the Ford-Fulkerson algorithm.
- Minimum spanning tree problem: Find a subgraph that connects all vertices of a network and has the minimum total cost of edges.
- Critical path method (CPM): In network scheduling models, determine the longest sequence of tasks that establishes the minimum possible time to complete the entire project. The tasks on this path have zero slack.
Examples
- Shortest path: Finding the optimal route with a navigation system between two points on a city map, where cities are nodes and roads are arcs with weights equal to length or travel time.
- Maximum flow: Determining the maximum capacity of a pipeline network, where pumping stations are nodes and pipes are arcs with limited capacity.
- Minimum spanning tree: Designing a communication network (e.g., laying fiber optic cable) to connect several cities with the minimum total cable length.
- Critical path: In a house construction project, where tasks (laying the foundation, erecting walls, installing the roof) have specified durations and technological dependencies, the critical path determines the minimum completion time for the project. Any delay in a task on this path will delay the entire project.
See also
- Operations research
- Graph theory
- Transportation problem
- Critical path method
- PERT
Notes