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



         

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


/p>

 

1) Предметы в таблице 13.4 перенумерованы в порядке возрастания веса; стоимости их также возрастают, что не обязательно, но естественно. Заранее ясно, что загружать машину предметами большого веса и малой стоимости нецелесообразно.

 

§ 14. Задача динамического программирования в общем виде. Принцип оптимальности

Рассмотренные выше простейшие задачи динамического программирования дают понятие об общей идее метода: пошаговая оптимизация, проходимая в одном направлении «условно», в другом — «безусловно». Метод динамического программирования является очень мощным и плодотворным методом оптимизации управления; ему не страшны ни целочисленность решения, ни нелинейность целевой функции, ни вид ограничений, накладываемых на решение. Но в отличие от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре; оно может быть передано на машину только после того, как записаны соответствующие формулы, а это часто бывает не так-то легко.

В этом параграфе мы дадим нечто вроде «сводки советов начинающим» — как ставить задачи динамического программирования, в каком порядке их решать, как записывать и т. д.

Первый вопрос, на который нужно ответить ставящему задачу: какими параметрами характеризуется состояние управляемой системы S

перед каждым шагом? От удачного выбора набора этих параметров часто зависит возможность успешно решить задачу оптимизации. В трех конкретных примерах, которые мы решали в предыдущем параграфе, состояние системы характеризовалось очень небольшим числом параметров: двумя координатами — в первом примере, одним числом — во втором и третьем. Но такие ультрапростые задачи не так уже часто встречаются на практике. Если, как это обычно и бывает, состояние системы описывается многими параметрами (так называемыми «фазовыми координатами»), то становится трудно перед каждым шагом перебрать все их варианты и для каждого найти оптимальное условное управление. Последнее еще больше затрудняется в случае, когда число возможных вариантов управления велико.


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