Многокритериальные задачи. Метод альтернативных решений (стр. 1 из 3)
1. Постановка задачи
Необходимо разработать программное средство для поиска альтернативных решений для следующей задачи:
· многокритериальная задача
входные данные: количество критериев и решений; весовые значения, заданные напрямую, степень важности критериев, интервалы превосходства, цена перехода значения в соседний класс.
выходные данные: матрица согласия; матрица несогласия; ядро бинарного отношения.
программный альтернативный решение многокритериальный
2. Краткие теоретические сведения
Пусть задан набор числовых функций
, определенных на множестве возможных решений X. В зависимости от содержания задачи выбора эти функции именуют критериями оптимальности, критериями эффективности или целевыми функциями.Указанные выше числовые функции образуют векторный критерий
, который принимает значения в пространстве m-мерных векторов 
. Это пространство называют критериальным пространством или пространством оценок, а всякое значение 
именуют векторной оценкой возможного решения x. Все возможные векторные оценки образуют множество возможных оценок (возможных или допустимых векторов) 
Как правило, между множествами возможных решений X и соответствующим множеством векторов Y можно установить взаимно однозначное соответствие, т.е. каждому возможному решению поставить в соответствие определенный возможный вектор, и обратно – каждому возможному вектору сопоставить определенное возможное решение. В таких случаях выбор во множестве решений с математической точки зрения равносилен выбору во множестве векторов и все определения и результаты можно формулировать как в терминах решений, так и в терминах векторов, причем при желании всегда можно без труда осуществить переход от одной формы изложения к другой.
Задачу выбора, которая включает множество допустимых решений X и векторный критерий f, обычно называют многокритериальной задачей или задачей многокритериальной оптимизации.
Необходимо отметить, что формирование математической модели принятия решений (т.е. построение множества X и векторного критерия f ) нередко представляет собой сложный процесс, в котором тесно взаимодействуют специалисты двух сторон. А именно, представители конкретной области знаний, к которой относится исследуемая проблема, и специалисты по принятию решений (математики). С одной стороны, следует учесть все важнейшие черты и детали реальной задачи, а с другой, – построенная модель не должна оказаться чрезмерно сложной с тем, чтобы для ее исследования и решения можно было успешно применить разработанный к настоящему времени соответствующий математический аппарат. Именно поэтому этап построения математической модели в значительной степени зависит от опыта, интуиции и искусства исследователей обеих сторон. Его невозможно отождествить с простым формальным применением уже известных, хорошо описанных алгоритмов.
Здесь следует еще добавить, что любая задача выбора (в том числе и многокритериальная) тесно связана с конкретным ЛПР(лицо, принимающее решение). Уже на стадии формирования математической модели при построении множества возможных решений и векторного критерия дело не обходится без советов, рекомендаций и указаний ЛПР, тем более что векторный критерий как раз и служит. Принятие решения при многих критериях для выражения целей ЛПР. При этом ясно, что построить модель в точности соответствующую всем реальным обстоятельствам невозможно. Модель всегда является упрощением действительности. Важно добиться, чтобы она содержала те черты и детали, которые в наибольшей степени влияют на окончательный выбор наилучшего решения.
Рассмотрим два произвольных возможных решения
и 
. Для них имеет место один и только один из следующих трех случаев:1) справедливо соотношение
(ЛПР первое решение предпочитает второму),2) справедливо соотношение
(ЛПР второе решение предпочитает первому),3) не выполняется ни соотношение
, ни соотношение (ЛПР не может отдать предпочтение ни одному из указанных двух решений).Заметим, что четвертый случай, когда оба участвующих здесь соотношения
и выполняются, невозможен благодаря асимметричности отношения предпочтения 
В первом из указанных выше случаев, т.е. при выполнении соотношения
, говорят, что решение доминирует решение .Если же реализуется третий случай, то говорят, что решения
и не сравнимы по отношению предпочтения.3. Реализация программного средства
Среда разработки: VisualStudio2008 Язык программирования: C#
3.1 Проектирование
При проектировании программного средства будем использовать объектно-ориентированный подход. Список классов с кратким описанием:
1) Program.cs– это главное окно, служит для ввода данных, запуска работы алгоритма поиска парето-оптимальных решений, содержит методы для решения поставленной задачи.
2) Reader.cs– методы для загрузки данных из файла
3) Writer.cs– методы для сохранения данных в файл
3.2 Алгоритм поиска альтернативных решений
Шаг 1. Назначение весов. Назначаются положительные веса каждого из критериев
Шаг 2. Построение индекса согласия. Для каждой пары альтернатив jи kмножество критериев 
разбивается на три группы: 
, 
, 
Множество
включает те категории, по которым j-я альтернатива лучше k-й, множество 
, состоит из критериев, которым j-я альтернатива хуже k-й, а множество 
, состоит из тех критериев, по которым j-я и k-я альтернативы эквивалентны. Индекс согласия с тем , что альтернатива jлучше альтернативы kопределяется следующим образом:
,Где α – параметр, α
Шаг 3. Построение списка несогласия. Для каждой пары jи kиндекс несогласия с тем, что альтернатива jлучше альтернативы kопределяется по формуле:
Где интервал превосходства k-й альтернативы над j-й по i-му критерию определяет число последовательных переходов из класса в класс, которое необходимо осуществить для того, чтобы j-й вариант стал эквивалентен k-му по i-му критерию, умноженное на цену одного деления такого перехода. При этом требуется, чтобы величины
не превышали единицуШаг 4. Построение решающего правила. На основе чисел
и 
, определяемы ЛПР, на множестве альтернатив строится следующее бинарное отношение: j-я альтернтива признается лучше альтернативы k, при условии того, что 
. Сразу можно заметить, что при 
указанное бинарное отношение становится аналогом бинарного отношения Слейтера, поскольку в этом случае j-я альтернатива доминирует k-ю лишь тогда, когда 
, т.е. 
для всех 
. При 
могут возникнуть другие пары альтернатив, связанные введенным бинарным отношением.