Preview

Вестник Воронежского государственного университета инженерных технологий

Расширенный поиск

Поиск всех решений задачи динамического программирования в случае совпадения их многкритериальных оценок

https://doi.org/10.20914/2310-1202-2020-1-398-403

Аннотация

Среди математических методов, используемых в экономике, видное место занимает метод динамического программирования, с помощью которого организуется оптимальное управление многостадийными процессами. Недостатком этого метода является невозможность вычисления всех решений задачи при совпадении их критериальных оценок. Факт существования нескольких оптимальных траекторий многошагового процесса может означать, что задача поставлена не вполне корректно, в том смысле, что назначенные критерии не полно характеризуют исследуемую систему. Это означает, что традиционный метод динамического программирования необходимо доработать на случай существования нескольких оптимальных траекторий с одинаковым значением критерия. В данной статье предлагается наиболее общий вариант такой доработки, а именно, обобщению подвергается многокритериальная численная схема. Для более наглядного представления выкладок и результата исследования дискретную задачу динамического программирования будем описывать в терминах теории графов. В этом случае она сведется к задаче поиска оптимального пути на ориентированном графе. Для ее решения предлагается трехэтапный алгоритм, в состав которого включены следующие шаги. Первый этап – построение оптимальных критериальных оценок для путей из начальной вершины во все остальные. Для выполнения этого этапа наиболее универсальным методом является многокритериальный вариант метода Форда–Беллмана. Второй этап – построение графа оптимальных путей. В исходном графе отбираются дуги, составляющие часть оптимальных путей. Из них затем с помощью оригинального алгоритма формируется подграф, в котором все пути оптимальны. Аналитически доказывается, что данный алгоритм дает верный результат (корректен). Третий этап – перебор всех путей в построенном подграфе. Проведенные численные эксперименты показали, что предложенный трехэтапный метод эффективно работает на ориентированных графах любого типа в достаточно большом диапазоне размерности. Предложенный алгоритм с минимальными изменениями может быть использован для решения произвольной дискретной задачи динамического программирования.

Об авторах

Ю. В. Бугаев
Воронежский государственный университет инженерных технологий
Россия
д.ф.-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия


Л. А. Коробова
Воронежский государственный университет инженерных технологий
к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия


И. Ю. Шурупова
Военный учебно-научный центр военно-воздушных сил «Военно-воздушная академия» им. проф. Н.Е. Жуковского и Ю.А. Гагарина, ул. Старых Большевиков
к.ф.-м..н., преподаватель, кафедра математики, ул. Старых Большевиков, 54 «А», г. Воронеж, 394064, Россия


Список литературы

1. Тарасенко А.В., Егорова И.Л. Принцип оптимальности Беллмана в задаче оптимального распределения средств между предприятиями на расширение производства // Вестник университета. 2019. № 10. С. 132–138.

2. Параев Ю.И., Грекова Т.И., Полуэктова К.О. Оптимальное управление односекторной экономикой при случайном изменении фондовооруженности труда // Вестник томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 42. С. 23–29.

3. Скворцов Ю.С., Рындин Н.А., Амоа А.Ж.К.К. Модель динамического севооборота на основе уравнения Беллмана с конечным горизонтом // Моделирование, оптимизация и информационные технологии. 2019. Т. 7. № 1 (24). С. 449–458.

4. Катаев А.В., Катаева Т.М. Сетевая бизнес-модель развития регионального промышленного комплекса в условиях цифровизации // Вестник Таганрогского института управления и экономики. 2019. № 2 (30). С. 26–28.

5. Si Y., Yang W., Zhou H. A simulation analysis on regional logistics development based on system dynamics: The case of Yunnan province // 5th International Conference on Industrial Engineering and Applications (ICIEA). Singapore. 2018. P. 560–564.

6. Castellacci F., Natera J.M. The dynamics of national innovation systems: A panel cointegration analysis of the coevolution between innovative capability and absorptive capacity // Research Policy. 2013. V. 42. № 3. P. 579–594.

7. Uriona-Maldonado M., Grobbelaar S.S. Innovation system policy analysis through system dynamics modeling: A systematic review // Science and Public Policy. 2019. V. 46. № 1. P. 28–44.

8. Ferraz J.C., Coutinho L. Investment policies, development finance and economic transformation: Lessons from BNDES // Structural Change and Economic Dynamics. 2019. V. 48. № C. P. 86–102.

9. Valencic R., Wawrosz P. Limits of neoclassical utility theory and some possible ways how to overcome them // Journal of International Scientific Publications Volume. 2016. № 10. P. 23–31.

10. Бугаев Ю.В., Коробова Л.А. Использование аппарата двойственности в задаче о назначениях на сетевой модели // Современные методы прикладной математики, теории управления и компьютерных технологий (ПМТУКТ2019): сб. тр. XII междунар. конф. 2019. С. 100–104.

11. Блинов И.В., Бугаев Ю.В., Чикунов С.В. Обобщение алгоритма Флойда-Уоршалла на случай нескольких критериев // Вестник Тамбовского государственного технического университета. 2009. Т. 15. № 4. С. 885–892.


Рецензия

Для цитирования:


Бугаев Ю.В., Коробова Л.А., Шурупова И.Ю. Поиск всех решений задачи динамического программирования в случае совпадения их многкритериальных оценок. Вестник Воронежского государственного университета инженерных технологий. 2020;82(1):398-403. https://doi.org/10.20914/2310-1202-2020-1-398-403

For citation:


Bugaev Y.V., Korobova L.A., Shurupova I.Y. Search for all solutions to the dynamic programming problem if their multicriteria estimates coincide. Proceedings of the Voronezh State University of Engineering Technologies. 2020;82(1):398-403. (In Russ.) https://doi.org/10.20914/2310-1202-2020-1-398-403

Просмотров: 520


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-910X (Print)
ISSN 2310-1202 (Online)