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

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

ЗОЛТОЕВА Ирина Александровна

МЕТОДЫ КОРРЕКЦИИ ДАННЫХ ДЛЯ ФОРМАЛИЗАЦИИ И РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

05.13.17 - теоретические основы информатики

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

МОСКВА 2006

003067005

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

Научный руководитель

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

Ведущая организация

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

ГОРЕЛИК Виктор Александрович.

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

КОНОНЕНКО Александр Федорович.

кандидат физико-математических наук, доцент

МОРОЗОВ Владимир Викторович.

Московский городской педагогический университет.

Защита состоится «27» апреля 2007 г. в ч. Q£ мин. на заседании Диссертационного совета К 212.154.11 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет Mill У, ауд 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета по адресу: 119992, г. Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан «$» Меьр/ъ 2007 г. Ученый секретарь Диссертационного совета

_ ЧИКАНЦЕВА Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Многокритериальным задачам посвящено значительное количество работ иностранных авторов (Райфа X., Кини P.JI, Саати Т., Штойер Р. и др.). Параллельно с зарубежными исследованиями аналогичные работы проводились и в России (Емельянов C.B., Ларичев О.И., Гермейер Ю.Б., Жуковский В.И., Ногин В.Д., Подиновский В.В и др.).

Принятие решений при многих критериях представляет собой особый вид человеческой деятельности, по которым человек учитывает и сопоставляет различные (и часто противоречивые) качества объектов или событий при их сравнении или нахождении их общей ценности. Научное направление «многокритериальное принятие решений» направлено на изучение следующих вопросов: 1) как люди принимают решения; 2) как люди должны принимать решения; 3) как, на основе каких методов и технических средств можно помочь людям принимать лучшие решения.

В этой области работают различные группы специалистов: психологи разными способами осуществляют изучение того, как именно люди в лабораторных экспериментах и в реальном мире принимают разнообразные решения; математики и экономисты на основе ряда постулатов и теорем выводят правила рационального принятия решений; практики-консультанты (сотрудники консультативных организаций) помогают руководителям проводить рациональный анализ варианта решений и выбирать лучший вариант. При этом они часто используют ЭВМ, а результаты своей работы называют системами поддержки принятия решений. Многокритериальное принятие решений и исследование операций имеют одну весьма общую область практических приложений: целенаправленную человеческую деятельность. В этой области есть задачи, которые целесообразно решать традиционными методами исследования операций. Есть задачи, для которых успешно применяются подходы и методы принятия решений при многих критериях. Наряду с этим существуют «пограничные» проблемы, осознание которых важно для специалистов того или другого направления. Есть задачи, которые считают «своими» и специалисты по исследованию операций, и специалисты по принятию решений.

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

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

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

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

Задача многокритериальной (векторной) оптимизации в исходной постановке задается объектом {Х,1У(х)}, где X - множество стратегий или альтернатив (подмножество произвольного пространства), Ж(*)- векторная функция (векторный критерий), заданная на X и задающая частичный порядок на X. Наиболее распространенным является порядок по Парето: х'ух", если

¡У^^Ф^х") и 1У(хг)*1¥(х") (в предположении требования максимизации каждой компоненты вектора IV, неравенства и равенства понимаются в обычном для векторов смысле покомпонентно).

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

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

При всем многообразии подходов к формализации задачи многокритериальной оптимизации условно можно выделить два основных направления. Первое основано на введении некоторой строгой математической процедуры выбора, связанной с вектором критериев Ж. Сюда относятся методы свертки критериев, идеальной точки, выделения главного критерия и перевода других в ограничения, пороговых значений и уступок, лексикографии, целевого программирования и т.д. Во всех этих методах присутствуют некоторые параметры (весовые коэффициенты, пороговые значения, порядок лексикографии, условные значения критериев, штрафы за отклонения, меры, расстояния и т.д.), которые должны быть назначены ЛПР, т.е. требуют от него дополнительной информации. Второе направление основано на непосредственном выявлении предпочтений ЛПР путем постановки ему «более простых» вопросов (нежели, например, назначение весовых коэффициентов). Это направление привело к появлению целого ряда эвристических процедур итеративного типа, реализованного в виде диалоговых человеко-машинных

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

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

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

Нами предлагается несколько иной подход, в какой-то степени синтезирующий подходы обоих направлений и состоящий в следующем. Выбирается один из методов, относящийся к первому направлению. ЛПР предлагается дать информацию о необходимых параметрах метода (например, весовых коэффициентах или пороговых значениях), руководствуясь при этом тенденцией к максимальной полноте информации без требования ее непротиворечивости, а затем противоречивость (ярко проявляющаяся, например, в методе попарных сравнений) устраняется путем минимальной коррекции оценок ЛПР. Если найденное решение и, следовательно, скорректированные оценки ЛПР не устраивают, то на их основе оно может дать новые оценки и процедура повторяется. Здесь возникает аналогия с методами прогнозирования. Можно брать исходную информацию в минимальном объеме, достаточной для построения интерполяционной зависимости, но практически, как правило, надежнее использовать «избыточную» информацию, по которой можно построить только аппроксимирующую зависимость, что эквивалентно минимальной коррекции исходной информации в той или иной метрике (метод наименьших квадратов, обобщенный метод наименьших квадратов, равномерное приближение и другие). Такая обработка при достаточной избыточности информации позволяет исключить неточности измерений, внешнее воздействие (шумы) и т.п. Для многокритериальной оптимизации это означает нивелирование ошибок ЛПР, связанных с неточностью представлений о предпочтениях, недостаточной компетентностью, усталостью и т.п.

Данный подход к формализации и решению задач многокритериальной оптимизации на основе методов коррекции исходной информации позволяет взглянуть более широко на данную проблему. Обычно в задачах векторной оптимизации множество стратегий X считается фиксированным и все внимание уделяется построению на нем некоторого порядка. Однако объект {X, №(х)} представляет собой модель выбора на основе согласования некоторых возможностей X и потребностей УУ. На практике этого согласования можно достичь не только приведением потребностей к

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

Формально противоречивость информации ЛПР может быть представлена в виде несовместности соответствующих систем уравнений и неравенств. В последние годы методы коррекции несовместных систем и несобственных задач линейного программирования развивались весьма интенсивно -матричная коррекция, обобщенный метод наименьших квадратов (Ватолин A.A., Горелик В.А., Еремин И.И., Ерохин В.И., Матросов В.Л., Попов Л.Д., Rosen J.B., Vun Huffei S., Lemmerling Р. и др.).

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

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

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

Объектом исследования является теория многокритериальной оптимизации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Ежегодная научно-практическая конференция сотрудников БГУ Улан-Удэ, 2006 г. Институт математики и информатики БГУ.

2. Объединенный семинар Иркутского Института Динамики систем управления СО РАН, Бурятского центра информатизации Байкальского региона и Института математики и информатики БГУ, 2006.

3. Научно-методические семинары кафедры теории информатики и дискретной математики Mill У.

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

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

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

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

Для объекта (Х0, fV0(x)) вводится некоторая процедура выбора решения F(X0,JV0(x),a), зависящая от вектора параметров а. Для определения параметров а ЛПР задает дополнительную информацию - вектор Д,, который определяет возможные значения а в виде множества А(0О), в идеале одноэлементное, но не исключается и пустое множество.

При Хо*0 и фиксированном а множество решений для данной процедуры будет также обозначать F(X0,W0(x),a), а множество решений при всех возможных значениях а как

SF= (J F{Xa,W,{x),a). aeAfio)

Будем считать, что SF Ф0, если одновременно ЛГо*0, А(/30) Ф 0 и F(X0,Wo(x),a)=A0 VaeA(J30), в противном случае SF = 0 и задачу будем называть несобственной. В этом случае погрузим ее в параметрическое семейство задач следующим образом. Будем считать, что множество возможных стратегий X задается ограничениями, которые параметризованы вектором //еМ, т.е. Х(/л), при этом исходное Х0 = Х(/л0),/лаеМ, Вектор критериев W также параметризован W(x,co), су е Q, при этом

fF0(x) = W(x,a>Q),coed. Для произвольных значений параметров J3,ju,a и фиксированной процедуры F(X,ff(x),a) множество решений есть SF0>fi,m)= (J F{X{fS),W{x,m),a).

aeA(fi)

Будем предполагать, что существует совокупность (/?,//, й>) такая, что SF(/3,p,c))*0. На множестве параметров Л = (Р,ц,<о) введем некоторую метрику р. Поставим задачу минимальной коррекции несобственной задачи jnin0, где Л^ = (Д,д,,ю0). Ее решение Л' будет определять

собственную (разрешимую) задачу, аппроксимирующую исходную несобственную задачу.

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

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

В §-2.1 рассмотрена проблема построения единого критерия с помощью метода линейной свертки критериев многокритериальной задачи.

На пространстве стратегий XeR" задачи принятия решений заданы несколько критериев эффективности Wl(x),W2(x),...,Wr(x), хеХ. Требуется

г г

построить единый критерий W(x) =

¿-1 *=i Для определения вектора X = (Л,,-^.....Лг) заданы экспертные оценки общего

критерия на конечном наборе стратегий bl = W (xl), b2 = W(х2).....bm-W{xm).

Можно вычислить значения всех частных критериев в заданных точках. Обозначим wjk = Wk(xJ), j = 1.....т, fc = l,...,r, W -(w]k)- матрица размерности

тхг (возможно т>г), вектор Ъ = {Ьх,Ьг,...,Ьт) е Ra. Тогда система линейных ограничений относительно Л имеет вид:

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

v, = inf (У2: 1ГЛ = Ъ + h, Л й О, ¿Л* = 1}, (1)

¡ы

v2 = inf{|#||2: (W + Н)Л = b, А 2> 0, = 1}, (2)

v3 - inf {||[-А,Я]||:(W + Я)Я = b + h, Я ä 0, ¿Я, = 1}. (3)

ы

Задачи (1)-(3) сводятся к нахождению собственных чисел и векторов некоторых матриц. Так для задачи (3) справедлива

Теорема.

v3 = min |||-й,Я||2: (W + Н)Я = Ь + И,Л^0,^Лк = 1 j=

= min (Ve,Ve)= min Uk(jD2)), (g.e)'0

где ~D1 = {E-PgjVTV, V = [-b,W], g = (-l,l.....1), \(рг), e„ - собственные

значения и соответствующий собственный вектор матрицы £>2.

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

Определение:

Разреженной матрицей будем называть вещественную матрицу, в которой большинство элементов равны нулю:

А = {atJ:а9 = 0,(гJ)еК0,К0аК,К = {(i,j):i = 1.....т; j = 1.....л}},

dim(iC0) > dim(^T)/2.

Обозначим символом „ множество всех вещественных матриц размера т у. п, имеющих фиксированную разреженную структуру (4), задаваемую Кй.

Дана несовместная система линейных алгебраических уравнений вида

Ах = Ъ,

где АееRm,xeR",b*0.

Требуется найти матрицу Я* е и вектор А* е Rm такие, что система (A + H')x = b + h' совместна и выполнено условие

ЦГ-А-.Я'Щ = min |[-Л,Я]|| , (5)

lip

ZZh''

4 '=1 M

результаты справедливы при любом р (р ä 1), но реально, как правило,

- гельдерова норма матрицы. Все дальнейшие

гдаИ,=

используются р = \ и /> = ооу|Л||ю =тах|<зу|

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

По условию задачи (5) Я - разреженная матрица той же структуры что и А, поэтому можно записать

Матрице Я однозначно соответствует вектор

= О",У) eK\K0)eRk,k = dim(K \ К0). Матрица Н - параметрическая, зависящая от вектора а, поэтому можно ввести обозначение Н(а).

Вектору xeR" поставим в соответствие матрицу К(х) е Rm*k следующего вида:

Г [*« = *,,>если r = i„s = l,l = 1.....k,i, еIA,j, е

= 0, в остальных случаях I

где множества 1А и JА имеют следующий вид:

IA = {i: (i,j)eK\ К0} = = {/,:/ = 1.....*},

Ja = U'-VJ)еК\К0} = Ц.....jt} = {j, :l = l,...,k}.

Параметрическая матрица задаваемая формулой (6), позволяет получить полезное тождество, связывающее х,а,Н(а) и N(x), а именно, Лемма

Н(а)х = Ы(х)а. (8)

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

~г(а,х)' а

(6)

(7)

► min,

а,х

(9)

где г(а,х) = Ь-(А + Н(а))х.

Подвергнем векторы а их линейным приращениям Д а и Ах. Рассмотрим вектор г(а + Асс,х+Дх). В силу леммы выполняется тождество

Н(Аа)х = К(х)Аа.

Отбрасывая слагаемое Н(Аа)Ах как величину второго порядка малости, получаем

г(а + Аа,х + Ах) = г(а,х) - Х(х)Да - (А + Н{а))Ах. Для решения задачи (9) применим алгоритм обобщенной наименьшей нормы (ТЬ№ алгоритм).

Алгоритм ТЪМ.

Шаг О.(инициализация). Задать некоторые векторы aeRi и Шаг 5. (итерационный). Решить вспомогательную задачу:

'К(х) А + Ща) Да 4_ '-г(а,х)1

. 1. о„ _ Ах а J

—> min,

Д аг,Дх

(10)

где lt и 0„- вектора из единиц и нулей соответствующей размерности. Аа

Если

Ах

йе- остановка, в противном случае а = а + Аа,х = х+Ах и

продолжить вычисления.

Вспомогательная задача (10) на каждом шаге алгоритма при

различных р решается различными методами. При р = 2 она превращается в

м=

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

"NO) А+Н{а) 0„

или ее разложения в произведение ортогональной (Q) и верхней треугольной (R) матриц, т.е. так называемого QR- разложения. При р = х> задача (10) сводится к задаче линейного программирования:

и -> min .

и, Да,Ах

и > Щх)А а + (А+Н(а))Ах - г(а,х), и £-Щх)Аа - (Л + Н(а)) Дх+г (а, х), uZa + Aa, и>-а- А а.

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

/ Л \

А о ...... ... 0

А = 0 А2 0 .. ... 0 (13)

1° 0 0 .... ..0 AQJ

= М, ¿и„ = N. щ = 0.

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

В §-2.3 рассмотрен метод попарных сравнений. Составим матрицу А попарных сравнений критериев многокритериальной задачи

А =

Г1 ап ап 1

г2

.1

(14)

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

правило, не обладает свойством совместности, т.е. не для всех ¡,],к е {1,2,...г} выполняется аиа1У = ал,1Ф ].

Рассмотрено 2 подхода к решению задачи попарных сравнений:

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

г-1

1 ]>!

В этом случае предполагая малыми и отбрасывая члены второго порядка в ограничениях (15), получаем задачу квадратичного программирования.

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

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

о-

1К

1 ]»

'ПИП,

(16)

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

Г1 ~ап О О -а,

О О

Л-а,

1

■г-1,г 1

' О Л

г(г—1)/2

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

В §-2.4 задача многокритериальной оптимизации представлена в виде иерархической структуры:

III уровень

Щ Щ......к* ......

Используя принцип синтезирования критериев, получаем: 2л

Г г п

¡Ы ,

>1

(=1

*еЛ.О7* = 'о./о = {1.2,...,и}, = 1,X«* =£Я/ = ■

Шк /-1 /-1

X ж* ч

ак

Таким образом, мы имеем следующую блочную структуру:

ад

О

11!_%

О

)Г4] КМ

Л

«да,™)

3=

и,

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

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

В §-3.1 рассмотрена матричная коррекция многокритериальной задачи с заданными пороговыми значениями.

Задачу многокритериальной оптимизации PFt(x)-»max,£ = l.....г при

ограничениях х е X = {х : Ах = Ъ,х £ 0} формализуем путем введения пороговых значений w°k, удовлетворяющих ЛПР и не подлежащих коррекции. В случае их недостижимости подвергается коррекции система ограничений. Рассматривается задача коррекции системы линейных уравнений с фиксированными ограничениями-неравенствами

тт{||[-А,Я]||2:(^ + Я)х = г» + А, ад>и-°,;с>0}. (17)

Введем обозначения:

Hx-h = b- Ах, В =(-Ь ,А ),

V V

= в

л

[~h,H]' =В ' ,y = (l,x),[-h,H]y = By. W

Решением задачи (17) будет

Введем векторы £?t=(-w®, clt, ... k~l,....,r. Задачу (17) можно

свести к задаче квадратичного программирования с дополнительными ограничениями <dk,e>>0,k = 1,...,г:

min{< D е,е >:eZ0, |е|| = 1, < dk,e>ОД = 1.....г}, (18)

где D =ВТВ ,В = (-Ь,А), которая решается нахождением собственных значений, а именно,

Лемма. Решение задачи (18) сводится к перебору минимальных собственных чисел матриц D, Dl=(E- Pd)D и всех подматриц D и D{:

inf{(De,e)> 0,||е|| = 1 ,(d,e)> 0} = min min )}, тт^АДД)} , (19)

[(<Д)20 ' ' J

где D (Ц) - все квадратные подматрицы £>(Д), полученные вычеркиванием строк и столбцов с одинаковыми номерами (включая саму матрицу £)(Д)); А„е' - минимальное собственное число и соответствующий ему собственный вектор некоторой подматрицы D или Ц .

В §-3.2 задачу многокритериальной оптимизации формализуем введением для пороговых значений ск уступок wk и решаем задачу одновременной матричной коррекции пороговых значений и ограничений многокритериальной задачи. В качестве пороговых значений естественно брать по методу идеальной точки с° = max.Wt, к = . Для аппроксимации исходной задачи используем

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

min тах||[-А,Я]|[<),|м'|[1): (A+H)x=b+h, ^(x)=c°-w*,w4>0, х>о, ¿=1,...,г|.

Запишем Wt(x) = c°k-wk,k = l,...,r в матричном виде Сх-с" -w. Если обозначить компоненты векторов Ь —Ах через (Ъ - Ах),, а компоненты вектора с0 - Сх через (с" - Сх\, то задача коррекции примет вид:

тах<

max|(b-v4*),

1=1, я

1 + ZXj j-1

, тах|(с° - Сх)к

► тт.

»20

(20)

которую, в свою очередь сводится к задаче:

и —> min

х.У.*

utb,y-a'yx, и > -Ь,у + а'ух, i = 1 ,...,т и>с1~скх,к = 1.....г

У' = l + txj

(21)

и>0,хк0.

Задача (21) не является задачей линейного программирования, но фиксируя значения у с помощью метода деления отрезка она сводится к последовательности задач линейного программирования.

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

Г(А+Н)х = Ь + к

~-ъ А .

, с еЯг, С - матрица коэффициентов целевых

Обозначим через А =

с0 С

функций. Пусть А'х = 0, где х =

, несовместная система линейных

алгебраических уравнений. Требуется найти матрицу Я' =

обладающей блочной структурой, Я* е (А' + Н')х = 0 совместна и выполнено условие

■h Я' и> 0

такую, что система

Задача (22) решается на основе модификации алгоритма наименьшей обобщенной нормы, рассмотренной в §-2.2 для случая блочной структуры и сводится к последовательности задач линейного программирования.

В §-3.4 рассмотрен случай изменения матрицы коэффициентов критериев С на величину 5 при одновременной коррекции пороговых значений с° и системы ограничений. Рассматривается следующая задача:

хттжтах{||[-Л,Я]||„:{А + Н)х = Ь + И,хеЯ",{С + 5)х>с°к -мк>0,х>0}

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

к->тт,

и^Ьу- а'г, и ^ -Ь,у + а'г,»= 1,...,т, и £ с°у - с 2, и ^ -с°у + с"г, к = 1,...,г,

1 = У + ±2>,

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

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

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

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

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

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

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

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

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

1. Золтоева И.А. Коррекция задачи многокритериальной оптимизации с заданными пороговыми значениями // Вестник Бурятского университета. Серия 13: Математика и информатика. - Вып.З.- Улан-Удэ: Изд-во Бурятского госуниверситета, 2006. С.150-152. - 0,19 п.л. (авторский вклад -100 %)

2. Горелик В.А., Золтоева И.А. Матричная коррекция несовместных линейных систем с разреженными матрицами // Моделирование, декомпозиция и оптимизация сложных динамических процессов - М.: ВЦ РАН, 2006. С.47-57. - 0,74 п.л. (авторский вклад - 80 %)

3. Горелик В.А., Муравьева О.В., Золтоева И.А. Некоторые методы коррекции экспертных оценок задачи многокритериальной оптимизации // Некоторые вопросы математики, информатики и методики их преподавания - МПГУ, 2006. С. 55-60. - 0,38 п.л. (авторский вклад - 60 %)

Подл, к печ. 15.03.2007 Объем 1 п.л. Заказ №. 63 Тир 100 экз.

Типография Mill У

ВВЕДЕНИЕ.

ГЛАВА 1. ИСПОЛЬЗОВАНИЕ МЕТОДОВ КОРРЕКЦИИ ДАННЫХ ДЛЯ ФОРМАЛИЗАЦИИ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

§ -1.1.Анализ современных подходов к формализации и решению многокритериальных задач.

§ -1.2. Методы решения многокритериальных задач.

§ -1.3. Постановка проблемы коррекции данных как формализации задач многокритериальной оптимизации.

ГЛАВА 2. РЕШЕНИЕ ЗАДАЧ КОРРЕКЦИИ ДЛЯ ВЫБОРА ВЕСОВЫХ

КОЭФФИЦИЕНТОВ КРИТЕРИЕВ.

§ - 2.1 Метод линейной свертки критериев.

§ - 2.2 Матричная коррекция несовместных линейных систем уравнений с разреженными матрицами.

§ - 2.3 Использование методов коррекции разреженных матриц в задаче попарных сравнений.

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

ГЛАВА 3. РЕШЕНИЕ ЗАДАЧ КОРРЕКЦИИ ОГРАНИЧЕНИЙ И

ПОРОГОВЫХ ЗНАЧЕНИЙ КРИТЕРИЕВ.

§ - 3.1. Коррекция системы ограничений линейной многокритериальной задачи с заданными пороговыми значениями.

§ - 3.2 Минимаксная матричная коррекция системы ограничений и пороговых значений линейной многокритериальной задачи (обобщенный метод идеальной точки).

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

§ - 3.4 Минимаксная коррекция системы ограничений и пороговых значений многокритериальной оптимизации в случае изменения матрицы коэффициентов критериев.

§ - 3.5 Вычислительные эксперименты.

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

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

Многокритериальным задачам посвящено значительное количество работ иностранных авторов (Райфа Х.[66], Кини P.JI.[43], Саати Т. [67;68], Штойер Р.[75] и др.). Параллельно с зарубежными исследованиями аналогичные работы проводились и в России (Емельянов С.В.[48], Ларичев О.Щ49], Гермейер Ю.Б.[7], Жуковский В.И.[38;39], Ногин В.Д.[58], Подиновский В.В.[60;63] и др.).

Принятие решений при многих критериях представляет собой особый вид человеческой деятельности, по которым человек учитывает и сопоставляет различные (и часто противоречивые) качества объектов или событий при их сравнении или нахождении их общей ценности. Научное направление «многокритериальное принятие решений» направлено на изучение следующих вопросов: 1) как люди принимают решения»; 2) как люди должны принимать решения; 3) как, на основе каких методов и технических средств можно помочь людям принимать лучшие решения.

В этой области работают различные группы специалистов: психологи разными способами осуществляют изучение того, как именно люди в лабораторных экспериментах и в реальном мире принимают разнообразные решения; математики и экономисты на основе ряда постулатов и теорем выводят правила рационального принятия решений; практики-консультанты (сотрудники консультативных организаций) помогают руководителям проводить рациональный анализ варианта решений и выбирать лучший вариант. При этом они часто используют ЭВМ, а результаты своей работы называют системами поддержки принятия решений. Многокритериальное принятие решений и исследование операций имеют одну весьма общую область практических приложений: целенаправленную человеческую деятельность. В этой области есть задачи, которые целесообразно решать традиционными методами исследования операций. Есть задачи, для которых успешно применяются подходы и методы принятия решений при многих критериях. Наряду с этим существуют «пограничные» проблемы, осознание которых важно для специалистов того или другого направления. Есть задачи, которые считают «своими» и специалисты по исследованию операций, и специалисты по принятию решений.

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

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

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

Задача многокритериальной (векторной) оптимизации в исходной постановке задается объектом {Х, W(x)}, где X - множество стратегий или альтернатив (подмножество произвольного пространства), W(x)- векторная функция (векторный критерий), заданная на X и задающая частичный порядок на X. Наиболее распространенным является порядок по Парето: х'Ухп, если W(x')>W(x") и W(x')^W(x") (в предположении требования максимизации каждой компоненты вектора W , неравенства и равенства понимаются в обычном для векторов смысле покомпонентно).

В такой постановке можно определить множество оптимальных по Парето стратегий или ядро такого предпочтения, а именно, х°- оптимально по Парето, если не существует х*, что х'ух0 , и множество Парето - образ множества оптимальных стратегий в пространстве критериев W. Однако множество Парето, как правило, «велико», что затрудняет решение о конкретном выборе стратегии. Поэтому обычно предполагается, что существует некоторое предпочтение ЛПР >-, задающее непосредственный порядок (возможно полный) на X. Это предпочтение задается не в явном виде (иначе проблема многокритериальности снимается), а косвенно в виде дополнительной информации, которую способно дать ЛПР. Естественное требование к этой информации, чтобы она не противоречила порядку по Парето и позволяла выделить из множества паретооптимальных стратегий «более узкое» подмножество (в идеале - одну точку).

При всем многообразии подходов к формализации задачи многокритериальной оптимизации условно можно выделить два основных направления. Первое основано на введении некоторой строгой математической процедуры выбора, связанной с вектором критериев W . Сюда относятся методы свертки критериев, идеальной точки, выделения главного критерия и перевода других в ограничения, пороговых значений и уступок, лексикографии, целевого программирования и т.д. Во всех этих методах присутствуют некоторые параметры (весовые коэффициенты, пороговые значения, порядок лексикографии, условные значения критериев, штрафы за отклонения, меры, расстояния и т.д.), которые должны быть назначены ЛПР, т.е. требуют от него дополнительной информации. Второе направление основано на непосредственном выявлении предпочтений ЛПР путем постановки ему «более простых» вопросов (нежели, например, назначение весовых коэффициентов). Это направление привело к появлению целого ряда эвристических процедур итеративного типа, реализованного в виде диалоговых человеко-машинных процедур. Впрочем, в таких процедурах также присутствуют некоторые параметры (например, величина шага в релаксационных методах), которые назначаются весьма произвольно.

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

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

Нами предлагается несколько иной подход, в какой-то степени синтезирующий подходы обоих направлений и состоящий в следующем. Выбирается один из методов, относящийся к первому направлению. ЛПР предлагается дать информацию о необходимых параметрах метода (например, весовых коэффициентах или пороговых значениях), руководствуясь при этом тенденцией к максимальной полноте информации без требования ее непротиворечивости, а затем противоречивость (ярко проявляющаяся, например, в методе попарных сравнений) устраняется путем минимальной коррекции оценок ЛПР. Если найденное решение и, следовательно, скорректированные оценки ЛПР не устраивают, то на их основе оно может дать новые оценки и процедура повторяется. Здесь возникает аналогия с методами прогнозирования. Можно брать исходную информацию в минимальном объеме, достаточной для построения интерполяционной зависимости, но практически, как правило, надежнее использовать «избыточную» информацию, по которой можно построить только аппроксимирующую зависимость, что эквивалентно минимальной коррекции исходной информации в той или иной метрике (метод наименьших квадратов, обобщенный метод наименьших квадратов, равномерное приближение и другие). Такая обработка при достаточной избыточности информации позволяет исключить неточности измерений, внешнее воздействие (шумы) и т.п. Для многокритериальной оптимизации это означает нивелирование ошибок ЛПР, связанных с неточностью представлений о предпочтениях, недостаточной компетентностью, усталостью и т.п.

Данный подход к формализации и решению задач многокритериальной оптимизации на основе методов коррекции исходной информации позволяет взглянуть более широко на данную проблему. Обычно в задачах векторной оптимизации множество стратегий X считается фиксированным и все внимание уделяется построению на нем некоторого порядка. Однако объект [X,W(x)} представляет собой модель выбора на основе согласования некоторых возможностей X и потребностей W . На практике этого согласования можно достичь не только приведением потребностей к возможностям (например, метод уступок при заданных пороговых значениях), но и подтягиванием возможностей к потребностям. Математически это выражается в коррекции ограничений, задающих множество X , или одновременной коррекции ограничений на значения стратегий х и значения критериев W . Подобная идея несколько в ином контексте и на совершенно других математических формулировках задач была высказана еще академиком В.М. Глушковым и названа системной оптимизацией.

Основная проблема многокритериальной оптимизации состоит в том, что в исходной постановке многокритериальная задача, как правило, не формализована. Для ее формализации требуется дополнительно выявлять предпочтения ЛПР. Такие предпочтения могут быть неполными или противоречивыми. Возникает идея обработки информации, представленной ЛПР, путем ее минимальной коррекции так, чтобы в результате получить строгую математическую задачу, имеющую решение. При этом естественно использовать развиваемое в последние годы направление, связанное с коррекцией несобственных задач оптимизации, в первую очередь методы матричной коррекции несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования (Ватолин А.А.[4;5], Горелик В.А.[13;16;24], Еремин И.И.[36;37], Ерохин В.И.[14;17], Матросов В.Л.[52;53], Попов Л.Д.[59], Rosen J.B.[79], Van Huffel S.[81], Lemmerling P.[78] и др.).

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

Данная работа посвящена указанной проблеме и этим определяется ее актуальность.

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

Объектом исследования является теория многокритериальной оптимизации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Ежегодная научно-практическая конференция сотрудников БГУ Улан-Удэ, 2006 г. Институт математики и информатики БГУ.

2. Объединенный семинар Иркутского Института Динамики систем управления СО РАН, Бурятского центра информатизации Байкальского региона и Института математики и информатики БГУ, 2006.

3. Научно-методические семинары кафедры теории информатики и дискретной математики МПГУ.

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

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

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

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

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

В §-2.1 рассмотрена проблема построения единого критерия с помощью метода линейной свертки критериев многокритериальной задачи.

На пространстве стратегий XeR" задачи принятия решений заданы несколько критериев эффективности Wl(x),W2(x),.,Wr(x), хеХ. Требуется г г построить единый критерий W(x) = ^Лк1¥к(х), Лк >0, ^Лк=\. k=l к=1

Для определения вектора Л = (Л1,Л2,.,ЛГ) заданы экспертные оценки общего критерия на конечном наборе стратегий bx = W (У), b2-W (х2),., bm=W(xm). Можно вычислить значения всех частных критериев в заданных точках. Обозначим wjk=Wk(xJ), j = l,.,m, k = \,.,r, W = (wJk)~ матрица размерности wxr (возможно т>г), вектор b = (bl,b2,.,bm)eRm. Тогда система линейных ограничений относительно Л имеет вид: г

1¥Л = Ь, Л>0, 1. к=1

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

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

Дана несовместная система линейных алгебраических уравнений вида

Ах = Ь, где AeKmn,beRm,xeRn,b*0, где „- множество всех вещественных матриц размера тхп, имеющих фиксированную разреженную структуру

А = {<itj: ау = 0, (i,j) е К0, К0с:К,К = {(/,;): i = l,.,m; j = 1,., w}}, dim(AT0) > dim(AT)/2.

Требуется найти матрицу H* е $lm n и вектор h* eRm такие, что система

A + H*)x = b + h* совместна и выполнено условие

Г-/Ля1| = rnin ||И,яЦ ,

IIL Лр HeKm„,h£Rm,(A+H)x=b+h,xeR""L Л"Р г р\[/р п п у где M L =

ЕЕ м j=1 ) щ

- гельдерова норма матрицы.

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

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

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

А =

4 о о а2 О . о

О 0 0 .0 А lQJ

AeRMxN,A0eRm°xN,AveRm*хя>, xeRn,v = \,.,Q,

Q Q v=l v=0

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

Составим матрицу А попарных сравнений критериев многокритериальной задачи

А =

1 а12 ап

21 1 «23 а if а

2 г аП аг2 1 atj -положительное число, показывающее во сколько раз вес критерия Wi больше веса W. Полученная таким образом матрица парных сравнений, как правило, не обладает свойством совместности, т.е. не для всех i,j,k е {1,2,.г} выполняется а^а]к - ajk, j.

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

В §-2.4 задача многокритериальной оптимизации представлена в виде иерархической структуры:

I уровень

II уровень

III уровень

Wo

Wi w2.wnj w„i+1.wn)+n2 w

П]+.+Пг]+1

W„

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

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

В §-3.1 рассмотрена матричная коррекция многокритериальной задачи с заданными пороговыми значениями.

Линейную задачу многокритериальной оптимизации Wk(x)->maх,к = 1,.,г при ограничениях хеХ = {х:Ах = Ь,х>Щ формализуем путем введения пороговых значений w°k , удовлетворяющих J11 LP и не подлежащих коррекции. В случае их недостижимости подвергается коррекции система ограничений. Рассматривается задача коррекции системы линейных уравнений с фиксированными ограничениями-неравенствами гшп{||Н,Я]||2 :(A + H)x = b + h, Wk{x) > w°k, х > о}.

В §-3.2 задачу многокритериальной оптимизации формализуем введением для пороговых значений с°к уступок wk и решаем задачу одновременной матричной коррекции пороговых значений и ограничений многокритериальной задачи. В качестве пороговых значений естественно брать по методу идеальной точки с°к =maxff Д = 1,.,г. Для аппроксимации исходной задачи используем минимаксный критерий оптимальности и получаем задачу безусловной оптимизации: (A+H)x=b+h, Wk(x)=c°k-wk,wk> 0, *>0, к=J.

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

А + Н)х = b + h \wk(x) = 4-wk,wk> 0,х>0' min max W

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

В §-3.4 рассмотрен случай изменения матрицы коэффициентов критериев С на величину S при одновременной коррекции пороговых значений с°к и системы ограничений. Рассматривается следующая задача: min max{\[-h,H]\\ JkSj|e :(A + H)x = b + h,xeR",(C + S)x>c\ -wk, wk >0,x>0} tH fhfStW

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

Заключение содержит основные результаты и выводы диссертационной работы. Основное содержание диссертации опубликовано в [18],[19],[40].

ЗАКЛЮЧЕНИЕ

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

При этом получены следующие результаты:

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

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

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

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

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

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

1. Ашманов С.А. Линейное программирование. М.: Наука, 1982. 134 с.

2. Баврин И.И., Матросов В.Л. Общий курс высшей математики. М.: Просвещение, 1995.464 с.

3. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Изд-во "Факториал", 1998.176 с.

4. Ватолин А.А. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы. // ЖВМиМФ, 1984. Т. 24.12. С. 1907-1908.

5. Ватолин А. А. Об аппроксимации несовместных систем уравнений и неравенств. В кн.: Методы аппроксимации несобственной задачи линейного программирования. УНЦ АН СССР. Свердловск, 1984. С.39-54.

6. Вентцелъ Е.С. Теория вероятностей. М.: Наука, 1964. 576 с.

7. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.384 с.

8. Глушков В.М. О системной оптимизации. Кибернетика, 1980, № 5. С. 89-90.

9. Глушков В.М., Михалевич B.C., Волкович В.Л., Доленко Г.А. К вопросу системной оптимизации в многокритериальных задачах линейного программирования. Кибернетика, 1982, № 3. С. 4-8.

10. Голуб Док., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. 548 с.

11. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений. // ЖВМ и МФ, 2001. Т. 41,11. С. 1697-1705.

12. Горелик В.А., Ибатуллин P.P. Коррекция системы ограничений задачи линейного программирования с минимаксным критерием // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.:ВЦ РАН, 2001. С.89-107.

13. Горелик В.А., Ерохин В.И. Оптимальная матричная коррекциянесовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. М.: ВЦ РАН, 2004.193 с.

14. Горелик В.А., Ерохин В.И., Печенкин Р.В. Численные методы коррекции несобственных задач линейного программирования и структурных систем уравнений. М.: ВЦ РАН, 2006. 150 с.

15. Горелик В.А. Ерохин В.И. Печенкин Р.В. Минимаксная матричная коррекция несовместных систем линейных алгебраических уравнений с блочными матрицами коэффициентов// Известия РАН. ТИСУ, 2006, №5. С.52-62.

16. Горелик В.А. Ерохин В.И. Печенкин Р.В. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений с блочной матрицей коэффициентов // Дискретный анализ и исследование операций. Июль-декабрь 2005. Серия 2. Том 12, №2. С.41-73.

17. Горелик В.А., Золтоева И.А. Матричная коррекция несовместных линейных систем с разреженными матрицами // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2006. С.47-57.

18. Горелик В.А., Муравьева О.В., Золтоева И.А. Некоторые методы коррекции экспертных оценок задачи многокритериальной оптимизации // Некоторые вопросы математики, информатики и методики их преподавания -М.МПГУ, 2006. С. 55-60.

19. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 1999. С. 57-82.

20. Горелик В.А., Муравьева О.В. Матричная коррекция данных в задачах оптимизации и классификации.//Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. С.94-120.

21. Горелик В.А., Муравьева О.В. Задача аппроксимации с коррекцией всех данных. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2000. С. 21-32.

22. Горелик В.А., Муравьева О.В. Коррекция несовместной системы линейных уравнений с дополнительными ограничениями. // Тезисы докладов 1-й Московской конференции Декомпозиционные методы в математическом моделировании. М.: ВЦ РАН, 2001. С. 36.

23. Горелик В.А., Фомина Т.П. Основы исследования операций. М.: МПГУ, 2004. 248 с.

24. Горелов М.А., Кононенко А.Ф. Информационные аспекты принятия решений в условиях конфликта. М.: ВЦ РАН, 1994, 42 с.

25. Грунина А.Ю. Решение многокритериальных задач оптимизации в условиях неопределенности на основе метода анализа иерархий, Дис. к.т.н. -М., 1998.

26. Давыдов Э.Г. О системах несовместных линейных уравнений // Вестник МГУ, 1989. сер. 15.2. С. 76-79.

27. Доленко Г. А. Методы решения многокритериальных задач оптимизации при изменении области допустимых решений. Дис.к.ф-м.н. -Киев, 1983.

28. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов решений. М.: Наука, 1986.295 с.

29. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного ивыпуклого программирования. М.: Наука, 1976.192 с.

30. Еремин И.И. Вопросы двойственности для несобственной задачи многокритериальной линейной оптимизации. В кн.: Исследования по несобственным задачам оптимизации. УНЦ АН СССР. Свердловск, 1988. С. 27-33.

31. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001. 179 с. .

32. Еремин И.И. Двойственность для несобственной задачи линейного программирования. В кн.: Несобственные задачи оптимизации. УНЦ АН СССР. Свердловск, 1982. С. 3-10.

33. Еремин И.И., Ватолин А.А. Двойственность для несобственных бесконечномерных задач линейного и выпуклого программирования. В кн.: Методы аппроксимации несобственной задачи линейного программирования. УНЦ АН СССР. Свердловск, 1984. С. 3-20.

34. Еремин И.И. Несобственная задача квадратичного программирования и вопросы регуляризации. В кн.: Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования. УНЦ АН СССР. Свердловск, 1985. С. 47-50.

35. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука. Физматлит, 1983. 336 с.

36. Жуковский В.И., Салуквадзе М.Е. Оптимизация гарантий в многокритериальных задачах управления Тбилиси: "Мецниереба". 1996. 476 с.

37. Жуковский В.И., Молостов B.C. Многокритериальная оптимизация систем в условиях неполной информации. М: МНИИПУ, 1990. 112 с.

38. Золтоева И.А. Коррекция задачи многокритериальной оптимизации с заданными пороговыми значениями // Вестник Бурятского университета. Серия 13: Математика и информатика. Вып.З.- Улан-Удэ: Изд-во Бурятского госуниверситета, 2006. С. 150-152.

39. Ириков В. А., Ларин В .Я., Самущенко JI.M. Алгоритмы и программы решения прикладных многокритериальных задач // Изв. АН СССР, Техн. Кибернетика, 1986, №1. С. 5-16

40. Карманов В.Г., Федоров В.В. Моделирование в исследовании операций. М.: Твема, 1996.102 с.

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

42. Кондратьева В.А. Несобственные задачи линейной оптимизации и параметрическое программирование. Дисс. на соиск. учен. степ. канд. физ.-мат. наук: 05.13.17. МПГУ, 2000.

43. Кононенко А. Ф. О многошаговых конфликтах с обменом информацией.—ЖВМ и МФ, 1977. Т. 17, № 4. С. 922-931.

44. Кононенко А.Ф. Структура оптимальной стратегии в динамических управляемых системах //Ж. вычисл. матем. и матем. физ.1980.Т.20, N 5.С.1105-1116.

45. Кононенко А.Ф., Халезов А.Д., Чумаков В.В. Принятие решений в условиях неопределенности. М.: ВЦ АН СССР, 1991. 197с.

46. Ларичев О.И. Емельянов СВ. Многокритериальные методы принятия решений, М. 1985.32 с.

47. Ларичев О.И. Объективные модели и субъективные решения. М.: Наука, 1987. 141 с.

48. Лоусон Е., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986.232 с.

49. Макаров И.М., Виноградская Т.М., Рубчинский А.А., Соколов В.Б. Теория выбора и принятия решений. М., 1982. 328 с.

50. Матросов В.Л., Горелик В.А., Жданов С.А., Муравьева О.В., Угольникова Б.З. Теоретические основы информатики. Учебное пособие. -М.: МПГУ, 2005. 420 с.

51. Многокритериальная оптимизация: математические аспекты / Березовский Б.А., Барышников Ю.М., Борзенко В.И., Кемпнер Л.М. М.: Наука, 1989.128 с.

52. Моисеев Н.Н., Кононенко А.Ф. Методы оптимизации. М.:МФТИ, 1972, 158 с.

53. Морозов В.В. Основы теории игр. М.: Изд-во МГУ, 2002. 150 с.

54. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высшая школа, 1986. 287 с.

55. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. М.: Физматлит, 2005.176 с.

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

57. Подиновский В.В. Многокритериальные задачи с однородными равноценными критериями // Ж. вычислительной математики и математической физики, 1975. № 2. С. 330-344.

58. Подиновский В.В. Система, использующая Информацию о Важности Критериев для Анализа альтернатив (СИВКА)// НТИ. Сер. 2.- 1998.- № 3.-С.52-57.

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

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

61. Прасолов В.В. Задачи и теоремы линейной алгебры. М.: Наука. Физ-матлит, 1996. 304 с.

62. Райфа X. Анализ решений: введение в проблему выбора в условиях неопределённости. М.: Физматлит, 1977. 407 с.

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

64. Саати Т., Керне К. Аналитическое планирование. Организация систем. М.: Радио и связь, 1991.224 с.

65. Салуквадзе М.Е., Киласония Н.А., Топчишвили A.JI Об одном классификационном подходе к методам многокритериальной оптимизации. Тбилиси: Институт систем управления АН Грузии, 1990. 18 с.

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

67. Тимохин С.Г., Шапкин А.В. О задачах линейного программирования в условиях неточных данных // Экономика и матем. методы, 1981. Т. 17. 5. С. 955-963.

68. Тихонов А.Н. О приближенных системах линейных алгебраических уравнений. // ЖВМиМФ, 1980. Т20. 6. С. 1373-1383.

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

70. Хорн Р, Джонсон У. Матричный анализ. М.: Мир, 1989. 655 с.

71. Штойер Р. Многокритериальная оптимизация: теория, вычисления, приложения М.: Наука, 1992. 504 с.

72. David Н.А. The method of Paired Comparisons. 2 nd ed., rev.- L.-N.: Griffin-Oxford Univ. Press, 1988. 636 p.

73. Monarchi D. E., Weber J.E., Duckstein L. An interactive multiple objectivedecision making aid using nonlinear goal programming // M. Zeleny (Ed.). Multiple criteria decision making. Berlin: Springer Verlag, 1976, p. 235-253.

74. Lemmerling P. Structured total least squares: analysis, algorithms and applications // PhD dissertation. Kattholieke Universiteit Leuven, Arenbergkasteel, Belgium, 1999,189 p.

75. Rosen J.B. Park H. Glick J. Total least norm problems: formulation and solution// illUMSI reserch report. Minniapolis(Mn) Univ. of Minnesota. Supercomput. inst.,1993, 93/223.18p.

76. Roy B. Multicriteria Methodology for Decision Aiding. Dordrecht: Kluwer Academic Pulieher, Vol. 48, №12,1997. p. 1257-1258.

77. Van Huffel S., Vandewale J. The Total Least Squares problems: Computational Aspects and Analysis. Philadelfia PA: SIAM Publishing, Vol. 35, №4,1993. p. 660-662.