A Constrained Capital Budgeting Problem with Applications to Repair Kit Selection
研究一个资本预算问题，其中项目所需活动集不互斥，共享活动可同时满足多个项目，通过构建带边约束的最大网络流模型并利用拉格朗日松弛求解，并应用于现场维修包中零件和工具的选择。
We consider a capital budgeting problem in which each potential project requires the performance of a known set of activities. In general, these sets of activities are not mutually exclusive. However, when a particular activity is common to the requirements of multiple projects, a single performance of the activity simultaneously satisfies the requirements of the multiple projects. Associated with the performance of each activity are two quantities: a known fixed cost and a consumption of a known amount of a scarce resource. Because the sets of activities required by the projects are not mutually exclusive, we cannot apportion an activity's fixed cost or resource consumption to a single project. In this paper, we formulate this capital budgeting problem (and a slight variant) as a maximal network flow problem with a side constraint, and we report computational experience using Lagrangian relaxation to find an optimal solution. We also discuss an application to the selection of parts and tools to include in a field repair kit used to fix a variety of types of breakdowns.