Исследование билинейных минимаксных задач и задач оценивания в линейных системах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Я — Л Ч *

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

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

КОРЖЕНЕЕИЧ Сергей Константинович

ИССЛЕДОВАНИЕ БИЖ-ОКЫХ АШИАКСШХ ЗАДАЧ И ЗАДАЧ ОЦЕНИВАЮТ В МШШ СИСТЕМАХ

Специальность: 01.01.09 - математическая кибернетика

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

Мииск - 1991

Работа выполнена в Институте математики: Академии наук Беларуси.

Научный руководитель - кандидат физико-математических

наук, старший научный сотрудник Астрозскчй Анатолий Иванович

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

- доктор физико-математических наук, профессор Никольский Михаил Сергеевич кандидат физико-математических наук, доцент Жевняк Ростислав Михайлович

Ведушее учреждение

- Институт математики и механики Уральского отделения Российской академии наук

Защита состоится " 24

января

1992 года в "

15

часов на заседании специализированного совета К 006.019.01 в Институте математики АН Беларуси по адресу: 220072. г.Минск, ул. Сурганова 11, Институт математики АН Беларуси.

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

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

¿3-

1991 года.

Ученый секретарь специализированного совета, кандидат физико-математических наук

1 "

А. И. Астровский

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

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

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

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

. '.-oïl:: . общая характеристика диссертационной работы

л -л.:тУальносгь темы. В теории оптимального управления важное место занимают задачи наблюдения и оценивания в условиях неопределенности. Часто фазовый век'ор системы управления недоступен непосредственному измерению, а информация о его реализациях получается с помощью некоторого измерительного устройства. Поэтому возникает принципиальный вопрос: можно ли на оснозании выполненных измерений и с использованием известных уравнений системы восстановить начальное или текущие состояния фазового вектора при наличии возмущавдих воздействий?

Первые задачи наблюдения были поставлены и решены Р.Кал-маком. Проблемы решения задач наблюдения-оценивания для непрерывных и дискретных систем привлекали внимание многих математиков. Отметим здесь работы H. Н. Красовского, А.Б.Курганского, М.С.Никольского, Ф. Л. Черноусько, Р.Габасова, Ф. М. Кирилловой. При исследовании дискретных систем наблюдения с помехами выделялись два основных подхода: стохастический подход и гарантированное оценивание. В 1G65 году Л.А.Заде .была предложена новая концепция для учета разного рода неопределенностей, встречающихся при применении математических методов для описание и анализа сложных систем. Предложенный ... Л. а.Заде подход положил начало теории нечетких множеств.

В настоящее время теория нечетких множеств привлекает внимание исследователей, работахщих в самых разных областях, начиная от теоретических вопросов оснований математики до конкрэтных приложений (техника, медицина, планирование и

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

Публикации и апробация работы. До теме диссэртационнной работы опубликовано 6 работ, одна работа в печати Основные результаты диссертации докладывались на научной конференции молодых ученых БГУ (Кинск,198<5), IX Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Минск, 19£6>, Республиканской научной конференции "Математическое моделирование и вычислительная математика" (Гродно, 1990), Всесоюзной конференции "Неглах'/.ий анализ и его приложения к математической экономике" (Баку, 1991). Результаты диссертации обсуждались на семинаре лаборатории моделирования и анализа систем Института метематики АН Беларуси (руководитель - академик АН Беларуси, доктор физ.-мат. наук И. 3. Ггйш/н), на объединенном семинаре по качественной теории оптимизации кафедры методов оптимального управления Белгосуниверситета им. В.И.Ленина и лаборатории теории процессов управления Института метематики АН Беларуси (руководители - профессор Р.Габасов, профессор Ф.М.Кириллова).

Структура и объем работы. Диссертация состоит из ь&едекия, двух глав, четырех приложений и списка литературы С/6 наименоБаний). Объем работы - 132 страницы машинописного текста.

- з -

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

Глаза I посвящена исследованию згдач наблюдения в условиях неопределеннее!и, когда возмущения и посохи списываются нечеткими множествами. Рассматривается задача апостериорного оценивания для линейных дискретных систем наблюдения в следующей постановке: пусть объект наблюдения описывается линейной нестационарной дискретной системой с возмущениями:

х< (+1}-АС1>-<<: I .МиСО, £ 0,1,..., > , <1>

где хсо - п-мерный вектор; ж'О - заданная пхп-матрица; \jCty - п-мерный вектор возмущения, информация о возможных реализациях которого описывается с помощью нечеткого множества V б к" с непрерывной функцией принадлежности предполагается, что ачррИ ограничен в Кп. Возможные реализации

начального состояния х =хС0.> системы (1) принадлежат заданО

нону компакту X в Предполагается, что непосредственное

О

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

у1еТ ег, т -а л.....с >. <25

и и 1 2 СЛ.

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

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

Задача. Пусть в системе (1), <2> реализовались некото-

рь'е неизвестные нам начальное состояние возмущения

vCi^es-jpp/, £еГ И помехи {COesuppE, teT^, кс'орь'е породили выход Требуется описать в терминах теории

нечетких множеств максимальное по включению нечеткое множество допустимых начальных состояний х", совместимое с заданным выходом У*. Это нечеткое множество X* в R" будем назвать решением задачи апостериорного оценивания.

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

В §2 описывается постановка задачи апостериорного оценивания для линейных дискретных систем наблюдения с помехами, описываемыми нечетки:п множествами, вводятся понятия траектории системы il), совместимости нечеткого множества допустимых начальных состояний с заданным выходом, решения задачи апостериорного оценивания для системы <1?, (2). описывается процедура построения решзнся задачи апостериорного оцениаш'ия.

Для любого начального состояния определим состо-

яние системы <i) в момент времени ter как нечеткое множество

xVx У a Rr' с функцией принадлежности м , следующим ° Хс«Гх >

о

образов :

1> для t-О положим Х°<х>"<х>, а/ , гце х - ха-

Х°Сх > х° х°

о

рактеристическая функция множества Xе,

2) для е>0 функцию принадлежности ^ зададим с помощью

X i* ^

о

рекуррентного соотношения

P <ГгО = sup iftin < 11 Cxi. jli <%o >, где

X Cx > , . . XlCx ^ V

о <Гх. V.}«=8v. r, О О

ifr, iJ = < <:,\>> « CR^xR" I xcsuppxVx^, vesvppV,r=AC >,

rem", i20.

Траекторию системы С1> для любого начального состояния определим как последовательность нечетких множеств в к": хсх .>,... ,х"сх ;». Множеством потенци-

с о о о

альной достижимости системы (1) в момечт времени t, t<=r, будем называть нечеткое множество X1<XJ> в О?" с функцией принадлежности ,и

X сх з

о

Лемма 1. Для любого t«=r справедливо следующее равенство: U xVx^ = xVx ;>.

хеХ

о ■

Пусть в системе; (1), <2> реализовались некоторые неизвестные нам начальное состояние х «=х ,возмущения vCOes-upp/,

о о

>.е~т у, помехи f< i i&jupps, te/'^, которые породили ВЫХОД У*, у'=< у*<О. t«=r >.

Li

Для каждого определим множество наблюдаемости как

нечеткое множество y"Vo в R" с функцией принадлежности /jy»<,t^ Следующим образом: tJymcti<T^ " *с t}~C( 1.~>гЭ. гйк". Наличие выхода позволяет для каждого teT уточнить мно-

U

жество потенциальной достижимости системы (1): наблюдаемыми множествами достижимости ZCtJ> будем называть нечеткие множества в В?", представляющие собой для каждого t«r пересечение множества потенциальной достижимости xlcx .> и множества

о

наблюдаемости K*<ro: zco = xVx s> п y"<t>.

с

Определение. Будем говорить, что нечеткое множество х в

с функцией принадлежности удовлетворяющее условию

х

х £ х , совместимо с заданным выходом у*=<\Л:о, «сТ ■>,

^^ о и

если для каждого сеТ^ выполняется условие £ гсс;.

Несложно покасать, что соотношение (1) определяет нечеткое отображение «и:

1У кПх1й" -► С0,1Л : (х.х? -► <3>

Пусть V - нечеткое множество и к", тогда его прообраз

при нечетком отображений чсо представляет собой нечеткое

множество в к'1 с функцией принадлежности р . для вьтсле-

I

ния которой а литературе приводилось явное зыражение.

Опипзм процедуру построения каксимального по включению нечеткого множества догусгимых начальных состояний х*, совместимого с заданным выходам. Процедура использует известные параметры системы <1 >, <2 )/заданный зыход У*-< До.'.еГ >

и

и формулу для вычисления функции принадлежности прообраза нечеткого множества при нечетком отображении. Будем обозначать возникающие при работе процедуры Нечеткие множества о через ГО, Г1, «так,

1) ПОЛОЖИМ ,

о.

<:) положим гО-у<тэ, 3? положим П=г0лхтсх .>,

о •

4) ПОЛОЖИМ т=т-1. Ь) вычислим множество

6) если т«=7" , то положим гО^гго/СтР и перейдем к пункту 1),

и

в противном случае перейдем к пункту 7),

7) если т=0, то х*=г2,

в противном случаз положим г0=г2 и перейдем к пункту 4). Справедлива следующая теорема.

- д

Теорема 1. Нечеткое множества X , построенное согласно процедуре 1 )-7 >, является решением задачи апостериорного оценивания состояния системы <1), <2).

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

В §4 приводятся свойства траектории системы (1) и рассматриваются раздичные способы ее описания.

Лемма 1. Еуеуь X - нечеткое множество в Rn с функцией принадлежности ¡u,^ удовлетворяющее условию s-uppxsx^. Тогда для любого ter справедливо следующее равенство:

U XíCx^ xlcx.>. x«3s xippX

Рассмотрим набор нечетких отображений «ct;>, t«=r, (3), определяемый системой.

Лемма 2. Для любого ter имеет место равенство xVxJ> = Ж l-l>.VCt-2j.. .. .<ьсОэ ex?, где X - произвольное подмножество (обычное или нечеткое) множества х , xVxje3:cx> - элемент траектории множества х.

о

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

Лемма 3. Пусть р=Сх - нечеткая точка в Rn, х - про-

Ог

извольное подмножество (обычное или нечеткое) множества допустимых начальных состояний Хо, x^esuppxVxj, P=>Jxlcx>CxJ:' и с t+iу^т. Тогда справедливо следующее равенство

- ю -

хи1сх;> •> и к СрУ.

х^еяиррХ

йэ лемм 1-3 следует справедливость следующей теоремы. Георема 1 <о представлении решения задачи апостериорного оценивания).Пусть р=<гх ,(0 - нечеткая точка в к" и х «х .

о> о о

Обозначим

р" «■ аир < р.: 4<зГ >; р*=Сх

/?<=С0,13

Тогда решение х* задачи апостериорного оценивания представи-

мо а виде х" = и р .

х еХ

Л о

Определение. Будем говорить, что задача апостериорного оценивания имеет нетривиальное решение х*, если оно непусто и отлично от всего множества допустимых начальных состояний.

Пусть в системе (1), <2) реализовались некоторые начальное состояние , ВОЗМуценИЯ \>"< ОеэиррИ, ¿еГ, и по-

О О

мехи ¿^со^виррг, которые породили выход у*"=<у*'со,

и

Теорема 2 (критерий нетривиальное™ -решения). Задача апостериорного оценивания имеет нетривиальное решение х* тогда и "только тогда, когда существует нечеткое множество х в к", виррхех , для которого выполнено следующее условие:

О

вирр Х1(ГХ.> £ вирр 2<Г£> ДЛЯ любого ¿.гГ^

и существует по крайней мере одно ТеГу,такое что хьс%>вг<Т}.

Сформулированные выше утверждения позволяют осуществить следующую классификацию выходов у":

I) будем говорить, что полученный выход у" является тривиальным для системы <1). если для любого х«х и для любого

во

(«г справедливо включение

supp xVx J> S isupp 2Ct>, где X'Vx J> «

о о о

II) будем говорить, что полученный выход у* является вырож-, денным для системы (1), если для любого хаХ существует, по

О

крайней мере, один момент измерения t«r , такой что sxtpp xY*.> sZ supp Z(tJ-,

III) будем говорить, что полученный выход У* является уточ-няквдм для системы <1>, если задача апостериорного оценивания имеет нетривиальное решение.

посвшде« рассмотрению задачи апостериорного оценивания с точки зрения задач многокритериальной оптимизации с нечеткими критериями. Имеет место следующая лемма.

Лемма 1. Пусть У* - некоторый уточняющий или тривиальней выуод системы (1>, (2), x* - соответствующее данному выходу решэние. Тогда для лкбого и для любого ьабире. возмущений г = ^ vct> е supp v. ter | существует набор помех

* = £ ?<ro « supp з, te7"u такой 4vo выход, порожденный в

силу (1),(2> начальным состоянием х, возмущениями т и помэ-хами s, совпадает с заданным выходом у*.

Для каждого допустимого .¡ачглоногс состояния и для

каждого момэнта измерения teru определим свертку критерия 2со как функцию "достоверности" начального состояния следующим образом:

й: x нТ —*■ 10д) : с*, о —► sup miTi <IU Cr».

° u VeR" x'ixJ У CO

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

х

Г miп i еХ

с

задаваемой формулой /j<r г J = ■ ie u

Х I 0, rttX

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

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

&1 посьяшен постановке задачи и описанию областей применения билинейных минимаксных задач. Рассматривается задача минимизации функции максимума билинейной функции:

(¡Су> = max JCx,y} -» m.in, (4)

хеХ уеУ

где /Сх, у-Э-j'' Сх+а' х+Л'у, x=xCJ->=< x,JeJ >, y=yCI->, Х=С1,2, . . . ,ir>, J=<1 ,2,. . . ,п>,

е К": Ах < Ь. Ьт <;< < Ь*>, <5)

У=<"у «.R*"- By = d, da< у < d*>, (G)

здесь .A=ACK,J>, В=BCL.I>, C=C(1,J2 - .заданные pxn, qxn, mxn -матрицы соответственно; ь,ьт,ь*>d,dit.di'- заданные векторы соответствующих размерностей,1=<1,2,...&,к=<\, 2,..,р>. Рекение задачи (4-6) состоит ь нахождении оптимального (субоптимального! плана уеГ и соответствующего ему экстремального вектора я-ех.

В §2 ьводятся основные' понятия и определения, которые используются при анализе задачи <4-6) и описании алгоритма ее решения. Известно, что решение билинейной минимаксной за-

дачи с линеиными ограничениями можно искать путем сведения ее к двум задачам линейного программирования. Наше исследо-заиие задачи (4-С) основывается на изучении так называемых верхней и нижней задач линейного программирования, построенных по параметрам исходной задачи. Планы вспомогательных задач линейного программирования нижа будем обозначать через

=» <ъ>СЗ>,гСЗ> ,\<3>,у<Т.» И =» СеСО,т)<1.>,!:<1:>» ДЛЯ

о Н

верхней и нижней задач соответственно.

Внешней опорой задачи (4-6) будем называть любую невырожденную подматрицу ВОП=£С!_ОП,1ОГ,;> матрицы всь,1>, ьопй., |Ь0П|=|хоп|. Отметим, что мы не исключаем вогможиос.ти ^п-10П=э. В этом случае будем говорить, что опора пустая. Определим матрицу £хм,1 }"С'сзлоп->в~*в<ь,1}-ссз ,1} и рассмотрим следующие множества индексов:

.Г ^оп^у ^ч-^оп' кн=кмг,'

з г =л иг , з «о иг (д | + |1 Мл,,,,!-

V у г> у \лг V г 'у' 'у' 1 ОП ' Заметим, что некоторые из описанных множеств могут быть

пустыми, а принцип разбиения множеств будет описан ниже при

построении алгоритма. Обозначим осл.д^^игл'сл».^'^.!,!

и назозем матрицу <эоп=<э^-),оп>-,^:1у-;> внутренней опорой задачи

(4-6), если * Совокупность /г0п=<е0п>°0п> бУдем на_

зывать опорой задачи (4-6).

Пару увУ, будем называть у-опорным планом за- •

дачи (4-6). Если известен х.ех, то <*,гоп> будем называть

х-опорным планом задачи (4-6).

Обозначим гсо «= ь.'<х> -

оп оп оп' оп оп ^сз^э ■= сь'*ои>,г£<ма>] и, используя опору г , определим

вектора потенциалов И оценок:

г1*с.1 ь-сз >-ч'сз уа'сз ,3 .-!„„.>.

А ОП ъ <лг мкг г» ОП г» ОП

»'о^оп'--"' '1»>ашС1 у' ^ •

"'^оп^^оп^Ь^оп^

Д' <ГК„ >=Ь' <Г1СО-и' СЗУАСЗ, А' С1 СI СЗЭВСЗ

. х Н Н ' Н у Н к н

Будем говорить, что опора Гоп нижнесогласована, если

Л <-|Си^>0, 6 <г;.<Ь*, ./еЛ .

X Н ' } )' -1 ОП

Если Хв - план верхней зг. .ачи, '1 хн - план нижней задачи, то пару > будем называть верхним опорным планом, а ,ГС_,> - нижним опорным планом. Верхний опорный план назовем невырожденным, если выполнены саотнопения:

■и<3 У > 0, гО У > О, 1>СЗ У > 0, <й < у. < и*

ы 'а ' v v 4* оп

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

Для верхнего плана х =<Гь>,г,«,у.> введем обозначения: в

1-=<^н:У1=<>, ^Н^-иК^

з.=0>, 3~=3\3°.

Допустим, что опора гоп нижнесогласована. Построим для данной опоры .сопровождающий нижний гглан х^ следующим образом: уРсЛ^ЗУ; [СС1оп,ЗУиСЗУ-<-Г1С1опУ] вс и г}С вычислим, исходя из условий согласования. При этом имеет место следующее равенство: Будем говорить, что опора гоп нижнеоптимальна, если она нижнесогласована и сопровождающий нижний план х^ оптимален в нижней за-

дьче. Верхний опорный план <К„,Уп„> ог.гимапен, если опти-

В ОН Ц

мелен г верхнзй задаче, а опора "оп -- нижнеотимальио.

Имрет место следующая теорема - критерий оптимальности верхнего опорного плана <К,,Г__,>.

о ОП

Теорема 1. Соотношения д <"1 и;>>0, л а

у у Л у

vCJ >=0,сС.7 5=0; Л СК°>£0, Л С|О=0, ■и <ь", ./е* Л_т°,

а ' и» ' х Н 'хН '¿о'-^ОПш

■и.»о* , и -Ь

} ) ОП и>' ) *}* О!» с I ^ ОП а

достаточны, а в случае чевырокде.чьости верхнего опорного

плана ''~<ш> и необходимы, для оптимальности верхнего

опорного плана »''дл'•

Сбоаначим 5с;,зл=л'сл,д л^-сод

' v оп v оп с'ь

ист *СП'1 С' °ОП '1 ^^оп^3 •

Будем называть у-огюрный план > согласованным,

если жз ;><0, к'гл лгО, усз ¿>0.

Предположим, что имеется согласованный опорный плгп <у,Гоп> задачи (4-6), построим по нему сопровождающий верхний план = С1иС,гС,иС,у^ следующим образом: г>СС .Г

Н * ОП ОП ' ь> ъ> ' г- а

Будем говорить, что согласованный опорный план <у,^"оп- невырожденный, если невырожден сопрогождаищий верхний опорный план сх=.гоп>.

Тесрема 2. Для оптимальности согласованного опорного

плана <^>гоп> в задаче (4-6) достаточно, а в случае иевырож-

дгнности у-епорного плана ^-У»'^3' и необходимо, выполнение

условий л а ,о>0, д С1*.><0, л а скиэ>0; ь <&*,

у «Н ' у Н у xH'•Jjj*

-^оп" -

Предположим., что нам известен нижний коплан <5„ и опора

н

fQn. Построим псевдоплан yCLi задачи <4--6) следующим образом: d", если ¿н^>0,

ес™ -5Hll<0. i«l„

любое значение из отрезка Cd ,d*], если <5=0,

y^ln^y- W1 c'c Jon •1 onJ3oi"CLonJ+Q°on• V*'V]

^ on-5=ßcn1 Lon^-ßf Lon •1Hy^* VJ • Очевидно, что если d^.SySd", и ßCLH,l,">vfi^-dfLH^=0,

то будет планом задачи (4-6). Будем говорить, что

х-опорный план <у, ^оп> верчнесогласован, если псевдсплач у является планом задачи (4-6) и выполняются условия согласования, Назовем х-опорный план f"on> невырожденным, если

W*0; Vxi<b!' ^оп' W>0-

Итак, пусть задан план х«=х. По х-опорному плану <х,гоп>

построим сопровождающий' нижний план =(s,ri,( нижней за-

н

дачи:

<5П<Г1^=С'<ГГ , LJ?<rL>-CCI, JixCJ>-h'I>;

f. =17.«0, s =<5„ . tj=0, если <5 >0,

I I ОП v Hv 4 Hl

s.=0, r,.=-Ä , если «5 CO, isl .

V int f 11 (1

Будем говорить, что х-опорный план <*,^оп> оптимален, если план оптимален в нижней задаче.

п

Рассмотрим множества' индексов j"-<jeJ: х.-ь*У,

Ii

j =<>eJ:x.»fc .>, лек,з>хсзэ=ъ<ю>. Имеет место еле-

** J

дующий критерий оптимальности х-опорного плана <х, i"Qn>. Теорема 3. Соотношения

VC3 r>J .>>0, VCJ M J)=0; УО Ajn^>0, vrj \J°^=0

2»' 3» V V

достаточны, а ь случаи невырожденности х-опорного плана <x,fQn> и необходимы, для оптимальности х-опорного плана <х,/-оп> и соответствующего ему псевлоплана у в задаче (4-6).

Из приведенных выше рассуждений следует, что при заданном опорном плене ^у»^,,1 задачи (4-6) можис получить оценку отклонения плача у от оптимального по целевой функции. Пусть у°еУ - оптимальный план задачи (4-6), гогца

£ -min (Ь-А-ч-Ь*' Л^Ь'^&г+К' ¿.у}, Дъ>, As, Av, Ау

где - некоторый согласованный план верхней за-

о

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

в

гласоааьнсй опоры определим оценку субоптимальности /^У» у-опорного плана <У»^0П> как минимум рассматриваемого выражения при следующих ограничениях на прирасения переменных:

AuCJ J>-Zcj AzCJ , Jä-eCJ AufK, Jä-üfK,^. u>il inh ' 2H ЯН ' H H '

Можно показать, что оценка субоптимальности ßcv>FQn> допускает разложение ^У'^оп^ " ^У-* + '5с^оп;> + l3Cg:>' где ¡xFQn> = - мера неоптимальности опоры f"Qn,

ftCy^ = g<y>-gCya> - мера неептимальности плана у, рсв^-рС^У-gCy^ - логрепность при вычислении функции g.

О

При этом, если плану уеУ поставить в соответствие нижкесо-

гласованную опору, сопровождающий нижний план х* которой оп-

н .

тимален в нижней задаче, то ^зсгопл=0. В предположении, что функция s вычисляется точно (или с достаточной точностью), получаем теорему.

Теорема. 4 (критерий «-оптимальности). При - с

(опора F нижнесогласована) у является «-оптимальным планом

задачи I4—61. Для каждого .г-оптикального плана ус существует т.чкая опора г , «то /?<Гу*,г01|;><с.

§4 и §5 писвягсены описанию алгоритма решения билинейной минимаксной задачи при различной исход кол информации ( задан начальный пла.ч у; задан начальные план л; заданы оГ5а начальных плана; информация о начальных планах отсутствует). Для проверки работоспособности и оценки эффективности предложенного алгоритма был прсБеден вычислительный эксперимент с программой, реализующей алгоритм данного типа. Для проведения вычислительного эксперимента был разработан и программно реализован алгоритм генерации билинейных минимаксных задач с заранее известным ответом, который описывается в §6. В §7 приводится описание вычислительного эксперимента и обсуждаются полученные результаты.

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

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

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

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

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

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

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

- алгоритм Нормирования билинейных минимаксных задач с заранее известным ответом.

Основные результаты диссертации опубликованы в patio^ax:

1. Астровскил А.И., Корженевич С. К. Обшая билинейная минимаксная задача: алгоритм, программная реализация //

IX Всесоюзный _симпозчум "Системы программного обеспечения решения задач оптимального планирования". Тез. докладов. Минск, 198G. С.17.

2. Асгровский А. И. , Корхеневич С.К. Методы решения общей ии-линейной минимаксной задачи с линейными ограничениями. Ми., 198G. - 32 с. - (Препринт / АН БССР. Ин-т математики; № 27 (263)).

3. Асгровский А.И., Корженевич С. К. Билчнейнэя минимаксная задача. Алгоритм, область применил, вычислительный экспе-

- го -

римент // Республиканская научная конференция "Математическое моделирование и вычислительная математика". Тез. докладоз. Гродно, 1990. С. 13-14.

4. Астрсвский А. И., КоржганеЕИЧ С. К. Исследование билингйных минимаксных задач: теория и вычислительный эксперимент. Мн. , 1990. - 60 с. - (Препринт / АН БССР. Ин-т математики; № 43 (443)).

5. Астровский А.И., Корженезич С.К. Нечеткие мкохества в задачах апостериорного оценивания для линейных дискретным систем наблюдения // Докл. АН БССР. - 1991. - Т. 38. - Nt 8. - С. 677-680...

J

6. Астровский А.И., Корикневяч С.К. Алгоритм поиска седлозой точки билинейной функции. программная реализация и применение // Всесоюзная конференции "Негладкий анализ и его приложения к математической эхоиомике". Тез. докладов. Баку, 1991. С.6.