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

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

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

Рассмотрим пример многошаговой операции планирования хозяйственной деятельности объединения (группы) промыш­ленных предприятий Пi, П₂, П_k на некоторый период вре­мени Т, состоящий из m хозяйственных лет.

Предположим, что в начале периода планирования на раз­витие группы предприятий выделены капитальные средства в размере К₀, которые предназначены для расходования в процессе функционирования системы. Эти средства определенным образом должны быть распределены между предприятиями рассматри­ваемой группы. Считается, что предприятие за год прино­сит доход, величина которого зависит от вложенных средств. В начале каждого хозяйственного года сумма имеющихся средств должна быть перераспределена между предприятиями — каждому предприятию выделяется определенная доля средств.

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

Приведенный пример является типичной задачей динами­ческого программирования, поскольку здесь рассматривается управляемый процесс. Управление состоит в распределении и перераспределении средств в ходе процесса. Шагом управления является выделение определенных средств каждому предприя­тию в начале хозяйственного года. Математическая формулировка задачи выглядит следующим образом.

Предположим, что в начале некоторого года / предпри­ятиям П₁, П₂, П_к выделяются соответственно средства Х_i1, Х_i2,… X_ik. Совокупность этих значений представляет собой не что иное, как управление на шаге i:

Ui=(X_i1, Х_п,…, Х_!к).

А управление операцией в целом выражается как совокупность всех шаговых управлений:

U =(U₁, U₂,…U_m).

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

W = W(U) = W(U₁, U₂,..,U_m).

Возникает вопрос: как выбрать пошаговые управления U₁ U₂, U_m, чтобы величина показателя эффективности была наибольшей (максимальной) из всех возможных?

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

u = (u₁,и₂…,и_т).

Задача оптимизации управления выглядит следующим образом: определить оптимальное управление на каждом шаге процесса u_i (i= 1, 2, т) и, следовательно, оптимальное управление всей операцией и.

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

W = w₁ + w₂ + … + w_m

где w, — доход от всей системы за год i.

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

Рассмотрим задачу динамического программирования в общем виде. Предположим, что исследуется операция с аддитив­ным показателем эффективности, состоящая из некоторого количества (т) шагов. Пусть на каждом шаге используется некоторое управление U_i и требуется определить оптимальное управление

u = (u₁,и₂…,и_т).

при котором показатель эффективности W = w₁ + w₂ +... + w_m становится максимальным.

Поставленную задачу можно решать разными способами:

1) сразу искать оптимальное управление для всего периода;

2) строить его постепенно, шаг за шагом, таким образом, что на каждом этапе расчета оптимизируется только один шаг процесса.

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

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

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

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

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

Далее будем исходить из того, что условное оптимальное управление известно на каждом шаге, тем самым нам 'извест­но, что делать дальше (или как планировать) при любом состоя­нии операции к началу каждого шага. Тогда можно определить уже не «условное», а истинное оптимальное управление на каждом шаге.

В самом деле, предположим, что нам известно начальное состояние процесса (операции), обозначим его S₀. Мы знаем, что делать на первом шаге — нужно использовать то условное оп­тимальное управление, которое выработано для первого шага при условии, что в начале было состояние S₀. В результате выпол­нения этого управляющего воздействия оптимизируемая система перейдет после первого шага в некоторое состояние S₁ но для этого состояния уже известно условное оптимальное управление на втором шаге и т.д. Таким образом, будет найдено оптималь­ное управление процессом

u = (u₁,и₂…,и_т).

приводящее к максимально возможному эффекту W_max.

Приведенное описание показывает, что в процессе оптими­зации управления методом динамического программирования многошаговый процесс выполняется дважды:

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

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

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