Содержание к диссертации
Введение
1 Исчисление возможностей при агрегировании нечеткой информации на основе t-норм 14
1.1 Основные понятия теории возможностей 14
1.2 Агрегирование нечеткой информации на основе t-норм 22
1.3 Способы моделирования взаимодействия возможностных переменных 26
1.4 Взвешенная Tw-сумма нечетких величин 30
1.5 Примеры идентификации функции распределения TV-суммы и расчета границ ее а-уровневых множеств 36
1.6 Выводы по первой главе 40
2 Методы решения задач возможностного программирования с взаимодействующими нечеткими параметрами 43
2.1 Базовые модели возможностной оптимизации 43
2.2 Непрямые методы решения в случае меры возможности 45
2.3 Непрямые методы решения в случае меры необходимости 54
2.4 Спецификация генетического алгоритма решения эквивалентных детерминированных аналогов 59
2.5 Выводы по второй главе 65
3 Сравнительное изучение эквивалентных детерминирован ных аналогов задач возмолсностного программирования при различных t-нормах 69
3.1 Сравнительный анализ 69
3.2 Теорема вложенности множеств допустимых решений 75
3.3 Исследование задач возможностной оптимизации в контексте возможность/необходимость 79
3.4 Выводы по третьей главе 81
4 Программный комплекс и модельные расчеты 84
4.1 Программный комплекс FIESTA 84
4.2 Архитектура системы 85
4.3 Модельные расчеты в системе FIESTA 89
4.4 Выводы по четвертой главе 97
Заключение 99
Список литературы
- Агрегирование нечеткой информации на основе t-норм
- Взвешенная Tw-сумма нечетких величин
- Непрямые методы решения в случае меры возможности
- Теорема вложенности множеств допустимых решений
Введение к работе
Актуальность
Физико-математические науки, вместе со всей наукой в целом, переживают эпоху сменяющих друг друга научных революций и, как следствие, смену типов научной рациональности: от классического ньютоновского детерминизма, когда весь мир представлялся точным, четким, предсказуемым, действующим по понятным, логичным, но еще не до конца открытым законам природы, к эйнштейновской неклассической относительности, когда мир вокруг нас перестает быть таким понятным и детерминированным, все приобретает свойство относительности, а вероятность становится неотъемлемым свойством материи, и, наконец, к современным постнеклассическим человеко-центрированным взглядам на мир. В частности, стало понятно, что далеко не все явления нашей жизни можно описать при помощи лишь строгих детерминированных математических моделей, что многие практические задачи приходится решать в условиях неопределенности, возникающей по самым разным причинам: из-за неполноты, неточности или полного отсутствия информации или из-за того, что ряд задач принципиально не решается методами строгой математики.
Одним из ярких примеров современных постнеклассических наук являются науки из цикла искусственного интеллекта, основная задача которых — моделирование человеческого интеллекта, самого процесса мышления и принятия решений, механизма человеческого восприятия, рассуждений и оценки, агрегирования и оперирования знаниями и т.д. — иными словами решение человеко-центрированных задач. При этом многие классические математические науки, применяемые для решения практических задач, как например теория оптимизации, также получили свое дальнейшее развитие в свете постнеклассических идей искусственного интеллекта. Очевидно, что результат применения современных ма-
тематических методов оптимизации может быть в ряде случаев (в силу своего детерминизма) абстрагированным от действительности. С одной стороны, человек, принимая те или иные решения, в основном оперирует не точными значениями, а нечеткими понятиями: больше, меньше, примерно, около и т.д. С другой стороны, иногда задачи приходится решать в условиях неполной (неточной) исходной информации.
В настоящее время интенсивно разрабатываются многочисленные математические формализмы для описания и моделирования неопределенности. Одним из таковых является подход, предложенный в середине 60-х годов американским ученым Лотфи Заде. Он предложил способ моделирования неопределенности как нечеткости, основанный на идее расширения понятия характеристической функции множества до функции принадлежности, принимающей значения на отрезке [0,1]:
рА(-):А->[0,1].
Значения функции /^л(-) характеризуют степень проявления отдельных свойств объектом А.
Одним из многих научных направлений, использующих упомянутый математический аппарат для моделирования нечеткой информации, является теория нечеткой (возможностной) оптимизации. Предметом ее изучения стали модели и методы оптимизации в условиях неточности, нечеткости, неполноты информации. Вместо четких значений параметров в таких задачах используются возможностные величины, которые моделируют неопределенность описания модели.
Возможностная оптимизация — это сравнительно молодая научная дисциплина, в которой есть еще много нерешенных вопросов, требующих дальнейшего исследования. К настоящему моменту достаточно хорошо исследованы модели и методы возможностной оптимизации с минисвя-занными нечеткими параметрами. Однако минисвязанность не является единственным способом агрегирования неопределенности. В настоящее время существует и активно развивается новое научное направление: ме-
тоды агрегирования информации — в значительной степени оно опирается на использование математического аппарата t-норм.
Цель данной диссертационной работы состоит в изучении вопросов, связанных с агрегированием нечеткой информации, неизбежно происходящим при любых операциях над нечеткими величинами и моделируемом при помощи аппарата треугольных норм, применительно к классу задач возможностной оптимизации.
В диссертационной работе показано, что минисвязанность это лишь одна из возможных реализаций t-нормы. В ней проводится сравнительное изучение других t-норм — в частности исследуется взаимозависимость параметров по другой экстремальной t-норме — слабой треугольной норме Тцг- При использовании различных t-норм можно добиться управления «нечеткостью» при решении задач оптимизации, что, в свою очередь, дает большую гибкость при принятии решений.
Однако разработка этого вопроса применительно к задачам возможностной оптимизации находится на начальном этапе развития. Этим определяется актуальность темы диссертации.
Обзор литературы
Основоположником теории нечетких множеств и связанной с ней теории возможностей является профессор Калифорнийского университета Беркли Лотфи Заде, который в своей знаменитой работе «Fuzzy Sets» [115] обобщил понятие характеристической функции множества /2, предположив, что она может принимать значения не только из множества {0,1}, но и из всего отрезка [0,1], характеризуя таким образом «степень принадлежности» элемента нечеткому множеству.
В 1978 году Стефан Намиас в своей работе «Fuzzy Variables» [97] предложил «аксиоматическую базу, являющуюся основой для построения строгой теории возможностей» («theoretical framework from which a rigorous theory may ultimately be constructed»). В этой статье было введено понятие нечеткой переменной, которое в дальнейшем трансформиро-
валось в такое важное понятие, как возможностная (нечеткая) величина. В этой основополагающей статье Намиас также ввел понятие несвязанности (unrelatedness) нечетких величин и аксиоматически определил бинарные операции над несвязанными нечеткими величинами, тем самым заложив теоретические основы современного исчисления возможностей. Позже в работе Рао и Рашеда [105] было замечено, что несвязанность, определенную Намиасом, было бы логичней называть минисвязанностыо (min-relatedness), так как получалось, в частности, что по Намиасу нечеткая величина А несвязанна сама с собой. Эти работы можно считать одними из основополагающих в теории возможностей.
В дальнейшем была установлена взаимосвязь (интерпретация) теории нечетких множеств и теории возможностей. Дальнейшие исследования показали, что различные модели неопределенности (теория вероятностей, теория возможностей) и другие так называемые нечеткие меры, могут быть построены на основе монотонных функций множества при наложении на них дополнительных требований.
Появление теории нечетких множеств и теории возможностей послужило началом новых научных направлений. Многие из этих направлений являют собой обобщение существующих классических теорий и формализмов и ориентированы на более сложные методы агрегирования информации. В частности, возможностное математическое программирование изучает оптимизационные модели, в которых вместо обычных четких параметров и отношений используются нечеткие величины.
Одной из первых работ в области возможностной оптимизации можно назвать работу Беллмана и Заде «Decision making in a fuzzy environment» [68]. Значительную роль в развитии данного научного направления также сыграли работы Циммермана [118], Луханджулы [89-91], Дюбуа и Прада [14], К.Негойце [33], Бакли [69,70], Орловского С.А. [26], Р.Фуллера [53], Рамика [104], А.В.Язенина [58-65,113] и М. Вагенкнех-та [114] и многие др.
К настоящему моменту хорошо изученными являются модели воз-
можностной (нечеткой) оптимизации в случае независимых (минисвязан-ных) нечетких параметров. Получены методы решения соответствующих задач как в классах параметризованных возможностных распределений, так и в общем случае — квазивогнутых полунепрерывных сверху распределений. Следует отметить, что взаимодействие нечетких параметров в них основано на использовании жесткой конъюнкции, принятой в нечеткой логике. Помимо разработки непрямых методов решения, проведены также исследования вопросов устойчивости данных задач [11,12,37-42], изучены модели возможностной оптимизации, в которых не только параметры, но и отношения, связывающие операнды моделей критерия и моделей ограничения, являются нечеткими [8-10,13]. Однако в том случае, когда параметры оптимизационных моделей являются взаимодействующими, исследования в этом научном направлении находятся на начальном этапе развития.
Стоит отметить, что учет зависимости нечетких параметров может быть осуществлен различными способами, а не только на основе і-норм.
В работе Танака и Ишибучи [108] зависимость параметров «отражается» через совместную функцию распределения нечетких параметров. В том случае, когда это распределение является эллипсоидальным, в [114] рассматривается одна из возможных постановок задачи идентификации функции распределения взвешенной суммы возможностных величин и предлагается метод ее решения, основанный на методе множителей Лагранжа. В работах Фуллера, Мажлендера и Карлссона [71,77,78] вводятся понятия вариации, ковариации и корреляции возможностных переменных и предлагаются методы их расчета в ряде случаев. Интерпретация данных характеристик тесно связана с теорией вероятностей. Как видно из работ авторов, возможностная ковариация между нечеткими числами А и В есть ни что иное, как взвешенное среднее вероятностных ковариации между случайными величинами, имеющими равномерное совместное распределение на уровневых множествах совместного
распределения возможностей А и В:
Covf{A,B)= [ со^(Х7,У7)/(7)й7, Jo
где Xj и Y7 — это случайные величины, имеющие равномерное совместное распределение вероятностей на С7 для всех 7 Є [0,1], С7 — 7-уровневое множество совместного распределения нечетких величин Л и Б, /(7) : [0,1] —> R — неотрицательная, монотонно возрастающая весовая функция, удовлетворяющая следующему условию нормировки:
/ fh)dy = 1. Jo
Использование весовой функции мотивировано, в частности, желанием дать меньшую степень важности нижним уровням нечетких множеств (именно поэтому / является монотонно возрастающей).
Точно так же возможностная вариация нечеткого числа есть взвешенное среднее вероятностных вариаций случайных величин, равномерно распределенных на его уровневых множествах:
Varf(A) = J
где Щ — это случайная величина, равномерно распределенная на А1 для всех 7 6 [0,1].
Как видно из формул, соответствующие понятия возможностной вариации и ковариации базируются на рандомизации. Эти результаты также могут быть положены в основу соответствующего исчисления, необходимого для построения методов решения задач возможностного программирования в случае зависимых нечетких параметров, чья зависимость моделируется таким образом.
В настоящей работе взаимодействие возможностных переменных моделируется, как нам представляется, более естественным образом — при помощи аппарата t-норм. Это есть более естественный механизм моделирования процесса агрегирования нечеткой информации, к тому же позволяющий контролировать рост нечеткости результатов, неизбежно возникающий при выполнении операций над нечеткими величинами. С этой
целью в работе используется понятие взаимной Т-связанности, которое было введено в работе Хонга «Parameter estimations of mutually T-related fuzzy variables» [79]. Такой способ моделирования взаимодействия (зависимости) параметров позволяет более гибко управлять нечеткостью при решении задач возможностной оптимизации и является в данный момент наиболее общим. В частности, операция конъюнкции (минимума) выступает одним из видов t-норм. Подробную информацию о ^-нормах можно найти, например, в [83-85]. Вопросам построения исчислений, основанных на различных ^-нормах, посвящены работы Месьяра [93-96], Дюбуа и Прада [72,74] и многих других.
Цель работы
Целью работы является разработка моделей и методов возможностной оптимизации в случае агрегирования неопределенности с использованием математического аппарата t-норм. Это предполагает разработку соответствующего исчисления возможностей, построение непрямых методов решения задач возможностной оптимизации в возможностно-необходимостном контексте, их реализацию на основе генетических алгоритмов и разработку программного комплекса поддержки соответствующих методов оптимизации.
Основные задачи
Для достижения поставленной цели в диссертации решены следующие задачи:
разработано исчисление возможностей для взаимно Т^-связанных нечетких величин, предполагающее решение задач идентификации функций распределения взвешенных Tw-сумм нечетких величин с одинаковыми и различными функциями представления формы;
получены формулы для вычисления границ а-уровневых множеств взвешенной Тил-суммы возможностных величин;
разработаны непрямые методы решения задач возможностной оптимизации при взаимно Тр^-связанных параметрах в возможностно-необходимостном контексте;
осуществлена спецификация генетических алгоритмов оптимизации, ориентированных на исследуемый класс задач;
проведено сравнительное изучение моделей и методов возможностной оптимизации при агрегировании нечеткой информации на основе Ту/- и Тм-норм;
реализован программный комплекс поддержки соответствующих методов возможностной оптимизации при моделировании взаимодействия нечетких параметров на основе t-норм.
Методика исследования
Для построения математических моделей возможностной оптимизации используется современная теория возможностей. Для построения эквивалентных детерминированных аналогов моделей возможностной оптимизации применяются методы математического программирования, для реализации эквивалентных детерминированных аналогов — методы эволюционного программирования. Программный комплекс реализован на языке программирования высокого уровня C++.
Практическая значимость работы
Модели и методы возможностной оптимизации, предложенные в работе, расширяют класс решаемых задач на случай, когда параметры задач оптимизации являются взаимосвязанными относительно слабой t-нормы Ту/- Эти результаты позволяют более гибко управлять нечеткостью при решении задач возможностной оптимизации. Полученные методы могут быть использованы для «интеллектуального» анализа и решения задач производственного, финансового и экономического планирования.
Внедрение результатов работы
Результаты диссертационной работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Тверского госуниверситета. Непрямые методы решения задач, полученные в диссертации, представлены в дисциплине «Теория неопределенностей», методы агрегирования возможностной информации — в программе курса «Современные проблемы прикладной математики и информатики». Соответствующее программное обеспечение, разработанное в диссертации, используется в качестве программной составляющей учебно-методического комплекса по дисциплинам «Теория неопределенностей» и «Нечеткое математическое программирование». Часть исследований, проводимых в работе, была поддержана грантом РФФИ, проект номер 08-01-08076.
Апробация
Основные результаты работы докладывались автором на IV Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2007 год), на 27-м ежегодном съезде Северо-Американского общества обработки нечеткой информации NAFIPS-2008 (Нью-Йорк, 2008 год), на семинарах в Тверском госуниверситете и ВЦ РАН.
Достоверность и обоснованность
Достоверность и обоснованность полученных в диссертационной работе результатов подтверждается строгостью проводимых математических обоснований при формулировании и доказательстве теорем, результатами численных расчетов, сравнительным анализом полученных в ходе модельных экспериментов результатов с известными.
Структура работы и ее содержание
Структурно диссертация состоит из введения, четырех глав основного содержания, заключения и библиографии.
Во введении обосновывается актуальность темы диссертации, ставятся цели исследования и формулируются задачи, решение которых необходимо для достижения целей исследования.
Первая глава состоит из шести разделов. В ней систематизируется необходимый аппарат теории возможностей. Кратко анализируются различные способы моделирования взаимодействия нечетких параметров и вводятся необходимые определения. В четвертом разделе первой главы автором получены собственные результаты, позволяющие идентифицировать функции распределения возможностей взвешенной TV-суммы нечетких величин и рассчитывать границы ее а-уровневых множеств, а в пятом разделе это все иллюстрируется на модельном примере. Полученные результаты используются при разработке методов решения задач возможностной оптимизации, описываемых во второй главе. В шестом разделе подводятся краткие итоги первой главы.
Во второй главе диссертации приводятся постановки задач линейного программирования в возможностно-необходимостном контексте.' Предлагаются методы решения сформулированных задач. Эти методы классифицируются как непрямые. Они основаны на построении эквивалентных детерминированных аналогов исходных задач. Ввиду того, что детерминированные эквиваленты являются невыпуклыми и негладкими моделями нелинейного программирования, для их численного решения привлекаются генетические алгоритмы. С этой целью осуществляется их необходимая спецификация к исследуемому классу задач.
В третьей главе проводится сравнительное изучение эквивалентных детерминированных аналогов. Доказываются теоремы, показывающие взаимосвязь различных способов агрегирования нечетких данных.
В четвертой главе диссертации представлен программный комплекс, реализующий систему поддержки принятия решений на основе разработанных методов и алгоритмов. Проводятся модельные расчеты с использованием разработанного программного комплекса.
В заключении обсуждаются полученные результаты.
Агрегирование нечеткой информации на основе t-норм
В диссертационной работе агрегирование нечеткой информации в исследуемом классе задач основано на треугольных нормах (t-нормах) [83-85], которые позволяют обобщить понятие минисвязанности (связанности), заложенное в бинарных операциях над нечеткими множествами и возможностными переменными [97,105].
Возможностные величины (L, і?)-типа, рассмотренные в предыдущем параграфе, удобны тем, что их распределения являются параметризованными и для исчислений, построенных на соответствующих -нормах (например, хорошо известной Тм(х,у) = тіп{ж,г/}), выполнение основных арифметических операций над возможностными величинами сводится к операциям над параметрами их распределений. Еще одно свойство, присущее ряду t-nopu и которым обладают параметризованные распределения возможностей, называется свойством сохранения формы [96]: если функции представления левых (правых) форм операндов совпадают, то и у результата будет точно такая же левая (правая) форма. Напомним вкратце основные определения и понятия из математического аппарата треугольных норм.
Определение 20. Отображение Т : [0,1] X [0,1] —» [0,1] называется треугольной нормой (или t-нормой), если для любого х Є [0,1] оно обладает следующими свойствами: 1) ограниченность: Т(1,х) = х, 2) симметричность: Т(х, у) =Т(у, х), 3) ассоциативность: T(x,T(y,z)) = T(T(x,y),z), 4) монотонность: T(w,y) T{x,z), если w ж, у z. Пример 2. Примерами некоторых хорошо известных t-норм являются (рис. 2 и 3): \ тт{х,у}, если тах{ж, у} = 1, 1) слабая t-норма 1\у{х,У)= \ [ 0, иначе, 2) t-норма Лукасевича TL(X, у) = тах{ж + у — 1, 0}, 3) алгебраическое произведение Тр(х, у) = ху, 4) операция взятия минимума Тм(х,у) = min.{x,y}. Следующее определение дает простой способ сравнения различных -норм. Очевидно, что не все -нормы можно сравнить таким образом. Более подробно вопросы порядка на множествах і-норм изучаются в [86,106]. Легко может быть доказана следующая теорема [83]. Теорема 1. Если Т есть t-норма, то \/х, у Є [0,1] Tw{xty) Т{х,у) Тм(х,у). Теорема 1 показывает, что треугольные нормы Tw и Тм являются экстремальными, при этом Тм называется сильной, а Тцг — слабой t-нормой. Иными словами, не существует t-нормы более слабой, чем Tw, и более сильной, чем Тм- В частности, все приведенные в примере 2 треугольные нормы связаны следующими неравенствами: Tw(x,y) TL(x,y) Тр{х,у) Тм{х,у). Определение 22. t-норма Т называется архимедовой, если Т является непрерывной и Т(х, х) х для любого х Є (0,1). Пример 3. Треугольные нормы Тр и Ті являются архимедовыми. Определение 23. t-норма Т называется строгой, если она строго возрастает по обоим аргументам. Нестрогая архимедова t-норма называется нулъпотентной. Пример 4. Треугольная норма Тр является строгой, a TL — нульпо-тентной. Любая архимедова -норма задается непрерывной убывающей функцией / : [0,1] - [0, оо] с /(1) - 0: T(x,y) = fW(f(x) + f(y)), где /f-1J — это псевдообратная для / функция, определяемая как: 0, у Є (/(0),оо). Функция f называется аддитивным генератором t-нормы Т. 1.3 Способы моделирования взаимодействия возможностных переменных Учет зависимости нечетких параметров задач возможностной оптимизации может осуществляться различными способами.
В работе Танака и Ишибучи [108] зависимость параметров «отражается» через совместную функцию распределения нечетких параметров. В том случае, когда это распределение является эллипсоидальным, в [114] рассматривается одна из возможных постановок задачи идентификации функции распределения взвешенной суммы возможностных величин и предлагается метод ее решения, основанный на методе множите-лей Лагранжа. В работах Фуллера, Мажлендера и Карлссона [71,77,78] вводятся понятия вариации, ковариации и корреляции возможностных переменных и предлагаются методы их расчета в ряде случаев. Интерпретация данных характеристик тесно связана с теорией вероятностей. Как видно из работ авторов, возможностная ковариация между нечеткими числами А и В есть ни что иное, как взвешенное среднее вероятностных ковариации между случайными величинами, имеющими равномерное совместное распределение на уровневых множествах совместного распределения возможностей А и В:
Взвешенная Tw-сумма нечетких величин
Под взвешенной Т-суммой нечетких величин понимается В03М0ЖН0СТ-ная функция следующего вида: /(Л, 7) = АіАі(7) Фг А2Л2(7) г ... Фг КАпЬ), (1.5) где Л = (Лі,...,Лп) Є Е", Aj(fy) — нечеткие (возможиостыые) величины, Фг — операция суммирования по соответствующей -норме Т, выполняемая по формуле (1.4).
Взвешенные Т-суммы такого вида используются в задачах возмож-ностной оптимизации при построении моделей критериев и ограничений. К настоящему моменту хорошо изученным является случай, когда в качестве tf-нормы выступает Тм(х,у), которая моделирует условие невзаимодействия (минисвязанности, взаимной Т -связанности) возможност-ных величин. Для этой i-нормы хорошо развито исчисление нечетких величин, широко используемое в возможностной оптимизации.
В диссертации исследуется случай, когда в качестве t-нормы выступает слабая і-норма Ти/. Выбор в пользу этой i-нормы был сделан по той причине, что она является, как следует из теоремы 1, экстремальной, также как и і-норма минимума — поэтому представляется интересным изучить вопрос поведения задач возможностной оптимизации в условиях взаимодействия, задаваемого данной і-нормой. Во-вторых, для слабой -нормы в ходе диссертационной работы удалось получить соответствующее ей исчисление возможностей.
В настоящее время ведутся активные исследования вопросов идентификации суммы нечетких величин для других -норм. На сегодняшний день получены результаты, позволяющие в ряде частных случаев t-норм дать оценку функции распределения суммы или получить ее аналитическое представление. Однако в общем случае для любой произвольной t-нормы Т решение вопроса идентификации распределения Т-суммы двух возможностных величин остается открытым.
В этом параграфе для слабой треугольной нормы получены элементы исчисления возможностей, которые во второй части диссертационной работы используются для построения непрямых методов решения задач возможностной оптимизации.
Для разработки непрямых методов решения задач возможностной оптимизации важным условием является умение аналитически выражать функции распределения возможностей взвешенных сумм вида (1.5), а также находить границы их а-уровневых множеств, необходимые при построении их детерминированных эквивалентных аналогов.
Идентификация функции распределения возможностей взвешенной суммы нечетких величин основывается на исчислении возможностей — правилах выполнения операций над нечеткими величинами.
Хорошо известен результат сложения п нечетких величин с одинаковыми формами относительно слабой -нормы Ти/ [93,95].
Теорема 2. Пусть ЛІ = (ai,bi,ai,Pi)LR, і = l,n есть взаимно Т\у-связанные нечеткие величины (L,R)-muna. Тогда их Тцг-сумма фу АІ определяется на уровне параметров распределений следую щей формулой [67, 72, 74, Ц, 95]: п / п п фЛ = У2аі:У Ьі, max ai} max / rJr \ — — г=1,...,п г=1,...,тг 2Vt=i \г=1 г=1 / Я Доказательство теоремы 2 непосредственно следует из определения слабой -нормы Т\у и формулы (1.4).
Таким образом, коэффициенты нечеткости TV-суммы возможност-ных величин вычисляются как максимум из соответствующих коэффициентов нечеткости операндов. При этом еще раз подчеркнем, что в рассматриваемом случае функции представления формы L и R операндов являются одинаковыми.
Легко доказывается следующая теорема о взвешенной TV-сумме.
Теорема 3. Пусть имеется п взаимно Tw-связанных нечетких величин (L,R)-muna А{ = (а Ъ оц,PIJLR, г = 1,П. Тогда их Тцг-сумма фу ._ ХІАІ, где Aj 0, определяется следующей формулой: п / п п ф ХІАІ = ]Г}А,-а , Аг-& , max А а,-, max АгД TVv,=i \г=1 г=1 / LR Доказательство теоремы 3 является следствием теоремы 2 и результатов, позволяющих вычислять умножение нечетких величин (L, Л)-типа на скаляр [114]. Обобщим теорему 3 на случай взвешенной суммы нечетких величин, в которой операнды имеют различные функции представления формы hi, Hi) 1 — 1, 7Z. В работе [95] показано, что сложение п нечетких величин (L, Д)-типа по любой і-норме Т может быть выполнено следующим образом: п / п п п п \ Гг=1 \г=1 г=1 Тг=1 Тг=1 / где ФГІ=І $і — функционал, определяющий по функциям представления формы операндов (Si, г = 1,п) функцию представления формы результата. Таким образом, можно отдельно рассчитать интервал толерантности результата как сумму интервалов толерантности операндов, а затем независимо друг от друга получить Т-сумму левых форм операндов, а значит и левую форму результата, и Т-сумму правых форм операндов, получив правую форму результата. Иными словами, в формировании функции представления левой (правой) формы результата участвуют только функции представления левых (правых) форм операндов.
Непрямые методы решения в случае меры возможности
Рассмотрим задачу (2.1)-(2.3) в случае меры возможности: к — max, (2.6) T{/o(s,7) = fc} ao, (2.7) я"Шя,7) = } і г = 1,т, хЄЕ». (2.8) Исследуем сначала систему (2.8). Построим для нее эквивалентную детерминированную систему. Имеет место следующая теорема.
Теорема 6. Пусть в модели ограничений (2.8) параметры dij{y) и &г(т) есть взаимно Тцг-связанные нечеткие величины (L,R)-muna: aij(l) = {dip afjj, Vij,Pij)LR, J = 1, n, і = 1, га, bi{l) = % 6", a,-, fa)LR, і = X, с идентичными функциями представления формы L и R. Если L и R имеют обратные функции, то эквивалентный детерминированный аналог модели (2.8) имеет вид: п Y a ijxi - .max { %-}-1(a0 b + piR 1(ai), і = l,m, n У]аіі + max {.,/% jiT1 ) 6- - гцЬ 1(аі), і = 1,га, Г т j=l,...,n (2.9) Доказательство. Функция fi(x,y) описывается выражением: п /»(ж»т) = 2aijh)xj - 6» (7). Перенесем свободный член 6j(7) в правую часть уравнения и получим следующую форму ограничения: ЧЛО Т) = k(y)} оц, і = l,m, хЄЕ .
Функция f- (х, 7) является взвешенной Ти/-суммой нечетких величин (L, і?)-типа с идентичными функциями представления формы. Согласно теореме 3 о взвешенной Ти/-сумме нечетких величин (L, і?)-типа, распределение возможностей Д(ху 7) будет иметь вид: где: n n 3=1 3=1 77 = maxlxiTjn,..., Здт} = max {z/%}, 3=1,...,n $ - max{xi/3iu ..., xnpin} = max { /}. .7=1,...,n Таким образом для //(ж, 7) функции представления левой и правой формы L {x) и R {x), соответственно, будут выражаться соотношениями: } Для свободного члена функция распределения возможностей будет иметь вид, заданный в условии теоремы: &г(т) = (Ц, 77г А)иг, а функции представления левой и правой формы, соответственно: х - Ъ Г Lbi(x) = L ( - ) , Rbi(x) = R Pi ) Возможностное неравенство тт{/г-(ж, 7) = Мт)} эквивалентно следующей системе детерминированных неравенств: \/[ rbi f jb (2-10) где Vі и г — это такие значения аргумента функций L и Я , соответственно, при которых эти функции принимают значения, равные af L ) =-R V ) = а /Ьі и rbi — значения аргумента функций Lbi и Я&і, при которых они принимают значение оц\ Lbi(lbi) = Л6і( Ьі) = «і-Найдем ih и r : L ( )= ai Г = i_1(ai) " = vIL 1{ai) R i jA) = = !: pi = -R V ) = г" = г + ftR- ). Найдем теперь lbi и rbi: ( У — lbi\ У — 1ЬІ m J m RI -j ) = a = —j = R \ ) = ri =b" + PiR-4 i) Тогда система (2.10) может быть записана в виде: - " («О бГ + А-л- ), rJ + iZT J - L-1 ). Представив 1 ,г ,г] и /? в явной форме, получаем утверждение тео ремы. Что и требовалось доказать. Теперь построим эквивалентный детерминированный аналог для модели критерия (2.6)-(2.7). Имеет место следующая теорема.
Теорема 7. Пусть дана модель критерия задачи воз можно стной оптимизации вида (2.6)-(2.7), где аоі(т) есть взаимно Тцг-связанные нечеткие величины (L, R)-muna: с идентичными функциями представления формы L и R. Если L и R имеют обратные функции, то эквивалентный детерминированный аналог модели критерия (2.6)-(2.7) имеет вид: к -» max, (2-11) f п abjx3 .max (%} 1(ао) ) (2.12) 3=1 п 2_2aojxj + max {xj/3oj}R 1(ao) к. 3=1 Доказательство. Функция /о(ж, 7) = ТУі=і a0j(l)xj является взвешенной TV-суммой нечетких величин (L, Д)-типа с идентичными функциями представления формы. Аналогично как и при доказательстве теоремы б, находим распределение возможностей функции fo(x, 7)1 а, затем левую и правую границы его ао-уровневого множества: /Л = /0 - TtfZTW гЛ - г0 + /% Д_1Ы, где: п гг /0 — / aojxjj го — 2- i а х 3=1 3=1 rj 0 = max {ajj-r/oj}, / = .max -OjAy} j=l,...,n J=l,-,n Возможностное неравенство 7г{/о( т) = &} «о эквивалентно следующей системе детерминированных неравенств:
Теорема вложенности множеств допустимых решений
Программный комплекс поддержки принятия решений для построения детерминированных аналогов задач возможностнои оптимизации с взаимодействующими параметрами и численного их решения реализован в виде модуля для программной системы FIESTA.
Система FIESTA (сокр. от англ. Fuzzy Intelligent System) разработана СВ. Сорокиным [50] и является интерактивной системой для построения различных моделей задач возможностнои оптимизации, их анализа и численного решения. Система FIESTA содержит в себе функциональность, реализующую все основные результаты Язенина А.В. и Вагенкнех-та М. по построению детерминированных эквивалентных аналогов задач возможностнои оптимизации с минисвязанными параметрами, результаты Сорокина СВ., полученные в его диссертационной работе, позволяющие анализировать совместность систем ограничений и находить недоминируемые векторы уровней совместности, а также результаты работ Гордеева Р.Н., благодаря которым появилась возможность расширить класс решаемых задач на случай нечетких бинарных отношений.
В результате работы над данной диссертацией система FIESTA была дополнена методами построения эквивалентных детерминированных аналогов для случая Ти/-связанных параметров.
Система FIESTA реализована на основе библиотеки MFC в виде объектно-ориентированного приложения, в результате чего есть возможность для расширения функциональности системы. Система может быть применена как для практического решения задач финансового, экономического, производственного планирования, так и для проведения лабора торных работ по исследованию непрямых методов решения оптимизационных задач и поведения задач при использовании различных агрегирующих t-норм на занятиях по дисциплинам «Теория неопределенностей» и «Современные проблемы прикладной математики и информатики», читаемым на факультете прикладной математики и кибернетики ТвГУ в рамках направления подготовки «Информационные технологии», «Прикладная информатика» и специальности «Математические методы в экономике».
Архитектура системы поддержки принятия решений FIESTA определяется следующими компонентами: блок генерации, обработки и сохранения моделей задач возможноет ной оптимизации; блок непрямых методов решения задач возможностной оптимизации; блок анализа несовместных ограничений; решатель; интерфейс взаимодействия с пользователем; блок визуализации.
Первый блок из перечисленных выше позволяет создавать различные модели задач возможностной оптимизации. На настоящий момент в системе реализованы следующие модели критериев:
Второй блок системы содержит в себе комплекс алгоритмов, реализующих непрямые методы решения задач возможностной оптимизации. В настоящее время система поддерживает непрямые методы решения задач, построенных по моделям, перечисленным в предыдущем параграфе, в двух случаях: когда параметры задач являются минисвязанными — данные методы взяты из работ Язенина А.В., Вагенкнехта М., и взаимно TV-связанными — непрямые методы являются результатами исследований данной диссертационной работы.
Данный блок позволяет проводить анализ систем ограничений на совместность и избыточность. Эти результаты были получены Сорокиным СВ. в его диссертационной работе. Напомним, что строка-ограничение задачи линейного программирования называется избыточной, если это ограничение выполняется для всех х, удовлетворяющих остальным ограничениям задачи. Ограничение, которое не выполняется ни для одного значения х, удовлетворяющего остальным ограничениям, называется несовместным.
Блок решателя реализует численные методы для решения эквивалентных детерминированных аналогов, получаемых в результате применения соответствующих непрямых методов решения задач возможностной оптимизации. В текущей версии системы данный блок состоит из трех компонент. Модуль решения задач линейного программирования, основанный на симплекс-методе. Данный модуль позволяет решать обычные задачи линейного программирования, к которым сводятся некоторые задачи линейного возможностного программирования при минисвя-занных параметрах. Модуль генетического алгоритма оптимизации, позволяющий решать задачи нелинейного и невыпуклого программирования, получаемые при применении непрямых методов решения к задачам с Ти/-связанными параметрами, а также используемый для анализа систем ограничений задачи. Модуль подключения внешнего решателя. Данный модуль был разработан и внедрен в систему FIESTA Гордеевым Р.Н. Модуль позволяет подключать внешние решатели к системе и таким образом расширять класс решаемых задач оптимизации.
