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

РГо од

2 9 аяг 7пп:1

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

РЫБКИН Владимир Александрович

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

05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Тверь — 2000

Диссертация выполнена на кафедре информатики Тверского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор A.B. Язенин.

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

доктор физико-математических наук, профессор В.В. Федоров,

кандидат физико-математических наук, доцент Ю.А. Егоров.

Ведущая организация: Вычислительный центр РАН.

Защита диссертации состоится « 3 » июля 2000 г. в /6 часов на заседании диссертационного совета Д.063.97.01 при Тверском государственном университете по адресу: 170000, Тверь, ул. Желябова, 33.

С диссертацией можно ознакомиться в научной библиотеке Тверского государственного университета.

Автореферат разослан « » июня 2000 г.

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

доцент

В.А. Хижняк

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

Актуальность проблемы. Оптимизационные задачи возникают при формализации задач проектирования, анализе сложных экономических I технических систем, решении проблем управления, планирования про-13водственных процессов. При этом может иметь место влияние на негодные данные неконтролируемых возмущающих факторов, ошибок, по-эождаемых идеализированностью математической модели, округлений, 1роизводимых при численной реализации метода решения и т. д. В этих условиях оказывается важным выделение классов оптимизационных за-а,ач, на решения которых подобные факторы не оказывают существенного влияния. Такие задачи называются устойчивыми. Вопросы устойчивости применительно к классическим постановкам задач принятия решений исследовались в фундаментальных трудах А.Н. Тихонова, получили развитие в работах Ф.П. Васильева, В.Г. Карманова, В.В. Федорова и других авторов. В этих работах сформировались математический аппарат и методологические подходы к исследованию устойчивости.

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

Тем не менее, вопросы устойчивости задач возможностной оптимизации изучены явно недостаточно. Наиболее значительными в этом направлении являются работы Р. Фуллера и М. Ковач. В них исследована устойчивость некоторых классов оптимизационных задач и систем линейных уравнений с нечеткими параметрами. Однако, во всех этих работах исследуется фактически один критерий принятия решений — критерий Беллмана-Заде, и, вместе с тем, отсутствует единообразный подход к исследованию — определение устойчивости уточняется в контексте конкретной рассматриваемой задачи. Также следует отметить, что в подавляющем большинстве случаев остается открытым вопрос об условиях сильной устойчивости.

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

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

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

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

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

В случае а, б' назовем задачу устойчивой по результату (или слабо устойчивой), в случае а, б" — устойчивой по решению (сильно устойчивой).

Основными задачами диссертационного исследования являются следующие:

• анализ специфики исследования устойчивости задач оптимизации в услових нечеткой или неполной информации при возможностной интерпретации неопределенности;

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

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

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

'Тихонов А.Н. О некорректных задачах оптимального планирования // ЖВМиМФ, 1966, т. 6, № 1,с. 81-89.

• установление взаимосвязей между слабо и сильно устойчивыми задачами;

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

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

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

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

1) единообразный подход к исследованию устойчивости задач оптимизации с нечеткими параметрами на базе теории возможностей;

2) теоремы устойчивости базовых моделей возможностной оптимизации в различных классах распределений нечетких параметров;

3) условия эквивалентности сильной и слабой устойчивости;

4) метод регуляризации неустойчивых моделей нечеткой оптимизации, основанный на понижении возможности выполнения ограничений.

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

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

Внедрение результатов работы. Проведенные научные исследования поддержаны грантом РФФИ, проект № 98-01-00212 «Разработка и исследование моделей и методов возможностной оптимизации», исполнителем которого диссертант являлся в 1998 - 2000 гг. Результаты диссертации используются также в учебном процессе на факультете прикладной математики и кибернетики Тверского госуниверситета.

Апробация. Основные результаты диссертационной работы докладывались автором на 6-м и 7-м Европейских конгрессах по интеллектуальным технологиям и мягким вычислениям (Е11Р1Т '98, ЕиР1Т '99, Ахен, Германия), на научной конференции, посвященной 70-летию со дня рождения академикаВ.А. Мельникова (Москва, 1999 год), на I конференции-семинаре «Математические модели сложных систем» (Тверь, 1999 год), на семинарах в ТвГУ и ВЦ РАН.

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

Структура и объем диссертаилонной работы. Диссертация состоит из введения, трех глав и заключения, содержит 5 рисунков, 1 таблицу, список литературы, включающий 96 наименований. Общий объем работы составляет 101 страницу.

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

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

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

Определение 1.2. Мерой возможности называется функция 7Г : Р(Г) —> [0,1], обладающая следующими свойствами:

1)тг{0} = О, я{Г}=1,

2) и А,} = зиртгТАЛ УА,- 6 Р(Г), V/.

<6/

Определение 1.3. Мерой необходимости называется функция и : Р(Г) —> [0,1], обладающая свойствами:

1)1/{0}=О, *>{Г} = 1,

2) П А} = Ы»{А{} УА,' е Р(Г), V/. •€/ »е/

Здесь Г есть множество элементов 7 6 Г, Р(Г) — множество всех подмножеств Г. В дальнейшем триплет (Г,Р(Г), 7г) будем называть воз-можностным пространством.

Определение 1.4. Возможностей величиной называется отображение 2 : ГЕ1, априорные возможные значения которого ограничены функцией : —[0,1], называемой распределением возможностей величины 2:

/**(*) =*{7€ Г|Я(7) = *} УгбЕ1.

1\2 есть «возможность того, что величина 2 может принять значение г». Здесь и далее Е1, Еп обозначают евклидовы пространства соответствующей размерности.

Определение 1.8. Возможностная величина 2 называется выпуклой, если ее функция распределения является квазивогнутой, т. е.

/^(Ал + (1 -Л)г2) > тт{112{г{), ЯгЫ} Угь г2еЕх, УА€[0,1].

Выпуклые возможностные величины со значениями в Е1 также называют возможностными (нечеткими) числами.

Пусть 2\, ..., 2п — возможностные величины. Функция распределения совокупности возможностных величин определяется следующим образом:

М2,,-.,2„(г1. - .2п) = т{7 е Г 1^1 (7) = 2Ь ...,гп{ч) = г„>,

(¿1,...,*„)€£".

Определение 1.9. Возможностные величины 2\, ..., 2п называются минисвязанными, если для любого подмножества {г'1, множества {1,..., п}

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

Пусть 2\, ¿/2 — возможностные величины, II — отношение, заданное на Е1 х Е1. Возможность того, что 2\ находится в отношении II к 22 есть

тг{ВД,г2)} = тг{7 € Г| II(¿^(7), 22Ь))}.

Носителем возможностной величины Z будем называть множество

множеством а-уровня — множество

[Zr^izEE'lvziz)^*}, а € (0,1],

модальным значением — точку а £ Ei, такую что /iz(a) = 1.

Множество всех возможностных величин, характеризующихся квазивогнутыми функциями распределения, имеющих компактные носители и замкнутые множества a-уровня, Va € (0,1], обозначим через J(Е1). Определим метрику в множестве $(Е1):

d(Z1,Z2)= sup dK{[Z{\a,[Z7\a).

0<a<l

Здесь da — метрика Хаусдорфа, da (Л, В) = тах[Д(Л, В), Д (В, Л)], где

Д(Л, В) = sup inf |]a — Ь||, Д(В, Л) = sup inf ||a - Ь|| есть полуметрики. а£АЬеВ ЬеВавА

Пусть 5с(Ь11) С $ {Е1) есть подмножество возможностных величин с непрерывными распределениями. Равномерную метрику в (Е1) определим следующим образом:

c(ZuZ2)= sup \fxZl{t) -/iZa(f)l-

Для любого Z € и в > 0 определим вспомогательную характе-

ристику bj{Z\6), называемую модулем непрерывности величины Z:

u{z-,e)= sup I^(i') - fiz{t")\. |t'-t"|<e

Наряду с понятием возможностной величины, фундаментальным в теории возможностей является понятие возможностной случайной величины. Пусть {Q, Л, Р) есть вероятностное пространство.

Определение 1.15. Возможностной случайной величиной называется отображение У : П х Г т$(Е1), определяемое следующим образом:

п

где (А\, ..., Ап) есть разбиение Q, /д, — индикаторная функция события

At.

Если pi — P(Ai), то У принимает значение Yi(7) с вероятностью р;. В этом случае математическое ожидание Е У случайной величины У является возможностной величиной, имеющей вид

п i=i

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

»Лемма 1.6. Пусть {Zn\n = 1,2,...} есть последовательность воз-можностных величин, принадлежащих (Е1), Z (z^dE1). Тогда

lim d (Z, Zn) = 0 lim c(Z, Zn) = 0.

Л-+ОО П-+ОЭ

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

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

Пусть (iij[l), Ь{(7) есть минисвязанные возможностные величины, определенные на возможностном пространстве (Г,Р(Г),5г), а о — мера тт или мера v, Ro — отношение на Ех х Е1, а, € (0,1] — уровни возможности, X = (i £ Еп | xi, ..., хп > 0} — множество альтернатив,

Модальная проблема:

M[/o(z>7)] -+max, M[/i (*,7)] = 0, »= 1, ...,m, хеХ,

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

Проблема максимизации уровня при построчных ограничениях по возможности:

k max,

тШгл) = к) > «о,

S (г.-у) = 0} > a,-, i = l, ...,т, хеХ.

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

В приведенных выше моделях /0(г, 7) = aoj(j) xj • Проблема максимизации меры достижения цели при построчных ограничениях по возможности:

^о {/о Iх. 7) Ro 0} шах,

*{fi (г.7) = 0} > » = 1. хеХ.

Здесь /о (х, 7) = Ц?=1 aoj(y) Xj - 60(7).

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

Проблема максимизации меры достижения ожидаемой цели при построчных ограничениях по ожидаемой возможности:

ME/ofa.w.vjRoO} max, тг{Е/,• (*,w,7) = 0} > о,-, i= 1, ... ,m, :с€ X.

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

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

Пусть 51 есть оптимальное значение целевого функционала (результат решения) задачи, содержащей возможностные параметры 01(7),..., ар(7), ОТ достигается на множестве Хо С X, № — результат решения этой задачи с параметрами <^(7), ..., а*(7), такими, что

тах ¿(«¡(7),а-(7)) < е, »=1 ,...,р

где е € Е1, е > 0 — величина возмущения, достигается на множестве XI С X.

Определение 2.1. Задача возможностной оптимизации являет-1 ся устойчивой по результату (или слабо устойчивой), если

(У<5 > 0) (3£0 > 0) (Уе > 0, шах <1{а^),а\(7)) < г < £0) : - | < «5.

¡=1......

Определение 2.2. Задача возможностной оптимизации является устойчивой по решению (сильно устойчивой), если

> 0) (Зе0 > 0) (Уе > 0, шах с{(а,(7), а? (7)) < £ < £о) : Д(*о. <

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

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

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

Теорема 3.1. Если в модели максимизации уровня возможностные параметры целевого функционала являются минисвязанными и принадлежат множеству $ (Е1), то справедлива оценка

|!Я ~ 91£ | < £ sup Их

x£D

и данная модель устойчива по результату.

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

Теорема 3.3. Если в модели максимизации возл{ожности достижения цели возможностные параметры целевого функционала являются минисвязанными и принадлежат множеству 5С (Е1), то имеет место оценка

|9Я-9\Е| < max{w(aoj;e),w(a£0j;£),a.(bo;e),w(b^£:)} и данная модель устойчива по результату.

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

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

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

Теорема 3.13. Устойчивая по решению или по результату задача максимизации уровня имеет ограниченное множество решений.

Теорема 3.14. Проблема максимизации уровня при построчных ограничениях по возможности с параметрами aoj € ^(Е1), € §:с(£'1) устойчива по решению тогда и только тогда, когда она устойчива по результату.

2Федоров В.В. К вопросу об устойчивости задачи линейного программирования // ЖВМиМФ, 1975, т. 15, № 6, с. 1412-1423.

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

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

D4 = {t£X | тг{/, (а, 7) = 0} > а,- + т), i = 1,..., тп].

Теорема 3.22. Пусть в задаче возможностьюй оптимизации мо-( дель критерия устойчива по результату, множество допустимых решений, определяемое системой построчных ограничений по возможности с параметрами a,j, Ь,- € З^Е1), ограничено. Если существует г) > О такое, что непусто, то данная задача устойчива по решению.

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

Вводится в рассмотрение система

тг{/, (х, 7) = 0} > ог,- - г, г — 1, ..., ш, х Е X,

с параметром регуляризации т Е (0,а], а = minj{cc,}, й SciE1),

определяющая множество допустимых решений DT. Отмечается, что корректность предложенного метода обеспечивается выполнением требования A(Dr, D) —>- 0 при г ->■ 0.

Следующая теорема показывает, что регуляризованная система обладает свойством устойчивости при любом г СЕ (0, о]. Пусть DeT есть множество допустимых решений, определяемое возмущенной регуляризованной системой ограничений.

Теоре ма 3.26. I) lim Д(т,DT) = 0. II) lim Д(Я£,£>) = 0.

е-»0+ Т-+0+

г=о(г)

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

Основные результаты диссертации

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

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

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

3. Доказано, что в случае устойчивости (по решению или по результату) рассмотренные модели имеют ограниченное множество решений. При этом условии доказана эквивалентность устойчивости по результату устойчивости по решению.

4. Получено условие сильной устойчивости для всех рассмотренных моделей.

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

Благодарности

Автор выражает глубокую благодарность своему учителю профессору A.B. Язенину, научно-педагогическая деятельность которого сделала возможным появление на свет данной работы.

3Yazenin A.V. On the problem of possibilistic optimization // Fuzzy Sets and Systems, 1996, v. 81, p. 133-140.

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

1. Рыбкин В. А. Исследование устойчивости одной задачи возможност-иого линейного программирования // Ученые записки ТвГУ, 1998, т. 4, с. 9-13.

2. Rybkin V.A., Yazenin A.V. Regularization and stability of possibilistic linear programming problems // Proceedings of 6th European Congress on Intelligent Techniques к Soft Computing, Aachen, Germany, 1998, v. 1, p. 37-41.

3. Rybkin V.A., Yazenin A.V. Strong and weak stability in possibilistic linear programming // Proceedings of 7th European Congress on Intelligent Techniques & Soft Computing, Aachen, Germany, 1999, v. 1, p. 193-196.

4. Рыбкин В.А. Исследование устойчивости задач возможностной оптимизации // Сборник докладов научной конференции, посвященной 70-летию со дня рождения академика В.А. Мельникова, РАН, Москва, 1999, с. 190-192.

5. Рыбкин В.А. О специфике вопросов устойчивости в нечеткой оптимизации / / Моделирование сложных систем: сборник научных трудов, вып. 3, Тверь, 2000 (в печати).

6. Рыбкин В.А., Язенин А.В. О сильной устойчивости в задачах возможностной оптимизации // Известия РАН. Теория и системы управления, 2000, № 2, с. 90-95.

7. Rybkin V.A., Yazenin A.V. On the problem of stability in possibilistic optimization // International Journal of General Systems, 2000 (в

печати).

Введение

1 Исчисление возможностей

1.1 Меры неопределенности

1.2 Возможностные величины.

1.3 Преобразования.

1.4 Операции.

1.5 Отношения.

1.6 Метризация множеств возможностных величин.

1.7 Замкнутые семейства.

1.8 Теорема представления.

1.9 Возможностные случайные величины.

2 Модели задач возможностной оптимизации и критерии устойчивости

2.1 Модели критерия.

2.2 Модели ограничений

2.3 Модели принятия решений.

2.4 Критерии устойчивости.

3 Исследование устойчивости задач возможностной оптимизации

3.1 Устойчивость критериев оптимальности.

3.1.1 Модель уровневой оптимизации.

3.1.2 Модель максимизации возможности

3.1.3 Модель максимизации необходимости

3.1.4 Принцип ожидаемой возможности.

3.2 Устойчивость решений задач возможностной оптимизации

3.3 Метод регуляризации.

Актуальность

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

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

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

Тем не менее, вопросы устойчивости задач возможностной оптимизации изучены явно недостаточно. Наиболее значительными в этом направлении являются работы Р. Фуллера [51, 69, 72, 73, 74] и М. Ковач [23, 24]. В них исследована устойчивость некоторых классов оптимизационных задач и систем линейных уравнений с нечеткими параметрами. Однако, во всех этих работах исследуется фактически один критерий принятия решений — критерий Беллмана-Заде, и, вместе с тем, отсутствует единообразный подход к исследованию — определение устойчивости уточняется в контексте конкретной рассматриваемой задачи. Также следует отметить, что в подавляющем большинстве случаев остается открытым вопрос об условиях сильной устойчивости.

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

Обзор литературы

Вопросам устойчивости моделей и принципов принятия решений в теории оптимизации систем и исследовании операций уделено значительное внимание. Очевидная важность и многообразие рассматриваемых аспектов позволило результатам исследований оформиться в самостоятельный раздел — теорию устойчивости задач оптимизации. Из большого числа работ, посвященных данной тематике, в первую очередь следует отметить общепризнанные монографии А.Н. Тихонова, В.Я. Арсенина [44], В.К. Иванова и др. [20], а также монографии С.А. Ашманова [5], Ф.П. Васильева, А.Ю. Иваницкого [11], В.Г. Карма-нова [21], Д.А. Молодцова [30], В.В. Федорова [50]. Достаточно полные библиографии по теории устойчивости приведены, например, в [11, 32].

Что касается устойчивости моделей нечеткой и возможностной оптимизации, составляющих подкласс класса задач оптимизации и принятия решений в условиях неопределенности, то здесь, как уже упоминалось ранее, основополагающими являются работы Р. Фуллера и М. Ковач. В них последовательно исследуется устойчивость систем линейных возможностных равенств, параметры которых характеризуются трапециевидными [23] и липшицуемыми распределениями [74], задач нечеткой линейной оптимизации в классах симметричных три-ангулярных [73] и непрерывных распределений [72]. Приведем основные полученные результаты.

В работе [23] рассмотрены системы линейных алгебраических уравнений с нечеткими коэффициентами, моделируемыми симметричными трапециевидными нечеткими числами с верхней шириной в > 0 и нижней шириной а > 0. Получена оценка

7 — <JS\\c — sup |а(х) — < min{l; ¿/а'}, где <т, as есть функции принадлежности нечетких решений исходной и возмущенной задач соответственно, S — величина возмущения.

В предположении, что множество четких оптимальных решений системы непусто, получена оценка р{х,Х*) = inf \х-у\< C0{S + e)(\x\i + l), х е Х*(6), где X* — множество оптимальных решений исходной системы, = х Е Мп | as(x) = 1}, С'о — некоторая положительная постоянная. В работе также отмечено, что так как симметричные трапециевидные или триангулярные нечеткие числа могут быть получены сглаживанием прямоугольных или острых нечетких чисел, то такое сглаживание представляет собой некоторую регуляризацию систем, рассматриваемых на классах прямоугольных или острых нечетких чисел.

В работе [73] исследована линейная задача минимизации четкой целевой функции при нечетких ограничениях, параметры которых являются симметричными триангулярными нечеткими числами. Получена оценка

1 1 i - flS\\c = sup Ifl{x) - HS(x) I <6[— + где /¿, ¡/ есть степени выполнения ограничений исходной и возмущенной систем, а — коэффициент нечеткости параметров технологической матрицы, d — минимальный коэффициент нечеткости компонент вектора ресурсов.

В работе [72] для задачи возможностного линейного программирования в постановке Дж. Бакли [68] получена оценка возмущения возможностного распределения целевого функционала, позволяющая сделать вывод о слабой устойчивости задачи при моделировании нечетких параметров непрерывными функциями распределения: sup \Poss[Zs = z]~ Poss[Z = z]\< co(S), xeRn и;(с>) = тах{со>(ау,5), со(а^б), и(Ь{,6), ш(Ь*,5), иси(с£,5). Здесь у

Ровэ^ = г], Робб^ = г] и аг-у, 6г-, с,, оф, с^ есть возможностные распределения целевых функционалов и параметры исходной и возмущенной задач соответственно. Отметим, что в теореме 3.3 мы получаем аналогичную оценку для задачи максимизации меры достижения нечеткой цели, используя несколько более простую технику доказательства, чем в данной работе.

В заключение упомянем ряд работ [64, 65, 76, 89], посвященных выходящему за рамки тематики данной диссертации исследованию устойчивости некоторых задач многокритериальной нечеткой оптимизации.

Цель работы

Цель предлагаемой диссертационной работы состоит в исследовании устойчивости ряда моделей возможностной оптимизации, называемых базовыми, поведение которых относительно некорректности задания нечетких параметров не изучено до настоящего времени. При возможностной интерпретации нечеткости, которой мы придерживаемся в данной работе, под некорректностью задания параметров понимается наличие погрешностей в задании функций распределения их возможных значений. Устойчивость задачи в данном случае, в соответствии со сложившейся классической методологией [44], предлагается определять выполнением следующих условий: а) задача разрешима на множествах точных и приближенных параметров; б') оптимальные значения нечеткого целевого функционала, вычисленные по приближенным данным, при уменьшении погрешности приближения сходятся к его точному оптимальному значению; б") множество решений (оптимальных альтернатив) задачи с приближенными параметрами при уменьшении погрешности стягивается к множеству решений задачи с точными параметрами.

В случае а, б' назовем задачу устойчивой по результату (или слабо устойчивой), в случае а, б" — устойчивой по решению (сильно устойчивой).

Основные задачи

Основными решаемыми в диссертационной работе задачами являются:

• анализ специфики исследования устойчивости задач оптимизации в услових нечеткой или неполной информации при возмож-ностной интерпретации неопределенности;

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

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

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

• установление взаимосвязей между слабо и сильно устойчивыми задачами;

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

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

Методика исследования

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

Практическая значимость работы

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

Внедрение результатов работы

Проведенные научные исследования поддержаны грантом РФФИ, проект № 98-01-00212 «Разработка и исследование моделей и методов воз-можностной оптимизации», исполнителем которого диссертант являлся в 1998 - 2000 гг. Результаты диссертации используются также в учебном процессе на факультете прикладной математики и кибернетики Тверского госуниверситета.

Апробация

Основные результаты диссертационной работы докладывались автором на б-м и 7-м Европейских конгрессах по интеллектуальным технологиям и мягким вычислениям (ЕИИТ '98, ЕЦЕ1Т '99, Ахен, Германия), на научной конференции, посвященной 70-летию со дня рождения академика В.А. Мельникова (Москва, 1999 год), на I конференции-семинаре «Математические модели сложных систем» (Тверь, 1999 год), на семинарах в ТвГУ и ВЦ РАН.

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

Диссертация состоит из введения, трех глав, заключения и библиографии.

Заключение

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

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

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

3. Доказано, что в случае устойчивости (по решению или по результату) рассмотренные модели имеют ограниченное множество решений. При этом условии доказана эквивалентность устойчивости по результату устойчивости по решению.

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

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

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

1. Аверкин А.Н. и др. Нечеткие множества в моделях управления и искусственного интеллекта / Под редакцией Поспелова Д.А. М.: Наука, 1986.

2. Агаян Г.М., Рютин A.A., Тихонов А.Н. О задаче линейного программирования с приближенными данными // ЖВМиМФ, 1984, т. 24, № 9, с. 1303-1311.

3. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.

4. Ашманов С. А. Условие устойчивости задач линейного программирования // ЖВМиМФ, 1981, т. 21, № 6, с. 1402-1410.

5. Ашманов С. А. Линейное программирование. М.: Наука, 1981.

6. Борисов А.Н., Алексеев A.B., Меркурьева Г.В. и др. Обработка нечеткой информации в системах принятия решений. М.: Радио и связь, 1989.

7. Борисов А.Н., Крумберг O.A., Федоров И.П. Принятие решений на основе нечетких моделей. Рига: Зинатне, 1990.

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

9. Васильев Ф.П. Критерии устойчивости общей задачи линейного программирования // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика, 1998, № 2, с. 17-20.

10. Васильев Ф.П. К вопросу устойчивости методов регуляризации в линейном программировании // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика, 1998, № 3, с. 19-23.

11. Васильев Ф.П., Иваницкий АЛО. Линейное программирование. М.: Факториал, 1998.

12. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Советское радио, 1966.

13. Данциг Дж. Линейное программирование, его обобщения и применение. М.: Прогресс, 1966.

14. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

15. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике. М.: Радио и связь, 1990.

16. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

17. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988.

18. Заде JI.A. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976.

19. Зангвилл У.И. Нелинейное программирование. М.: Советское радио, 1973.

20. Иванов В.К., Васин В.В., Танана В.П. Теория линейных некорректных задач и ее приложения. М.: Наука, 1978.

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

22. Ковалерчук Б.Я. О корректности применения и обосновании теории размытой оптимизации // Изв. АН УзССР, серия техн. наук, 1981, № 5, с. 7-12.

23. Ковач М., Васильев Ф.П., Фуллер Р. Об устойчивости нечеткого решения систем линейных алгебраических уравнений с нечеткими коэффициентами // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика, 1989, № 1, с. 5-9.

24. Ковач М., Фуллер Р. О нечетко расширенных линейных системах равенств и неравенств / Актуальные вопросы прикл. математики, М.: МГУ, 1989, с. 73-80.

25. Колмогоров А.Н. Основные понятия теории вероятностей. М: Наука, 1974.

26. Кофман А. Введение в теорию нечетких подмножеств. М.: Радио и связь, 1982.

27. Минаев Ю.Н. Стабильность экономико-математических моделей. М.: Статистика, 1980.

28. Мину М. Математическое программирование. М.: Наука, 1990.

29. Моисеев H.H., Иванилов Ю.П., Столярова E.H. Методы оптимизации. М.: Наука, 1978.

30. Молодцов Д.А. Устойчивость принципов оптимальности. М.: Наука, 1987.

31. Морозов В.А. Методы регуляризации неустойчивых задач. М.: МГУ, 1987.

32. Морозов В.А., Гребенников А.И. Методы решения некорректно поставленных задач: алгоритмический аспект. М.: МГУ, 1992.

33. Муртаф М. Современное линейное программирование. М.: Мир, 1984.

34. Нечеткие множества и теория возможностей / Перевод с английского В.Б. Кузьмина под редакцией Травкина С.И. М.: Радио и связь, 1986.

35. Орлов А.И. Устойчивость в социально-экономических моделях. М.: Наука, 1979.

36. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Наука, 1981.

37. Рыбкин В.А. Исследование устойчивости одной задачи возможностного линейного программирования // Ученые записки ТвГУ, 1998, т. 4, с. 9-13.

38. Рыбкин В.А. Исследование устойчивости задач возможностной оптимизации // Сборник докладов научной конференции, посвященной 70-летию со дня рождения академика В.А. Мельникова, РАН, Москва, 1999, с. 190-192.

39. Рыбкин В.А., Язенин A.B. О сильной устойчивости в задачах возможностной оптимизации // Известия РАН. Теория и системы управл., 2000, № 2, с. 90-95.

40. Рыбкин В.А. О специфике вопросов устойчивости в нечеткой оптимизации // Моделирование сложных систем: сборник научных трудов, вып. 3, Тверь, 2000.

41. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

42. Тихонов А.Н. О некорректных задачах оптимального планирования // ЖВ-МиМФ, 1966, т. 6, № 1, с. 81-89.

43. Тихонов А.Н., Караманов В.Г., Руднева Т.Л. Об устойчивости задач линейного программирования. Сб. работ НИВЦ МГУ «Вычислительные методы и программирование», М.: МГУ, 1969, Вып. 12, с. 3-9.

44. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1974.

45. Тихонов А.Н. О нормальных решениях приближенных систем линейных алгебраических уравнений // Докл. АН СССР, 1980, т. 254, № 3, с. 549-554.

46. Тихонов А.Н., Гончарский A.B., Степанов В.В., Ягола А.Г. Регуляризующие алгоритмы и априорная информация. М.: Наука, 1983.

47. Тихонов А.Н., Морозов В.А., Кармазин В.Н. О задаче коррекции линейных неравенств. Сб. работ НИВД МГУ «Численный анализ: методы, алгоритмы, приложения», М.: МГУ, 1985, с. 3-13.

48. Трухаев Р.И. Модели принятия решений в условиях неопределенности. М.: Наука, 1981.

49. Федоров В.В. К вопросу об устойчивости задачи линейного программирования // ЖВМиМФ, 1975, т. 15, № 6, с. 1412-1423.

50. Федоров В.В. Численные методы максимина. М.: Наука, 1979.

51. Фуллер Р. Исследование некоторых классов нечетких линейных задач. Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Москва, 1987.

52. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.

53. Шер А.П. Решение задачи математического программирования с линейной целевой функцией в размытых ограничениях // Автоматика и телемеханика, 1980, № 7, с. 137-143.

54. Шокин Ю.И. Интервальный анализ. Новосибирск: Наука, 1981.

55. Юдин Д.Б. Математические методы управления в условиях неполной информации. М.: Советское радио, 1974.

56. Язенин A.B. Задача векторной оптимизации с нечеткими коэффициентами важности критериев // Математические методы оптимизации и управления в сложных системах. Калинин, КГУ, 1981, с. 38-51.

57. Язенин A.B. Нечеткое математическое программирование. Калинин, 1986, 60 с.

58. Язенин A.B. Гибридная экспертная система для планирования // Изв. АН СССР. Техн. кибернетика, 1989, № 5, с. 162-167.

59. Язенин A.B. Линейное программирование со случайными нечеткими данными // Изв. АН СССР. Техн. кибернетика, 1991, № 3, с. 52-58.

60. Язенин A.B. Модели возможнос.тного программирования в оптимизации систем // Изв. АН СССР. Техн. кибернетика, 1991, № 5, с. 133-142.

61. Язенин A.B. Возможностное и интервальное линейное программирование // Изв. РАН. Техн. кибернетика, 1993, № 5, с. 149-155.

62. Язенин A.B. Моделирование ограничений в задачах возможностного линейного программирования // Изв. РАН. Техн. кибернетика, 1994, № 2, с. 84-88.

63. Язенин A.B. Методы оптимизации и принятия решений при нечетких данных. Автореферат диссертации на соискание ученой степени доктора физико-математических наук. Тверь, 1995.

64. Ammar E.E., Kassem M.A. On stability analysis of multicriteria LP problems with fuzzy parameters // Fuzzy Sets and Systems 82 (1996), p. 331-334.

65. Ammar E.E. Stability of multiobjective NLP problems with fuzzy parameters in the objectives and constraints functions // Fuzzy Sets and Systems 90 (1997), p. 225-234.

66. Bellman R., Zadeh L.A. Decision making in a fuzzy environment // Management Sci. 17 (1970), p. 141-164.

67. Buckley J.J. Possibility and necessity in optimization // Fuzzy Sets and Systems 25 (1988), p. 1-13.

68. Buckley J.J. Possibilistic linear programming with triangular fuzzy numbers // Fuzzy Sets and Systems 26 (1988), p. 135-138.

69. Canestrelli E., Giove S., Fuller R. Stability in possibilistic quadratic programming // Fuzzy Sets and Systems 82 (1996), p. 51-56.

70. Dubois D., Prade H. Systems of fuzzy linear constraints // Fuzzy Sets and Systems 3 (1978), p. 37-48.

71. Dubois D., Prade H. Fuzzy Sets and Systems: Theory and Applications. Academic Press, New York, 1980.

72. Fedrizzi M., Fuller R. Stability in possibilistic linear programming with continuous fuzzy number parameters // Fuzzy Sets and Systems 47 (1992), p. 187-191.

73. Fuller R. On stability in fuzzy linear programming problems // Fuzzy Sets and Systems 30 (1989), p. 339-344.

74. Fuller R. On stability in possibilistic linear equality systems with Lipschitzian fuzzy numbers // Fuzzy Sets and Systems 34 (1990), p. 347-353.

75. Kaleva O. Fuzzy differencial equations // Fuzzy Sets and Systems 24 (1987), p. 301— 317.

76. Kassem M.A., Ammar E.E. Stability of multiobjective nonlinear programming problems with fuzzy parameters in the constraints // Fuzzy Sets and Systems 74 (1995) p. 343-351.

77. Kwakernaak H. Fuzzy random variables I. Definitions and theorems // Inform. Sci. 15 (1978), p. 1-29.

78. Kwakernaak H. Fuzzy random variables II. xAlgorithms and examples for discrete case // Inform. Sci. 17 (1979), p. 253-278.

79. Lodwick W. Analysis of structure in fuzzy linear programs // Fuzzy Sets and Systems 38 (1990), p. 15-26.

80. Luhandjula M.K. Linear programming problems under randomness and fuzziness // Fuzzy Sets and Systems 10 (1983), p. 45-55.

81. Luhandjula M.K. On possibilistic linear programming // Fuzzy Sets and Systems 18 (1986), p. 15-30.

82. Luhandjula M.K. Fuzzy optimization: an appraisal // Fuzzy Sets and Systems 30 (1989), p. 257-287.

83. Nahmias S. Fuzzy variables // Fuzzy Sets and Systems 1 (1978), p. 97-110.

84. Nahmias S. Fuzzy variables in a random environment // Advances in fuzzy sets theory, Amsterdam, 1979.

85. Puri M.L., Ralescu D.A. Fuzzy random variables // Journal of mathematical analysis and applications 114 (1986), p. 409-422.

86. Rybkin V.A., Yazenin A.V. Regularization and stability of possibilistic linear programming problems // Proceedings of 6th European Congress on Intelligent Techniques & Soft Computing, Aachen, Germany, 1998, v. 1, p. 37-41.

87. Rybkin V.A., Yazenin A.V. Strong and weak stability in possibilistic linear programming // Proceedings of 7th European Congress on Intelligent Techniques & Soft Computing, Aachen, Germany, 1999, v. 1, p. 193-196.

88. Rybkin V.A., Yazenin A.V. On the problem of stability in possibilistic optimization // International Journal of General Systems, 2000 (in print).

89. Saad O.M. Stability on multiobjective linear programming problems with fuzzy parameters // Fuzzy Sets and Systems 74 (1995), p. 207-215.

90. Tanaka H., Asai K. Fuzzy linear programming with fuzzy numbers // Fuzzy Sets and Systems 13 (1984), p. 1-10.

91. Yazenin A.V. Fuzzy and stochastic programming // Fuzzy Sets and Systems 22 (.1987), p. 171-180.

92. Yazenin A.V. On the problem of possibilistic optimization // Fuzzy Sets and Systems 81 (1996), p. 133-140.

93. Yazenin A.V., Wagenknecht M. Possibilistic optimization. Cottbus, Germany, 1996.

94. Zadeh L.A. Fuzzy sets // Information and Control 8 (1965), p. 338-353.

95. Zadeh L.A. Fuzzy sets as a basis for a theory of possibility // Fuzzy Sets and Systems 1 (1978), p. 3-28.

96. Zimmermann H.-J. Applications of fuzzy set theory to mathematical programming // Inform. Sci. 36 (1985), p. 29-58.