Dynamic programming in applied tasks which are allowing to reduce the options selection

Abstract

The article discusses the dynamic programming algorithm developed by R. Bellman, based on the search for the optimal trajectory connecting the nodes of a predefined regular grid of states. Possibilities are analyzed for a sharp increase in the effectiveness of using dynamic programming in solving applied problems with specific features, which allows us to refuse to split a regular grid of states and implement an algorithm for finding the optimal trajectory when rejecting not only unpromising options for paths leading to each of the states, and all of them continuations, as in R. Bellmanʼs algorithm, but also actually hopeless states and all variants of paths emanating from them. The conditions are formulated and justified under which the rejection of hopeless states is possible. It has been established that many applied problems satisfy these conditions. To solve such problems, a new dynamic programming algorithm described in the article is proposed and implemented. Concrete examples of such applied problems are given: the optimal distribution of a homogeneous resource between several consumers, the optimal loading of vehicles, the optimal distribution of finances when choosing investment projects. To solve these problems, dynamic programming algorithms with rejecting unpromising paths, but without rejecting states, were previously proposed. The number of hopeless states that appear at various stages of dynamic programming and, accordingly, the effectiveness of the new algorithm depends on the specific numerical values of the source data. For the two-parameter problem of optimal loading of vehicles with weight and volume constraints, the results of comparative calculations by the R. Bellman algorithm and the new dynamic programming algorithm are presented. As a source of data for a series of calculations, pseudorandom numbers were used. As a result of the analysis, it was shown that the comparative efficiency of the algorithm with rejection of states increases with increasing dimension of the problem. So, in the problem of the optimal choice of items for loading a vehicle of a given carrying capacity with a number of items of 150, the number of memorized states and the counting time are reduced by 50 and 57 times, respectively, when using the new algorithm compared to the classical algorithm of R. Bellman. And for 15 items, the corresponding numbers are 13 and 4.

Keywords

• dynamic programming
• objective function
• optimal trajectory
• rejection of states