Быстрый поиск

Контрольная работа: Многокритериальные задачи. Метод альтернативных решений

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

· многокритериальная задача

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

выходные данные: матрица согласия; матрица несогласия; ядро бинарного отношения.

программный альтернативный решение многокритериальный

2. Краткие теоретические сведения

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

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

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

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

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

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

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

1) справедливо соотношение (ЛПР первое решение предпочитает второму),

2) справедливо соотношение (ЛПР второе решение предпочитает первому),

3) не выполняется ни соотношение , ни соотношение (ЛПР не может отдать предпочтение ни одному из указанных двух решений).

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

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

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

3. Реализация программного средства

Среда разработки: Visual Studio 2008 Язык программирования: 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-ю лишь тогда, когда , т.е. для всех . При могут возникнуть другие пары альтернатив, связанные введенным бинарным отношением.

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