On the dynamic programming algorithm under the assumption of monotonicity

We formulate a discrete optimal control problem, which has not been considered earlier, which arises in the design of oil and gas networks. For this problem we set four theorems so that you can have a process, the optimal process and the optimum value. Necessary and sufficient conditions we give in Theorem 1. Under these conditions, by Theorem 1, we get not empty attainability intervals. For each interval, we choose the grid-a subset of its points, where by an arbitrary point of interval, we find the nearest point on the left. By means of such approximations, we define the Bellman functions on the grids. Using Bellman functions in Theorem 2 we give the process and we evaluate its deviation from the optimal process. In Theorem 2, we guarantee, that the given process is optimal when the attainability intervals and their grids coincide. In other cases, to get the optimal process, we use Theorem 3 and Theorem 4. In Theorem 3 we set that the process given in Theorem 2, is minimal in the lexicographical order which we introduce using Bellman functions. In Theorem 3 we give procedure that builds, if possible, in this order, the next process, skipping only the processes that are not optimal. We find the optimal process and the optimal value by Theorem 4, starting from the process given in Theorem 2, using one or more calls of the procedure given in Theorem 3.

dynamic programming, Bellman functions, procedures, algorithms