д.ф.-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия
Dr. Sci. (Phys.-Math.), professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia
к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия
Cand. Sci. (Engin.), associate professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia
к.ф.-м..н., преподаватель, кафедра математики, ул. Старых Большевиков, 54 «А», г. Воронеж, 394064, Россия
Cand. Sci. (Phys.-Math.), lecturer, math department, st. Old Bolsheviks, 54 "A", Voronezh, 394064, Russia
Среди математических методов, используемых в экономике, видное место занимает метод динамического программирования, с помощью которого организуется оптимальное управление многостадийными процессами. Недостатком этого метода является невозможность вычисления всех решений задачи при совпадении их критериальных оценок. Факт существования нескольких оптимальных траекторий многошагового процесса может означать, что задача поставлена не вполне корректно, в том смысле, что назначенные критерии не полно характеризуют исследуемую систему. Это означает, что традиционный метод динамического программирования необходимо доработать на случай существования нескольких оптимальных траекторий с одинаковым значением критерия. В данной статье предлагается наиболее общий вариант такой доработки, а именно, обобщению подвергается многокритериальная численная схема. Для более наглядного представления выкладок и результата исследования дискретную задачу динамического программирования будем описывать в терминах теории графов. В этом случае она сведется к задаче поиска оптимального пути на ориентированном графе. Для ее решения предлагается трехэтапный алгоритм, в состав которого включены следующие шаги. Первый этап – построение оптимальных критериальных оценок для путей из начальной вершины во все остальные. Для выполнения этого этапа наиболее универсальным методом является многокритериальный вариант метода Форда–Беллмана. Второй этап – построение графа оптимальных путей. В исходном графе отбираются дуги, составляющие часть оптимальных путей. Из них затем с помощью оригинального алгоритма формируется подграф, в котором все пути оптимальны. Аналитически доказывается, что данный алгоритм дает верный результат (корректен). Третий этап – перебор всех путей в построенном подграфе. Проведенные численные эксперименты показали, что предложенный трехэтапный метод эффективно работает на ориентированных графах любого типа в достаточно большом диапазоне размерности. Предложенный алгоритм с минимальными изменениями может быть использован для решения произвольной дискретной задачи динамического программирования.
Among the mathematical methods used in economics, a prominent place is occupied by the dynamic programming method, with the help of which the optimal control of multi-stage processes is organized. The disadvantage of this method is the impossibility of calculating all solutions to the problem if their criteria-based estimates coincide. The fact of the existence of several optimal trajectories of a multi-step process may mean that the task is not set correctly, in the sense that the assigned criteria do not fully characterize the system under study. This means that the traditional method of dynamic programming needs to be refined in case of the existence of several optimal trajectories with the same value of the criterion. This article proposes the most general version of such refinement, namely, a multi-criteria numerical scheme is generalized. For a more visual representation of calculations and the result of the study, we will describe the discrete dynamic programming problem in terms of graph theory. In this case, it reduces to the problem of finding the optimal path on a directed graph. To solve it, a three-stage algorithm is proposed, the composition of which includes the following steps. The first stage is the construction of optimal criteria estimates for paths from the initial vertex to all the others. To perform this stage, the most universal method is the multicriteria version of the Ford – Bellman method. The second stage is the construction of a graph of optimal paths. In the original graph, arcs are selected that are part of the optimal paths. Of these, using the original algorithm, a subgraph is formed in which all paths are optimal. It is analytically proved that this algorithm gives the correct result (correct). The third stage is enumeration of all paths in the constructed subgraph. Numerical experiments showed that the proposed three-stage method works efficiently on oriented graphs of any type in a sufficiently large range of dimensions. The proposed algorithm with minimal changes can be used to solve an arbitrary discrete dynamic programming problem.
The authors declare that there are no conflicts of interest present.