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

г Г Я

с- ^

московашй ОРДЕНА ЛЕНИНА И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени В. И. ЛЕНИНА

Специализированный совет К 053.01.10

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

ПУЛИЧЕВА Елена Аркадьевна

МЕТОД ШТРАФНЫХ ФУНКЦИЙ II МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА В ЭКСТРЕМАЛЬНЫХ ЗАДАЧАХ С НЕЯВНО ЗАДАННЫМИ ЦЕЛЕВЫМИ ФУНКЦИЯМИ И ОГРАНИЧЕНИЯМИ

Специальность 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ

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

Москва 1994

Работа выполнена в Московском педагогическом государственно м университете им. В. И. Ленина.

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

академик Международной академии информатизации, доктор физико-математических наук', профессор ГОРЕЛИК В. А.

Официальные оппоненты:

доктор физико-математических наук, профессор СОТНИКОВ Л. И.,

кандидат физико-математических наук ЛЕВИКОВ А. А.

Ведущая организация: Московский технический университет связи и информатики.

Защита диссертации состоится ......^¿т 1994 г.

в часов па заседании специализированного совета

К 053.01Л6 но защите диссертации на соискание ученой степени кандидата физико-математических наук в Московском ордена Ленина п ордена Трудового Красного Знамени педагогическом государственном университете им. В. И. Ленина но адресу: 107140, Москва, Краснопрудная ул., д. 14, математический факультет МПГУ им. В. И. Ленина, ауд. 301.

С диссертацией можно ознакомиться в библиотеке МПГУ им. В. И. Ленина по адресу: 119435, Москва, Малая Пироговская ул., д. 1.

Автореферат разослан

Ученый секретарь сп^давявдированного совета, доктор педагогически^ наук, профессор ( ЕЦОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

- на основе использования метода штрафов и метода МФЛ разработать численные процедуры нахождения решений некоторых видов экстремальных задач с неявно заданнымми целевыми функциями и ограничениями;

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

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

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

функций и метода МЛ. Для рассмотренных задач предложены и апробированы численные методы решения.

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

Основные положения, выносимые на защиту:

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

- для решения задач с неявно заданными ограничениями возможно применение комбинированного подхода (метод штрафов + метод МФЛ); при этом или не требуется согласования штрафных параметров,- или это согласование слабее, чем при методе штрафов;

- идеи МФЛ могут быть использованы в задачах динамического типа, что приводит к формулировке модифицированного дискретного принципа максимума, на основе которого возможно построение вычислительных процедур.

Апробация работы. Результаты исследования нашли отражение в двух печатных работах, докладывались' на Ш Международном форуме информатизации (конференция "Телекоммуникационные и вычислительные системы связи", МТУСИ, ноябрь 1993 г.), на заседании аспирантского объединения, на научно-методическом семинаре кафедры информатики и дискретной математики МПГУ им.В.И.Ленина (декабрь 1993 г.).

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения, списка использованной литературы и приложения. Диссертация содержит 140 страниц, из них НО страниц основного текста, 7 страниц - список использованной литературы, включвщий 78 наименований, 23 страницы - приложение.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе (§§ I.I-I.4) рассматриваются некоторые классы, экстремальных задач с неявно заданными ограничениями.

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

f(x) " miтг, хао, 1о=(ха^п\8(х)ф), Щ •

где g(x)= mar G(x,y), Y=(yiY^Wy)=Oi. ' (2)

У&о

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

Теорема I. Если точка х" - ■решение задачи (I), (2), и функции f(x,y) и G(x,y) непрерывно дифференцируемы в точке х*, то

существуют такие векторы Х*20, y{tY(x*) и числа а^О, 1=1 ,п+1,

п+;

Е а,-1, что точка х* удовлетворяет системе уравнений i=f '

\df(x') n+t QG(x", у)

- + 2 a.-- 0,

dx 1=1 dx

G(x',y.)= max G(x*,y), i=),n+1,

1 V#o k'gcx*) = 0,

П4 f

2 a. = >, а.Ю, 1=1,n+U i = i 1 1

Однако при численном решении задачи (I), (2) для хорошей сходимости алгоритмов, построенных на основе необходимых условий, необходимо выполнение весьма жестких требований. Метод штрафных функций и метод модифицированных функций Лаграюка позволяют расширить класс решаемых задач.

В § 1.2 метод штрафных функций применяется для решения задачи

f(x) — min , xtX6, Xo=(xzXsRn\g(x)=0), (3)

где g(x)= min G(x,y), У = fyеУ^Я™|<pf у)=0) ' (4)

V&o

Теорема 2. Пусть для задачи (3), (4) выполняются следующие условия:

AI) все функции являются непрерывными, множества - компактными, ха&. Yom

А2) функция G(x,y) для любого хеХ удовлетворяет условию Липшица по переменной у с константой К, т.е. G(x,yJ(.Lip^(K) Vi

A3) <рСу)Х>, G(x,y)>0 ixiX, ytY.

A4) 3 0>0,с>0,а>0 такие, что |<pfyj|> cp*(y,Yo)

при всех у«(УбГУ0;\У0)ПУ. Тогда

lim min [f(x)+>JG(x,y)+'ky.q(y)] при а<1,

А.-«» хеХ °

j _ уеУ •

° lim min С/(х)+№(хгу)+Цщ>(у)], если а>1. «Я

Аналогичный результат доказывается и для произвольных по знаку функций <f>(y), G(x,y).

В § 1.3 рассматривается комбинированный подход к решению задачи (3), (4). Для снятия ограничений на переменную х применяется метод штрафов, а "внутренняя" задача (4) решается с помощью модифицированной функции Лагранжа.

Теорема 3. Пусть для задачи (3), (4), в которой все функции являются непрерывными, а множества - компактными, выполняются условия:

BI) G(x,y)K) VxeX, yeY;

В2) У.теХ функции G(x,y), ф(у) дважды дифференцируемы по у в

окрестности точки y*lx)eYo;

ВЗ) v.rfX точка у*(х) является регулярной точкой минимума для задачи (4) (?уЧ>(у* (х)

В4} <?vv2L(x,y'(х),\*(х))у,у>>0 Чу/0, для которых справедливо <vv4>(y* (х)) ,у>-0. (Здесь ~ матрица вторых производных

регулярной функции Лагранжа L(x,y,\)=G(x,y)+tyi(y) задачи (4), Х'(х) - соответствующий точке у*(х) множитель Лагранжа.)

Тогда •

/ = lim min [f(x)+c min (G(x,y)+\.* (х)<р(у)+уир2(у))], ° c^00 xzX y(.Y

где ц - некоторое достаточно большое число. Здесь

G(x,y)+\'(x)<p(y)+\uf(y) = l(x,y,\*(x),\x) -

модифицированная функция Лагранжа для задачи (4).

Применение комбинированного подхода к решению задачи (3),

(4) позволяет использовать одновременно достоинства и метода

штрафных функций, и метода модифицированных функций Лагранка

(более высокую скорость сходимости метода МФЛ и более простую

форму вспомогательных задач при применении метода штрафных

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

функций при более слабых требованиях к исходной задаче).

В § 1.4 исследуется частный случай лексикографической

задачи оптимизации - задачй минимизации функции на множества

точек минимума некоторой другой функции:

f(x) - min, xiXa=(xiX\g(x)=mln g(z)l,

га (5)

Х=ши\П(х)$0).

Теорема 4. Пусть в задаче (5) функции f(x), g(x), h(x) непрерывны на компакте U, причем функции / и g удовлетворяют условию Липшица на !/, и ограничение Щх)ф подчиняется условию: существуют постоянные ö>0, Ь>0, а>0 такие, что h(.r)2bpy(x,X) 4x(AVü(X)\X)MJ. Тогда

ta-

lim min max lf(x)i-\(g(x)-g(z))i-c{max(0,h(x))) -A.-KO X(JJ Zill

-Ц1(тах(0,П(х)))я] при CXaqH,0<dq^1,

lim min max lf(x)t\(,g(x)-g(z))+c\max(0,h(x)))q-A.-«» xeU z&

ц-«> • -7y.(mnx{0,h(x)))4} при aq>1, aq>1

C-«» _

сАГ"4 -К» ' .

В § 1.4 рассматривается также два варианта комбинированного подхода к решению лексикографической задачи оптимизации.

В главе 2 (§§ 2,1-2.4.) исследуются максиминныо задачи, возникающие в процессах' принятия решений в условиях неопределенности, в том числе и конфликта. Максиминные задачи представляют собой характерный вид задач с неявно заданнцми целевыми функциями. В таких задачах целевая функция, caf/a является решением некоторой экстремальной задачи, причем ограничения также могут быть определены неявно. Такие максиминные задачи со сложной структурой ограничений рассматриваются в §§ 2.2-2.3.

В § 2.1 дается обзор исследований по максиминным задачам, 'определяется общая постановка задачи и формулируются известные необходимые условия оптимальности для некоторых типов максиминных задач.

В § 2.2 рассматриваются максиминные задачи, возникающие при исследовании статических моделей ■ оптимального управления иерархическими системами.

ИСследуется двухуровневая иерархическая система с одним элементом верхнего уровня (центром) и т элементами нижнего уровня (подсистемами). Управление центра обозначено через и, управления подсистем - у{ {1=1 а управление нижнего

уровня в целом через v=(v1.....v ).

Реакция нижнего уровня задается многозначным отображением R: ü - V.

Критерием эффективности центра является функционал F(u,v). Гарантированная оценка эффективности управления равна

f(u)=inf F(vl.v), vzR(u)

так как для центра возможный выбор нижнего уровня описывается его реакцией Щи). В соответствии с известным принципом

гарантированного результата оптимальным управлением центра и° (при фиксированном виде передачи информации) является любое

u°€ Arg max f(u)=(u(.D\ f(u)= max f(z)=F°) U(D zeD

(в . предположении достижимости верхней грани функционала

f(u)), где D=(uiU\(u,v)fQ 4vt.R(u)} - множество допустимых

управлений центра, обеспечивающих гарантированное выполнение

условия устойчивости системы (u,v) е П.

Задача центра заключается в нахождении • и°, 1°,

удовлетворяющих соотношению

F° = Inf F(u°,v) = max Inf F(u,v), (6) •

vcR(u°) uzDyä(u)

Задача (6) определения максимина на связанных множествах (иначе со связанными переменными или ограничениями) является типичной в информационной теории иерархических систем.

Предполагается, что шкний уровень знает управление центра и стремится к максимизации своего критерия эффективности ip{u-,v). Тогда его реакция описывается отображением >

R(u) = Arg max <р(a,v}t veV

то есть определяется из решения задач '- поиска экстремума критериев подсистем.

Пусть пространства управлений U и V являются некоторыми подмножествами конечномерных евклидовых пространств Я0, и соответственно. Задача (6) рассматривается в случае, когда множество допустимых управлений определяется ограничениями на и:

D = mu\ g(u)=0),

но само ограничение g(u) задается в неявном виде:

g(u)= min G(u,v),V = (veVj h(v)=0). vtVa

Таким образом, задача (6) имеет вид:

определить Р°= max Inf F(u,v), D - (u&| g(u)^ö), ueD veR(u)

g(u)= min G(u,v), V = iueV| h(v)=0), (7) viV °

о

R(u) - fueV| ф(u,v)= max q(u,z)].

ztV

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

Теорема 5. Пусть для задачи (7) выполняются условия:

CI) все функции являются непрерывными, множества - компактами,

2*0, Vo*0, R(u)#6

CZ) функции F(u,v); ф(u,v) удовлетворяют на множестве U условию Липшица йо переменной и VueV, функция G(u,v) удовлетворяет на множестве V условию Липшица по переменной v 4utUi

СЗ) G(u,v)^0 VuçU, vçY; ' . ' '

C4) существуют постоянные . 8>0, Ъ>0, a>0 такие,, что Vue(YôÎJ)AD)nir g(u)Z bpy(u,D) (для справедливости • последнего -, неравенства достаточно, чтобы G(u,vJ> bçfi(u.D) Vue?); : ' :

С5) существуют постоянные ö'>0, Ъ'>0, а'>0 такие-, , что' h(v)> b'ç>a'(v,v ) ivtiv (V )\v ' .

y о Q , о о • ;

Тогда

lim max mln[F(u,v)+w>(u,z)-\up(u,v)-}JJ(u,t)-\chq(t)] ц-® иф vzV >r

teV при (Xa<i, 0<o'^, .

Ilm max mlnlF(utv)+\up(u,z)-iup(u,v)-XG(u,t)-\oh4(t)] ■ ц.о-« fV'vzV . vmo при 0<a$1, a'>|-. •

teV ' ■ -

/ =\lim max mtniF(u,v)i\xip(u,z)-p.qi(urv)-}iG(uft)-Xchq(t)) K.ii-^o ueU vcV Vc^c при а>1, 0<a'^,

ty a~® ttv ° .4

lim max mln[F(u,v)-Hiip(u,z)-pt()(u,v)-XG(uft)-\ch':i(t )]

Ter ПРИ a>u

tèV 4

Таким образом, задача (7) сводится к задаче'" поиска максимина функции многих переменных на. множествах достаточно . простой структуры. ■ '■

' 5 2.3 посвящен некоторым -видам ■ максиминных , задач, возникающих при изучении игр с передачей информации.

Пусть F(x,y), G(xry) - функции "выигрыша игроков, X, Y - множества стратегий. Наилучший гарантированный результат . первого игрока, сообщающего свой "ход" хеХ второмуравен

Fo = sup Щ F(x,y).

up Inf xçX yeB(x)

где В(х) = (у€У| G(x,y)= max G(x,z)).

zîY

Предполагается; что первый игрок выбирает свою стратегию так, чтобы второй мог обеспечить себе выигрыш не меньше некоторого-фиксированного числа р, то есть

х(.Х = G(x,y)}p).

° У(.У

С учетом этого условия возникающая новая задача записывается в следующем виде :

f(x) - max, XiXo=(xiX\g(x)>0),

g(x)=mxc G(x,y)-p=max (G(x.y)-p), (8)

ytY ycY

f(x)*mtn F(x,y), B(jç)=(yiY\G(x,y)- max 0(x,z)}. yiB(x) zi.Y

Теорема 6. Пусть для задачи (8) выполняются условия:

fil) все функции непрерывны, множества Х,У - компакты, функции F(x,yl, G(x,y) удовлетворяют на множестве X условию Липшица по переменной х VytY;

D2,) существуют постоянные ô>0, аХ), Ь>0 такие, что

g(x)i-bp%(x.Xo) 4xi{Vö(X0)\Xa№. Тогда

lim max min lF(x,y)+\i(max G(x,z)-G(x,y))-ц-да xtX ytY ztY

-XlmtnfO.max G(x,t)-p)l) VA^A.

t(Y °

при 0<asl,

Ilm max min [F(x,y)+\i(max G(x,z)-G(x,y))~ цД-œ x(.X yeY ztY

Ли~а~оо -XlmtnfO.max Gii,î;-p)l ]

t<d' -при a>1.

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

4 В третьей главе рассматривается возможность использования идеи модифицированной" функции 'Лагранжа для решения некоторых

/ = max f(x)=

° ха

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

В § 3.1 формулируется 'общая постановка задачи.

Исследуются иерархические системы с дискретным временем, динамика которых описываетоя многошаговой системой- уравнений (векторным уравнением)

хк>г!к(хк>%'"к>- \ ' . /

Здесь х^ - фазовые переменные, опиоывающие состояние* системы в момент времени к. Управляющие воздействия верхнего и нижнего уровней, соответственно ий и осуществляются в фикси- .

рованные моменты времени к= О, N-1.

Предполагается, что на переменные налагаются следующие ограничения :фазовые ограничения гг^Х^; смешанные ограничения на значения фазовых переменных и управляющих воздействий верхнего-' уровня и^и^(х^) с У^; совместные -ограничения на значения, управляющих воздействий нижнего уровня . с /^, где

- многозначное отображение из конечномерного пространства Х-^ в конечномерное пространство У^х^ц^) - многозначное

отображение из произведения пространств Х^хг/^ в, конечномерное пространство У^.

Вводятся следующие обозначения:

ъ=(ха,х1,... ,х1г)=(х,х11)=ц>(м,у)=(ц>(и,ч),ц>1!(п,ч)), v-1 я-1

Х= Л хк. Х= ХхХя, и(х)= П ик(хк),

к=о к=о - -

Я-1

и=ии(х), ч(х,и;= П уь(хь,иь), ■: и Ч(х,ъ).

Эффективность функционирования. системы с точки зрения центра в общем случае оценивается функционалом

&=о

Ёсли элементы нижнего уровня не связаны мейду собой или при наличии связей действуют в соответствии • с одним из основных

принципов коллективного поведения (равновесие,

паретооптимальность), то их можно рассматривать как один элемент, оптимизирующий в общем случае функционал

J(x,u,vj= £ hk(xk,uk,vk)>h(xN).

R=o

Тогда задача центра состоит в определении и°, для которых f°= sup Inf 1(ц>(и,ч),и,ч)= Inf 1(ц>(и°,ч),иа,тг), (9)

U£ü v^Wu) V{R(U°)

где R(u)=Arg max /((pCu.Yj.u.v; - (10)

реакция нижнего уровня системы.

Основное содержание § 3.2 - формулировка модифицированного дискретного принципа максимума, с помощью которого получаются условия оптимальности в задачах динамического типа.

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

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

N fe- 1

при ограничениях-

sk=^k^k-i'uk)f ха ~ фиксировано, (12)

ukiUk, k=1,N. (13)

Если функции /¿fx^j.u^J, gk(xk,up), непрерывны, а

множества ük, fe=f,W компактны, то задача = (II)-(13) имеет решение, то есть существует оптимальное управление и .соответствующая ему траектория. Пусть ((х^.и^), k=1,N)-оптимальный процесс в задаче (II)-(13). Предполагается, что функции ffrfx^j.tipj, 8%(хк,ик), к=1 ,И имеют непрерывные частные првизводные по всем переменным. В пространстве состояний вводится сопряженную с (12) систему уравнений

те ~ >

дхя ввк(4,ир 1 к ■ - дхк

(14)

Ь-К-1.1.

Решение системы (14), соответствующее процессу

к=1,Я), обозначается через к=1,Я. . . ■

Модификация дискретного принципа максимума основана на использовании модифицированных функций Гамильтона,, которые для задачи (II)-(13) имеют вид:

СЮ,

где >, -

обычше функции Гамильтона для задачи (П)-(13);

- решение системы (12), соответствующее

оптимальному управлению и°=(и°,... ,и°); ф°=("ф°,... - решение

системы' (14); ' •и=('и?,...,ид.) - произвольной.' 'управляющее воздействие.

В следующей теореме сформулированы предположения, при которых справедлив модифицированный дискретный принцип максимума.

Теорема 7. Пусть функции /^(х^^и^), П=1, К,

непрерывно дифференцируемы по переменным хк и дважды дифференцируемы ' по переменным и^ на компактах и^;

(х°,иа) ~ оптимальный процесс в задаче (II)-(13),. функция •

Гамильтона в точке оптимального управления

удовлетворяет либо условию '. .

<5 «ь,

—-? к •).<.(?, для любого 6иъсК(и^),

либо условию

Г

для любого Стакого, что

а4

duh

бик = 0.

Тогда существует С°, такое, что для любого

IV

модифицированная функция Гамильтона имеет в

точке и^ строгий локальный максимум, а если при этом траектория

х° соответствует единственному управлению и°, то строгий

глобалышй максимум (fe^J ,N).

В § 3.3 с помощью обычного и модифицированного принципов максшума сформулированы условия оптимальности для задачи (9), (10) программного управления центра при дальновидном поведении низшего уровня иерархической системы, в которой пространство управлений центра задано неявными ограничениями.

Теорема 8. Если для задачи (10) справедлив модифицированный принцип максимума, то для того чтобы управление центра ио было

оптимально, необходима существование таких v°, х°, ф°, С°, при которых справедливы соотношения

Ä it & *

где-

--f

дХъ

.С»-

При этом оптимальный результат центра равен 1°=то(хо).

По доказанной теореме динамическая задача управления центра сводится .к последовательности статических (параметрических) задач. Вычислительная схема решения задачи (9), (10), построенная на основе теоремы 8, предлагается в § 3.4.

В § 3.4 также предлагается численный метод решения задачи-динамического программирования (II )-(13), основанный на использовании дискретного модифицированного принципа максимума: формулируется алгоритм - метода, .. описывается. ': численный эксперимент, проведенный по предложенному алгоритму. Результаты, эксперимента показывают работоспособность предлагаемого метода, *

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1) Исследованы некоторые новые типы оптимизационных задач с-' неявно заданными целевыми функциями и ограничениями. Для. рассмотренных клабсов задач установлены необходимые условия оптимальности и доказана теоретическая сходимость 1/етОда штрафных функций. _

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

3) На. основе использования метода штрафов И метода МФЛ разработаны численные процедуры нахождения решений некоторых видов экстремальных задач с неявно заданными целевыми функциями • и ограничениями и проведены тестовые расчеты, показавшие их работоспособность.

4) Для "задач с неявно - заданными." _ целевыми функциями и ограничениями динамического типа'разработаны численные" процедуры решения с использованием модифицированного дискретного принципа макашума . и проведены' тестовые расчеты, показавшие . их работоспособность. : ■

Основные положения диссертации нашли отражение в следующих работах; •' -

1. Горелик В.А.. Пуличева Е.А. Экстремальные задачи с неявно заданными, ограничениями/' Моделирование, оптимизация и декомпозиция сложных динамических процессов. - М.: ВЦ РАН, 1993.- С.54-74.

2. Горелик В.А., Пуличева Е.А. Оптимизация при неявно заданных целях и ограничениях//Информационные коммуникации, сети, системы и технологии: Т.езисц докладов конференции "Телекоммуникационные и вычислительные системы связи". - М.: МТУСИ,•1993.- С.64.