Improved algorithm using generalised flows for an optimisation problem in a cash flow network

摘要

We consider a cash-flow optimisation problem for the cash management method proposed by Golden et al. One of the important objectives of a company is to maximise the total cash at the final term in the network, with the constraints that the total cash supply meets the total demand and some money is invested at each term j= 1,2,...,n, where n is the number of terms run by the company. Golden et al. formulated this as a flow problem with gains or losses in a cash flow network, and they gave an algorithm for finding the optimal flow in the network. This algorithm is not necessarily efficient from a computational complexity point of view. The three main results of this paper are as follows: 1) we propose an efficient algorithm for this optimisation problem; 2) we point out close relations between the optimisation of cash flow and the generalised flow problem with gains or losses; 3) we improve an algorithm that we developed in an earlier study. Our proposed algorithm runs in O(n(min{n,i~*})~2) time where i~* ＞ 0 is an integer calculated from a given instance. The complexity is strongly polynomial, which implies that the computation time depends on only the structure of the underlying graph of the cash flow network. Our algorithm can be directly applied to the cash flow management of a real industry, such as an agricultural business.