Исследование операций. Линейное, динамическое программирование



         

Исследование операций - часть 88


В этих случаях над нами повисает, по меткому выражению Р. Беллмана, «проклятие многомерности» — бич не только метода динамического программирования, но и всех других методов оптимизации. Обычно задачи динамического программирования решаются не вручную, а на ЭВМ, однако многие такие задачи не под силу даже современным машинам. Поэтому очень важно уметь правильно и «скромно» поставить задачу, не переобременяя ее лишними подробностями, упрощая елико возможно описание управляемой системы и вариантов управления. Так что в методе динамического программирования очень многое зависит от искусства и опыта исследователя.

Вторая задача после описания системы и перечня управлений — это членение на шаги (этапы). Иногда (на счастье) оно бывает задано в самой постановке задачи (например, хозяйственные годы в экономических задачах), но часто членение на шаги приходится вводить искусственно как мы сделали, например, в задаче 1 § 13. Если бы мы в этой задаче не ограничились самым примитивным случаем всего двух управлений («с» и «в»), то было бы удобнее членение на шаг произвести иначе, например, считая за «шаг» переход с одной прямой, параллельной оси ординат, на другую. Можно было бы вместо прямых рассмотреть окружности с центром в точке А или же другие кривые. Все такие способы выбора наивыгоднейшего пути неизбежно ограничивают выбор возможных направлений. Если за «шаги» считать переходы с одной прямой, параллельной оси ординат, на другую, то здесь множество возможных управлений не предусматривает «пути назад», т. е. с более восточной прямой на более западную. В большинстве задач практики такие ограничения естественны (например, трудно себе представить, чтобы наивыгоднейшая траектория космической ракеты, пущенной с Земли, на каких-то участках включала движение «назад», ближе к Земле). Но бывает и другая обстановка. Например, путь по сильно пересеченной местности («серпантинная» дорога в горах) часто «петляет» и возвращается ближе к исходному пункту. При постановке задачи динамического программирования, в частности при выборе системы координат и способа членения на шаги, должны быть учтены все разумные ограничения, накладываемые на управление.




Содержание  Назад  Вперед