Глава 1 ЗАДАЧИ УПРАВЛЕНИЯ МНОГОШАГОВЫМИ ПРОЦЕССАМИ И МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|                         XI = 1(хо,и),

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

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

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

Z = z(xо, и).

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

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

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

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

Рассуждая аналогично, получим наконец, что на последнем шаге процесса, г = N, система S под действием управления «дг переходит из состояния ждг-i в конечное состояние ждг, и при этом достигается экономический эффект, равный гдг. Таким образом, при многошаговом процессе система S под действием управлений щ, ■ ■ ■, им переходит последовательно из начального состояния xq в состояния xi,x₂, ■ ■ ■,ждг, причем различным наборам управлений соответствуют различные по­следовательности состояний.

вид и свойства этих множеств обычно бывают известны из формули­ровок соответствующих задач.

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

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

Последовательность состояний жо, х\,..., хм от начального до ко­нечного называется траекторией системы.

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

Допустимым вектором управляющих параметров, или до­пустимым управлением, или допустимым решением задачи называется такой вектор управлений (и\, и₂, ■ ■ ■, им), под действием которых система Б переходит из начального состояния жо Є Хо в ко­нечное состояние Хм Є Хм-

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

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

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

Значение целевой функции которое она принимает при опти­мальном управлении (и\, ■ ■ ■, и^), называется оптимальным зна­чением задачи и обозначается через

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

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

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