Cengage Learning Copyright Policies

Network Modeling

• Network flow problems are decision problems in business that can be visually represented using a network.
• Common network flow problems include: transshipment, shortest path, maximal flow, transportation/assignment, and generalized network flow.
• Minimum spanning tree problems are also a type of network problem.

The Transshipment Problem

• The transshipment problem is a fundamental network flow problem, of which other network flow problems are variations.
• It involves transporting goods between various locations, allowing for temporary storage at intermediate points.
• The Bavarian Motor Company (BMC) example (provided in the text) demonstrates a transshipment problem: manufacturers cars in Hamburg, Germany, and ship them to US distributors via ports in Newark and Jacksonville
• Distribution centers then ship the cars to different US cities.
• The problem aimed to determine the least costly way for BMC to transport cars.
• Nodes represent locations; arcs represent possible routes.
• Directed arcs indicate the direction of flow.
• Supply nodes have a surplus of items.
• Demand nodes require items.
• Transshipment nodes both receive and send items.

Decision Variables in Network Flow Problems

• Decision variables represent the number of units flowing between any two nodes.
• Xij represents the number of items transported from node i to node j.
• Node identification numbers are used for simpler representation.

Objective Function in Network Flow Problems

• The objective is usually to minimize the total cost or distance or penalty.
• This is a "minimum cost network flow problem."
• Costs associated with each arc (shipping between nodes) determine the objective function.
• The objective function in the BMC example uses costs for each arc to represent the total transportation cost.

Constraints in Network Flow Problems

• Constraints describe the total supply and demand at each node and the flow of items.
• Balance-of-flow rules apply for each node:
  • total supply > total demand, then Inflow - Outflow ≥ Supply or Demand
  • total supply = total demand, then Inflow - Outflow = Supply or Demand
  • total supply < total demand, then Inflow - Outflow ≤ Supply or Demand.
• Specific constraints given for each node and each flow.

Spreadsheet Implementation

• Spreadsheet software (like Excel) is useful in implementing network flow problems to model, calculate, and solve.
• Formulas are used to automate the calculations of total transportation cost, node inflows and outflows, and to manage variables and constraints.

Analysis of Solution

• Example spreadsheet computations illustrate how solutions can be found using LP optimization tools in software, like Excel.
• The results, i.e. optimal shipping routes for the car example, are shown graphically and numerically in provided figures.

The Shortest Path Problem

• The shortest path problem determines the least-cost route/path between a starting node to an ending node.
• Often used to find optimal routes for emergency vehicles, deliveries, or travel planning.

The Equipment Replacement Problem

• The equipment replacement problem focuses on optimizing a schedule for replacing equipment over time.
• This type of problem may be tackled as a shortest path problem, using the balance-of-flow rule to calculate costs of potential alternatives.

Transportation/Assignment Problems

• Transportation/assignment problems involve modeling the movement of items from sources to destinations, e.g. Tropicsun Company moving citrus from groves to processing plants.
• Networks in transportation problems have supply and demand nodes to indicate quantities.

Generalized Network Flow Problems

• Situations with gains or losses in the flows of items in a network, e.g., transportation of raw materials with yield factors to create new products at different costs.
• These problems must adjust how constraints are handled computationally (compared to other problems mentioned).

Minimal Spanning Tree Problems

• Problems that require connecting n nodes of a network with the fewest amount of arcs (connecting all nodes, but not repeating any connections).
• Methods for visually calculating the minimum amount of connecting arcs is demonstrated graphically (using an algorithm).