Введение к работе
Актуальность темы. В настоящее время многокритериальные задачи представляют собой бурно развивающуюся область исследования операций.
На рубеже 70-80-х годов появились работы, в которых изучались вопросы, имеющие непосредственно связь с задачами многокритериальной оптимизации. К началу 80-х годов теория многокритериальной оптимизации получила в научных кругах статус самостоятельного, богатого идеями, методами и, в особенности, приложениями научного направления в рамках системного анализа и исследования операций.
Многокритериальным задачам посвящено значительное количество работ иностранных авторов (Райфа X., Кини Р.Л, Саати Т., Штойер Р. и др.). Параллельно с зарубежными исследованиями аналогичные работы проводились и в России (Емельянов СВ., Ларичев О.И., Гермейер Ю.Б., Жуковский В.И., Ногин В.Д., Подиновский В.В и др.).
Принятие решений при многих критериях представляет собой особый вид человеческой деятельности, по которым человек учитывает и сопоставляет различные (и часто противоречивые) качества объектов или событий при их сравнении или нахождении их общей ценности. Научное направление «многокритериальное принятие решений» направлено на изучение следующих вопросов: 1) как люди принимают решения; 2) как люди должны принимать решения; 3) как, на основе каких методов и технических средств можно помочь людям принимать лучшие решения.
В этой области работают различные группы специалистов: психологи разными способами осуществляют изучение того, как именно люди в лабораторных экспериментах и в реальном мире принимают разнообразные решения; математики и экономисты на основе ряда постулатов и теорем выводят правила рационального принятия решений; практики-консультанты (сотрудники консультативных организаций) помогают руководителям проводить рациональный анализ варианта решений и выбирать лучший вариант. При этом они часто используют ЭВМ, а результаты своей работы называют системами поддержки принятия решений. Многокритериальное принятие решений и исследование операций имеют одну весьма общую область практических приложений: целенаправленную человеческую деятельность. В этой области есть задачи, которые целесообразно решать традиционными методами исследования операций. Есть задачи, для которых успешно применяются подходы и методы принятия решений при многих критериях. Наряду с этим существуют «пограничные» проблемы, осознание которых важно для специалистов того или другого направления. Есть задачи, которые считают «своими» и специалисты по исследованию операций, и специалисты по принятию решений.
Анализ многих реальных практических проблем, с которыми сталкивались специалисты по исследованию операции, естественным образом привел к классу многокритериальных задач, где отсутствует информация, позволяющая объективно определить наилучшее решение.
Модель принятия решений при многих критериях принципиально отличается от традиционных моделей исследования операций по способам ее
4 построения. Важнейшей задачей аналитика (специалиста по проблемам принятия решений) является изучение системы предпочтений лица, принимающего решения (ЛПР) и построение решающих правил, отражающих эти предпочтения. Конечно, аналитик не может обойтись без изучения объективных параметров модели, без изучения организации, к которой принадлежит ЛПР, внешней среды.
В качестве лица, принимающего решения, в таких задачах рассматривается обычно руководитель, формулирующий задачу и несущий ответственность за ее решение.
Задача многокритериальной (векторной) оптимизации в исходной постановке задается объектом {X,W(x)}, где X - множество стратегий или альтернатив (подмножество произвольного пространства), W(x)- векторная функция (векторный критерий), заданная на X и задающая частичный порядок на X. Наиболее распространенным является порядок по Парето: xVx", если
Wipe4)tW(x") и W{xt)^W{xri) (в предположении требования максимизации каждой компоненты вектора W, неравенства и равенства понимаются в обычном для векторов смысле покомпонентно).
В такой постановке можно определить множество оптимальных по Парето стратегий или ядро такого предпочтения, а именно, Xй- оптимально по Парето, если не существует х', что х'>-х0, и множество Парето - образ множества
оптимальных стратегий в пространстве критериев W. Однако множество Парето, как правило, «велико», что затрудняет решение о конкретном выборе стратегии. Поэтому обычно предполагается, что существует некоторое предпочтение ЛПР >, задающее непосредственный порядок (возможно полный) на X. Это предпочтение задается не в явном виде (иначе проблема многокритериальности снимается), а косвенно в виде дополнительной информации, которую способно дать ЛПР. Естественное требование к этой информации, чтобы она не противоречила порядку по Парето и позволяла выделить из множества паретооптимальных стратегий «более узкое» подмножество (в идеале - одну точку).
При всем многообразии подходов к формализации задачи многокритериальной оптимизации условно можно выделить два основных направления. Первое основано на введении некоторой строгой математической процедуры выбора, связанной с вектором критериев W. Сюда относятся методы свертки критериев, идеальной точки, выделения главного критерия и перевода других в ограничения, пороговых значений и уступок, лексикографии, целевого программирования и т.д. Во всех этих методах присутствуют некоторые параметры (весовые коэффициенты, пороговые значения, порядок лексикографии, условные значения критериев, штрафы за отклонения, меры, расстояния и т.д.), которые должны быть назначены ЛПР, т.е. требуют от него дополнительной информации. Второе направление основано на непосредственном выявлении предпочтений ЛПР путем постановки ему «более простых» вопросов (нежели, например, назначение весовых коэффициентов). Это направление привело к появлению целого ряда эвристических процедур итеративного типа, реализованного в виде диалоговых человеко-машинных
5 процедур. Впрочем, в таких процедурах также присутствуют некоторые параметры (например, величина шага в релаксационных методах), которые назначаются весьма произвольно.
Оба направления продолжают интенсивно развиваться, пополняя арсенал подходов к формализации и решению задач многокритериальной оптимизации. Сейчас уже очевидно, что проблема векторной оптимизации является «плохо формализуемой», т.е. для нее в принципе не существует единого принципа оптимальности и «право на жизнь» имеют разные подходы и методы.
Разделение на два направления является, конечно, условным, т.к. процедуры получения дополнительной информации у ЛПР могут быть связаны с нахождением параметров в методах первого направления (например, весовых коэффициентов свертки или пороговых значений). При этом считается, что непосредственное задание этих параметров слишком сложно для ЛПР и приводит к противоречию (несогласованности информации) при ответах на соответствующие вопросы, поэтому следует задавать последовательно «простые» вопросы, постепенно уточняя значения параметров.
Нами предлагается несколько иной подход, в какой-то степени синтезирующий подходы обоих направлений и состоящий в следующем. Выбирается один из методов, относящийся к первому направлению. ЛПР предлагается дать информацию о необходимых параметрах метода (например, весовых коэффициентах или пороговых значениях), руководствуясь при этом тенденцией к максимальной полноте информации без требования ее непротиворечивости, а затем противоречивость (ярко проявляющаяся, например, в методе попарных сравнений) устраняется путем минимальной коррекции оценок ЛПР. Если найденное решение и, следовательно, скорректированные оценки ЛПР не устраивают, то на их основе оно может дать новые оценки и процедура повторяется. Здесь возникает аналогия с методами прогнозирования. Можно брать исходную информацию в минимальном объеме, достаточной для построения интерполяционной зависимости, но практически, как правило, надежнее использовать «избыточную» информацию, по которой можно построить только аппроксимирующую зависимость, что эквивалентно минимальной коррекции исходной информации в той или иной метрике (метод наименьших квадратов, обобщенный метод наименьших квадратов, равномерное приближение и другие). Такая обработка при достаточной избыточности информации позволяет исключить неточности измерений, внешнее воздействие (шумы) и т.п. Для многокритериальной оптимизации это означает нивелирование ошибок ЛПР, связанных с неточностью представлений о предпочтениях, недостаточной компетентностью, усталостью и т.п.
Данный подход к формализации и решению задач многокритериальной оптимизации на основе методов коррекции исходной информации позволяет взглянуть более широко на данную проблему. Обычно в задачах векторной оптимизации множество стратегий X считается фиксированным и все внимание уделяется построению на нем некоторого порядка. Однако объект {X, W(x)} представляет собой модель выбора на основе согласования некоторых возможностей X и потребностей W. На практике этого согласования можно достичь не только приведением потребностей к
возможностям (например, метод уступок при заданных пороговых значениях), но и подтягиванием возможностей к потребностям. Математически это выражается в коррекции ограничений, задающих множество X, или одновременной коррекции ограничений на значения стратегий хи значения критериев W. Подобная идея несколько в ином контексте и на совершенно других математических формулировках задач была высказана еще академиком В.М. Глушковым и названа системной оптимизацией.
Формально противоречивость информации ЛПР может быть представлена в виде несовместности соответствующих систем уравнений и неравенств. В последние годы методы коррекции несовместных систем и несобственных задач линейного программирования развивались весьма интенсивно -матричная коррекция, обобщенный метод наименьших квадратов (Ватолин А.А., Горелик В.А., Еремин И.И., Ерохин В.И., Матросов В.Л., Попов Л.Д., Rosen J.B., Vun Huffel S., Lemmerling P. и др.).
Наш подход подразумевает использование и развитие методов коррекции для формализации и решения задач векторной оптимизации (или шире -системной оптимизации).
Таким образом, важная проблема многокритериальности состоит в формализации задачи векторной оптимизации путем устранения противоречий при выявлении предпочтений ЛПР.
Основной целью работы является развитие подхода матричной коррекции к формализации и решению задач многокритериальной оптимизации.
Объектом исследования является теория многокритериальной оптимизации.
Предметом исследования - вопросы формализации и решения многокритериальных задач на основе методов обработки информации ЛПР.
В основу исследования положена следующая гипотеза: формализация многокритериальной задачи на основе методов минимальной коррекции исходных данных позволяет найти в некотором смысле оптимальное решение.
Для реализации поставленной цели и на основе сформулированной гипотезы потребовалось решить следующие задачи, включающие:
исследование проблемы построения единого критерия на классе линейных сверток в задаче многокритериальной оптимизации с использованием дополнительной информации о значениях критерия на конечной выборке стратегий;
постановку и решение задачи коррекции несовместных линейных систем с разреженными матрицами;
использование коррекции несовместных линейных систем с разреженной структурой для формализации и решения задач многокритериальной оптимизации;
исследование задачи коррекции данных многокритериальной задачи при использовании метода попарных сравнений и метода анализа иерархий;
7 задачу коррекции системы ограничений многокритериальной задачи с фиксированными пороговыми значениями, с изменением пороговых значений, с изменением матрицы коэффициентов критериев;
Методологическую основу работы составляют современные методы математической теории принятия решений, теории вероятностей, линейной алгебры, матричного анализа, математического анализа.
Научная новизна состоит в применении методов коррекции данных для формализации и решения задачи многокритериальной оптимизации:
получены методы решения задач коррекции системы ограничений и пороговых значений при использовании минимаксного и квадратичного критериев;
разработаны методы оптимальной коррекции несовместных систем с разреженными матрицами, которые позволяют применить данный подход для решения ряда многокритериальных задач;
получено решение задачи коррекции данных многокритериальной задачи при использовании метода попарных сравнений и метода анализа иерархий.
Практическая значимость работы заключается в том, что предложенные способы формализации и коррекции многокритериальных задач могут быть применены к различным прикладным задачам в сфере планирования и управления в различных видах деятельности. При построении математической модели векторной оптимизации можно дать более адекватное реальности описание и при этом получить разумные решения, возможно отличающиеся от классических, благодаря научно обоснованной возможности заменять исходную проблему скорректированной задачей.
Основные положения, выносимые на зашиту:
выбор весовых коэффициентов при формализации задачи многокритериальной оптимизации методом линейной свертки может быть основан на коррекции исходных данных о значениях критериев;
разработанные методы коррекции несовместных систем линейных алгебраических уравнений с разреженной структурой могут быть использованы для формализации и решения ряда многокритериальных задач, в частности, связанных с методом попарных сравнений и методом анализа иерархий;
задача коррекции системы ограничений и пороговых значений многокритериальной задачи при использовании квадратичного критерия аппроксимации сводится к безусловной задаче оптимизации, а при использовании минимаксного критерия - к последовательности задач ЛП.
8 Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях и семинарах:
Ежегодная научно-практическая конференция сотрудников БГУ Улан-Удэ, 2006 г. Институт математики и информатики БГУ.
Объединенный семинар Иркутского Института Динамики систем управления СО РАН, Бурятского центра информатизации Байкальского региона и Института математики и информатики БГУ, 2006.
Научно-методические семинары кафедры теории информатики и дискретной математики Mill У.
