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

На правах рукописи

БЕЛЫШЕВ Дмитрий Владимирович

АЛГОРИТМЫ УЛУЧШЕНИЯ ДИСКРЕТНОГО УПРАВЛЕНИЯ С ВРЕМЕННЫМ РЕГУЛЯТОРОМ И ИХ ПРОГРАММНАЯ

РЕАЛИЗАЦИЯ

Специальность 05.13.11— математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Переславль-Залесский - 2004

Работа выполнена в Институте программных сиситем Российской академии наук

Научный руководитель:

доктор технических наук, профессор В.И. Гурман Официальные оппоненты:

доктор технических наук, профессор Л.Н. Никифорова кандидат технических наук М.Ю. Ухин

Ведущая организация:

Институт проблем управления Российской академии наук

Защита состоится 18 июня 2004 г. в 1400 час. на заседании диссертационного совета Д 002.084.01 в Институте программных систем РАН по адресу: 152020, г. Переславль-Залесский, м. «Ботик», ИПС РАН.

С диссертацией можно ознакомиться в библиотеке Института программных систем РАН.

Автореферат разослан « » мая 2004 г.

Ученый секретарь диссертационного совртя.

кандидат технических наук

Общая характеристика работы

Актуальность темы. Одной из фундаментальных проблем современности является задача оптимального управления. Разработано множество методов и приемов для улучшения управления динамическими системами, тем не менее, работа по созданию новых алгоритмов не теряет своей актуальности, поскольку практические задачи настолько разнообразны, что невозможно предложить единственный-универсальный подход, который был бы одинаково эффективным для всех возможных постановок.

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

В работах В.Ф. Кротова сформулирована общая схема вычислительной процедуры и предложен алгоритм улучшения управления, в котором итеративным образом ищется функция Кротова и соответствующее ей синтезирующее управление. Дискретный вариант данного алгоритма описан в работах В.И. Гурмана, В.А. Батурина, Д.Е. Урбановича. Там же предложены его варианты в виде алгоритмов первого и второго порядка, а также способ регуляризации задачи путем добавления к основному функционалу нормы близости улучшаемого решения к улучшенному. Данный способ является универсальным, однако он сложен в настройке и требует больших вычислительных затрат. Для непрерывных систем возможен и используется другой способ локализации — варьирование управления на достаточно малом временном интервале, который выступает в качестве регулятора алгоритма. К сожалению, для дискретной системы второй способ непосредственно неприменим.

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

3 | РОС НАЦИОНАЛ»"«»! I

особых механизмов для их выбора и комбинирования в процессе решения задачи. Такой подход называется мультиметодным, описание его применения есть в работах А.И. Тятюшкина, А.Ю. Горнова. Тем не менее, нет достаточно проработанных методик, позволяющих использовать знания о свойствах решаемой задачи и применяемых алгоритмов для повышения эффективности решения задачи. Всем этим и объясняется актуальность выбранной темы.

Цель работы и задачи исследования. Целью диссертационной работы является создание на основе достаточных условий оптимальности В.Ф. Кротова группы итерационных алгоритмов решения задач оптимального управления для дискретных систем и их программная реализация.

Для достижения поставленной цели в работе решаются следующие задачи:

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

• разработка базового алгоритма второго порядка и его модификаций;

• исследование свойств базового алгоритма на предмет релаксационности и сходимости;

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

• создание программных комплексов на основе предложенных принципов;

• решение тестовых и актуальных прикладных задач.

Методы исследования. В работе для проведения исследований были использованы методы теории управления и теории достаточных условий оптимальности Кротова, принцип расширения, методы теории экспертных систем, концепции объектно-ориентированного программирования и баз данных.

Научная новизна. Основные научные результаты, полученные автором:

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

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

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

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

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

Реализация и внедрение результатов работы. На базе полученных алгоритмов разработан программный комплекс, использовавшийся для сценарных расчетов в социо-эколого-экономическом моделировании региона Пере-славля-Залссского и Сумской области (Украина), и проведен расчёт оптимальных стратегий их развития в рамках международного проекта TACIS АСЕ Project P95-4097-R, а также РФФИ №№ 97-01-00109, 02-01-06471,03-01-00414-а. Результаты этих исследований отражены в ряде публикаций, в том числе в монографии «Моделирование социо-эколого-эконом и ческой системы региона» Под редакцией В.И. Гурмана, Е.В. Рюминой, Наука, 2001.

Предложенный принцип построения многометодных процедур лёг в основу программного комплекса, реализованного в рамках проекта РФФИ № 00-01-00731.

Разработанное программное обеспечение используется для исследовательских и учебных целей при решении задач оптимального управления, в рамках учебных курсов «Методы оптимизации» и «Оптимальное управление» в Университете города Переславля.

Апробация работы. Результаты работы обсуждались на семинарах Исследовательского центра процессов управления Института программных систем РАН и кафедры системного анализа Университета города Переславля. В виде докладов результаты были представлены на научных конференциях:

• международной конференции «Интеллектуальное управление: Новые интеллектуальные технологии в задачах управления (ГС!Т'99)» (Переславль-Залесский, 1999);

• международной конференции IFIP WG2.5 WoCo 8 «Software Architectures for Scientific Computing Applications» (Ottawa, Canada, 2000);

• школе-семинаре «Понтрягинские чтения» (Воронеж, 2001);

• IV Всероссийской научной mtemet-конференции «Компьютерное и математические моделирование в естественных и технических науках» (Тамбов, 2002);

• международном симпозиуме «Обобщенные решения в задачах управления» (Переславль-Залесский, 2002);

• школе-семинаре «Понтрягинские чтения — XIII» (Воронеж, 2002).

Публикации. По результатам исследований опубликовано 14 печатных работ. Из них автору лично принадлежат работы [4-7,13], остальные опубликованы в соавторстве. В монографии [2] автором выполнены сценарные расчёты социо-эколого-экономической модели и описан программный комплекс; в работах [8-11] автором предложен принцип построения интеллектуальных многометодных процедур оптимального управления и дано описание архитектуры программного комплекса, реализующего данный принцип; в работе [12] автору принадлежит вывод и описание алгоритма поиска оптимального управления дискретной системой; в работе [14] автором решена задача поиска оптимального управления для предложенной модели; в работе [1] автором реализован алгоритм и выполнены расчёты на основании полученных начальных приближений.

Структура и объем работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы, содержащего 73 наименования и 2-х приложений, объем работы составляет 93 страницы.

Содержание работы

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

Глава 1. Описание метода улучшения и вывод базового алгоритма Формулируется дискретная задача оптимального управления со свободным правым концом и производится вывод общего метода её решения, основанного на теореме о достаточных условиях оптимальности Кротова. Предлагается

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

Рассматривается дискретная управляемая система и функционал как функция ее конечного состояния

Функция /(£, х, и) при каждом ¿6 Т и функция F(x) непрерывны вместе со своими производными до второго порядка. В множестве D возможных решений т — (Т,x(t),u(t)) системы (1) имеется элемент ттг1, требуется решить задачу улучшения: найти элемент m11 € D, такой что I(mu) < 1(т1). При последовательном решении задач улучшения строится итеративный процесс оптимизации рассматриваемой модели. Учет ограничений, отличных от указанных, производится но методу штрафов.

Общие конструкции метода улучшения управления приведены в работе [Гурман, 1985], где по принципу локализации с использованием регулятора типа нормы, осуществляется поиск т" как аппроксимации локальной мини-мали в окрестности функционала

где определяется уравнением

которое присоединяется к исходной системе (1). Обозначим

На основе теории Кротова рассматриваемая задача со связями (1), (2) сводится к задаче минимума функционала без связей (обобщенного Лагранжиана)

R(t,x,u) = ip(t + 1 ,f(t,x,u)) - <p(t,x), G(x) = Fa(x) + <f(tF,x) + const,

<p(t,x) — функция Кротова, которая задастся как линейно-квадратичная

ip{t, х) = Tp°(t) Дх° + ipT(t) Дх + ^ AxTa(t) Дх,

где Дх = х — xx(i), Дх° = х° — x0'(i), Ди = и — v}(t). В этих терминах получаются основные соотношения:

где Na = Нии+£а(Ш)/и-аЕ^ _Я = ^+l)f(t,x,u)+^(x°+\||Ди||2), Р = /Jcr(£ + l)/u + Нхи. Значения выражений, зависящих от х и и, подсчи-тываются при x'(i) и v}(t). Выражение Na — это расшифровка Ruu, Ruu < О при надлежащем выборе а.

Однако поиск удачного а представляет определенную проблему из-за плохой «осязаемости» данного регулятора. В связи с этим предлагается второй регулятор — временной интервал. Варьирование управления по правилу (6) можно производить не на всем дискретном интервале Т — tp, а на любой его части, вплоть до одного момента, а на оставшейся части управление оставлять неизменным, равным v}(t). При этом соответствующая накопленная вариация траектории будет меньше полной, что только улучшит аппроксимацию условий оптимальности, предусмотренную в соотношениях алгоритма.

Назначение временнбго регулятора — сделать множество моментов времени, в которых варьируется управление, таким, что результирующая траектория x(t) окажется близкой к исходной х'(£), оставаясь в сё окрестности. Однако простого выделения подмножества из заданного может ока-

заться недостаточным, даже если это подмножество минимальное, состоящее из одного момента соответствующая вариации управления вариа-

ция траектории может оказаться слишком большой.

Для преодоления этого препятствия рассматривается непрерывный интервал [tq,tq + 1]. Искусственно вводится промежуточная точка t4g = tq + в, в € [0,1], рис. 1. В результате получается виртуальная система, где множество временных отсчётов имеет вид Т9 = {tq$, ig + l,..., if}. Чтобы избежать дробного шага в полученной системе, производится перенумерация отсчётов, для этого вводится зависимость t(r), т £ {т/,т/ + 1,...,туг}, где i(r/) = t4$, t(j[ + 1) = tq + 1,... Система (1) доопределяется в точке t4e как:

х(т/ + 1) = (1 - в)/(т1,х(т1),и(т1))+0х(т1 + 1), (7)

Рис. 1: Схема временного регулятора

В остальных временных моментах вид системы (1) не меняется. За начальный момент времени принимается т/ = t4o, а за начальное состояние исправление

При в —» 1 левая граница придвигается к ¿„ + 1 и Дx(tao) 0. Поскольку для любого выбора множества варьирования необходимо просчитывать систему (3) - (6) «справа налево» до левой границы множества Т,;. то целесообразно данное множество выбирать примыкающим к tf, с тем, чтобы вычисления сосредоточить лишь в тех узлах, где ожидаются улучшающие вариации.

В результате разработан базовый алгоритм улучшения. Разрешается цепочка (1) на Т при заданном u'(i) и x'(i/) = X/, откуда определяется т1 =

Задается временной регулятор Рассматриваются подзадачи на Tg = {tq, tq + 1,..., tp}.

А1. Разрешается цепочка (1) на Т9 при x(t4) = x}{t4), вычисляется mj = (Т q,x\t),u\t)).

А2. Решается «справа налево» система (3)-(6) и определяются f(i)-Далее возможны три случая: 1°. Hu(t,xl(t),Tl>(t+1)^(1)) ¿0.

2°. Hu{t,xl{t),^{t + lj.uty)) = 0, существует Г € Т„ что при t = t' нарушается неравенство

3°. tfu(i, sty). i>(t + 1), «'(О) = 0 и ^a(^) < 0.

Случай 1°.

81.Разрешается цепочка (1) = Ди(£, Ах^)), £ ё Т^, где

Ди(£) определяется по формуле (б), находится т^(£).

82. Если 1(т> /(ш^), то временной отрезок + 1} дробится и левая граница сдвигается вправо £/ = Переход на Шаг А1. х(£д0), и(£чв) и К^в,') определяются в соответствии с описанием, данным выше.

Иначе итерация закончена; полагается т^ = т'1, переход на Шаг А1. Случай 20. Используется регулятор а € [0,1].

С1. Решается «справа налево» система (3) - (6), параметр а задается так, чтобы при выполнялось

С2. Вычисляется значение Ди(£(7,') из условия

ЫаАи^,,, Ах) = 0, |Дк(£(„Д1)| = £ > 0. (8)

СЗ. Разрешается цепочка (1) при и(Ь) = и}(Ь) + Ди(£, Дз;(£)), Аи определяется по формуле (6), при и по (8) при находится

С4. Если /(ш11) > /(яг1), то £ уменьшается, переход к шагу СЗ.

Иначе итерация закончена; полагается т^ = т^, а = 0, переход на А1.

Случай 3°. Соответствует выполнению условий локального минимума, при этом если £9 > £/, то уменьшается левая граница временного интервала: = Ьч — 1, переход к шагу А1. Если же = £/, то задача полностью решена.

Глава 2. Свойства и модификации базового алгоритма В главе исследованы с использованием гомотопического метода свойства ре-лаксационности и сходимости базового алгоритма, предложены четыре модификации алгоритма второго и первого порядков, рассмотрены примеры использования базового алгоритма и модификаций на тестовых задачах, приведены рекомендации по настройке алгоритмов и учёту ограничений, в том числе по повышению эффективности взаимодействия с методом штрафов.

Задача (1) погружается в однопараметрическое семейство подзадач (Ю,/)$, определяемых интервалом Т9, при этом его левая граница £/9 может варьироваться в пределах непрерывного интервала + 1]. В силу того, что рассматривается дискретная задача со свободным правым концом, и значение х(Ьр), а следовательно и !(£/•)), определяется программой управления

u(t), исходную задачу можно представить в виде безусловной конечномерной задачи вида J(u(tq), u(ig+l), ■■ ■, u(tp—l))- Таким образом, возможен переход к семейству конечномерных задач J(w,q), которое эквивалентно исходному.

Рассматривается функционал J(u;qg), где qg Е [<?, 9+ 1]. Предполагается, что на интервале [17, q + 1] ф у н к ц и о pep ы вен по и для любого

вместе с градиентом Пусть при каждом функци-

онал J(w,qe) имеет экстремалы^епрерывно зависящую от параметра qg. Однопараметрическое семейство J(u\qg) называется невырожденной деформацией функционала J\(u) = J(u\q+ 1) в функционал J(\(u) = J(w,q). если при каждом qg 6 [g, q + 1] нет отличных от и'Й критических точек функционала J(w,qe). Тогда, согласно гомотопическому методу [Емельянов, Коровин, Бобылёв, 2001], справедлива следующая теорема.

Теорема 1 Пусть существует невырожденная деформация функционала Jl в функционал Ju. Пусть критическая точка и\ функционала J\ является точкой локального минимума. Тогда точка uj является точкой локального минимума функции Jq.

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

Разработан спектр модификаций. Поиск глобального оптимума на первом шаге. В данной модификации отдельно рассматривается первый шаг алгоритма, где решается задача (1) на врсменнбм промежутке, состоящем их двух точек: Т = {if — Здесь явно используется уравнение Беллмана

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

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

при а(Ь) ^ 0. Система (3) - (4) преобразуется к системе вида

т = нх = £(их1(г),и№№ +1).

а формула для подсчёта приращения по управлению

Алгоритм улучшения без пересчёта вспомогательных функций. При реализации алгоритма наибольшие вычислительные ресурсы требуются при решении матричных задач для расчета функций -ф(Ь) и Следующие модификации позволят уменьшить количество таких вычислений.

В базовом алгоритме ставится условие на вычисление ф(Ь) и После

первого расчёта ^(О и сг(£) происходит в ы ч и сДщ(б, и определя-

ются новые состояние и управление системы: хи(4),ии(4). В случае, если улучшение произошло, при следующей итерации не пересчитываются, а используются прежние значения. Пересчёт происходит, если на предыдущей итерации не произошло улучшения.

Алгоритм улучшения по направлению. Данная модификация также направлена на уменьшение количества вычислений. В соответствии с алгоритмом улучшения первого или второго порядка находится направление дальнейшего улучшения и получается в виде линейной комбинации

затем решается задача минимизации относительно

ип(£) = up.it), Р* = а^гшп

По достижении минимума вычисляется новое направление улучшения. Если улучшение прекращается, происходит переход на Шаг А1, где полученное управление принимается за новое начальное приближение.

Эффективным способом учета ограничений является метод штрафных функций. Наиболее удобным классом для использования в оптимизационных алгоритмах рассматриваемого типа являются экспоненциальные штрафные функции вида РтаХ = рт{п — для ограничений типа

неравенств: х < хтах, х > хт{п и функции вила ред = ■у(х-х)'2, ред = ~/\х-х\ для ограничений типа равенств: х = х. Основные трудности, возникающие при применении метода штрафных функций, связаны с неудачным масштабированием. Для более эффективной манипуляции штрафными коэффициентами нами используется следующие принципы:

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

• по мере приближения к локальному оптимуму необходимо увеличивать значение штрафа.

Для каждой из рассмотренных модификаций приводятся результаты расчётов для тестовых задач. Производится сравнение модификаций с базовым алгоритмом. Оценивается точность решения задачи, количество выполненных итераций и время работы. Во всех случаях для предложенных задач модификации базового алгоритма демонстрируют лучшее время: от 10% для методов, направленных на сокращение вычислений вспомогательных конструкций, до 70% для алгоритма первого порядка. Аналогичное сравнение проводится и для иллюстрации предложенных принципов управления штрафными коэффициентами. При анализе решения задачи с фиксированными штрафными коэффициентами и с динамически изменяемыми значениями штрафа последний вариант демонстрирует 25% выигрыш по времени.

Глава 3. Программное обеспечение

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

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

С использованием этого комплекса решён ряд учебных и тестовых задач, в том числе рассмотренные в работе примеры. Элементы этого программного приложения использовались в учебном процессе в курсах «Оптимальное управление» и «Методы оптимизации» в Университете города Переславля в 2002-2004 годах. Кроме того, на его базе проводились экспериментальные расчеты в рамках проекта РФФИ № 03-01-00414-а «Магистрали в задачах оптимального управления».

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

Рис. 2: Программный комплекс для решения задач со сложной структурой данных

трудоёмко, что является расплатой за удобство и универсальность. При необходимости оперировать большими объемами сложно структурированных данных (размерности векторов 20-30) и использовать сложную логику, интерпретатор встроенного языка Maple начинает требовать очень серьезных ресурсов и выполнять операции недопустимо медленно, кроме того, оказалось серьезной проблемой хранение и манипулирование такими данными.

Исследования сложных региональных моделей выявили необходимость уделить особое внимание таким возможностям как:

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

2) произвольная модификация модели и множества данных без остановки системы и перекомпиляции;

3) использование разных методов при решении задач и их частей;

4) генерация различных версий расчётов, их сравнение и анализ.

С учетом перечисленных требований разработана архитектура и реализован исследовательский прототип программного комплекса поиска оптимального управления (рис. 2). Он был использован в рамках проекта TACIS АСЕ Project P95-4097-R для сценарных расчетов при исследовании стратегии развития Персславского региона и Сумской области (Украина). Всего было исследовано пять различных сценариев. Результаты рачетов отражены в монографии [2] и в работе [1].

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

Для более полного анализа доступной информации о задаче и алгоритмах предложен подход, основывающийся на построении цепочек алгоритмов, содержащих в себе наряду с вычислительными процедурами интеллектуальные операторы, которые позволяют активно управлять ходом решения задачи (интеллектуальный многометодный подход). Принцип их функционирования заключается в анализе текущего состояния процесса оптимизации: учёте свойств окрестности текущего приближения (овражность, линейность), скорости сходимости текущего алгоритма, точности приближения, удовлетворения ограничений и т.д., и выработке решения о дальнейших шагах оптимизации. Наиболее перспективным средством разработки операторов на наш взгляд является использование экспертных систем. Существующие сегодня инструментальные средства (например, разработка ИПС РАН — SIMER + MIR) применимы для реализации предлагаемого типа операторов. В реализованном программном комплексе используется два типа операторов: конкурсный отбор (поочерёдный запуск с поиском наилучшего) и сопоставление свойств алгоритмов и задач на основе их паспортов (перечней свойств). Программный комплекс выполнен в клиент-серверной технологии с wcb-интср-фейсом пользователя.

Глава 4. Приложение к задаче оптимизации стратегии развития региона. В главе приведены результаты, полученные при исследовании со-цио-эколого-экономической модели региона на примере региона Переславля.

Рассматриваемая модель, описывается следующими соотношениями [2]:

Здесь у, z, d — соответственно, векторы выпусков продукции по отраслям, активного природо-социовосстановления, активных инноваций; с — конечное потребление; (к, к\ к*), (Г(&), Гг(£г), Г*^)), (и, иг, и*), (6, 6г, 5а) - основные фонды, мощности, инвестиции и темпы амортизации в экономическом, природо-социовосстановительном и инновационном секторах; р — матрица-строка цен; г — вектор индексов состояния природной среды и социума; в — вектор инновационных индексов; — заданная опорная функция, например, получаемая из статистического прогноза; ¡шг, ехг — миграционные потоки загрязнений и ресурсов; А, А*, Ал — матрицы прямых затрат в экономическом, природо-социовосстановительном и инновационном секторах; В, Вг, Вл — матрицы фондообразующих затрат в указанных секторах; C,N — матрицы коэффициентов: прямого воздействия отраслей экономики на природную и социальную подсистемы, взаимовлияния компонентов природной и социальной подсистем; — матрицы коэффициентов воздействия на

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

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

Описана многошаговая процедура оптимизации ряда вариантов расчётов, в том числе приведены результаты вычислений на полной и агрегированной модели. Рассмотрено 5 сценариев развития, и качественно проанализированы и интерпретированы полученные значения. Для агрегированной модели за 23 итерации с использованием модификации алгоритма первого порядка был достигнут приближенный глобальный оптимум (рис. 3) с верхней оценкой

П» П 0р( П тад Пор/

~п:

= 2.5%,

'ор* П

где — истинное оптимальное значение (которое неизвестно).

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

Рис. 3: Изменение функционала агрегированной модели по итерациям

В заключении сформулированы основные результаты, полученные в диссертации.

В приложениях содержатся блок-схемы предложенных алгоритмов, а также акты об использовании реализованного программного обеспечения.

Основные результаты работы

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

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

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

4. Предложены принципы построения интеллектуальных многометодных процедур.

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

6. С помощью разработанных алгоритмов и программного обеспечения проведена серия вычислительных экспериментов над социо-эколого-эконо-мической моделью региона.

Список публикаций по теме диссертации

[1] Белышев Д.В., Шевчук Е.В. Алгоритм и программный комплекс для поиска оптимального управления, Интеллектуальное управление: Новые интеллектуальные технологии в задачах управления (ICIT'99). — Труды Международной конференции. Переславль-Залесский, 6-9 декабря 1999, М.: Наука, Физматлит, 1999, С. 146-150.

[2]Моделирование социо-эколого-экономическоймоделирегиона, Под ред. В.И. Гурмана, Е.В. Рюминой, М.: Наука, 2001, С. 175.

[3] Belyshev D., Gurman V. Software architecture for the investigation of controllable models with complex data sets, The Architecture of Scientific Software, R.F. Boisvert and P.T.P. Tang, eds., Kluwer Academic Publishers, Ottawa, Canada, 2001, C. 317-332.

[4] Белышев Д.В. Алгоритм улучшения управления для дискретных систем, Современные методы в теории краевых задач «Понтрягинские чтения», Воронеж: ВГУ, 2001, С. 18.

[5] Белышев Д.В. Реализация многометодных процедур оптимального управления, Компьютерное и математические моделирование в естественных и технических науках: Материалы IV Всероссийской научной Internet-конференции, Гл. ред. серии проф. А.А Арзамасцев, Вып. 12, ВГУ, ИМФИ ГТУ им. Г.Р. Державина, 2002, С. 3-7.

[6] Белышев Д.В. Многометодные процедуры оптимального управления, Сборник материалов «Понтрягинские чтения - XIII», Воронеж: ВГУ, 2002, С. 20-21.

[7] Белышев Д.В. Итерационный алгоритм второго порядка оптимизации дискретных управляемых систем, Обобщенные решения в задачах управления. Труды международного симпозиума 27-31 августа 2002г, Пе-реславль-Залесский, 2002, С. 225-227.

[8] Белышев Д.В., Гурман В.И. Интеллектуальные процедуры оптимального управления, Автоматика и Телемеханика, № 5, 2002, С. 147-155.

[9] Белышев Д.В., Гурман В.И. Мультиметодные процедуры оптимального управления, Обобщенные решения в задачах управления. Труды международного симпозиума 27-31 августа 2002г, Переславль-Залесский, 2002, С. 131-132.

[10] Белышев Д.В., Гурман В.И. Программный комплекс многометодных ин-теллектуальныхпроцедур оптимальногоуправления, Автоматика и телемеханика, № 6, 2003, С. 60-67.

[11] Белышев Д.В., Гурман В.И. Многометодный подход к оптимизации управления, Математика, информатика: теория и практика. Сборник трудов, Переславль-Залесский: УГП, 2003, С. 130-135.

[12] Белышев Д.В., Саблин М.Ю. Алгоритм второго порядка поиска оптимальногоуправления дискретной системой, Математика, информатика: теория и практика. Сборник трудов, Переславль-Залесский: УГП, 2003, С. 125-129.

[13] Белышев Д.В. Алгоритм улучшения дискретного управления с времен -ным регулятором и его программная реализация, Программные системы: теория и приложения, Т. 2, М.: Физматлит, 2004, С. 349-368.

[14] Белышев Д.В., Соловьева О.В. Анализ инновационных эффектов раз-витиярегиона на социо-эколого-экономическоймодели, Программные системы: теория и приложения, Т. 2, М.: Физматлит, 2004, С. 437-444.

Объем 1,0 п.л. Формат 60 х 84 / 16. Тираж 100 экз. Отпечатано в ИПС РАН

»11684

Введение

1 Описание метода и вывод базового алгоритма

1.1 Постановка дискретной задачи оптимального управления

1.2 Метод улучшения управления с временным регулятором

1.3 Базовый алгоритм улучшения

1.4 Примеры использования базового алгоритма

2 Свойства и модификации базового алгоритма

2.1 Релаксационность и сходимость.

2.2 Поиск глобального оптимума на первом шаге.

2.3 Алгоритм первого порядка.

2.4 Алгоритм улучшения без пересчёта вспомогательных функций

2.5 Алгоритм улучшения по направлению.

2.6 Учёт ограничений и взаимодействие с методом штрафов

3 Программное обеспечение

3.1 Программный комплекс в среде Maple.

3.2 Программный комплекс для решения задач оптимального управления со сложной структурой данных.

3.3 Программный комплекс на основе многометодного интеллектуального подхода.

3.3.1 Принципы построения программного комплекса многометодных интеллектуальных процедур.

3.3.2 Описание системы.

3.3.3 Реализация исследовательского прототипа.

4 Задача оптимизации стратегии развития региона

4.1 Социо-эколого-экономическая модель региона.

4.2 Сценарный анализ и процедура оптимизации.

4.3 Исследование агрегированной модели с использованием магистрального решения. щ 4.4 Сценарные расчеты для многомерной модели.

4.4.1 Сценарии Б и В.

4.4.2 Сценарии Г, Д и Е.

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

Важными для практики являются исследования дискретных моделей управляемых систем. Во-первых, такие модели, часто возникают в изначальных постановках задач; во-вторых, использование компьютерной техники для расчетов в большинстве случаев явно или неявно приводит непрерывные постановки к дискретному виду для применения численных схем. Кроме того, важное преимущество дискретных схем — отсутствие обременительных требований непрерывности и гладкости в общих достаточных условиях оптимальности (Кротова, Беллмана), что значительно расширяет ^ круг их приложений. В частности, существует концепция дискретно-непрерывной (гибридной) системы, которая позволяет трактовать непрерывную систему с дискретным управлением как дискретную и применять соответствующие методы для дискретных систем. Однако в литературе им уделяется значительно меньше внимания, чем непрерывным моделям. Отчасти это объясняется сложившимися традициями исследований по теории управления, берущими начало из классической механики и аналоговой электроники, а отчасти тем обстоятельством, что наиболее распространённые математические методы гораздо хуже адаптированы к дискретным моделям, чем к непрерывным, наделённым хорошими теоретико-функциональными свойствами. Основная же причина такого положения — отсутствие в общем случае дискретного аналога принципа максимума Понтрягина для непрерывных систем [15,54].

Настоящая работа посвящена численным методам оптимального управления. Приведём краткий обзор работ по этой тематике.

Краткий обзор

Впервые численные методы в оптимальном управлении были разработаны в конце 50-х — начале 60-х годов после получения необходимых условий оптимальности JI.C. Понтрягиным и его учениками [53]. Построение вычислительных методов, основанные на упомянутых условиях, получивших название «принцип максимума», началось с работ И.А. Крылова и Ф.Л. Черноусько [38,39]. Ими был разработан метод последовательных приближений, обладающий, однако, рядом существенных недостатков. Дальнейшее совершенствование схемы указанного метода велось параллельно школами, возглавляемыми Ф.Л. Черноусько и О.В. Васильевым. Предлагалось большое количество модификаций для различных классов задач. В конце 70-х годов были получены результаты, позволяющие судить о релаксацион-ности и сходимости методов [Васильев О.В., Тятюшкин, 1981, 1983; Васильев О.В., 1994; Vasiliev, 1996; Любушин, 1979, 1982; Любушин, Черноусько, 1983; Срочко, 1982].

Такой подход во многих задачах позволял найти приближенно-оптимальное решение, но во многих случаях оказывался неэффективным. Связано это было с отсутствием специальных регуляторов в алгоритмах.последовательных улучшений. Только в конце 70-х годов появились работы, в которых указанные недостатки были преодолены и для методов улучшения доказаны свойства релаксационности и сходимости. Следует отметить, что процедуры, основанные на принципе максимума, наиболее эффективны в задачах, где оптимальное управление имеет релейный характер. Для некоторого класса задач строились вычислительные процедуры, предусматривающие решение двухточечной краевой задачи [Васильев Ф.П;, 1981; Моисеев, 1971. 1975; Федоренко, 1978], что в общем случае вызывает существенные трудности. Успехи здесь достигнуты только для определенных классов задач, а универсальных вычислительных процедур не получено. Важной особенностью методов, основанных на принципе максимума, является наличие задачи максимизации функции Понтрягина по управлению на отрезке времени ненулевой меры. Если такая задача требует большого количества вычислений, то эффективность алгоритмов снижается.

Многие алгоритмы группируются вокруг методов спуска в пространстве управлений и основаны на исследовании первой и второй вариации функционала [Брайсон, Хо Ю-Ши, 1972; Келли, 1965; Кротов, Гурман, 1973; Сеф, 1973; Шатровский, 1962]. Сюда относятся все методы градиентного спуска, и их модификации. Такие алгоритмы эффективны для задач без ограничений на управление либо в случае, когда оптимальное управление находится внутри допустимой области. Если структура ограничений достаточно проста (например, ограничения параллелепипедного типа), то для приближенного решения задачи оптимального управления широко используются различные аналоги методов конечномерной оптимизации, такие как методы условного градиента, проекции градиента, возможных направлений, неопределенных множителей Лагранжа, методы последовательной линеаризации [Федоренко, 1975, 1978; Демьянов, Рубинов, 1968; Карманов, 1975; Срочко, 1989; Тятюшкин, 1992] и, т.д. Трудности, возникающие при решении задач со сложной структурой ограничений на управление, могут быть преодолены с помощью методов штрафных функций [Карманов, 1975] или модифицированных множителей Лагранжа [Гольштейн, Третьяков, 1989], позволяющих свести приближённо (но с любой степенью точности) исходную задачу к задаче, в которой нет ограничений или части из них.

Другое направление развития вычислительных процедур связано с исследованиями уравнения Беллмана [Беллман, 1960]. Сам по себе объект представляет сложную математическую структуру — уравнение в частных производных первого порядка, нагруженное операцией максимума. Достоинство таких исследований — получение оптимального синтезирующего управления как наиболее желаемой формы решения. Отметим работы В.З. Букреева [Букреев, 1968], связанные с построением приближённого оптимального синтеза управления, нашедшего отражение во многих прикладных задачах. Функция Беллмана в его исследованиях ищется в виде позинома, т.е. суммы произведений функций одной переменной. Используя эту идею и принцип локализации [Гурман, 1985], в работе [Новые методы., 1987] построена вычислительная схема последовательных улучшений.

Большая серия методов приближённого решения задач оптимального управления основана на достаточных условиях оптимальности Кротова, которые в дальнейшем, дополненные и переосмысленные, получили название принципа расширения. Исследования по существованию функции Кротова содержатся в работах М.М. Хрусталёва [Хрусталёв, 1978, 1988]: Основополагающей в направлении применения достаточных условий оптимальности к построению вычислительных процедур послужила работа В.Ф. Кротова [Кротов, 1975]. В ней сформулирована общая схема, в которой итеративным образом ищется функция. Кротова и соответствующее ей синтезирующее управление. На основе этой процедуры в работах [Кротов, Фельдман, 1978, 1983] представлен алгоритм последовательных улучшений управления, включающий в себя интегрирование присоединённой системы принципа максимума и линейного матричного уравнения.

Кроме упомянутого алгоритма, на основе принципа расширения развита серия методов первого и второго порядка слабого и сильного улучшения [Гурман, Батурин, Расина, 1983; Новые методы., 1987; Батурин, Урбанович, 1997]. Их особенностью является то, что итерационный процесс строится в форме нелинейного синтеза управления: В случае, когда исходный режим удовлетворяет необходимым условиям оптимальности (принципу максимума либо условиям стационарности), вычислительная процедура позволяет улучшить исследуемый режим, если он неоптимален в локальном смысле. Похожие алгоритмы содержатся в работах [Мерриэм, 1967; Jacobsonj 1968; Miele, 1975]. Они получены квадратичной аппроксимацией уравнения Беллмана, а регулятором выступает длина отрезка времени, отсчитываемая от правого конца траектории.

Отметим, что основные исследования проводились для задач оптимального управления с непрерывным временем, в то время как дискретные задачи исследованы существенно меньше. Р. Беллманом [Беллман, 1960] рассматриваются задачи динамического программирования для дискретных процессов, однако, как упоминалось выше, данный подход достаточно трудоёмок за счет необходимости'брать максимум по управлению на каждом шаге, тем не менее, на конечном множестве управлений он может быть эффективно реализован. Несмотря на невыполнение принципа, максимума для дискретных систем в общем случае, удалось для отдельных классов задач сформулировать аналог принципа максимума [Болтянский, 1973; Мордухович, 1988], на основе которого был разработан ряд алгоритмов улучшения.

Достаточно широкий класс итерационных методов улучшения управления дискретными системами основан на принципе расширения. В работах [Гурман, 1985,1997; Новые методы., 1987; Батурин, Урбанович, 1997] предложены алгоритмы первого и второго порядков, которые строятся в виде синтеза оптимального управления. В качестве регулятора в них используется добавка к функционалу в виде нормы близости текущего решения к начальному приближению, которая записывается следующим образом: пусть имеется функционал /: D—> R и некоторый элемент т1 Е D, где

D' — множество допустимых решений. Требуется найти лучший элемент т11 £ D в том смысле, что I(mn) < /(га1). Для этого вводится функционал J(ml, га) типа нормы близости га к m1 (J(ml, га1) = 0, J(ml,m) > 0 при m ф га1), и рассматривается задача о минимуме вспомогательного функционала/а .=■ (1 — a)I(m) -f aJ(ml,m), a £ [О,1]. Пусть ma = argmin/a, тогда при естественных предположениях о непрерывности, существует такое а*, что I(ma) < /(го1) для всех а* < а < 1, при этом гаа —> га1 (по норме J). Таким:образом, изменяя с* от 0 к 1, можно достичь необходимой степени близости та к га1 и эффективно использовать достаточные условия локального минимума, получаемые путем тейлоровских представлений конструкций достаточных условий Кротова в окрестности га1. В итоге получается алгоритм с параметром а, играющим роль регулятора, настраиваемого при конкретном применении, который выбирается так чтобы разность /(га1) — 1(та) была наибольшей:

Кроме тейлоровского представления функции; Кротова в работе [Никифорова, Ухин, 2004] рассматривается метод приближенного синтеза оптимального управления, где в качестве способа задания; функции Кротова используется интерполяционный полином. В работе [Гурман, Ухин, 2004] строится итерационная; процедура улучшения и оптимизации дискретного управления; основанная на локализации глобальной схемы решения задачи оптимального управления в стандартной форме как задачи о минимуме функции конечного состояния, задающей минимизируемый функционал задачи, на множестве достижимости управляемой системы. При этом используется новый оригинальный; подход к описанию и аппроксимации множества достижимости.

Одним из перспективных направлений решения задач оптимизации является применение многометодного подхода, заключающегося в комбинировании различных методов в процессе решения задачи. Описание подобных технологий есть в работах А.И. Тятюшкина, А.Ю. Горнова [24,60,61]. Данные авторы предлагают в качестве средства для создания многометодных поцедур использовать механизм параллельных вычислений, при котором выполняется одновременный запуск нескольких алгоритмов. После остановки алгоритмов происходит сравнение полученных результатов, среди которых выбирается наилучший, который принимается за начальное приближение. Процедура повторяется до тех пор, пока хотя бы один алгоритм позволяет улучшить текущее приближение. Описанный метод достаточно прост в реализации, но по сути он является полным перебором всех алгоритмов на каждом шаге, при этом не используются знания о свойствах решаемой задачи и применяемых алгоритмах улучшения, которые бы позволили снизить объем вычислнений.

Цель работы

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

Задачи работы

Для достижения поставленной цели в работе решаются следующие задачи:

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

• ■ разработка базового алгоритма второго порядка и его модификаций;

• исследование свойств базового алгоритма на предмет релаксационно-сти и сходимости;

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

• создание программных комплексов на основе предложенных принципов;

• решение тестовых и актуальных прикладных задач. Структура работы

Диссертационная работа состоит из четырёх глав (двух теоретических и двух прикладных), введения, заключения и двух приложений.

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

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

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

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

В четвертой главе приведены результаты, полученные при моделировании и оптимизации стратегии развития социо-эколого-экономической модели на примере региона Переел авля.

В заключении сформулированы основные результаты, полученные в диссертации.

В приложениях содержатся блок-схемы предложенных алгоритмов, а также справки об использовании реализованного программного обеспечения.

Научная новизна

Все результаты, полученные автором; являются новыми. Они состоят в следующем:

• разработан метод улучшения для задач оптимального управления с дискретным временем,.с новым типом регулятора — временным интервалом;

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

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

Практическая ценность

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

На базе полученных алгоритмов разработан программный комплекс, использовавшийся для сценарных расчетов= в социо-эколого-экономическом моделировании региона Переславля-Залесского и Сумской области (Украина) и проведен расчёт оптимальных стратегий их развития в рамках проектов TACIS АСЕ Project P95-4097-R, РФФИ » 97-01-00109, 02-01-06471, 03-01-00414-а. Результаты этих исследований отражены в ряде публикаций, в том числе в монографии [46].

Предложенный принцип построения многометодных процедур лёг в основу программного комплекса, реализованного в рамках проекта РФФИ N2 00-01-00731.

Для исследовательских и учебных целей была разработана Maple-библи-отека для решения задач оптимального управления, основу которой составили предложенные в данной работе алгоритмы. Этот программный продукт используется в курсах «Методы оптимизации» и «Оптимальное управление» в НОУ Институт программных систем — «Университет города Переславля» в качестве учебного пособия.

Апробация работы

Результаты работы обсуждались на семинарах Исследовательского центра процессов управления Института программных систем РАН и кафедры Системного анализа НОУ Институт программных систем— «Университет города Переславля». В виде докладов результаты были представлены на научных конференциях, в частности:

• международной конференции «Интеллектуальное управление: Новые интеллектуальные технологии в задачах управления (1С1Т'99)» (Пере-славль-Залесский, 1999);

• международной конференции IFIP WG2.5 WoCo 8 «Software Architectures for Scientific Computing Applications» (Ottawa, Canada, 2000);

• школе-семинаре «Понтрягинские чтения» (Воронеж, 2001);

• IV Всероссийской научной internet-конференции «Компьютерное и математические моделирование в естественных и технических науках» (Тамбов, 2002);

• международном симпозиуме «Обобщенные решения в задачах управления» (Переславль-Залесский, 2002);

• школе-семинаре «Понтрягинские чтения —XIII» (Воронеж, 2002). Основные публикации

По результатам исследований опубликовано 14 печатных работ [3-14,46, 68]. Из них автору лично принадлежат работы [3-7], остальные опубликованы в соавторстве. В монографии [46] автором выполнены сценарные расчёты социо-эколого-экономической модели и описан программный комплекс; в работах [8-11] автором предложен принцип построения интеллектуальных многометодных процедур оптимального управления и дано описание архитектуры программного комплекса, реализующего данный принцип; в работе [12] автору принадлежит вывод и описание алгоритма поиска оптимального управления дискретной системой; в работе [13] автором решена задача поиска оптимального управления для предложенной модели; в работе [14] автором реализован алгоритм и выполнены расчёты на основании полученных начальных приближений.

Автор выражает глубокую благодарность своему учителю В.И. Гурману за неоценимую помощь в работе над диссертацией.

Заключение

В ходе выполнения работы получены следующие основные результаты:

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

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

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

4. Предложены принципы построения интеллектуальных многометодных процедур. I

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

6. С помощью разработанных алгоритмов и программного обеспечения проведена серия вычислительных экспериментов над социо-эколого-экономической моделью региона.

1. Батурин В.А., Урбанович Д.Е. Приближенные методы оптимального управления, основанные на принципе расширения. — Новосибирск: Наука. Сиб. предприятие РАН, 1997.

2. Беллман Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1960.

3. Белышев Д.В. Алгоритм улучшения управления для дискретных систем // Современные методы в теории краевых задач «Понтрягин-ские чтения». — Воронеж: ВГУ, 2001. С 19.

4. Белышев Д.В. Многометодные процедуры оптимального управления II Сборник материалов «Понтрягинские чтения XIII». — Воронеж: ВГУ, 2002. С. 20-21.

5. Белышев Д.В. Итерационный алгоритм второго порядка оптимизации дискретных управляемых систем // Обобщенные решения в задачах управления. Труды международного симпозиума 27-31 августа 2002г. — Переелавль-Залесский, 2002. С. 225-227.

6. Белышев Д.В. Алгоритм улучшения дискретного управления с временным регулятором и его программная реализация // Программные системы: теория и приложения. — М.: Наука, Физматлит, 2004.— Т. 2. С. 349-368.

7. Белышев Д.В., Гурман В.И. Интеллектуальные процедуры оптимального управления // Автоматика и Телемеханика, 2002. № 5. С. 147155.

8. Белышев Д.В., Гурман В.И. Мультиметодные процедуры оптимального управления // Обобщенные решения в задачах управления. Труды международного симпозиума 27-31 августа 2002г. — Переславль-Залесский, 2002. С. 131-132.

9. Белышев Д.В., Гурман В.И. Программный комплекс многометодных интеллектуальных процедур оптимального управления // Автоматика и телемеханика, 2003. № 6. — С. 60-67.

10. Белышев Д.В., Соловьева О.В. Анализ инновационных эффектов развития региона на социо-эколого-экономической модели // Программные системы: теория и приложения. — М.: Наука, Физматлит, 2004.— Т. 2. С. 437-444.

11. Белышев Д.В., Шевчук Е.В. Алгоритм и программный комплекс для поиска оптимального управления // Интеллектуальное управление:

12. Новые интеллектуальные технологии в задачах управления (1С1Т'99). -Труды Международной конференции. — М.: Наука, Физматлит, 1999. С. 146-150.

13. Болтянский В.Г. Оптимальное управление дискретными системами. — М.: Главная редакция физико-математической литературы изд-ва «Наука», 1973.

14. Брайсон А., Хо-Ю-Ши Прикладная теория оптимального управления. — М.: Мир, 1972.

15. Букреев В.З. Об одном методе приближённого синтеза оптимального управления // Автоматика и Телемеханика, 1968. № 11. — С. 513.

16. Васильев Ф.П. Методы решения экстремальных задач. — М.: Наука, 1981.

17. Васильев О.В. Лекции по методам оптимизации. — Иркутск: Изд-во Иркут. ун-та, 1994.

18. Васильев О.В., Тятюшкин А.И. Об одном методе решения задач оптимального управления, основанном на принципе максимума // Журн. вычисл. математики и мат. физики, 1981. № 6. — С. 1376-1384.

19. Васильев С.Н., Жерлов А.К., Федосов Е.А., Федунов Б.Е. Интеллект-ное управление динамическими системами. — М.: Наука, Физматлит, 1999. С 425.

20. Голыитейн Е.Г., Третьяков Н.В. Модифицированные функции Лагран-жа. Теория и методы оптимизации. — М.: Наука., 1989.

21. Горнов А.Ю., Тятюшкин А.И. Программная реализация мультиме-тодной технологии для задач оптимального управления // Труды III Междунар. конф. «Проблемы управления и моделирования в сложных системах». Самара: ИПУСС РАН, 2001. С. 301-307.

22. Гурман В.И. Принцип расширения в задачах управления. 2-е изд., перераб. и доп. М.: Наука. Физматлит, 1997.

23. Гурман В.И. Принцип расширения в задачах управления. — М.: Наука, 1985.

24. Гурман В.И., Ухин М.Ю. Метод улучшения дискретного управления, основанный на аппроксимации множества достижимости // Программные системы: теория и приложения. — М.: Наука. Физматлит, 2004. (в печати)

25. Гурман В.И. Магистральные решения в задачах оптимизации стратегий развития // Автоматика и телемеханика, 2004.

26. Гурман В.И., Батурин В.А., Расина И.В. Приближённые методы оптимального управления. — Иркутск: Изд-во Иркут. ун-та, 1983.

27. Демьянов В.Ф., Рубинов A.M. Приближённые методы решения экстремальных задач. — JL: Изд-во Ленингр. ун-та, 1968.

28. Емельянов С.В., Коровин С.К., Бобылев Н.А., Булатов А.В. Гомото-пии экстремальных задач. — М.: Наука, 2001.

29. Иванов А.Г. Параллельная программа поиска минимум // Высокопроизводительные вычисления и их приложения: Труды Всероссийской научной конференции (30 октября-2 ноября 2000 г., г. Черноголовка). М.: Изд-во МГУ, 2000. С. 250-252.

30. Карманов В.Г. Математическое программирование. — М.: Наука, 1975.

31. Кротов В.Ф. Вычислительные алгоритмы решения и оптимизации управляемых систем уравнений // Изв. АН СССР. Техн. Кибернетика. 4.1: 1975, №5, С. 3-15; 4.2: №6, С. 3-13

32. Кротов В.Ф., Фельдман И.Н. Итерационный метод решения экстремальных задач ]/ Моделирование технико-экономических процессов. М.: МЭСИ, 1978. С. 160-168.

33. Кротов В.Ф., Фельдман И.Н. Итерационный метод решения задач оптимального управления // Изв. АН СССР. Техн. кибернетика. — М., 1983.- Т. 2. С. 160-168.

34. Кротов В.Ф., Гурман В.И. Методы и задачи оптимального управления. — М.: Наука, 1973.

35. Крылов И.А., Черноусько Ф.Л. О методе последовательных приближений для решения задач оптимального управления // Журн. вы-числ. математики и мат. физики, 1962. N® 6. — С. 1132-1138.

36. Крылов И.А., Черноусько Ф.Л. Алгоритмы метода последовательных приближений для задач оптимального управления // Журн. вы-числ. математики и мат. физики, 1972. № 1. — С. 1132-1138.

37. Келли Г.Дж. Метод градиентов // Методы оптимизации с приложениями к механике космического полёта. — М.: Наука, 1965. С. 101116.

38. Любушин А.А. Модификации и исследование сходимости метода последовательных приближений для задач оптимального управления // Журн. вычисл. математики и мат. физики, 1979. № 6. — С. 1414— 1421.

39. Любушин А.А. О применении модификации метода последовательных прилбижений для задач оптимального управления // Журн. вы-числ. математики и мат. физики, 1982. № 1. — С. 30-35.43