Динамическое программирование

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

Рассматриваются также задачи, в которых динамическое программирование позволяет найти «аналитические» решения, в том смысле, что даёт такой алгоритм обработки данных, который не требует анализа всех промежуточных состояний на всех шагах и соответственно вычисления целевой функции, но позволяет найти оптимальную траекторию.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >