МОДИФИЦИРОВАННЫЙ
АЛГОРИТМ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
О. Ю. Тимофеева, Т. Ю. Рябушкина
(Саратовский государственный технический
университет, Россия)
Среди математических методов оптимизации
важное место занимает метод динамического
программирования [I], который может быть применен
для решения самых разнообразных технических,
экономических, социальных, военных и других
задач.
Основная трудность, возникающая при решении
задач динамического программирования, связана с
необходимостью в процессе вычислений запоминать
большое количество промежуточной информации,
что предъявляет высокие требования к
оперативному запоминающему устройству ЭВМ.
Поэтому основное направление в развитии методов
динамического программирования связано с
преодолением недостатков, обусловленных
проблемой размерности.
Важным способом сокращения объема вычислений
является переход от основной задачи
динамического программирования к двойственной
[2]. Использование двойственной задачи
целесообразно, если объем вычислений в этой
задаче меньше, чем в основной. Кроме того, при
решении на каждом шаге предлагается учитывать не
исходные ограничения на систему, а уменьшенные с
учетом минимальных ресурсов на оставшиеся
подключаемые к вычислениям устройства. Исходя из
двойственности задачи оптимизации, разработан
модифицированный алгоритм ее решения.
Вычислительный алгоритм достаточно простой,
легко программируется на ЭВМ. Разработана
программа оптимизации для персональных
компьютеров типа IBM в среде программирования C++
(версия Borland C++ 4.5 под Windows). Память в процессе
работы выделяется. динамически. Данные могут
вводиться либо из файла, либо в диалоговом
режиме. Решение примеров на ЭВМ типа IBM PC при
одном и нескольких ограничениях показало
практическую реализуемость алгоритма и его
достаточную эффективность.
Результаты научных исследований по
оптимизации структуры электромеханических
систем высоко оценены на государственном
предприятии производственном объединении
«Корпус» и предполагается использовать на
предприятии для оптимизации структуры систем
подобного класса.
ЛИТЕРАТУРА
1. Беллман Р. Динамическое программирование. М-:
Издательство иностранной литературы, 1960.
2. Алексеев О. Г. Комплексное применение методов
дискретной оптимизации. -М.: Наука, 1987. |
