This thesis deals with analytical techniques to be utilized during the various decision making phases of the capital budgeting process. This thesis begins with the attempt to solve the capital budgeting problem in which both the following conditions hold: (1) the borrowing interest rate varies from period to period in close relation to the size of debt and (2) projects are indivisible, i.e., fractional projects are not allowed. The problem can be formulated in a mixed integer non-linear programming model. Generally, this model is difficult to solve because the constraints are not linear and solution set is not convex.
In order to solve the model, we characterized the dominance properties of the solution of the model. This special property reduces the solution space and the binary variables make the solution space finite. Thus we only need to search the finite points of the solution space. That is, this model could be solved by explicit enumeration. After that, we derived the equivalent model to solve the problem more efficiently. This equivalent model enables us to develop an implicit enumeration algorithm which requires much less computation than the explicit enumeration algorithm.
The other model developed in this thesis is to provide the optimal combinations of investment at each level of capital budget. This is important especially for a decision maker when he examines the possibilities for revising the underlying budget limits. This model is studied to answer the following question. Is it worthwhile to relax the current budget limits for a given set of projects? In linear programming framework, dual variables do work as an accurate shadow price evaluator of the theoretical payoff from very small continuous budget relaxation. Under project indivisibility condition, however, dual variables fail to work as an indicator of attractiveness of additional funds. So we employed the modified internal rate of return method to provide incremental rate of return on differing level of additional investments. To know how much each of additional funds will increase respective terminal value, we make an incremental analysis of respective additional funds with the modified internal rate of return. As a result, provided are many good but different solutions of each increased budget as well as an optimal solution of current budget.
Another part of this thesis is to develop an understanding as to how the two important types of interest rate - internal rate of return and cost of capital - can be incorporated in the applications of mathematical programming to capital budgeting problem. We presented a rationale for maximum net present value principle and its limitation. When the marginal cost of capital is not constant as in real world, we show that the appropriate criterion should be maximum surplus principle, not the maximum NPV principle. To compute the value of surplus, we used cost of capital as a proper discount rate. Each surplus is determined by deducing the cost of investment from the corresponding return on investment. To obtain the cost of investment, we first calculated the capital charge bases and then applied the cost of capital to them. The internal rate of return was employed as a measure to provide the capital charge bases.
본 논문의 첫번 째 모형은 기업이 주어진 자본예산 제약하에서 여러 개의 project들을 선택함에 있어서 현실적인 측면을 감안하여, borrowing 이자율을 borrowing양의 단조증가함수로 표현하였으며 동시에 project의 성격을 정확히 반영하기 위하여 project선택변수를 0-1 변수로 수리계획 모형을 세웠다. 이 모형은 non-convex set에서의 Non-linear Mixed Integer Programming문제를 푸는 모형으로 일반적으로 최적해를 구하는 해법이 없으나, 본 논문은 최적해의 행태를 특징짓는 특성을 찾아냄으로써 위의 문제를 Combinatorial Programming문제로 바뀌어 지는 것을 증명하였다.
이러한 Combinatorial Programming문제를 능률적으로 풀기 위하여 목적함수식이 다르나 같은 해를 제공하는 동일한 모형을 이끌어 냄으로써 능률적인 해법인 Implicit Enumeration Algorithm을 개발하였다. 이 해법은 먼저 목적함수값이 최적해의 하한값으로 하는 초기해로부터 후보해들(candidate solutions)을 얻는다. 후보해들은 Partial Ordering 개념을 이용하여 해집합 (solution space)을 탐색(search)하지 않고 구함으로써 계산량을 줄이고 이러한 후보해들을 탐색하여 최적해를 구한다. 개발된 해법에 대해서는 예제를 통해서 Explicit Enumeration Algorithm과의 계산속도(computational timi)을 비교함으로써 새로이 개발된 해법의 효율성을 평가하였다.
본 논문의 두번 째 모형은 예산의 성격이 flexible한 경우에 project들을 선택함에 있어서, "주어진 상황에서 예산한도를 늘리는 것이 가치가 있는가?"와 같은 질문에 답하기 위한 것이다. 그러나 project의 성격을 정확히 반영하기 위해 project선택변수를 0-1 변수로 삼으면, 추가예산 배정의 효율성지표로 사용되어 온 Linear Programming의 dual 변수의 shadow price기능을 상실하게 되는데 이러한 shadow price기능을 수행하는 새로운 효율성 지표로 modified internal rate of return을 도입하여 위 질문에 대한 문제를 해결하였으며 이를 풀기 위한 능률적인 해법을 개발하였다. 예제를 통해 현재 주어진 예산한도 내에서의 최적해 뿐만 아니라 추가예산 배정의 효율성이 높은 순서대로 여러 가지의 해들도 함께 제시하였다.
본 논문의 마지막 부분은 순 현재가치법(Net Present Value Method)이 marginal cost of capital이 일정하지 않은 경우, project들을 선정하는데에 한계점을 지적하고 새로운 기준으로 Maximum Surplus Principle이 타당함을 보였다. 이러한 새로운 기준하에서 두 개의 서로 다른 이자율, 즉 internal rate of return과 cost of capital이 어떻게 capital budgeting문제에 수리계획법을 이용하는 데 적용되는 지의 논리 근거를 제시하였다.