Network Flow Programming

The network model for this problem consists of nodes and arcs as shown in the figure. The nodes are the circles and represent the generating stations and cities. The arcs are the directed line segments between nodes. They represent the transmission lines between generating stations and/or cities.

Network Flow Model of Power Distribution Problem

The numbers adjacent to the nodes in the square brackets represent flows entering the network or flows leaving the network, positive numbers for flows entering and negative numbers for flows leaving. Power enters at the generation stations, nodes A, B, and C through arcs that enter these nodes. Power leaves the network at nodes X, Y, and Z, where a number at the node indicates the flow that is to be withdrawn at the node. The arcs for this case have three parameters, the upper bound, cost and gain. The upper bound for transmission arcs are

M, indicating a large number. For an arc that passes from nodeito nodej, the gain multiplies the flow leaving nodeito obtain the flow that enters nodej. For this problem the gain factors represent the losses of power in the transmission lines. The model structure also allows minimum flow, maximum flow and cost parameters to be associated with each arc.A solution to the network model is an assignment of flows to the arcs that satisfies the flow requirements at the nodes such that there is conservation of flow at the nodes. An arc that touches only one node, such as those entering A, B and C, contributes only to the conservation equation of the node. The optimum solution minimizes cost.

Updated 1/16/01

Operations Research Models and Methods

by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors