|
Вестник Южно-Уральского государственного университета. Серия «Математическое моделирование и программирование», 2013, том 6, выпуск 1, страницы 124–133
(Mi vyuru38)
|
|
|
|
Программирование
Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями
Е. Е. Иванко Институт математики и механики УрО РАН (г. Екатеринбург, Российская Федерация)
Аннотация:
В работе рассмотрен ряд специфических вариантов метода динамического программирования, используемых для решения минимаксной задачи распределения заданий при условии, что исполнители равноценны, и их порядок не важен. Для разработанных рекурсивных схем метода динамического программирования показана корректность, проводится сравнение вычислительной трудоемкости классической и предложенных схем. Демонстрируется, что использование специфики условия равноценности исполнителей позволяет сократить количество операций в рассмотренном методе динамического программирования по сравнению с классическим более чем в 4 раза, при этом при увеличении размерности исходной задачи относительный выигрыш лишь увеличивается. Одна из использованных техник сокращения вычислений — «встречное» динамическое программирование — по-видимому является общей для целого класса задач, допускающих использование при решении принципа Беллмана. Применение данной техники связано с неполным расчетом значений функции Беллмана в задаче, обладающей некоторой внутренней симметрией, после чего решение исходной задачи получается склеиванием полученных массивов значений функции Беллмана.
Ключевые слова:
метод динамического программирования, распределение заданий.
Поступила в редакцию: 05.07.2012
Образец цитирования:
Е. Е. Иванко, “Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 6:1 (2013), 124–133
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyuru38 https://www.mathnet.ru/rus/vyuru/v6/i1/p124
|
Статистика просмотров: |
Страница аннотации: | 285 | PDF полного текста: | 113 | Список литературы: | 47 | Первая страница: | 2 |
|