Динамическое программирование в прикладных задачах, допускающих сокращение перебора вариантов

В статье рассматривается разработанный Р. Беллманом алгоритм динамического программирования, основанный на поиске оптимальной траектории, соединяющей узлы предварительно заданной регулярной сетки состояний. Анализируются возможности резкого повышения эффективности применения динамического программирования при решении прикладных задач, обладающих специфическими особенностями, что позволяет отказаться от разбиения регулярной сетки состояний и реализовать алгоритм поиска оптимальной траектории при отбраковке не только бесперспективных вариантов путей, приводящих в каждое из состояний, и всех их продолжений, как в алгоритме Р. Беллмана, но и собственно бесперспективных состояний и всех вариантов исходящих из них путей. Сформулированы и обоснованы условия, при которых возможна отбраковка бесперспективных состояний. Установлено, что многие прикладные задачи удовлетворяют этим условиям. Для решения подобных задач предложен и реализован новый алгоритм динамического программирования. Приводятся конкретные примеры таких прикладных задач: оптимальное распределение однородного ресурса между несколькими потребителями, оптимальная загрузка транспортных средств, оптимальное распределение финансов при выборе инвестиционных проектов. Для решения этих задач ранее предлагались алгоритмы динамического программирования с отбраковкой бесперспективных путей, но без отбраковки состояний. Число бесперспективных состояний, появляющихся на различных этапах динамического программирования, и, соответственно, эффективность нового алгоритма, зависит от конкретных числовых значений исходных данных. Для двухпараметрической задачи оптимальной загрузки транспортных средств при ограничении по весу и объёму приведены результаты сопоставительных расчётов по алгоритму Р. Беллмана и по новому алгоритму динамического программирования. В качестве исходных данных для серии расчётов использовались псевдослучайные числа. В результате анализа показано, что сравнительная эффективность алгоритма с отбраковкой состояний растёт при увеличении размерности задачи. Так в задаче оптимального выбора предметов для загрузки транспортного средства заданной грузоподъёмности при числе предметов 150 количество запоминаемых состояний и время счёта снижаются в 50 и 57 раз, соответственно, при использовании нового алгоритма по сравнению с классическим алгоритмом Р. Беллмана. Для 15 предметов соответствующие числа равны 13 и 4.

динамическое программирование, целевая функция, оптимальная траектория, уравнение Р. Беллмана

1. Беллман Р. Динамическое программирование. М.: ИЛ., 1960. 402 с.

2. Ляховский В.Н., Михалевич В.С., Быков В.И. Определение на ЭВМ наивыгоднейшего положения красной линии продольного профиля на вольном ходу. Транспортное строительство. 1962;4:41-43.

3. Михалевич В.С., Шор Н.З. Математические основы решения задачи выбора оптимального очертания продольного профиля. Труды Всесоюзного НИИ транспортного строительства. 1964;51:12-14.

4. Михалевич В.С. Последовательные алгоритмы оптимизации и их применение. Кибернетика. 1965;1:45-56.

5. Михалевич В.С., Быков В.И., Сибирко А.Н. К вопросу проектирования оптимального продольного профиля дороги. Транспортное строительство. 1975;6:39-40.

6. Космин В.В., Струченков В.И., Фрадков Е.Б. Проектирование продольного профиля дороги на ЭВМ. Транспортное строительство. 1971;4:38-42.

7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. 460 с.

8. Лежнев А.В. Динамическое программирование в экономических задачах. М.: Бином, 2010. 176 c.

9. Кремер Н.Ш. Исследование операций в экономике. М.: Юрайт, 2012. 430 с. ISBN 978-5-9916-1849-6

10. Cavagnari G., Marigonda A., Piccoli B. Generalized dynamic programming principle and sparse meanfield control problems. J. Math. Anal. Appl. 2020;481(1): Article No. 123437. https://doi.org/10.1016/j.jmaa.2019.123437

11. Ramahatana F., David M. Economic optimization of micro-grid operations by dynamic programming with real energy forecast. J. Phys. Conf. 2019;1343(1): Article No. 012067. https://doi.org/10.1088/1742-6596/1343/1/012067

12. Firdausiyah N., Taniguchi E., Qureshi A.G. Impacts of Urban Consolidation Centres for Sustainable City Logistics Using Adaptive Dynamic Programming Based Multi-Agent Simulation. In: IOP Conference Series: Earth and Environmental Science. 2019;328(1): Article No. 012071. https://doi.org/10.1088/1755-315/328/1/012071

13. He S., Shin H.-S., Tsourdos A. Computational guidance using sparse Gauss-Hermite quadrature differential dynamic programming. IFAC-PapersOnLine. 2019;52(12):13-18. https://doi.org/10.1016/j.ifacol.2019.11.062

14. He S., Guo S., Chen, K., Deng L., Liao Z., Xiong F., Yin J. Dataset for reservoir im-poundment operation coupling parallel dynamic programming with importance sampling and suc-cessive approximation. Data in Brief. 2019;26: Article No. 104440. https://doi.org/10.1016/j.dib.2019.104440

15. Fayaed S.S., Fiyadh S.S., Khai W.J., Ahmed A.N., Afan H.A., Ibrahim R.K. Improving dam and reservoir operation rules using stochastic dynamic programming and artificial neural network integration model. Sustainability. 2019;11(19):5367. https://doi.org/10.3390/su11195367

16. Işik H., Sintunavarat W. An investigation of the common solutions for coupled systems of functional equations arising in dynamic programming. Mathematics. 2019;7(10):977. https://doi.org/10.3390/math7100977

17. Jia S., Sun J.Q., Ding Q. Flutter Control of a Two-dimensional Airfoil based on Adaptive Dynamic Programming. In: IOP Conference Series: Materials Science and Engineering. 2019;531(1): Article No. 012033. https://doi.org/10.1088/1757-899X/531/1/012033

18. Kozlowski K.M., Sharma G.K., Chen J.J., Qi L., Osann K., Jing J.C., Ahuja G.S. Dynamic programming and automated segmentation of optical coherence tomography images of the neonatal subglottis: Enabling efficient diagnostics to manage subglottic stenosis. J. Biomed. Opt. 2019;24(9):096001. https://doi.org/10.1117/1.JBO.24.9.096001

19. Durdán, M., Kačur, J., Laciak, M., Flegner, P. Thermophysical properties estimation in annealing process using the iterative dynamic programming method and gradient method. Energies. 2019;12(17):3267. https://doi.org/10.3390/en12173267

20. Wang P., Peng Y., Gao X.-J., Gao H.-H. Train Speed Trajectory Optimization using Dynamic Programming with speed modes decomposition. In: IOP Conference Series: Materials Science and Engineering. 2019;569(4):042019. https://doi.org/10.1088/1757-899X/569/4/042019

21. Ikeda S. Ooka, R. Comparison of metaheuristics and dynamic programming for district energy optimization. In: IOP Conference Series: Earth and Environmental Science. 2019:294(1):9. https://doi.org/10.1088/1755-1315/294/1/012040

22. Narendra Kumar P.V., Chengaiah C., Prasad J.V.K. Fuzzy dynamic programming based solarthermal load scheduling of Andhra Pradesh power generation using Matlab. International Journal of Recent Technology and Engineering (IJRTE). 2019;8(2S8):1242-1247. https://doi.org/10.35940/ijrte.B1046.0882S819

23. Карпов Д.А., Струченков В.И. Динамическое программирование как метод сплайн-аппроксимации в САПР линейных сооружений. Российский технологический журнал. 2019;7(3):77-88. https://doi.org/10.32362/2500-316X-2019-7-3-77-88

24. Романовский И.В. Дискретный анализ. СПб,: Невский Диалект, БХВ – Петербург, 2003. 320 с. ISBN 5-7940-0114-3

25. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: КноРус, 2010. 191 с. ISBN 978-5-406-00682-5

26. Косоруков О.А., Мищенко А.В. Исследование операций: Учебник для вузов. М.: Экзамен, 2013. 445 c. ISBN 5-94692-363-3

27. Струченков В.И. Использование параболических сплайнов в САПР линейных сооружений. Российский технологический журнал. 2018;6(1):40-52. https://doi.org/10.32362/2500-316X-2018-6-1-40-52