Chapter 6

• The circles in the network are called nodes
• The model for any minimum-cost flow problem is represented by a network with flow passing through it
• Each node where the net amount of flow generated (outflow minus inflow) is a fixed positive number

  Supply node
• Each node where the net amount of flow generated is a fixed negative number

  Demand node
• Any node where the net amount of flow generated is fixed at zero

  Transshipment node
• The amount of flow out of the node equal the amount of flow into thenode

  Conservation of flow
• The arrows in the network are called arcs
• The maximum amount of flow allowed through an arc is referred to as the capacity of that arc
• T/F: The network has enough arcs with sufficient capacity to enable all the flow generated at the supply nodes to reach all the demand nodes

  T
• T/F: The cost of the flow through each arc is proportional to the amount of that flow, where the cost per unit flow is known

  T
• A minimum-cost flow problem will have feasible solutions if and only if the sum of the supplies from its supply nodes equals the sum of thedemands at its demand nodes

  The Feasible Solutions Property
• As long as all the supplies, demands, and arc capacities have integer values, any minimum-cost flow problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its flow quantities


  The Integer Solutions Property
• All flow through the network originates at one node, called the source, and terminates at one other node, called the sink
• A streamlined version of the simplex method for solving minimum-cost flow problems very efficiently

  Network Simplex method
• A special type of minimum-cost flow problem where there are no capacity constraints on the arcs

  Transshipment problem
• The node for a maximum flow problem at which all flow through the network originates

  Source
• The node for a maximum flow problem at which all flow through the network terminates

  Sink
• A channel through which flow may occur in either direction between a pair of nodes, shown as a line between the nodes

  Link
• The node at which travel through the network is assumed to start for a shortest path problem

  Origin
• The node at which travel through the network is assumed to end for a shortest path problem

  Destination
• The number (typically a distance, a cost, or a time) associated with including the link or arc in the selected path for a shortest path problem

  Length of a link or arc
• T/F: The objective of the shortest path problem is to find the minimum total length from the origin to the destination

  T
• A fictitious destination introduced into the formulation of a shortest path problem with multiple possible termination points to satisfy the requirement that there be just a single destination

  Dummy destination
• A channel through which flow may occur from one node to another, shown as an arrow between the nodes pointing in the direction in which flow is allowed

  Arc