Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

1.1.    основные понятия и постановка задачи

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

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

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

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

составление календарных планов ремонта и обновления технологического оборудования на предприятии;

управление запасами сырья и готовой продукции на предприятии для обеспечения его бесперебойной работы;

проектирование дороги минимальной стоимости в условиях сложного рельефа местности;

загрузка транспортного средства предметами различных типоразмеров с целью перевозки груза максимальной стоимости;

определение наиболее экономичного режима полета летательного аппарата.

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

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

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

Состояние управляемой системы S может меняться под влиянием различных факторов. Наиболее важную роль среди них играет воздействие со стороны управляющего субъекта, осуществляемое путем выбора им надлежащих значений управляющих параметров, называемых иначе управляющими переменными или просто управлениями . В различных конкретных задачах в качестве управлений могут выступать, например, состав работающего оборудования, режим его эксплуатации, количество потребляемых ресурсов, объем подлежащих производству товаров, цены на производимую продукцию, количество принимаемых работников и т. п. Как и для фазовых переменных, будем рассматривать простейший и наименее громоздкий случай только одной управляющей переменной, которую будем обозначать через и. Управляющая переменная и может принимать значения из некоторого множества U допустимых значений, и ЄІІ; множество U задается, как правило, в виде ограничений типа равенств или неравенств.

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

|          xi = f(x0,u),

 

где / — некоторая функция, выражающая закон изменения состояния системы S, определяемая внутренними свойствами системы и внешними условиями ее существования и называемая функцией процесса. Само приведенное уравнение называется уравнением процесса.

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

выражается целевой функцией, или критерием оптимальности z:

z = z(xq, и).

 

Функцию z можно понимать как количественный показатель эффективности управления системой S на рассматриваемом шаге. Например, если функция z представляет собой доход или прибыль, то наибольший интерес представляет ее максимальное значение: z —* max; если же функция z представляет расход, убыток, затраты, издержки, то наибольший интерес представляет ее минимальное значение: z —► min. В отдельных случаях используется запись z —> extr, в которой под символом «extr» подразумевается экстремум, т. е. максимальное или минимальное значение функции.

Основным объектом изучения в данном учебном пособии являются многошаговые процессы, включающие в общем случае некоторое число N шагов. Будем обозначать через і переменный номер шага, который может принимать значения от 1 до N включительно; это обстоятельство будем отмечать записью і = 1,2, ...,N. На каждом шаге процесса управление и может принимать различные значения

щ,и2,.. .,Uff.

Обозначим через состояние системы после шага с номером і; при этом через xq естественно обозначить начальное состояние системы перед первым шагом процесса.

На первом шаге, і = 1, система S под действием управления и переходит из начального состояния жо в состояние х, и при этом достигается экономический эффект, равный z. На втором шаге, і = 2, система S под действием управления и2 переходит из состояния х в состояние Х2, и при этом достигается экономический эффект, равный z2.

Рассуждая аналогично, получим наконец, что на последнем шаге процесса, і = N, система S под действием управления un переходит из состояния ждг-1 в конечное состояние xn, и при этом достигается экономический эффект, равный гдг. Таким образом, при многошаговом процессе система S под действием управлений щ, и2, ■ ■ ■, им переходит последовательно из начального состояния xq в состояния х,х2, ■ ■ ■ ,xn, причем различным наборам управлений соответствуют различные последовательности состояний.

На каждом из шагов процесса фазовые переменные Х{ и управления щ могут принимать значения из соответствующих допустимых множеств: Хі є Хі, иі є Ui. Особую роль среди них играют множество начальных состояний Хо и множество конечных состояний Xn- Состав, вид и свойства этих множеств обычно бывают известны из формулировок соответствующих задач.

Схематически многошаговый процесс представлен на рис. 1.1, где точками отмечены состояния системы и соответствующие значения фазовых переменных (от х0 до ждг), стрелками показаны возможные изменения состояний системы в зависимости от выбора управлений (от щ до un), а также указаны экономические эффекты (от z до zn) на каждом из шагов процесса.

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

Последовательность состояний xq,xi, ... ,xn от начального до конечного называется траекторией системы.

Совокупность значений управления (ui,u2, ■ ■ ■ ,un) называется вектором управляющих параметров, или вектором управлений. (Напомним, что в алгебре вектором называется упорядоченный набор чисел, количество чисел в наборе — размерностью вектора, а сами числа — координатами, компонентами или элементами. Таким образом, (iti, «2, • • •, un) — вектор размерности N.)

Допустимым вектором управляющих параметров, или допустимым управлением, или допустимым решением задачи называется такой вектор управлений (щ, и2, ■ ■ ■, un), под действием которых система S переходит из начального состояния хо є Хо в конечное состояние xn Є Xn-

Функции Zi, і = 1,2, ...,N, выражающие экономический эффект на отдельных шагах процесса, будем называть частными целевыми функциями. Итоговый, результирующий экономический эффект по всему многошаговому процессу будем обозначать через Z и называть целевой функцией, или критерием оптимальности для всего процесса. Функция Z, как правило, определяется значениями частных целевых функций Z{. Простейшим, естественным и наиболее распространенным способом вычисления Z является суммирование частных целевых функций Zi] данный способ построения целевой функции является определяющим для применимости метода ДП, что будет особо оговорено ниже.

Оптимальным вектором управляющих параметров, или оптимальным управлением, или оптимальным решением задачи называется такое допустимое управление (и,и,..., u*N), которое доставляет целевой функции Z максимальное или минимальное значение по сравнению со всеми остальными допустимыми управлениями.

Исследование целевой функции Z на максимум или минимум определяется экономическим содержанием решаемой задачи. Отметим, что свойство допустимости означает фактическую реализуемость управления, а свойство оптимальности — наибольшую целесообразность управления с точки зрения выбранного критерия.

Значение целевой функции Z, которое она принимает при оптимальном управлении (u,U2, ■ ■ ■, u*N), называется оптимальным значением задачи и обозначается через Z*.

Последовательность х^, х,..., x*N оптимальных состояний системы называется оптимальной траекторией.

Как видно из введенных обозначений, символом «*» отмечаются те математические объекты, которые имеют непосредственное отношение к оптимальному решению.

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |