126
4. Application
of the Optimization
Algorithm
51 shows the reason for this discrepancy, namely that arc 51 competes for
available water with arc 52. If the upper bound of arc 51 were raised by one
unit, an extra unit of flow would result in the arc because a higher return
per unit flow results in arc 51 than in arc 52. Consequently, the flows in
arc 34 (from node 22 to node 24) and in arc 52 were reduced by one unit.
net effect of raising _ benefits gained by increasing _ benefits lost by decreasing
bound 51 by one
flow
by one unit in arc 51
flow
by one unit in arc 52
unit
=4-3=1
Similar reasoning is used to explain the discrepancy between 7,7 and the
cost coefficient for arc 54.
4.5.2. Comments
on Some Feasible
Solutions
Figure 4.4 shows the paths through the solution tree (composed of nodes
and arcs) of the first feasible solution and of one other solution that had a
higher return than the first solution. The solution tree may also be interpreted as a matrix (called BOUND) as shown for the first feasible solution
in Table 4.4, and examination of matrix BOUND (also see Appendix B)
at any time tells which possible solutions have been examined and which
remain to be examined.
Matrix BOUND in the example problem has 10 X 50 elements. The
columns represent the nine possible dams that may be constructed and the
decision to undertake no project. The rows represent the planning horizon
(50 yr). The nonzero elements in the matrix represent those nodes that
remain to be examined. The zero elements represent those nodes that have
been eliminated from further consideration for one of the following reasons:
(1) they have been examined already; (2) the bound associated with the
node(s) is lower than the current feasible solution; (3) the dam associated
with the node is infeasible for that year because of the capital budget limit.
The elements of matrix BOUND correspond to the nodes of the solution
tree. Since column 1 corresponds to dam 6, column 2 to dam 7, and so on,
the matrix elements for columns 1 through 9 have been modified so that
they are identified by the dam numbers. For example, element (2,7) in
the matrix in the revised nomenclature is known as (7, 7), since column 2
represents dam 7. Column 10 corresponds to the decision to build no project, and the elements in this column are known by the no-project number
(0). The correspondence of the elements of the matrix to the nodes of the
solution tree may be demonstrated by comparing the BOUND matrix
that occurs just after the first feasible solution as tabulated in the computer
4. Application
of the Optimization
Algorithm
51 shows the reason for this discrepancy, namely that arc 51 competes for
available water with arc 52. If the upper bound of arc 51 were raised by one
unit, an extra unit of flow would result in the arc because a higher return
per unit flow results in arc 51 than in arc 52. Consequently, the flows in
arc 34 (from node 22 to node 24) and in arc 52 were reduced by one unit.
net effect of raising _ benefits gained by increasing _ benefits lost by decreasing
bound 51 by one
flow
by one unit in arc 51
flow
by one unit in arc 52
unit
=4-3=1
Similar reasoning is used to explain the discrepancy between 7,7 and the
cost coefficient for arc 54.
4.5.2. Comments
on Some Feasible
Solutions
Figure 4.4 shows the paths through the solution tree (composed of nodes
and arcs) of the first feasible solution and of one other solution that had a
higher return than the first solution. The solution tree may also be interpreted as a matrix (called BOUND) as shown for the first feasible solution
in Table 4.4, and examination of matrix BOUND (also see Appendix B)
at any time tells which possible solutions have been examined and which
remain to be examined.
Matrix BOUND in the example problem has 10 X 50 elements. The
columns represent the nine possible dams that may be constructed and the
decision to undertake no project. The rows represent the planning horizon
(50 yr). The nonzero elements in the matrix represent those nodes that
remain to be examined. The zero elements represent those nodes that have
been eliminated from further consideration for one of the following reasons:
(1) they have been examined already; (2) the bound associated with the
node(s) is lower than the current feasible solution; (3) the dam associated
with the node is infeasible for that year because of the capital budget limit.
The elements of matrix BOUND correspond to the nodes of the solution
tree. Since column 1 corresponds to dam 6, column 2 to dam 7, and so on,
the matrix elements for columns 1 through 9 have been modified so that
they are identified by the dam numbers. For example, element (2,7) in
the matrix in the revised nomenclature is known as (7, 7), since column 2
represents dam 7. Column 10 corresponds to the decision to build no project, and the elements in this column are known by the no-project number
(0). The correspondence of the elements of the matrix to the nodes of the
solution tree may be demonstrated by comparing the BOUND matrix
that occurs just after the first feasible solution as tabulated in the computer