3.6.
Summary
105
budgeting problem is connected with the operating policy problem (a oneyear optimization problem) and how the first feasible solution FEyt
is
found. Figure 3.15 shows the backtracking sequence in which each node is
examined and eliminated or accepted as the new feasible solution. Appendix A gives the complete documentation for the algorithm together
with detailed flow charts and a listing of the FORTRAN IV computer
program.
3.6· Summary
In this chapter we have explored the various optimization techniques
that could be used to resolve the problem formulated in Chapter 2. Some
possible solution techniques (the generalized Lagrange multiplier technique, dynamic programming, and mixed integer programming) were discussed and rejected because of the characteristics of the optimal expansion
problem or inherent intractabilities of the technique itself. The algorithm
finally chosen takes advantage of the discreteness of the variables in the
original problem (Problem I) (1) to decompose it into the set of all feasible
combinations (termed Problem II) and (2) to consider the economic return
for each combination (termed Problem III). The combination of (1) and
(2) with the best return is necessarily the optimum solution for Problem I.
Problem II is a capital budgeting (CB) problem and is solved using
Little's branch and bound algorithm (BBA). Problem III is called the
operating policy (OP) problem and is solved by Fulkerson's out-of-kilter
algorithm (OKA) which takes advantage of the problem network structure. The two problems are interconnected because the operating return in
the CB problem is determined only by obtaining the optimal solution of the
OP problem, and the total number of dams in the OP problem is the optimal
solution of the CB problem.
This chapter provides the theoretical background of Little's and Fulkerson's algorithms, mentions some of their general applications, and demonstrates their methodology with simple and detailed examples. Finally the
application of the BBA and OKA algorithms to the optimal expansion
problem is explained.
Summary
105
budgeting problem is connected with the operating policy problem (a oneyear optimization problem) and how the first feasible solution FEyt
is
found. Figure 3.15 shows the backtracking sequence in which each node is
examined and eliminated or accepted as the new feasible solution. Appendix A gives the complete documentation for the algorithm together
with detailed flow charts and a listing of the FORTRAN IV computer
program.
3.6· Summary
In this chapter we have explored the various optimization techniques
that could be used to resolve the problem formulated in Chapter 2. Some
possible solution techniques (the generalized Lagrange multiplier technique, dynamic programming, and mixed integer programming) were discussed and rejected because of the characteristics of the optimal expansion
problem or inherent intractabilities of the technique itself. The algorithm
finally chosen takes advantage of the discreteness of the variables in the
original problem (Problem I) (1) to decompose it into the set of all feasible
combinations (termed Problem II) and (2) to consider the economic return
for each combination (termed Problem III). The combination of (1) and
(2) with the best return is necessarily the optimum solution for Problem I.
Problem II is a capital budgeting (CB) problem and is solved using
Little's branch and bound algorithm (BBA). Problem III is called the
operating policy (OP) problem and is solved by Fulkerson's out-of-kilter
algorithm (OKA) which takes advantage of the problem network structure. The two problems are interconnected because the operating return in
the CB problem is determined only by obtaining the optimal solution of the
OP problem, and the total number of dams in the OP problem is the optimal
solution of the CB problem.
This chapter provides the theoretical background of Little's and Fulkerson's algorithms, mentions some of their general applications, and demonstrates their methodology with simple and detailed examples. Finally the
application of the BBA and OKA algorithms to the optimal expansion
problem is explained.