|
|
Network
Flow Programming |
|
- Constructing the Network |
|
To enter the model in the form of a network, select Network from
the OR_MM menu. The Network Model Dialog allows the specification
of a name, indication of maximization or minimization for
the optimization, indication of whether the problem is linear
or nonlinear, specification of the numbers of arcs and nodes
and identification of integer flows on the arcs. Data is entered
for the example problem. |
|
|
|
The checkboxes near the middle
of the dialog determine the set of parameters that will appear
on the worksheet. We have unchecked the Include Minimum box
because all the arcs have 0 arc lower bounds. When data for
minimum flows are not shown, the 0 lower bounds are assumed.
With the Include Maximums box checked, a column will
be included for the maximum values of flows. If it were not
checked, the default is that arc flows are unbounded from above.
With the Include Gains box checked a column will be
included for arc gains. The default assumption is that arc
gains are all 1. The Sensitivity Analysis box tells
the selected solver to perform a sensitivity analysis on the
optimum solution. The Make Random Problem box generates
a random network. This is convenient for demonstrating the
network modeling and solving options.
We see three solver options at the bottom of the dialog: Excel
Solver, Jensen Network Solver and the Jensen LP Solver. Any
one of these can solve the linear network flow problem with
or without integer requirements. The Excel Solver and the Jensen
Network Solver can solve nonlinear problems. The Jensen Network
Solver does not provide sensitivity analyses.
The worksheet showing the model for the Power problem is shown
below. The data has been entered for the arc and
node parameters and after the problem has been solved. Column
D holds arc names. In this case we have chosen to name each
arc by the node names at its ends. Columns F through J hold
the arc parameters. Columns F and G contain the indices of
the nodes that originate and terminate the arcs. Columns H
through J hold the remaining parameters of the arcs. Lower
bounds on arc flows are assumed to be zero since that column
was not included in the display. The Upper column specifies
the upper bound. The transmission arcs for this case have bounds
of 99999, the large upper bound not restricting the flow. The
Cost column contains the unit cost of arc flow, and the Gain
column holds the multipliers for arc flows. The variables for
this problem are contained in the Flow column, column E. The
flow in an arc is the flow leaving the origin node of the arc.
The numbers shown in the illustration are the optimum values
obtained by the Solver program. The column labeled Flow_O,
column K, contains the flows entering the terminal nodes of
the arcs. This is provided by an equation that multiplies the
flow and the gain. The numbers in this column are used elsewhere
on the worksheet and the formulas should not be changed. |
|
|
Notice that arcs 13, 14 and 15
do not have origin nodes in the figure defining the problem.
Rather, these arcs bring flow into the network at the nodes
representing the power plants. This is shown in column F by
specifying 0 as the origin nodes of these arcs. Similarly,
an arc that starts at some network node and leaves the network
has 0 as its terminal node.
Information associated with the nodes is shown in the portion
of the worksheet starting in column M. Node indices appear
in column M, and names are provided by the user in column N.
Fixed flows entering or leaving the node are in Column O. A
positive number in this column is a flow that enters at the
node, while a negative number is a flow that leaves. In the
example, the negative numbers for nodes X, Y and Z are the
power demands at the cities.
Column P of the node display, Balance, holds the equations that
define conservation of flow for each node. Conservation of flow
requires that total flow out of each node equal the total flow
in. Formulas in these cells compute the net flow in or out of
the cells. Feasible solutions require that the numbers in the
Balance column all be zero. The solution shown here has very
small values for the balance equations indicating that the solution
is feasible within the numerical accuracy associated with the
Solver program. |
|
|
|