|
One option of the Math Programming
add-in is to create a linear network flow model. By selecting
Math Program from the Optimize menu when a
network model is on the active worksheet, the Optimize add-in
constructs a form for discrete variables that can interact with
the linear network model. When all the variables are specified
as the combinatorial variables in the dialog, the network flow
variables are manipulated directly by the search process. A
more interesting case is illustrated here in which the combinatorial
problem involves a selection of arcs that are to be excluded
or included in the network. In this example, we manually link
the combinatorial variables to the network model. For this example,
three add-ins must be installed, the Math Programming add-in,
the Network Solver add-in and the Optimize
add-in.
Consider a telecommunications network in which traffic flows
between various origins and destinations. The figure shows a
case with three source nodes S = {1, 3, 7}, four destination
nodes D = {2, 4, 5, 8}, and one transshipment node T = {6}.
The arcs drawn with solid lines represent existing communication
links while those drawn with dashed lines are proposed links.
The complete set of arcs is denoted by A = {1,…,17}.
Associated with each link is an upper bound on flow and a unit
flow cost shown as the two numbers on each arc. If one of the
proposed links is constructed, it will have the capacity and
cost indicated on the arc. Let A' = { 1,…,5} be the set
of proposed links with corresponding construction costs f1 =
8, f2 = 6, f3 = 9, f4 = 7 and f5 = 7. These costs are independent
of size. The problem is to determine which links to build, if
any, and how much traffic to put on each link in the network
so that the sum of the flow costs and construction costs is
minimized. For a solution to be feasible, it must satisfy flow
balance at each node and arc flows must stay within the arc
capacities. |