Разработка алгоритмов и программного комплекса многокритериальной оптимизации при разнотипных экспериментальных данных

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Академия наук Республики Узбекистан

Научно-технический центр

«Современные информационные технологии»

Автореферат

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

Разработка алгоритмов и программного комплекса многокритериальной оптимизации при разнотипных экспериментальных данных

05.13.18 - Теоретические основы математического моделирования,

численные методы и комплексы программ

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

Тавбоев Сирожиддин Ахбутаевич

Ташкент, 2007

Работа выполнена в Институте информатики Научно - технического центра «Современные информационные технологии» Академии наук Республики Узбекистан.

Научный руководитель: доктор технических наук, профессор Фазылов Шавкат Хайруллаевич

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

доктор технических наук, профессор Эшматов Хасан

кандидат технических наук Бобомуродов Озод Жураевич

Ведущая организация: Ташкентский Государственный Авиационный институт

Защита диссертации состоится «___» __________ 2007 г. в ___ часов на заседании разового специализированного совета при Научно-техническом центре «Современные информационные технологии» Академии наук Республики Узбекистан по адресу: 700125, Ташкент, ул. Ф.Ходжаева, 25.

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

Автореферат разослан «___» _________ 2007 г.

Ученый секретарь специализированного совета Исмаилов М.А.

Резюмеси

Таянч сўзлар: Кўп мезонли оптималлаш, альтернативлар, тегишлилик функцияси, ноани? тўпламлар назарияси, устунлик векторлари, фойдалилик функцияси, таба?алаштириш.

Тад?и?от объектлари: Турли хил маълумотларни ?айта ишлашга асосланган оптималлаштириш ва ?арор ?абул ?илиш тизимлари.

Ишнинг ма?сади: Турли хил экспериментал маълумотларни эътиборга олган ?олда мураккаб тизимларни бош?аришга мос математик моделлар доирасида кўп мезонли ечимларни ?абул ?илишга кўмаклашувчи алгоритмлар ва дастурий воситаларни ишлаб чи?иш

Тад?и?от усули: Математик статистика усуллари, операцияларни текшириш, оптималлаш назарияси, функционал анализ усуллари, алгебра, ноани? тўпламлар назарияси, объектга-мўлжалланган дастурлаш тамойиллари

Олинган натижалар ва уларнинг янгилиги:

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

-ани?мас шароитда ноани? тўпламларнинг тегишлилик функцияси ёрдамида локал мезонларни формаллаштириш методикаси таклиф этилган;

-?ўйилиши ноани? бўлган кўп мезонли оптималлаш масалаларини ?ал этиш учун ?урилган тегишлилик функциясини фойдалилик функцияси деб ?исоблаш мумкинлиги исботланган;

-ма?сад функциялари тартиб ёки балли шкалада ўлчанганлигини эътиборга олган ?олда кўп мезонли оптималлаш масалаларини ?ал этиш алгоритми ишлаб чи?илган;

-эквивалент маълумотлар мавжуд бўлганда кўп мезонли оптималлаш масалаларини ?ал этиш алгоритми ишлаб чи?илган;

-ишлаб чи?илган усул ва алгоритмни амалиётга жорий этишни таъминловчи дастурлар комплекси яратилган.

Амалий а?амияти: Яратилган алгоритмлар ва дастурий ма?сулотдан лойи?аланадиган ва бош?ариладиган объектларни характерловчи параметрларни оптималлаш учун ?ўлланиладиган АБС ва АЛС элементлари сифатида фойдаланиш мумкин.

Тадби? этиш даражаси ва и?тисодий самарадорлиги: Диссертация ишининг натижалари олий ў?ув юртларида ва табиатни му?офаза ?илиш ?ўмитасида амалиётга жорий этилди. АС «МАВ» дастурлар мажмуи олий ў?ув юртлари социал-маиший сфераси фаолияти самарадорлигини ани?лаш ва мониторингини олиб боришда ?ўлланилган. KP «IPOTMK» дастурлар мажмуи эса эрозияга ?арши кураш тадбирларини ишлаб чи?ишда ?ўлланилди.

?ўлланилиш со?аси: бош?арув ва лойи?а ишларида турли хил шкалаларда ўлчанган экспериментал маълумотларни ?айта ишлашга асосланган оптималлаштириш ва ?арорлар ?абул ?илиш тизими.

Резюме

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

Объекты исследования: системы оптимизации и принятия решений на основе обработки разнотипных экспериментальных данных.

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

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

Полученные результаты и их новизна:

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

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

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

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

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

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

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

Степень внедрения и экономическая эффективность: Результаты диссертационной работы применялись на практика в вузах и в Комитете охраны природы. АС «МАВ» использовано в социально-бытовой сфере вузов и позволило изучить факторы, определяющие уровень социально-экономической и профессиональной адаптации студентов вузов, и провести социологический мониторинг их эффективного функционирования. КП «IPOTMK» использовано при выборе комплекса противоэрозионных мероприятий.

Область применения: системы оптимизации и принятия решения, основанные на обработке разнотипных экспериментальных данных в управлении и проектировании.

Resume

Key words: multicriterial optimization, alternatives, accessories functions, theories of the fuzzy sets, fuzzy mathematics, priorities' vectors, matrix of the knowledge, functions of usefulness.

Subjects of the inquiry: systems of optimization on the base of the multitype experimental data processing.

Aim of the inquiry: development of algorithms and software for choosing real optimal decision within the framework of corresponding mathematical model of the problems of multicriterial optimization with multitype experimental data.

Methods of inquiry: methods of the mathematical statistics, algebra, theories of the functional analysis, optimization, theory of the fuzzy sets, the operation researches and object-oriented programming,

The results achieved and their novelty:

-the way for correction of the expert estimations, which allows to expand the scope of the hierarchies analysis methods in conditions of uncertainty by decision of multicriterial optimization problems is offered;

-methods for formalization of private criteria by means of functions by accessory to indistinct sets, in conditions of uncertainty - are offered;

-the statement according to which global vector of alternatives priorities is considered as function by accessory to the global purpose of the decision of the multicriterial optimization problem in indistinct statement -is proved;

-the algorithm of the decision multicriterial problems of optimization in view of which private criteria are measured on a serial or mark scale-is developed;

-algorithms for the decision of problems of multicriterial optimization in view of equivalence of experimental data are developed;

-software for applying obtained methods and algorithms into practice is created.

Practical value: Designed algorithms and software can be used as element of the existing systems CAD and AMS for optimizing of parameters of designed systems and managerial system.

Degree of embed and economical effectivity: using of AS «MAV» in social sphere of high schools has allowed to study the factors defining level of social-economic and professional adaptation of high school students and to conduct sociological monitoring of their efficient operation. Using of KP «IPOTMK» in scholastic process has allowed to evaluate the progress of trainees by using of pedagogical software programs.

Sphere of usage: systems of optimization on the base of multitype experimental data processing in management and designing.

Общая характеристика диссертации

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

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

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

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

Степень изученности проблемы: Впервые проблема многокритериальной оптимизации была сформулирована экономистом Парето в 1896 г. Аппарат многокритериальной оптимизации в настоящее время далек от своего завершения и продолжает интенсивно разрабатываться в нашей стране и за рубежом. Однако уже на современном уровне некоторые теоретические результаты могут быть использованы в качестве инструмента в научной аргументации принимаемых решений. В частности, вопросы свойств и структуры теоретические исследования рассмотрены в научных трудах таких зарубежных учеными, как Дж.Джоффрион, Дж.Дайер, Дж.Фон Нейман, Д.И.Батищев, Р.Л.Кини, Х.Райфа, Р.Штойер, В.И.Жуковский, О.И.Ларичев, В.В.Подиновский, С.В.Емельянов, С.А.Орловский.

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

Связь диссертационной работы с тематическими планами НИР: Диссертационная работа выполнена в соответствии с планами НИР Института информатики АН РУз, связанными с реализацией Государственной научно-технической программы 4.2 (ГНТП-4.2): «Разработка программных средств и методов информатизации, систем автоматизации управления и регулирования технологических процессов» (2000-2002 гг.) и ГНТП-20: «Разработка современных информационных систем, средств управления, баз данных и программных продуктов, обеспечивающих широкое развитие информационных и телекоммуникационных технологий» (2003-2005 гг.).

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

Задачи исследования:

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

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

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

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

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

-разработать программный комплекс, реализующий предложенные алгоритмы, и исследовать его работоспособность и эффективность;

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

Объект и предмет исследования: Системы оптимизации и принятия решений на основе обработки разнотипных экспериментальных данных.

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

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

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

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

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

Научная новизна результатов диссертации заключается в следующем:

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

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

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

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

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

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

Научная и практическая значимость результатов исследования:

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

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

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

Реализация результатов: Программный комплекс решения задач многокритериальной оптимизации при наличии разнотипных экспериментальных данных прошел экспертизу и получено 2 авторских свидетельства на программное обеспечение (КП «IPOTMK» № DGU 00608 от 29.01.2003, АС «МАВ» № DGU 01009 от 07.11.2005), зарегистрированных в Государственном патентном ведомстве РУз. Использование АС «МАВ» в социально-бытовой сфере вузов позволило изучить факторы, определяющие уровень социально-экономической и профессиональной адаптации студентов вузов, и провести социологический мониторинг для оптимального управления социально-бытовой сферой вузов. Использование КП «IPOTMK» позволило оптимизировать проектирование мелиоративных систем. Разработанные алгоритмы и программный комплекс используются в учебном процессе вуза при проведении занятий по специальным курсам «Математическое программирование» и «Исследование операций».

Апробация работы: Основные результаты диссертационной работы докладывались и обсуждались на: Республиканской научной конференции «Современные проблемы алгоритмизации и программирования» (Ташкент, 2001); Республиканской научной конференции «Математическое моделирование и вычислительный эксперимент» (Ташкент, 2002); Республиканской научно-практической конференции «Современные проблемы техники и технологии» (Фергана, 2002); Республиканской научно-практической конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Ташкент, 2003); Республиканской научно-практической конференции «Актуальные проблемы современных технологий и науки» (Джизак, 2004); Республиканской научно-практической конференции «Роль научно-технического прогресса в развитии народного хозяйства» (Джизак, 2005); Республиканской научно-практической конференции «Наука, образование и производство и их интеграции в области информационно-коммуникационных технологий» (Ташкент, 2005); научных семинарах Института информатики АН РУз (Ташкент, 2003 - 2006 гг.).

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

Структура и объем диссертации. Диссертационная работа, состоящая из введения, трех глав с выводами, заключения, списка использованной литературы и приложения, изложена на 134 страницах машинописного текста, список литературы включает 131 наименований, 11 рисунков и 30 таблиц.

Основное содержание диссертации

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

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

Традиционные методы многокритериальной оптимизации условно разделены на четыре ключевых подхода. Первый подход связан с идеей ранжирования критериев по важности и дальнейшей последовательной оптимизации каждого критерия по отдельности с назначением допустимой величины изменения значения критерия, полученного на предыдущих шагах. Суть второго подхода состоит в выделении из всех критериев главного, а затем оптимизации их и переводе остальных с ограничения. Наиболее часто используемым на практике является третий подход - скаляризация векторного критерия в один обобщенный критерий. Основной проблемой, касающейся большинства традиционных методов, является необходимость использования алгоритмов несколько раз для получения репрезентативной аппроксимации множества эффективных точек, что само по себе неудобно при решении практических задач, однако имеется и более существенный недостаток - получаемая аппроксимация множеств. Нерепрезентативно, так как генерируемые эффективные точки будут неравномерно распределены как в пространстве альтернатив, так и в пространстве критериев. Зачастую можно получить набор очень близких друг к другу решений при потенциальном бесконечном множестве Парето. Основной причиной такой ситуации является то, что в каждом из них задача многокритериальной оптимизации сводится к одной или нескольким задачам однокритериальной оптимизации. При таком подходе теряется суть реальной задачи одновременного учета многих критериев. Четвертый подход к решению многокритериальной задачи оптимизации связан с использованием генетических алгоритмов, которые можно применить к Парето - оптимальным множествам за один прогон. Эта область перспективна, так как при построении эволюционных методов решения нет четких предписаний, а используются лишь эволюционные принципы построения генетических алгоритмов. Однако для обеспечения более репрезентативной аппроксимации необходимо принимать специальные меры.

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

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

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

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

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

Лингвистическая шкала оценок относительной важности

№	Оценка
	Качественная	Количественная
1	Строго эквивалентно	1
2	Слабо предпочтительно	3
3	Несколько предпочтительно	5
4	Значительно предпочтительно	7
5	Строго предпочтительно	9
6	Промежуточные значения важности	2, 4, 6, 8

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

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

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

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

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

обоснованность многокритериальный иерархический неопределенность

где , -четкие интервалы соответствующие - уровням.

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

(1)

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

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

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

Отношения несогласованности определяются с помощью выражения

(2)

где SS-случайная согласованность экспертных оценок матрицы размерности n:

(3)

здесь W_ij-элементы матрица экспертной оценки W.

Алгоритм согласования оценок состоит из следующих этапов:

1. Определение отношения несогласованности () экспертных данных по каждому из свойств объекта.

2. Ранжирование свойств по показателю и определение свойств с максимальным и минимальным численными значениями (определение строк матрицы (W)).

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

4. Запись полученных новых оценок в матрицу W.

5. Расчет показателя «отношения согласованности».

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

7. Повторный расчет новых оценок при невыполнении условия допустимости с повторением пп. 3-6.

8. Расчет коэффициентов важности показателей свойств объектов при выполнении условия допустимости.

9. Определение наиболее предпочтительного объекта.

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

Особенностью данного метода является то, что он расширяет объект применения метода анализа иерархий, позволяя решать задачи принятия решений при уровне несогласованности исходной информации от 2 до 40%.

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

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

(4)

где Z_i=f_i (xS), - составляющие вектора критериев, S - множество допустимых решений.

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

Многокритериальная задача оптимизации представлена в виде иерархической декомпозиции с использованием теоремы Т.Л.Саати.

Теорема. Пусть Н - полная иерархия с элементом В на верхнем 0-м уровне и h уровнями. Пусть B_n - матрица приоритетов n-го уровня, n=1,...,h. Если W'-вектор приоритетов р-го уровня относительно некоторого элемента z на (p-1)- м уровне, то вектор приоритетов W - q - го уровня (p<q) относительно z определяется как

W=B_q*B_q-1, ... , B_q+1* W' (5)

т.е. вектор приоритетов самого нижнего уровня относительно элемента В определяется следующим выражением:

W=B_h* B_h-1*, ... ,*B₂*W' (6)

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

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

.(7)

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

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

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

1.

2.

3. тогда и только тогда, когда

4. Если ­й и ­й частные критерии равноценны, то .

5. - монотонная, неубывающая по некоторому аргументу функция, кроме того, возрастание ограничивается условием

.

6. для любого х тогда и тогда, когда .

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

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

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

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

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

f (Х') = f [Ф(Х)] (8)

Изложен метод нахождения решения уравнения (8) в случае, когда

Ф(X) = А Х + С (9)

где , т.е. в случае уравнения вида

f (Х') = f [АХ+С] (10)

Зависимости от собственных значений матрицы A и от вектора C, т.е. корни характеристического уравнения, следующие:

А - = 0 (11)

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

1) все _i, вещественны;

2) среди _i, имеются комплексные;

3) среди _i, имеются кратные;

4) среди _i, имеются равные нулю.

Например, для случая, когда среди _i, (i=1, n) имеются кратные, получены следующие инвариантные функции:

,

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

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

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

Программный комплекс выключает в себя следующие блоки:

1. Создание базы данных.

2. Создание базы знаний.

3. Выбор операций.

4. Организация запроса и запись результатов.

5. Поддержка экспертного отбора.

6. Обработка экспериментальных данных.

7. Отображение.

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

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

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

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

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

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

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

Приведены некоторые апробированные иерархии, имеющие непосредственное отношение к обсуждаемой проблеме.

На рисунке представлена иерархическая модель «Эффективность социально-бытовой сферы вуза», предназначенная для оценки эффективности ее функционирования.



Апробация данной иерархии позволила расставить приоритеты элементов второго уровня следующим образом: питание - 0,302, база отдыха - 0,301, медицина и спорт - 0,150, культура - 0,039. Интегрально (по всем подотраслям с учетом их значимости) распределение приоритетов элементов третьего уровня выглядит так: на первом месте - материальные факторы развития вуза с весом 0,410, на втором - факторы управления - 0,345 и на третьем - потребности (вес - 0,256).

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

Список опубликованных работ

1. Туракулов Х.А., Тавбоев С.А. Структурно-символьное описание процедур анализа экспериментальной информации. // Современные проблемы алгоритмизации и программирование. Тез. докл. респ. науч. конф. 5-7 сентября 2001. - Ташкент, 2001. -С. 413-414.

2. Тавбоев С.А., Юсупов Р.М. Интеграл кўрсаткичларни ?уриш учун функционал тенгламалардан фойдаланиш. // Узбекский журнал «Проблемы информатики и энергетики». - Ташкент, 2002. № 3. -С. 75-79.

3. Тавбоев С.А. Об одном способе приведения нелинейных функциональных зависимостей в линейный вид. // «Научно-технический журнал» ФерПИ. - Фергана, 2002. № 3. -С. 6-8.

4. Туракулов Х.А., Юсупов Р.М., Тавбоев С.А. Об одном способе решения многокритериальных задач оптимизации. // «Научно-технический журнал» ФерПИ. - Фергана, 2002. № 3. -С.12-14.

5. Тавбоев С.А. Кўп мезонли оптималлаш масаласида чизи?ли моделлардан фойдаланишнинг баъзи бир етарли шартлари. // Узбекский жур-нал «Проблемы информатики и энергетики». - Ташкент, 2002. № 4. -С.43-45.

6. Туракулов Х.А., Юсупов Р.М., Тавбоев С.А. Об одном методе оценки интегрального показателя. // Вопросы кибернетики. -Ташкент, 2002. -Вып.163. -С. 95-98.

7. Тавбоев С.А. Об одном методе решения линейных функциональных уравнений с помощью инвариантных функций. // Вопросы кибернетики. -Ташкент, 2002. -Вып.164. -С. 128-131.

8. Тавбоев С.А., Юсупов Р.М. Функциональная структура программно-математического обеспечения системы принятия решений с оценкой последствий. // Вопросы кибернетики. - Ташкент, 2003. -Вып.166. - С.116-120.

9. Тавбоев С.А., Юсупов Р.М., Хамдамов Ш. Структура программного комплекса для построения и оценки интегрального показателя при наличии многих критериев. // Алгоритмы. - Ташкент, 2003. -Вып.90. -С. 93-97.

10. Тавбоев С.А., Юсупов Р.М., Мингбоев У.Х. Олий таълим муассасаси социал-ижтимоий сфераси фаолиятини ба?олашнинг шажаравий модели. // Ахборот ва ишлаб чи?ариш технологияларининг ил?ор усулларини тад?и?оти ва технологияси. Респ. илмий-техник конф. материаллари. 23-24 май 2003. Фар?она, 2003. - 416-418 б.

11. Юсупов Р.М., Тавбоев С.А. О методе решения задач много-критериального выбора в условиях неопределенности. // Узбекский журнал «Проблемы информатики и энергетики». - Ташкент, 2003. № 3. - С.46-49.

12. Тавбоев С.А., Юсупов Р.М. Кўп мезонлар мавжуд бўлганда интеграл кўрсаткичларни ?уриш ва ба?олаш учун дастурлар мажмуаси (KP «IPOTMK»). // Государственное Патентное Ведомство РУз. Свидетельство об официальной регистрации программы для ЭВМ № DGU 00608, 29.01.2003 г. - Ташкент, 2003.

13. Тавбоев С.А. ?арор ?абул ?илиш масалаларини ?ал этишга кўмаклашувчи компьютерли тизим дастурли-методик таъминоти лойи?аси технологияси. // Актуальные проблемы современных технологий и науки: Тез. докл. научно-практич. конф. 18-19 май 2004. - Джизак, 2004. -С. 243-245.

14. Фозилов Ш.Х., Тавбоев С.А. Ма?сад функциялар тартиб шкаласида ўлчанганда интеграл кўрсаткичларни ?уриш методи ва алгоритми. //Узбекский журнал «Проблемы информатики и энергетики». - Ташкент, 2005. № 4-5. -С.1-7.

15. Тавбоев С.А., Ниязов А. Кўп мезонли оптималлаш масаласини ?ал этишнинг «инсон-компьютер» муло?отига асосланган усули. // Роль научно-технического прогресса в развитии народного хозяйства: Тез. докл. научно-практич. конф. 23-24 мая 2005. - Джизак, 2005. -С.78-80.

16. Тавбоев С.А. Субъектив кўринишда берилган маълумотларни тасвирлаш ва мувофи?лигини ани?лашнинг бир усули ?а?ида. // Наука, образование и производство и их интеграции в области информационно-коммуникационных технологий: Матер. научно-технич. конф. 31 мая-1 июня 2005. - Ташкент, 2005. - С.282-285.

17. Тавбоев С.А., Юсупов Р.М. Кўп мезонли альтернативларни танлаш учун автоматлаштирилган тизим (АС «МАВ»). // Государственное Патентное Ведомство РУз. Свидетельство об официальной регистрации программы для ЭВМ № DGU 01009, 07.11.2005 г. - Ташкент, 2005.

Размещено на Allbest.ru

...