2.2 Постановка задачи динамического программирования. Основные условия и область применения

Пусть рассматривается задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управ­ление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим че­рез W, а показатели эффективности на отдельных шагах — через i=1,m. Если W обладает свойством аддитивности, т.е.

(D1)

то можно найти оптимальное решение задачи методом динами­ческого программирования.

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

Определение D1. Переменная x_i, от которой зависят выиг­рыш на i-м шаге и, следовательно, выигрыш в целом, называ­ется шаговым управлением, i=1,m.

Определение D2.Управлением процесса в целом х называется последовательность шаговых управлений x=(x₁, x₂,…, x_i,…, x_m).

Определение D3. Оптимальное управление x^* — это значение управления x, при котором значение W(x^*) является максималь­ным (или минимальным, если требуется уменьшить проигрыш)

(D2)

где X - область допустимых управлений.

Оптимальное управление х* определяется последователь­ностью оптимальных шаговых управлений.

(D3)

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

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

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

1) возможные исходы предыдущего шага

2) вли­яние управления на все оставшиеся до конца процесса шаги.

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

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