Составители:
Рубрика:
243
Глава 7. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ПЛАНИРОВАНИИ
ПРОИЗВОДСТВА И УПРАВЛЕНИИ ИМ
Для решения некоторых типов задач нелинейного программирования может быть
применено динамическое программирование.
Динамическое программирование является сравнительно новым разделом той
отрасли математики, которая занимается анализом и разработкой числовых методов
решения экстремальных задач.
Динамическое программирование возникло в 50-х годах двадцатого столетия в
результате изучения задач, в которых были существенны изменения во времени. Точнее,
возникновение его связано с исследованием некоторых типов многошаговых процессов
управления, особенно многошаговых и стохастических процессов, возникающих в теории
создания запасов.
В дальнейшем аппарат динамического программирования был значительно
усовершенствован и развит для решения задач, не связанных с временными изменениями.
Термин «динамическое программирование» относится скорее к вычислительному
методу, чем к особому типу задач нелинейного программирования.
Таким образом, под динамическим программированием следует понимать
вычислительный метод, опирающийся на аппарат рекуррентных соотношений,
разработанный в значительной степени американским ученым Р.Беллманом.
В этой главе рассмотрена сущность вычислительного метода динамического
программирования и типы задач, которые могут решаться с его помощью.
7.1.Сущность и основные свойства динамического
программирования
Идея метода динамического программирования состоит в том, что отыскание
максимума (или минимума) функции многих переменных заменяется многократным
отысканием максимума (минимума) функции одного или небольшого числа переменных.
Сущность метода динамического программирования сводится к составлению
функциональных уравнений, управляющих процессом, и дальнейшему решению этих
уравнений посредством нестандартных вычислительных процедур.
Функциональным называется такое уравнение, которое выражает функциональную
связь между множеством функций.
Составление функциональных уравнений проводится на основе принципа
оптимальности Р.Беллмана, сущность которого заключается в следующем.
Оптимальная стратегия
1
имеет то свойство, что каково бы ни было начальное
состояние и принятое начальное решение, все остальные решения на последующих шагах
должны составлять оптимальную стратегию относительно состояния, возникшего в
результате первого решения.
Итак, динамическое программирование есть поэтапное планирование
многошагового процесса, при котором на каждом этапе оптимизируется только один шаг.
Задачи, которые могут быть отнесены к задачам динамического
программирования, должны обладать тремя основными свойствами.
Первое свойство задач динамического программирования заключается в том, что
задача (сформулированная в гл.1) может рассматриваться как N-шаговый процесс
принятия решения, в котором на каждом шаге принимается решение о количестве
Страницы
- « первая
- ‹ предыдущая
- …
- 241
- 242
- 243
- 244
- 245
- …
- следующая ›
- последняя »
