Разработка методов анализа многокритериальных задач с использованием информации о важности критериев тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Нелюбин Андрей Павлович

• Нелюбин Андрей Павлович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Нелюбин Андрей Павлович

Введение

Глава 1. Сведения из теории важности критериев, развитию методов которой посвящена диссертационная работа

1.1. Математическая модель и основные понятия теории важности критериев

1.2. Решающие правила сравнения альтернатив по предпочтительности

1.3. Постановка задач исследований

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

2.1. Решающее правило в случае порядковой шкалы критериев

2.2. Решающее правило в случае шкалы первой порядковой метрики

2.3. Построение объясняющих цепочек векторных оценок альтернатив

2.4. Алгоритм построения объясняющих цепочек в случае порядковой шкалы критериев

2.5. Алгоритм построения объясняющих цепочек в случае шкалы первой порядковой метрики

Выводы к главе

Глава 3. Аналитические решающие правила, использующие упорядочение критериев по важности

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

3.2. Решающие правила в случае шкалы первой порядковой метрики

3.3. Взаимосвязь качественной и количественной важности критериев

Выводы к главе

Глава 4. Решающие правила при интервальной информации о важности критериев и шкале критериев

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

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

4.3. Решающее правило при интервальной информации о важности критериев со шкалой ограниченной интервальной метрики

Выводы к главе

Глава 5. Численный метод анализа чувствительности результата сравнения альтернатив к изменению предпочтений

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

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

Выводы к главе

Глава 6. Решение задачи выбора параметров механической системы

6.1. Описание модели и постановка задачи оптимизации механизма

6.2. Численное моделирование кинематики механизма

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

Выводы к главе

Заключение

Список литературы

Приложение 1: описание компьютерной системы DASS

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

механической системы подвески

Введение

Введение диссертации (часть автореферата) на тему «Разработка методов анализа многокритериальных задач с использованием информации о важности критериев»

Актуальность темы

Большинство сложных и ответственных задач принятия решений являются многокритериальными [1-3]. Проблема многокритериального выбора среди множества альтернатив (вариантов решений) состоит в том, что лучшие из них по одним критериям, как правило, оказываются хуже по другим. Задание только набора критериев позволяет выделить лишь множество недоминируемых по Парето альтернатив [4]. Для окончательного выбора лучшей альтернативы необходимо привлекать дополнительную информацию о предпочтениях лица, принимающего решение (ЛПР).

Существует несколько подходов к решению этой задачи, включающих в себя способы извлечения и обработки сведений о предпочтениях ЛПР, разработку и обоснование рекомендаций по выбору наилучших альтернатив [1-3, 5-10]. Распространенным является использование агрегированного, обобщенного критерия - взвешенной свертки (линейной, мультипликативной, минимаксной) частных критериев [9-10]. При этом эвристически строится функция ценности, позволяющая сравнить любые две альтернативы по предпочтению. Однако процедура построения (выяснения) функции ценности довольно трудоемкая [1] и часто выполняется с применением некорректных операций [11-12]. Так, в [13-14] было показано, что метод анализа иерархий [6], использующий взвешенную сумму критериев, может привести к ошибочным результатам. Одним из принципиальных недостатков большинства методов, использующих взвешенную свертку критериев, является независимость процедур нормализации критериев и назначения их весов (коэффициентов важности), что в [8] названо «интеллектуальной ошибкой». Существует еще ряд недостатков, среди которых можно выделить фиксированность весов на всем диапазоне значений критериев. Это может быть справедливо для простых модельных задач, но в реальных задачах это условие, как правило, не выполняется [15].

В начале решения многокритериальной задачи ЛПР, как правило, не имеет

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

4

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

Такие процедуры, позволяющие корректно использовать информацию о важности критериев, можно построить на основе теории важности критериев (ТВК) [5, 16-28], которая опирается на строгие определения понятий относительной важности критериев и их коэффициентов важности. Ее методы предусматривают корректное получение и использование вначале качественной, и лишь затем, при необходимости, количественной информации о важности критериев и их шкале, причем в наиболее простой - интервальной форме. Таким образом, в ходе решения задачи ЛПР последовательно уточняет свои предпочтения, а формальные методы теории на основе этой информации сужают множество подходящих альтернатив [27-28]. При этом совершаемые выводы и рекомендации могут быть обоснованы с применением специальных методов теории.

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

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

Для достижения цели работы ставились и решались следующие задачи:

1) провести анализ существующих в ТВК методов сравнения альтернатив по

предпочтительности при различной информации о предпочтениях;

5

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

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

4) улучшить методы представления и обоснования результатов вычислений при сравнении альтернатив по предпочтительности;

5) разработать методы анализа чувствительности многокритериального выбора методами ТВК к изменению границ интервальных оценок степеней превосходства в важности одних критериев над другими.

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

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

Для численного моделирования кинематики механизма подвески автомобиля были использованы многомерный метод Ньютона решения системы нелинейных уравнений и метод регуляризации по Тихонову. Реализация численного моделирования и визуализации механизма проводилась в среде Delphi на языке Object Pascal.

Научная новизна

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

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

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

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

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

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

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

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

Разработанные методы и программная система были использованы в

диссертационной работе при решении прикладной задачи, связанной с

проектированием сложного механизма автомобильной подвески (см. главу 6 и

Приложение 2). Результаты, полученные в ходе работы над этой прикладной

задачей, сами по себе имеют научную ценность и практическую значимость в

7

областях математического моделирования, численных методов и комплексов программ.

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

Достоверность результатов, полученных в диссертации, обеспечивается строгостью доказательств и подтверждается результатами численного моделирования. На реализованный программный код численных методов моделирования кинематики механизма получено Свидетельство о государственной регистрации программы для ЭВМ № 2012661172 (см. приложение 2).

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

1) Для задач с упорядоченными по важности критериями с порядковой шкалой:

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

1.2) Модификация алгоритма построения объясняющей цепочки, гарантирующая минимальность длины получающейся цепочки.

2) Для задач с упорядоченными по важности критериями со шкалой первой порядковой метрики:

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

2.2) Алгоритм построения объясняющей цепочки.

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

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

3) Для случая интервальной информации о важности критериев и/или градаций их шкалы:

3.1) Единый аналитический алгоритм сравнения альтернатив по предпочтительности.

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

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

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

Объем и структура работы

Диссертация состоит из введения, шести глав, заключения, двух приложений и списка литературы. Диссертация содержит 138 машинописных страниц, 21 рисунок и 18 таблиц. В список литературы включено 64 наименований.

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

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

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

[29], обеспечивающей минимальность длины получающихся объясняющих

9

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

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

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

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

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

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

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

В шестой главе описывается пример практического применения разработанных методов и алгоритмов. Осуществляется выбор геометрических параметров 5-звенной подвески автомобиля с учетом нескольких критериев качества. Для этого производится численное моделирование кинематики подвески. Затем эта модель интегрируется с программным комплексом, предназначенным для поиска оптимальных параметров в заданном диапазоне. Полученные в результате такого поиска Парето-оптимальные альтернативы далее анализируются с помощью методов ТВК. Это позволяет выделить из сотен альтернатив всего четыре, наилучшим образом соответствующие указанным предпочтениям.

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

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

Апробация результатов работы

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

1) 52-я научная конференция МФТИ, г. Долгопрудный, 2009. «Билинейное программирование в анализе многокритериальных задач принятия решений методами теории важности критериев».

2) 22-ая Крымская Осенняя Математическая Школа. Крым, Ласпи-Батилиман, 17-29 сентября 2011. «Важность критериев в многокритериальных задачах принятия решений».

3) XXIV Международная инновационно-ориентированная конференция молодых ученых и студентов (МИКМУС - 2012). Москва, 24-26 октября 2012 г.

«Многокритериальная оптимизация кинематических характеристик 5-рычажной подвески».

4) XL Международная конференция "Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE'2012". Украина, Гурзуф, 25 мая

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

5) 23-ая Крымская Осенняя Математическая Школа. Крым, Ласпи-Батилиман, 17-29 сентября 2012. «Анализ чувствительности многокритериального выбора методами теории важности критериев к изменению границ интервалов относительной важности».

6) XLI Международная конференция "Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE'2013", Украина, Гурзуф, 25 мая

- 4 июня 2013. «Технология интерактивного решения многокритериальных задач».

7) Международная конференция «Дискретная оптимизация и исследование операций DOOR-2013. Новосибирск, 24 - 28 июня 2013. «Развитие методов аргументации в теории важности критериев».

8) VII Московская международная конференция по исследованию операций (0RM2013). Москва, 15-19 октября 2013. «Matrix ordinal decision rules in the criteria importance theory (Матричные ординальные решающие правила в теории важности критериев)».

9) XII Всероссийского совещания по проблемам управления (ВСПУ 2014) (Москва, Институт проблем управления РАН, 16-19 июня 2014). «Теория важности критериев: современное состояние и направления дальнейшего её развития».

10) 3-rd IFToMM Symposium on mechanism design for robotics (MEDER 2015). Denmark, Aalborg, 2-4 June 2015. «Kinematics analysis of 5-rod car suspension mechanism with singularities».

11) Научный семинар на кафедре Математического обеспечения ЭВМ Нижегородского государственного университета им. Н.И. Лобачевского. Нижний Новгород, 28 июня 2012.

12) Научный семинар отдела Интеллектуальных систем ВЦ РАН. Москва, 31 октября 2012.

13) Заседание научно-технического совета Отдела «Механика машин и управление машинами» ИМАШ РАН, Москва, 12 декабря 2013 г.

14) Научный семинар на кафедре высшей математики НИЯУ «МИФИ», Москва, декабрь 2013 г.

Публикации

Всего по теме диссертации опубликовано 19 работ в научных журналах и сборниках трудов конференций, в том числе 8 в реферируемых журналах из перечня ВАК, из них 8 статей индексированы системами Scopus и Web of Science.

Публикации в журналах из перечня ВАК:

1) Нелюбин А.П., Подиновский В.В. Билинейная оптимизация в анализе многокритериальных задач методами теории важности критериев при неточной информации о предпочтениях // Журнал вычислительной математики и математической физики. 2011. № 5. С. 802 - 813.

2) Нелюбин А.П., Подиновский В.В. Методы оптимизации в анализе многокритериальных задач принятия решений при интервальной информации о важности критериев или ценности шкальных градаций // Научно-техническая информация. Серия 2: Информационные процессы и системы, 2011, № 8, С. 22 -29.

3) Нелюбин А.П., Подиновский В.В. Взаимосвязь качественной и количественной важности критериев в многокритериальных задачах принятия решений // Открытое образование, 2011, № 6, С. 107 - 114.

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

первой порядковой метрики // Журнал вычислительной математики и математической физики, 2012, Т. 52, № 1, С. 48 - 65.

5) Нелюбин А.П., Подиновский В.В. Аналитические решающие правила, использующие упорядоченность по важности критериев со шкалой первой порядковой метрики // Автоматика и телемеханика, 2012, № 5, С. 84 - 96.

6) Нелюбин А.П. Анализ устойчивости многокритериального выбора методами теории важности критериев при изменении интервальных оценок важности критериев // Открытое образование, 2012, № 2, С. 47 - 51.

7) Нелюбин А.П., Подиновский В.В. Аналитические решающие правила для упорядоченных по важности критериев со шкалой первой порядковой метрики общего вида // Автоматика и телемеханика, 2014, № 9, С. 97 - 107.

8) Крейнин Г.В., Мисюрин С.Ю., Нелюбин А.П. Численное решение задачи о положении 5-рычажного механизма подвески автомобиля // Проблемы машиностроения и надежности машин, 2014, № 4, С. 3-9.

Публикации в других журналах и сборниках:

9) Подиновский В.В, Нелюбин А.П. Билинейное программирование в анализе многокритериальных задач принятия решений методами теории важности критериев // Труды 52-й научной конференции МФТИ. 2009. С. 105 - 107.

10) Подиновский В.В., Нелюбин А.П. Многокритериальные решающие правила для интервальной информации о важности критериев или их шкалах // Материалы XXXVII Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Украина, Гурзуф, 20 - 30 октября 2010 г.). Приложение к журналу «Открытое образование». 2010. С. 153 - 154.

11) Nelyubin A.P., Podinovski V.V. On the relationship between qualitative and quantitative importance of criteria in multicriterial decision making problems. In: Several Problems of Applied Mathematics and Mechanics / I. Gorgidze, T. Lominadze (Eds.). N.Y.: Nova Science Publishers, 2013, P. 43 - 55. ISBN: 978-1-62081-627-1.

12) Нелюбин А.П., Мисюрин С.Ю. Многокритериальная оптимизация кинематических характеристик 5-рычажной подвески // XXIV Международная

инновационно-ориентированная конференция молодых ученых и студентов (МИКМУС - 2012): материалы конференции. М: Изд-во ИМАШ РАН, 2012. C. 44.

13) Nelyubin A.P. Criteria importance theory: sensitivity analysis of multicriterial choice using interval importance information // American journal of control systems and information technology (Science book publishing house LLC). 2013, Vol. 1, No.1, pp. 13-17.

14) Нелюбин А.П. Построение объясняющих цепочек наименьшей длины при упорядоченных по важности критериях с порядковой шкалой // Вестник Московского университета имени С. Ю. Витте. Серия 1: Экономика и управление. 2013, № 3(5). С. 54 - 62.

15) Нелюбин А.П. Развитие методов аргументации в теории важности критериев // Материалы Международной конференции «Дискретная оптимизация и исследование операций D00R-2013». С. 120.

16) Podinovski V.V., Podinovskaya O.V., Nelyubin A.P. Matrix ordinal decision rules in the criteria importance theory (Матричные ординальные решающие правила в теории важности критериев) // Труды VII Московской международной конференции по исследованию операций (0RM2013). Т. 1. С. 107 - 110.

17) Нелюбин А.П. Технология интерактивного решения многокритериальных задач // Материалы XLI Международной конференции "Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE'2013". Приложение к журналу «Открытое образование». 2013. С. 61 - 63.

18) Misyurin S., Nelyubin A. Solution of forward kinematics problem of 5-rod car suspension mechanism with singularities // 11th International conference on electrical engineering, computing science and automatic control (CCE 2014). September 29-October 3, 2014, Mexico. p. 124.

19) Misyurin S.Yu., Nelyubin A.P. Kinematics analysis of 5-rod car suspension mechanism with singularities // Recent advances in mechanism design for robotics. Proceedings of the 3rd IFToMM Symposium on mechanism design for robotics, 2015, Vol. 33 of the series Mechanisms and machine science, pp. 435-443.

Глава 1. Сведения из теории важности критериев, развитию методов которой посвящена диссертационная работа

В этой главе приведены сведения из теории важности критериев (ТВК) [5, 1628], необходимые для дальнейшего изложения материала диссертационной работы. Описано состояние развития теории на момент начала исследований, проведенных автором работы. При этом сформулированы только те положения и результаты, которые используются далее в тексте, чтобы на них было удобно ссылаться. Поставлены конкретные задачи исследований диссертационной работы.

1.1. Математическая модель и основные понятия теории важности критериев

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

М = < X, K, Z, R >,

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

K = (Ki, ..., Km) - векторный критерий, состоящий из m^2 частных

критериев. Под критерием Ki понимается функция с областью определения X и областью значений Zi Q Re = (-да; +да). Далее полагается, что все критерии однородны или приведены к таковым. Это означает, что критерии имеют общую шкалу и, в частности, у них общая область значений Zo [12]. ТВК разработана для области значений критериев общего вида, но в данной работе рассматривается только дискретная область значений, представляющая собой множество градаций Zo = {1, ..., к, ..., q}, где q^2. Кроме того, предполагается, что каждый из

критериев независим по предпочтению от остальных (это понятие было введено в работе [1]) и его большие значения предпочтительнее меньших. Значения всех

критериев Ki(x) для альтернативы x из X образуют векторную оценку этой альтернативы y = K(x) = (Ki(x), ..., Km(x)). Таким образом, сравнение альтернатив по предпочтительности сводится к сопоставлению их векторных оценок.

Z = Zom - область значений векторного критерия K. Векторные оценки из множества Z могут соответствовать имеющимся альтернативам из X или быть гипотетическими.

R - отношение нестрогого предпочтения ЛПР на множестве векторных оценок Z: запись yRz означает, что векторная оценка y не менее предпочтительна, чем z. Отношение R является частичным квазипорядком, т.е. оно рефлексивно и транзитивно, и порождает на множестве Z отношения безразличия I и (строгого) предпочтения P:

ylz yRz л zRy; yPz yRz л —zRy.

Поскольку предпочтения ЛПР возрастают вдоль шкалы критериев Z0, то на множестве векторных оценок Z определено отношение Парето R0:

yR0z yi zi, i = 1, ..., m.

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

В качестве информации о предпочтениях ЛПР в ТВК используется информация об относительной важности критериев. Определения понятий равноважности и превосходства в важности формально вводятся следующим образом [5, 16-17]. Обозначим через y} векторную оценку, полученную из векторной оценки y = (yi, ..., ym) перестановкой ее компонент yi и yj.

Критерии Ki и Kj равноважны, или одинаково важны (такое сообщение обозначается i~j), когда векторные оценки y и y] одинаковы по

предпочтительности. Сообщение г~/ задает на множестве 2 отношение безразличия:

уП « 2 = /, Уг ф у. (1.1.1)

Критерий Кг важнее критерия К. (такое сообщение обозначается гу/), когда векторная оценка у, в которой уг > у, предпочтительнее, чем У' Сообщение ¡у задает на множестве 2 отношение предпочтения:

уРгУ/2 2 = у', у > у/. (1.1.2)

Совокупность сообщений вида г~/ и у образует качественную информация о важности критериев, которую обозначим О. Отношение ЯО, порождаемое на 2 качественной информацией о важности критериев О, определяется как наименьшее транзитивное отношение, содержащее отношение Парето Я0 и отношения Я® для всех сообщений сое О:

Список литературы диссертационного исследования кандидат наук Нелюбин Андрей Павлович, 2019 год

Список литературы

1. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. - М.: Радио и связь, 1981. - 560 с.

2. Ларичев О.И. Теория и методы принятия решений / Учебник. Изд. 2-е. - М.: Логос, 2002. - 382 с.

3. Лотов А.В., Поспелова И.И. Многокритериальные задачи принятия решений: Учебное пособие. - М.: МАКС Пресс, 2008. - 197 с.

4. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. - М.: Наука. 1982. - 256 с.

5. Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах принятия решений: Учебное пособие. - М.: Физматлит, 2007. 64 с.

6. Саати Т. Принятие решений. Метод анализа иерархий. - М.: Радио и Связь, 1993.

7. Roy B. The outranking approach and the foundation of ELECTRE methods // Theory and decision. 1991, Vol. 31. pp. 49-73.

8. Edwards W., Barron F.H. SMARTS and SMARTER: improved simple methods for multiattribute utility measurement // Organization Behavior and Human Processes. 1994. V. 60. pp. 306 - 325.

9. Trends in multiple criteria decision analysis / M. Ehrgott, J. Figuera, S. Greco (eds.). - New York: Springer, 2010.

10.Multiobjective optimization - interactive and evolutionary approaches / J.R. Branke, K. Deb, K. Miettinen, R. Slovinski (eds.). - New York: Springer, 2008.

11.Krantz D.H., Luce R.D., Suppes P., Tverski A. Foundation of measurement. V. 1. New York: Academic Press, 1971.

12.Пфанцагль И. Теория измерений. - М.: Мир. 1976. - 248 с.

13. Подиновский В.В., Подиновская О.В. О некорректности метода анализа иерархий // Проблемы управления. 2011. № 1. С. 8 - 13.

14. Подиновский В.В., Подиновская О.В. Еще раз о некорректности метода анализа иерархий // Проблемы управления. 2012. № 4. С. 75 - 78.

15. Горский П. Введение в дисциплину «Поддержка принятия решений». http: //www. pavel. gorskiy. ru/Articles/Dms s/d0. html.

16.Подиновский В.В. Многокритериальные задачи с упорядоченными по важности однородными критериями // Автоматика и телемеханика. 1976. № 11. С. 118 - 127.

17.Подиновский В.В. Аксиоматическое решение проблемы оценки важности критериев в многокритериальных задачах принятия решений // Современное состояние теории исследования операций / Под ред. Н.Н. Моисеева. - М.: Наука, 1979. С.117 - 145.

18.Подиновский В.В. Коэффициенты важности критериев в задачах принятия решений. Порядковые, или ординальные, коэффициенты важности // Автоматика и телемеханика. 1978. № 10. С. 130 - 141.

19.Подиновский В.В. Количественная важность критериев // Автоматика и телемеханика. 2000. № 5. С. 110 - 123.

20.Podinovski V.V. The quantitative importance of criteria for MCDA // Journal of multi-criteria decision analysis. 2002. Vol. 11. P. 1 - 15.

21.Подиновский В.В. Количественная важность критериев с дискретной шкалой первой порядковой метрики // Автоматика и телемеханика. 2004. № 8. С. 196 - 203.

22.Podinovski V.V. On the use of importance information in MCDA problems with criteria measured on the first ordered metric scale // Journal of multi-criteria decision analysis. 2009. V. 15. P. 163 - 174.

23.Подиновский В.В. Интервальные оценки важности критериев в многокритериальной оптимизации // Информационные технологии моделирования и управления. 2006. № 8 (33). С. 975 - 979.

24.Подиновский В.В. Интервальная информация о важности критериев в анализе многокритериальных задач принятия решений // Научно-техническая информация. Серия 2: Информационные процессы и системы. 2007. № 6. С. 15 - 18.

25.Подиновский В.В. Анализ устойчивости результатов выбора при частичном отношении предпочтения // Искусственный интеллект и принятие решений, 2009, № 4, С. 45-52.

26.Подиновский В.В. Качественная важность критериев и аддитивность многокритериальной структуры предпочтений // Открытое образование, 2011, № 2-2, С. 189-192.

27.Гафт М.Г., Подиновский В.В. О построении решающих правил в задачах принятия решений // Автоматика и телемеханика. 1981. № 6. С. 128 - 138.

28. Подиновский В.В. Анализ задач многокритериального выбора методами теории важности критериев при помощи компьютерных систем поддержки принятия решений // Известия РАН. Теория и системы управления. 2008. № 2. С. 64 - 68.

29. Алексеев Н.С. Алгоритмы многокритериального сравнения вариантов решения при ранжированных по важности критериях // Журнал вычислительной математики и математической физики. 1997. Т. 36, № 9. С. 60 - 70.

30.Fishburn P.C. Decision and value theory. New York: Wiley, 1964.

31.Claessens M. N. A. J., Lootsma F. A., Vogt F. J. An elementary proof of Poelinck's theorem on the convex hull of ranked criterion weights // European Journal of Operational Research, 1991, Vol. 52. pp. 255 - 258.

32.Бурбаки Н. Общая топология. Топологические группы. Числа и связанные с ними группы и пространства. - М.: Физматлит, 1969.

33.Horst R., Pardalos P., Thoai N. Introduction to global optimization. 2-d edition. Boston: Springer, 2000.

34.Nahapetyan A.G. Bilinear programming. In: Encyclopedia of optimization. 2009, pp. 279 - 282.

35.Нелюбин А.П. Построение объясняющих цепочек наименьшей длины при упорядоченных по важности критериях с порядковой шкалой // Вестник Московского университета имени С. Ю. Витте. Серия 1: Экономика и управление. 2013, № 3(5). С. 54 - 62.

36.Нелюбин А.П. Развитие методов аргументации в теории важности критериев // Материалы Международной конференции «Дискретная оптимизация и исследование операций DOOR-2013» (Новосибирск, 24 - 28 июня 2013). С. 120.

37.Нелюбин А.П., Подиновский В.В. Алгоритмическое решающее правило, использующее ординальные коэффициенты важности критериев со шкалой первой порядковой метрики // Журнал вычислительной математики и математической физики, 2012, Т. 52, № 1, С. 48 - 65.

38.Нелюбин А.П., Подиновский В.В. Аналитические решающие правила, использующие упорядоченность по важности критериев со шкалой первой порядковой метрики // Автоматика и телемеханика, 2012, № 5, С. 84 - 96.

39.Нелюбин А.П., Подиновский В.В. Аналитические решающие правила для упорядоченных по важности критериев со шкалой первой порядковой метрики общего вида // Автоматика и телемеханика, 2014, № 9, С. 97 - 107.

40.Нелюбин А.П., Подиновский В.В. Взаимосвязь качественной и количественной важности критериев в многокритериальных задачах принятия решений // Открытое образование, 2011, № 6, С. 107 - 114.

41.Nelyubin A.P., Podinovski V.V. On the relationship between qualitative and quantitative importance of criteria in multicriterial decision making problems. In: Several Problems of Applied Mathematics and Mechanics / I. Gorgidze, T. Lominadze (Eds.). N.Y.: Nova Science Publishers, 2013, P. 43 - 55. ISBN: 9781-62081-627-1.

42.Нелюбин А.П., Подиновский В.В. Методы оптимизации в анализе многокритериальных задач принятия решений при интервальной информации о важности критериев или ценности шкальных градаций // Научно-техническая информация. Серия 2: Информационные процессы и системы, 2011, № 8, С. 22 - 29.

43.Нелюбин А.П., Подиновский В.В. Билинейная оптимизация в анализе многокритериальных задач методами теории важности критериев при неточной информации о предпочтениях // Журнал вычислительной математики и математической физики. 2011. № 5. С. 802 - 813.

44.Нелюбин А.П. Анализ устойчивости многокритериального выбора методами теории важности критериев при изменении интервальных оценок важности критериев // Открытое образование, 2012, № 2, С. 47 - 51.

45.Nelyubin A.P. Criteria importance theory: sensitivity analysis of multicriterial choice using interval importance information // American journal of control systems and information technology (Science book publishing house LLC). 2013, Vol. 1, No.1, pp. 13-17.

46.Крейнин Г.В., Мисюрин С.Ю., Нелюбин А.П. Численное решение задачи о положении 5-рычажного механизма подвески автомобиля // Проблемы машиностроения и надежности машин, 2014, № 4, С. 3-9.

47.Misyurin S., Nelyubin A. Solution of forward kinematics problem of 5-rod car suspension mechanism with singularities // 11th International conference on electrical engineering, computing science and automatic control (CCE 2014). September 29-October 3, 2014, Mexico. p. 124.

48.Misyurin S.Yu., Nelyubin A.P. Kinematics analysis of 5-rod car suspension mechanism with singularities // 3-rd IFToMM Symposium on mechanism design for robotics (MEDER 2015) (Denmark, Aalborg, 2-4 June 2015).

49.Honda Worldwide site - http://world.honda.com/news/1997/t970702b.html

50.Samin J.C., et al. Multiphysics modeling and optimization of mechatronic

multibody systems // Multibody system dynamics, 2007.

51.Knapczyk J., Maniowski M. Elastokinematic modeling and study of five-rod suspension with subframe // Mechanism and machine theory, 2006, vol. 41, pp. 1031-1047.

52.Knapczyk J., Maniowski M. Optimization of 5-rod car suspension for elastokinematic and dynamic characteristics // The archive of mechanical engineering, 2010. Vol. 42, No. 2, pp. 133 - 147.

53.Reimpell J. Fahrwerktechnik: Radaufhängungen. - Vogel-Buchverlag, Würzburg, 1986. — 328 p.

54. Литвинов А.С., Фаробин Я.Е. Автомобиль. Теория эксплуатационных свойств. — М.: Машиностроение, 1989. — 238 с.

55.Raghavan M., Roth B. Solving polynomial systems for the kinematic analysis and synthesis of mechanisms and robot manipulators // Journal of mechanical design, 1995. №117 pp. 71-79.

56.Uchida T., McPhee J. Efficient solution of kinematics for multi-loop mechanisms using Grobner bases // Proceedings of the 13 th world congress in mechanism and machine science, Guanajuato, Mexico, 19-25 June, 2011.

57.Papegay Y.A., Merlet J-P., Daney D. Exact kinematics analysis of car's suspension mechanisms using symbolic computation and interval analysis // Mechanism and machine theory, 40:395-413, 2005.

58.Самарский А.А., Гулин А.В. Численные методы. — М.: Наука, 1989. — 432 с.

59.Калиткин Н.Н. Численные методы. — М.: Наука, 1978. — 512 с.

60. Лунев В.В., Мисюрин С.Ю. Особые многообразия плоских и пространственных механизмов с несколькими степенями свободы. // Проблемы машиностроения и надежности машин. 1993. № 1, с. 102-109.

61.Мисюрин С.Ю., Ивлев В.И., Косарев А.А., Костин А.В. Определение границ мертвых положений в механизмах с одной и несколькими степенями свободы. // Проблемы машиностроения и автоматизации (engineering & automation problems). ISSN 0234-6206 2008. № 3, с. 50-54.

62. Тихонов А. Н., Гончарский А. В., Степанов В. В., Ягола А. Г. Численные методы решения некорректных задач. — М.: Наука, 1990. — 230 с.

63.Подиновский В.В. Согласительные решения многокритериальных задач выбора // Математические проблемы управления, 2017, № 2. С. 17 - 26.

64.Нелюбин А.П., Подиновский В.В. Многокритериальный выбор методами теории важности критериев при неточной информации о предпочтениях // Журнал вычислительной математики и математической физики, 2017, Т. 57, № 9, С. 1494-1502.

Приложение 1: описание компьютерной системы DASS

Первая версия системы DASS (Decision Analysis Support System) была создана в 2006 году [28] авторами проф. Подиновским В.В., Потаповым М.А. и Шатохиным Е.А. Система включала в себя базовый интерфейс для ввода информации о предпочтениях ЛПР и библиотеку имеющихся на тот момент методов построения отношения предпочтения в рамках подхода ТВК. Последующие версии системы создавались после 2012 года и продолжают развиваться в настоящее время. В них автором диссертации реализованы методы сравнения векторных оценок по предпочтительности, разработанные в ходе данного диссертационного исследования. Кроме этого, в текущей версии системы DASS 2.4 автором реализованы процедуры получения согласительных решений [63-64]. Все актуальные версии системы DASS размещаются на сайте http://www.mcodm.ru/soft/dass. Имеется интерфейс на русском и английском языке, справочная информация. Система DASS используется в ряде курсов по принятию решений в Высшей школе экономики и МФТИ, а также применялась и планируется к использованию при решении ряда практических задач.

Версия системы DASS 2.4 включает в себя следующие компоненты:

- систему обработки и хранения данных о задаче и предпочтениях;

- библиотеку математических алгоритмов;

- пользовательский интерфейс.

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

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

Рис. П1. Ввод базовой информации о решаемой задаче.

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

Рис. П2. Выбор типа информации о важности критериев и их шкале.

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

Рис. П3. Упорядочение критериев по их относительной важности.

При выборе интервальной информации о важности критериев 5 требуется ввести количественные оценки границ интервалов ^ 0 К^ 0 г^, I = 1, ..., т - 1. При выборе количественной информации 0 требуется ввести точные оценки степеней

превосходства в важности критериев К^ =

а,-

а1+1

1, I = 1, ..., т - 1 (см. рис. П4).

Рис. П4. Ввод количественной информации об относительной важности

критериев.

Тип шкалы первой порядковой метрики соответствует информации Д|. Методы, учитывающие информацию Д| и Д о шкале критериев в текущей версии 2.4 не реализованы. При выборе типа шкалы ограниченной интервальной метрики (информация [V]) требуется ввести количественные оценки границ интервалов dk0 д(к)/д(к + 1)0 Ык, к = 1, ..., q - 2, уточняющие информацию Д|. При выборе типа шкалы интервалов требуется ввести точные количественные оценки величин у(к), к = 1, ..., q (см. рис. П5).

Рис. П5. Ввод количественной информации о скорости роста предпочтений вдоль

шкалы критериев. 123

После ввода информации о предпочтениях ЛПР следует выбрать пункт меню слева «Недоминируемые варианты». В соответствии с выбранным сочетанием типов информации о важности критериев и их шкале и введенными оценками параметров предпочтений с помощью разработанных методов сравнения векторных оценок по предпочтительности системой будет сформирован перечень недоминируемых и доминируемых альтернатив (см. рис. П6). Альтернатива называется недоминируемой, если не существует другой альтернативы из множества X, более предпочтительной по отношению Р. В противном случае альтернатива называется доминируемой. При выделении левой кнопкой мыши любой доминируемой альтернативы будет выведено текстовое пояснение, какая из альтернатив является более предпочтительной, чем выделенная (см. рис. П6). Выбор лучшей альтернативы следует осуществлять среди множества недоминируемых альтернатив [1-5].

Рис. П6. Вывод результатов сравнения альтернатив по предпочтительности в виде перечня недоминируемых и доминируемых альтернатив.

Система DASS версии 2.4 позволяет в любой момент решения многокритериальной задачи переключаться на любой из описанных типов информации о предпочтениях, получая в результате список недоминируемых и доминируемых альтернатив. Однако рекомендуется использовать итеративно-фрагментарный подход [27-28], идея которого заключается в последовательном и

непротиворечивом уточнении информации о предпочтениях ЛПР в ходе интерактивной процедуры взаимодействия ЛПР с аналитиком и компьютерной системой. При таком подходе исходное множество недоминируемых по отношению Парето альтернатив последовательно сужается, так что на одном из этапов решения задачи может остаться одна недоминируемая альтернатива, либо несколько недоминируемых альтернатив, эквивалентных по отношению I. В этом случае решение задачи многокритериального выбора найдено, и дальнейшее уточнение предпочтений не требуется. Также возможен случай, когда дальнейшее уточнение предпочтений затруднено или невозможно, а множество недоминируемых альтернатив все еще содержит несравнимые по предпочтению альтернативы. Тогда следует воспользоваться дополнительными методами выбора лучшей альтернативы среди множества недоминируемых. В системе DASS версии 2.4 реализовано два таких метода [64]: 1) рассчитать значения аддитивной функции ценности (1.2.15) альтернатив с использованием центроидных значений параметров предпочтений и выбрать альтернативу с наибольшим значением функции ценности; 2) определить максимально-правдоподобно оптимальную альтернативу. Оба этих метода доступны в меню слева «Согласительные решения» (см рис. П7).

Рэбб - Пример для иллюстрации работы системы

Справка

Текущая категория: Согласительные решения

Способ решения (•) Центроидные значения параметров О Максимально правдоподобно оптимальные альтернат

Лучшие среди недоминируемых вариантов:

Недоминируемы« варианты

Согласительные

Значение функции ценности

х! 0.792

хЗ 0.771

х4 0.771

х5 0.717

РаБЗ - Пример для иллюстрации работы системы

Сгщавка

Текущая категория: Согласительные решения

Способ решения О Центроидные значения параметров (.•) Максимально правдоподобно оптимальные аль~ернат

Лучшие среди недоминируемых вариантов:

НедоминируемыЕ варианты

Согласительные решения

Показать значения параметров

в

Вероятность оптимальности

х! 0,590

хЗ 0,348

х4 0,34В

х5 0,063

Применить Отмена

Показать значения параметров

Применить Отмена

Рис. П7. Методы выбора лучшей альтернативы при неполной информации о

предпочтениях.

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

В этом приложении приведены основные части программного кода системы для численного моделирования и визуализации автомобильной подвески, используемой в главе 6. Программа Suspension написана на языке Object Pascal и скомпилирована в среде Delphi 7. Программный код состоит из 3 модулей, описанных в главном файле проекта Suspension.dpr:

program Suspension; uses Forms,

Unitl in 'Unitl.pas' {Forml}, Newton in 'Newton.pas', Globals in 'Globals.pas'; {$R *.res} begin Application.Initialize; Application.CreateForm(TForm1, Forml); Application.Run; end.

Модуль Unit1.pas отвечает за пользовательский интерфейс - чтение и вывод данных, визуализацию кинематики подвески. В модуле Newton.pas содержатся основные вычислительные процедуры методов Ньютона и Гаусса. В модуле Globals.pas находятся глобальные переменные и вспомогательные функции.

Программный код модуля Globals.pas:

type DPoint = array[1..3] of Extended; var

A0, B0, C0, D0, F0, //фиксированные крепления

initAs, initBs, initCs, initDs, initFs, initOs, initNs, Es, //начальные положения prevA, prevB, prevC, prevD, prevF, prevO, prevN, //предыдущие положения newA, newB, newC, newD, newF, newO, newN: DPoint; //искомые

// длины рычагов и квадраты расстояний между шарнирами dist2_AA0, dist2_BA, dist2_BB0, dist2_CA, dist2_CB, dist2_CC0, dist2_DA, dist2_DB, dist2_DC, dist2_DD0, dist2_FA, dist2_FB, dist2_FC, dist2_FF0, dist2_OA, dist2_OB, dist2_OC, dist2_NA, dist2_NB, dist2_NC, distA, distB, distC, distD, distF: Extended;_

Программный код модуля Newton.pas:

const n = 17; eps = 0.1; low_val1 = 0.000001; low_val2 = 0.01; var Niters, fail, nfree: Integer;

tempA, tempB, tempC, tempD, tempF, tempO: DPoint; A: array[1..n, 1..n] of Extended; //матрица СЛАУ A_temp: array[1..n, 1..n] of Extended;

b: array[1..n] of Extended; //столбец свободных членов СЛАУ b_temp: array[1..n] of Extended; x: array[1..n] of Extended; //решение СЛАУ bestX: array[1..n] of Extended;

f: array[1..n] of Extended; //функции нелинейной системы

Jac: array[1..n, 1..3] of Extendedy/Якобиан, содержит все необходимые коэф для А

ord: array[1..n] of Integer; //номер строки в А для i-ой функции

ord_: array[1..n] of Integer;

free_col: array[1..n] of Integer; //номера свободных переменных при вырожденности А

procedure prepareSLAE; var i, k: Integer; begin

b[1] := dist2(tempA,A0) - dist2_AA0; b[2] := dist2(tempB,tempA) - dist2_BA; b[3] := dist2(tempB,B0) - dist2_BB0; b[4] := dist2(tempC,tempA) - dist2_CA; b[5] := dist2(tempC,tempB) - dist2_CB; b[6] := dist2(tempC,C0) - dist2_CC0; b[7] := dist2(tempD,tempA) - dist2_DA; b[8] := dist2(tempD,tempB) - dist2_DB; b[9] := dist2(tempD,tempc) - dist2_DC; b[10] := dist2(tempD,D0) - dist2_DD0; b[n] := dist2(tempF,tempA) - dist2_FA; b[12] := dist2(tempF,tempB) - dist2_FB; b[13] := dist2(tempF,tempc) - dist2_FC; b[14] := dist2(tempF,F0) - dist2_FF0; b[15] := dist2(tempO,tempA) - dist2_OA; b[16] := dist2(tempO,tempB) - dist2_OB; b[17] := dist2(tempO,tempc) - dist2_OC; for k := 1 to 3 do begin

Jac[1,k] := tempA[k] - A0[k]; Jac[2,k] := tempB[k] - tempA[k]; Jac[3,k] := tempB[k] - B0[k]; Jac[4,k] := tempC[k] - tempA[k]; Jac[5,k] := tempc[k] - tempB[k]; Jac[6,k] := tempC[k] - C0[k]; Jac[7,k] := tempD[k] - tempA[k]; Jac[8,k] := tempD[k] - tempB[k]; Jac[9,k] := tempD[k] - tempc[k]; Jac[10,k] := tempD[k] - D0[k]; Jac[11,k] := tempF[k] - tempA[k]; Jac[12,k] := tempF[k] - tempB[k]; Jac[13,k] := tempF[k] - tempc[k];

Jac[14,k] := tempF[k] Jac[15,k] := tempO[k] Jac[16,k] := tempO[k] Jac[17,k] := tempO[k] end;

for i := 1 to n do begin ord[i] := 0; free_col[i] := 0; b[i] := -b[i]/2; for k := 1 to n do A[i,k] := 0; end;

for k := 1 to 3 do begin A[1,k] := Jac[1,k];

A[2,3+k] := Jac[2,k]; A[2,k] := -Jac[2,k];

A[3,3+k] := Jac[3,k];

A[4,6+k] := Jac[4,k]; A[4,k] := -Jac[4,k];

A[5,6+k] := Jac[5,k]; A[5,3+k] := -Jac[5,k];

A[6,6+k] := Jac[6,k];

A[7,9+k] := Jac[7,k]; A[7,k] := -Jac[7,k];

A[8,9+k] := Jac[8,k]; A[8,3+k] := -Jac[8,k];

A[9,9+k] := Jac[9,k]; A[9,6+k] := -Jac[9,k];

A[10,9+k] := Jac[10,k];

A[11,12+k] := Jac[11,k]; A[11,k] := -Jac[11,k]; A[12,12+k] := Jac[12,k]; A[12,3+k] := -Jac[12,k]; A[13,12+k] := Jac[13,k]; A[13,6+k] := -Jac[13,k]; A[14,12+k] := Jac[14,k]; A[15,k] := -Jac[15,k]; A[16,3+k] := -Jac[16,k]; A[17,6+k] := -Jac[17,k]; end;

A[15,16] := Jac[15,1]; A[15,17] := Jac[15,2]; A[16,16] := Jac[16,1]; A[16,17] := Jac[16,2]; A[17,16] := Jac[17,1]; A[17,17] := Jac[17,2]; end;

// вспомогательная функция function max_in_col(k: Integer): Integer; var i: Integer; val: Extended; begin val := low_val1; result := 0; for i := 1 to n do begin

if ((abs(A[i,k]) > val)and(ord[i]=0)) then begin val := abs(A[i,k]); result := i; end end; end;

- F0[k];

- tempA[k];

- tempB[k];

- tempC[k];

procedure gauss; var i, k, i1, k1: Integer;

coef, sum, min_norm: Extended; found: boolean; begin

//метод Гаусса с выбором главного элемента по столбцу nfree := 0; for k := 1 to n do begin i1 := max_in_col(k); if (i1 > 0) then begin ord[i1] := k; ord_[k] := i1;

//вычитание из остальных строк

for i := 1 to n do

begin

if ((A[i,k] <> 0)and(i<>i1)) then begin coef := A[i,k]/A[i1,k]; for k1 := 1 to n do begin

if (A[i1,k1] <> 0) then begin

A[i,k1] := A[i,k1] - coef*A[i1,k1]; end; end;

A[i,k] := 0;

b[i] := b[i] - coef*b[i1]; end; end;

end else // k - нулевой столбец, i1 = 0 begin nfree := nfree + 1; ord_[k] := 0; free_col[nfree] := k; end; end;

if (nfree > 0) then // минимизация нормы решения, если матрица вырождена begin

// проверка на совместность for i := 1 to n do if ((ord[i] = 0) and (abs(b[i]) > low_val2)) then ShowMessage('несовместная СЛАУ');

// перебор значений свободных переменных от -20 до 20 и минимизация нормы решения for k := 1 to nfree do begin x[free_col[k]] := -20; bestX[free_col[k]] := -20; end;

min_norm := 10000;

while (x[free_col[1]] < 20) do

begin

// поиск следующего распределения свободных переменных found := false; k := nfree;

while ( (not found) and (k >= 1) ) do begin

if (x[free_col[k]] < 20) then begin

x[free_col[k]] := x[free_col[k]] + 0.1; found := true; end else begin x[free_col[k]] := -20; k := k - 1; end; end;

// считаем остальные компоненты решения for i := 1 to n do begin if (ord_[i] > 0) then begin sum := 0;

for k := 1 to nfree do sum := sum + A[ord_[i],free_col[k]]*x[free_col[k]]; x[i] := (b[ord_[i]] - sum)/A[ord_[i],i]; end; end;

// считаем норму х

sum := 0;

for i := 1 to n do

sum := sum + x[i]*x[i]; // норма - квадрат длины вектора if (sum < min_norm) then begin min_norm := sum;

for k := 1 to nfree do bestX[free_col[k]] := x[free_col[k]]; end; end;

// считаем лучшее решение for k := 1 to nfree do begin

x[free_col[k]] := bestX[free_col[k]]; end;

for i := 1 to n do begin if (ord_[i] > 0) then begin sum := 0;

for k := 1 to nfree do sum := sum + A[ord_[i],free_col[k]]*x[free_col[k]]; x[i] := (b[ord_[i]] - sum)/A[ord_[i],i]; end;

end; end

else // nfree = 0 - матрица A невырождена: begin for i := 1 to n do begin

x[ord[i]] := b[i]/A[i,ord[i]]; end; end; end;

procedure CalcNewtonMethod(Oz: Double; max_iter: Integer); var i, k, j: Integer;

max_delta, regul: Extended; begin Niters := 0; tempA := prevA; tempB := prevB; tempC := prevC; tempD := prevD; tempF := prevF; tempO := prevO; tempO[3] := Oz; // первый проход repeat prepareSLAE; gauss;

// проверка условия окончания счета max_delta := 0; for i := 1 to n do if (abs(x[i]) > max_delta) then max_delta := abs(x[i]);

for k := 1 to 3 do begin

tempA[k] := tempA[k] + x[k]; tempB[k] := tempB[k] + x[3+k]; tempc[k] := tempc[k] + x[6+k]; tempD[k] := tempD[k] + x[9+k]; tempF[k] := tempF[k] + x[12+k]; end;

tempO[1] := tempO[1] + x[16]; tempO[2] := tempO[2] + x[17]; Niters := Niters + 1;

until ( (max_delta < eps) or (Niters = max_iter) );

if (Niters >= max_iter) then begin tempA := prevA; tempB := prevB; tempC := prevC; tempD := prevD; tempF := prevF;

tempO := prevO; tempO[3] := Oz;

// при необходимости второй проход - с применением регуляризации repeat prepareSLAE;

// построение регуляризованной системы for i := 1 to n do begin b_temp[i] := b[i];

for k := 1 to n do A_temp[i,k] := A[i,k]; end;

regul := 0.005; for i := 1 to n do begin b[i] := 0; for k := 1 to n do begin

b[i] := b[i] + A_temp[k,i]*b_temp[k];

A[i,k] := 0;

for j := 1 to n do

A[i,k] := A[i,k] + A_temp[j,i]*A_temp[j,k]; if (i = k) then A[i,k] := A[i,k] + regul; end; end; gauss;

// проверка условия окончания счета max_delta := 0; for i := 1 to n do if (abs(x[i]) > max_delta) then max_delta := abs(x[i]);

for k := 1 to 3 do begin

tempA[k] := tempA[k] + x[k]; tempB[k] := tempB[k] + x[3+k]; tempc[k] := tempc[k] + x[6+k]; tempD[k] := tempD[k] + x[9+k]; tempF[k] := tempF[k] + x[12+k]; end;

tempO[1] := tempO[1] + x[16]; tempO[2] := tempO[2] + x[17];

Niters := Niters + 1;

until ( (max_delta < eps) or (Niters = max_iter) ); end;

newA := tempA; newB := tempB; newC := tempC; newD := tempD; newF := tempF; newO := tempO; end;

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

interface uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls, ComCtrls, Math, OpenGL, Globals, Newton; private DC: HDC; hrc: HGLRC;

quadSphere: GLUquadricObj; quadDisk: GLUquadricObj; var

Forml: TForml;

anglex, angley, angle, Xcoord, Ycoord, zoom, norm : GLfloat; wrkX, wrkY, xm, ym : Integer; downL, downR : Integer; en, animate : boolean;

implementation

procedure TForm1.DrawPlane(Ad, Bd, Cd, Dd, Fd, Od, Nd: DPoint);

var os, os2: Double;

begin

glBegin(GL_TRIANGLES); glVertex3f(Bd[1]/norm, Bd[2]/norm, Bd[3]/norm); glVertex3f(Ad[1]/norm, Ad[2]/norm, Ad[3]/norm); glVertex3f(Cd[1]/norm, Cd[2]/norm, Cd[3]/norm); glEnd;

glBegin(GL_TRIANGLES); glVertex3f(Ad[1]/norm, Ad[2]/norm, Ad[3]/norm); glVertex3f(Fd[1]/norm, Fd[2]/norm, Fd[3]/norm); glVertex3f(Cd[1]/norm, Cd[2]/norm, Cd[3]/norm); glEnd;

glBegin(GL_TRIANGLES); glVertex3f(Bd[1]/norm, Bd[2]/norm, Bd[3]/norm); glVertex3f(Cd[1]/norm, Cd[2]/norm, Cd[3]/norm); glVertex3f(Dd[1]/norm, Dd[2]/norm, Dd[3]/norm); glEnd;

glBegin(GL_LINES); glVertex3f(Od[1]/norm, Od[2]/norm, Od[3]/norm); glVertex3f(Nd[1]/norm, Nd[2]/norm, Nd[3]/norm); glEnd;

glColor3f(0.0, 0.0, 0.0); glBegin(GL_LINES);

glVertex3f(Ad[1]/norm, Ad[2]/norm, Ad[3]/norm); glVertex3f(A0[1]/norm, A0[2]/norm, A0[3]/norm); glEnd;

glBegin(GL_LINES); glVertex3f(Bd[1]/norm, Bd[2]/norm, Bd[3]/norm); glVertex3f(B0[1]/norm, B0[2]/norm, B0[3]/norm); glEnd;

glBegin(GL_LINES); glVertex3f(Cd[1]/norm, Cd[2]/norm, Cd[3]/norm); glVertex3f(c0[1]/norm, C0[2]/norm, C0[3]/norm); glEnd;

glBegin(GL_LINES); glVertex3f(Dd[1]/norm, Dd[2]/norm, Dd[3]/norm); glVertex3f(D0[1]/norm, D0[2]/norm, D0[3]/norm); glEnd;

glBegin(GL_LINES); glVertex3f(Fd[1]/norm, Fd[2]/norm, Fd[3]/norm); glVertex3f(F0[1]/norm, F0[2]/norm, F0[3]/norm); glEnd;

DrawPoint(Ad); DrawPoint(Bd); DrawPoint(Cd); DrawPoint(Fd); DrawPoint(Dd); DrawPoint(Od); DrawPoint(Nd);

os := SQRT(dist2(Nd, Od));

os2 := SQRT((Nd[1]-Od[1])*(Nd[1]-Od[1]) + (Nd[2]-Od[2])*(Nd[2]-Od[2])); glPushMatrix; glTranslatef(Od[1]/norm , Od[2]/norm, Od[3]/norm); glColor4d(0.8, 0.8, 0.8, 0.5);

glRotatef(arccos((Nd[3]-0d[3])/os)*180/pi, -(Nd[2]-Od[2])/os2, (Nd[1]-Od[1])/os2 , 0.0); gluDisk(quadDisk, 0, Radius/norm, 20, 20); glPopMatrix; end;

procedure TForm1.DrawPoint(point: DPoint); begin glPushMatrix;

glTranslatef(point[1]/norm , point[2]/norm, point[3]/norm); glColor3f(0.0, 0.0, 0.0); gluSphere(quadSphere, 0.01, 10, 10); glPopMatrix; end;

procedure TForm1.Draw(base: boolean); var

ps : TPaintStruct; begin

wglMakeCurrent(dc, hrc); BeginPaint(panel.Handle, ps);

glClearColor(0.85, 0.75, 0.5, 1.0);

glClear(GL_COLOR_BUFFER_BIT or GL_DEPTH_BUFFER_BIT);

glEnable(GL_DEPTH_TEST);

glEnable(GL_ALPHA_TEST);

glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

glEnable(GL_BLEND);

glMatrixMode(GL_PROJECTION);

glLoadIdentity;

gluPerspective(15.0, panel.Width / panel.Height, 1.0, 10.0); glViewport(0, 0, panel.Width, panel.Height); glMatrixMode(GL_MODELVIEW); glLoadIdentity;

glTranslatef(Xcoord, Ycoord, zoom); glRotatef (-90, 1.0, 0.0 , 0.0); glRotatef (-90, 0.0, 0.0 , 1.0); glRotatef (Angley, 0.0, 1.0 , 0.0); glRotatef (Anglex, 0.0, 0.0 , 1.0);

//координатные оси glColor3f(1.0, 1.0, 1.0); glBegin(GL_LINES); glVertex3f(0.0, 0.0, 0.0); glVertex3f(0.0, 1.0, 0.0); glVertex3f(0.0, 0.0, 0.0); glVertex3f(1.0, 0.0, 0.0); glVertex3f(0.0, 0.0, 0.0); glVertex3f(0.0, 0.0, 1.0); glEnd;

DrawPoint(A0); DrawPoint(B0); DrawPoint(C0); DrawPoint(D0); DrawPoint(F0);

//начальное положение

if (base) then

begin

glColor4d(0.0, 0.0, 1.0, 0.8);

DrawPlane(initAs, initBs, initCs, initDs, initFs, initOs, initNs); end;

//новое положение glColor4d(1.0, 0.0, 0.0, 0.8);

DrawPlane(newA, newB, newC, newD, newF, newO, newN);

glRotatef (angle*100, 1.0,0.0 , 0.0); glTranslatef(0.0, 2.0, 0);

glFlush;

SwapBuffers(DC); EndPaint(panel.Handle, ps); wglMakeCurrent(dc, 0); //InvalidateRect(panel.Handle, nil, False); end;

procedure TForm1.FormCreate(Sender: TObject); begin

DC := GetDC(panel.Handle);

SetDCPixelFormat;

hrc := wglCreateContext(DC);

Xcoord := 0.0; Ycoord := 0.0;

downL := 0; downR := 0; en := false; zoom := -6.0; norm := 500.0; ReadData;

quadSphere := gluNewQuadric(); gluQuadricDrawStyle(quadSphere, GLU_FILL); quadDisk := gluNewQuadric(); gluQuadricDrawStyle(quadDisk, GLU_FILL); end;

procedure TForm1.FormDestroy(Sender: TObject); begin

wglMakeCurrent(0, 0); wglDeleteContext(hrc); ReleaseDC(panel.Handle, DC); DeleteDC(DC); end;

procedure TForm1.PanelMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer); begin

If button = mbLeft then begin wrkX := X; wrkY := Y; downL := 1; end;

If button = mbRight then begin wrkX := X; wrkY := Y; downR := 1; end;

if (en) then Draw(not animate); end;

procedure TForm1.PanelMouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); begin

If downL <> 0 then begin anglex:=anglex + (x-xm); angley:=angley + (y-ym); end;

If downR <> 0 then begin

XCoord:=Xcoord + 0.003*(x-xm); Ycoord:=Ycoord - 0.003*(y-ym); end;

xm:=x; ym:=y;

if (en) then Draw(not animate); end;

procedure TForm1.PanelMouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer); begin

downL := 0; downR := 0; if (en) then Draw(not animate); end;

procedure TForm1.ZplusButtonClick(Sender: TObject); begin

if (zoom < -1) then zoom := zoom + 1.0; if (en) then Draw(not animate); end;

procedure TForm1.ZminusButtonClick(Sender: TObject); begin

if (zoom > -10) then zoom := zoom - 1.0; if (en) then Draw(not animate); end;