Задачи динамического программирования

Динамическое программирование (иначе, «динамическое планирование») представляет собой особый математический метод оптимизации решений, специально приспособленный к многошаговым (или многоэтапным) операциям.

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

Процесс, о котором идет речь, является управляемым, т. е. на каждом шаге принимается какое-то решение, от которого зависит успех данного шага и операции в целом. Управление операцией складывается из ряда элементарных, «шаговых» управлений.

Рассмотрим пример естественно-многошаговой операции О. Пусть планируется деятельность группы (системы) промышленных предприятий на некоторый период времени Т, состоящий из m хозяйственных лет (рис. 3.1).

В начале периода на развитие системы предприятий выделяются какие-то основные средства, которые должны быть как-то распределены между предприятиями. В процессе функционирования системы выделенные средства частично расходуются (амортизируются). Кроме того, каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале каждого хозяйственного года имеющиеся средства могут перераспределяться между предприятиями: каждому из них выделяется какая-то доля средств.

Ставится вопрос: как нужно в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всей системы предприятий за весь период был максимальным?

Рис. 3.1

Перед нами — типичная задаче динамического программирования.

Рассматривается управляемый процесс — функционирование си стемы предприятий. У правление процессом состоит в распределении (и перераспределении) средств. Шагом управления является выделение каких-то средств каждому из предприятий в начале хозяйственного года.

Пусть в начале года предприятиям выделяются соответственно средства:

Совокупность этих значений представляет собой не что иное, как управление на шаге:

Управление U операцией в целом представляет собой совокупность всех шаговых управлений:

Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления U оценивается тем же показателем W, что и эффективность операции в целом. В нашем примере показатель эффективности (целевая функция) представляет собой суммарный доход от всей системы предприятий за лет. Он зависит от управления операцией U, т. q. от всей совокупности шаговых управлений:

Возникает вопрос: как выбрать шаговые управления для того, чтобы величина W обратилась в максимум?

Поставленная задача называется задачей оптимизации управления, а управление, при котором показатель W достигает максимума, — оптимальным управлением. Будем обозначать оптимальное управление (в отличие от управления вообще U) буквой и. Оптимальное управление и многошаговым процессом состоит из совокупности оптимальных шаговых управлений:

Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге и, значит, оптимальное управление всей операцией.

Заметим, что в нашем примере (управление финансированием системы предприятий) показатель эффективности W представляет собой сумму доходов за все отдельные годы (шаги):

где — доход от всей системы предприятий год.

Показатель, обладающий таким свойством, называется аддитивным. Мы будем пока рассматривать только задачи с аддитивным показателем.

Поставим задачу динамического программирования в общем виде. Пусть имеется операция О с аддитивным показателем эффективности (1.5), распадающаяся (естественно или искусственно) на т. шагов. На каждом шаге применяется какое-то управление. Требуется найти оптимальное управление

при котором показатель эффективности

обращается в максимум.

Поставленную задачу можно решать по-разному: или искать сразу оптимальное управление и, или же строить его постепенно, шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов.

Такая идея постепенной, пошаговой оптимизации процесса и составляет суть метода динамического программирования.

С первого взгляда эта идея может показаться довольно тривиальной. В самом деле, чего, казалось бы, проще: если трудно оптимизировать операцию в целом, то разбить ее на ряд шагов; каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать на каждом шаге такое управление, при котором эффективность этого шага максимальна. Не так ли?

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

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

Но правильным ли будет такое решение сточки зрения операции в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы.

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

Однако из этого правила есть исключение. Среди всех шагов существует один, который может планироваться попросту, без «оглядки на будущее». Какой это шаг? Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т. д.

Поэтому процесс динамического программирования разворачивается от конца к началу: раньше всех планируется последний, шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать разные предположения о том, чем кончился предпоследний а, и для каждого из них найти такое управление, при котором выигрыш (доход) на последнем шаге был бы максимален. Решив эту задачу, мы найдем условное оптимальное управление на шаге, т. е. то управление, которое надо применить, если шаг закончился определенным образом.

Предположим, что эта процедура выполнена и для каждого исхода шага мы знаем условное оптимальное управление на шаге и соответствующий ему условный оптимальный выигрыш. Теперь мы можем оптимизировать управление на предпоследнем, шаге. Сделаем все возможные предположения о том, чем кончился предпредпоследний, шаг, и для каждого из этих предположений найдем такое управление на шаге, чтобы выигрыш за последние два шага (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управление на -м шаге, и т. д.

Одним словом, на каждом шагу ищется такое управление, которое обеспечивает оптимальное продолжение процесс а относительно достигнутого в данный момент состояния. Этот принцип выбора управления называется принципом оптимальности. Само управление, обеспечивающее оптимальное продолжение процесса относительно заданного состояния, называется условным оптимальным управлением на данном шаге.

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

Действительно, пусть нам известно начальное состояние процесса, обозначим его Теперь мы уже знаем, что делать на первом шаге: надо применить условное оптимальное управление, выработанное нами для первого шага, относящееся к состоянию. В результате этого управления после первого шага система перейдет в другое состояние но для этого состояния мы снова знаем условное оптимальное управление на втором шаге и т. д. Таким образом мы найдем оптимальное управление процессом

приводящее к максимально возможному выигрышу,

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговой процесс «проходится» дважды:

— первый раз — от конца к началу, в результате чего находятся условные оптимальные управления на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса;

— второй раз — от начала к концу, в результате чего находятся (уже не условные) оптимальные шаговые управления на всех шагах операции.

Эти общие правила станут более понятными на конкретном примере.