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

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

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

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

Обозначим через X,\ управление на к-м шаге (Л=1, 2, ..., л). Пе­ременные Хь удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Хц может быть числом, точкой в л-мерном пространстве, качественным признаком).

Пусть X (Х\, Х2, ..., Х„) — управление, переводящее систему 5 ИЗ СОСТОЯНИЯ М0 в состоянием . Обозначим через м* состояние сис­темы после £-го шага управления. Получаем последовательность СОСТОЯНИЙ М0> Мь ..., М*-!, %..., М„-Ь Мл=М, которую изобразим кружками (рис. 12.1).

Рис. 12.1

Показатель эффективности рассматриваемой управляемой опе­рации — целевая функция — зависит от начального состояния и управления:

0,х). (12.1)

Сделаем несколько предположений.

1. Состояние м* системы в конце к-го шага зависит только от предшествующего состояния м*-1 и управления на к-м шаге Х^ (и не зависит от предшествующих состояний и управлений) Это требование называется “отсутствием последействия”. Сформули­рованное положение записывается в виде уравнений

= Ф*(^-ь Хк), Л = 1,2, п, (12.2)

которые называются уравнениями состояний.

2. Целевая функция (12.1) является аддитивной от показателя эффективности каждого шага [3]. Обозначим показатель эффек­тивности &-го шага через

= Л(5*-ь Хк), к=1, 2, ..., п, (12.3)

тогда ,

п

^ . (12.4)

к=1

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление X, переводящее сис­тему 5[29] из состояния 50 в состояние 1, при котором целевая функция (12.4) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП:

1. Задача оптимизации интерпретируется как п-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага

3. Выбор управления на к-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги {нет обратной связи).

4. Состояние 5* после к-го шага управления зависит только от предшествующего состояния 5^-1 и управления Хк {отсутствие по­следействия).

5. На каждом шаге управление Хк зависит от конечного числа управляющих переменных, а состояние .5* — от конечного числа па­раметров (смысл замечания 5 станет ясным из рассмотренных ниже примеров).

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

12.1.