Главная страница
Навигация по странице:

  • Цель работы

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

  • Метод последовательных уступок

  • Практическая часть

  • Вопросы для самопроверки

  • Многокритериальный выбор. Метод последовательных уступок. Методические указания по выполнению лабораторной ра боты ЮгоЗап гос унт сост. В. В. Апальков, Р. А. Томакова


    Скачать 0.6 Mb.
    НазваниеМетодические указания по выполнению лабораторной ра боты ЮгоЗап гос унт сост. В. В. Апальков, Р. А. Томакова
    Дата16.05.2023
    Размер0.6 Mb.
    Формат файлаpdf
    Имя файлаМногокритериальный выбор. Метод последовательных уступок.pdf
    ТипМетодические указания
    #1134933


    УДК 519.816
    Составители: В.В. Апальков, Р.А. Томакова
    Рецензент
    Кандидат технических наук, доцент Е. И. Аникина
    Многокритериальный выбор. Метод последовательных
    уступок: методические указания по выполнению лабораторной ра- боты / Юго-Зап. гос. ун-т; сост.: В.В. Апальков, Р.А. Томакова. –
    Курск: ЮЗГУ, 2017. – 12 с. Библиогр.: с. 12.
    Излагается цель лабораторной работы, в теоретической части рассмат- риваются многокритериальная модель задачи принятия решений в услови- ях определенности, проблемы решения многокритериальных задач, метод последовательных уступок. В практической части приводятся пример выпол- нения задания на лабораторную работу и вопросы для самопроверки.
    Методические указания соответствуют требованиям рабочей програм- мы по направлению подготовки бакалавров 09.03.04 «Программная инжене- рия».
    Предназначены для студентов всех форм обучения направления подго- товки бакалавров 09.03.04 «Программная инженерия».
    Текст печатается в авторской редакции
    Подписано в печать
    Формат 60 84 1/16.
    Усл. печ. л. . Уч.- изд. л.
    . Тираж 25 экз. Заказ. Бесплатно.
    Юго-Западный государственный университет.
    305040, г. Курск, ул. 50 лет Октября, 94.

    Цель работы: изучить метод решения многокритериальных задач принятия решений (ЗПР) в условиях определенности – метод последовательных уступок.
    Теоретическая часть
    Многокритериальная модель задачи принятия решений в ус- ловиях определенности может быть представлена в виде:
    , , ,
    , , ,
    t A K X f P r
    , (1) где t – постановка задачи;
    A – множество допустимых альтернативных решений;
    K – множество критериев;
    X
    – множество шкал критериев;
    f – отображение множества допустимых решений в множество векторных оценок;
    P – система предпочтений ЛПР;
    r
    – решающее правило.
    Структурная схема процесса построения и выбора оптимального решения для многокритериальной задачи принятия решений представ- лена на рисунке 1.
    В реальных задачах, возникающих на практике, оценивание аль- тернативных решений осуществляется с помощью векторного крите- рия, компоненты которого являются не скалярами, а векторами.
    В зависимости от содержания условия в постановке задачи могут возникать требования определения, например, наиболее предпочтительного решения, либо полностью упорядоченного множества допустимых решений, либо выделения множества не- доминируемых решений и т.д.
    Множество A представляет собой совокупность альтернатив- ных решений, в каждой задаче удовлетворяющих определенным ограничениям и рассматриваемых как возможные способы дости- жения поставленной цели. Элементы множества A называются также допустимыми решениями, альтернативами, вариантами вы-
    бора.
    Множество допустимых альтернативных решений либо зада- ется, либо формируется в процессе исследования.
    Рассматриваемые варианты выбора могут характеризоваться различными признаками, которые выражаются критериями из мно- жества K .

    Рисунок 1 – Схема процесса выбора оптимального решения в мно- гокритериальной задаче принятия решений
    Тогда каждому решению
    i
    A
    ставится в соответствие n-мерная векторная оценка
    1
    ,
    ,
    (
    )
    i
    i
    in
    x
    х
    х , где
    ij
    x
    – оценка характеристики варианта
    i
    A
    по шкале
    j
    X
    критерия
    j
    K
    ,
    1,...,
    j
    n
    Совокупность векторных оценок свойств вариантов по шка-
    Полученное упорядочивание соответствует поставленной за- даче?
    Разработка оценочных шкал критериев
    Формирование множе- ства допустимых ре- шений
    Оценка допустимых решений по шкалам критериев
    Получение информа- ции о предпочтениях
    Построение решающе- го правила
    Упорядочивание до- пустимых решений
    Анализ результатов упорядочивания
    Постановка задачи
    Начало
    ?
    Конец
    Д
    а нет да
    лам критериев из множества X и образует множество допусти-
    мых решений.
    Качество варианта
    i
    A
    при наличии многих критериев пред- ставляется векторной функцией
    1
    ( ) (
    )
    ,
    ,
    i
    i
    i
    im
    y
    f x
    y
    y
    , где
    ( )
    ik
    k
    i
    y
    f x
    R
    – оценка варианта
    i
    A
    по частному критерию
    k
    f ,
    1,...,
    k
    m
    ;
    1
    ( ,...,
    )
    m
    f
    f
    f
    Совокупность векторных оценок вариантов образует множе-
    ство оценок качества решения, или множество достижимых це-
    лей.
    В теории принятия решений предполагается, что каждое
    ЛПР имеет некоторую свою систему предпочтений P , из которой он исходит при рациональных действиях.
    Под системой предпочтений ЛПР будем понимать совокуп- ность обычно неструктурированных его представлений, связанных с достоинствами и недостатками сравниваемых решений.
    В многокритериальной модели система предпочтений описы- вается совокупностью P некоторых множеств с соотношениями предпочтения (например, наборов критериев, интервалов между оценками допустимых решений определенного вида и т.п.).
    Решающее правило (метод принятия решения)
    r
    представляет собой принцип сравнения векторных оценок и вынесения сужде- ний о предпочтительности одних из них по отношению к другим.
    Оно может быть задано в виде аналитического выражения, алго-
    ритма или словесной формулировки.
    Например, из двух векторных оценок предпочтительнее та, которая имеет хотя бы одну максимальную компоненту и ни одной минимальной.
    Решающее правило должно приводить к такому упорядоче- нию множества допустимых решений, которое соответствует со- держательной постановке задачи и согласуется с принятыми в мо- дели допущениями и системой предпочтений ЛПР. К принимаемым допущениям относятся допущения о полноте множества решений и набора критериев, о соответствии множества шкал множеству кри- териев и т.п. В зависимости от принятых допущений, а также от це- лей и предпочтений ЛПР, могут быть построены различные ре- шающие правила.

    Проблемы, связанные с решением многокритериальных
    задач принятия решений
    При решении многокритериальных ЗПР возникает ряд специ- фических проблем, носящих не формальный (т. е. не вычислитель- ный), а концептуальный характер. Главная из них – рациональный выбор принципа оптимальности, определяющего свойства опти- мального решения и дающего ответ на вопрос – в каком смысле оп- тимальное решение лучше всех других решений (превосходит дру- гие решения).
    Принципиальное отличие многокритериальных задач приня- тия решений от однокритериальных детерминированных задач за- ключается в том, что для них имеется множество различных прин- ципов компромисса и соответствующих им принципов оптималь- ности, которые приводят к выбору различных оптимальных реше- ний. Это предъявляет серьезные требования к выбору принципа оп- тимальности.
    Рассмотрим основные проблемы, связанные с решением мно- гокритериальных задач принятия решений.
    Проблема 1выделение области компромисса. В многокрите- риальных задачах принятия решений имеются противоречия между некоторыми частными критериями, составляющими векторный критерий. Однако эти противоречия обычно является нестрогими, так как иначе задача становится конфликтной антагонистической. В силу этого множество допустимых решений
    A
    D
    распадается на две непересекающиеся части: область согласия
    C
    A
    D
    и область компро- мисса
    K
    A
    D
    . В области согласия
    C
    A
    D
    противоречий между частными критериями не возникает и качество решения может и должно быть улучшено одновременно по всем частным критериям или, во всяком случае, без снижения значений любого из них. В области компромисса
    K
    A
    D
    противоречия между некоторыми частными кри- териями имеются, при этом улучшение качества решения по одним частным критериям приводит к ухудшению качества решения по другим частным критериям.
    Все это дает основание утверждать, что оптимальное ре-
    шение может принадлежать только области компромисса, т. е.
    *
    K
    A
    A
    D

    В связи с этим утверждением, поиск оптимального решения надо ограничить только областью компромисса
    K
    A
    D
    . Отсюда воз- никает проблема 1 – выделение области компромисса
    K
    A
    D
    из мно- жества допустимых решений
    A
    D
    . Выделение области компромисса
    K
    A
    D
    обычно является первым этапом при решении многокритери- альных задач принятия решений. При этом следует отметить важ- ный практический результат – сужение области альтернативных вариантов решений, что уже само по себе улучшает качество при- нимаемых решений. В отдельных случаях поиск оптимальных ре- шений с приемлемой для практики точностью можно ограничить выделением области компромисса.
    Проблема 2выбор схемы компромисса и соответствующего
    ей принципа оптимальности. Поиск оптимальных решений в об- ласти компромисса может быть осуществлен только на основе не- которой выбранной схемы компромисса. Число возможных схем компромисса достаточно велико, поэтому обоснование и рацио- нальный выбор схемы компромисса представляет собой сложную концептуальную проблему.
    Рациональный выбор схемы компромисса соответствует рас- крытию смысла оператора оптимизации:
    *
    (
    )
    ( )
    A
    f A
    opt f A
    A D
    , (2) где
    *
    A
    – оптимальный вариант выбора,
    A
    D
    – множество допусти- мых решений, f – отображение множества допустимых решений в множество векторных оценок.
    Проблема 3 нормализация критериев. Эта проблема возни- кает в тех задачах, в которых частные критерии имеют различные единицы измерения. Для осуществления возможности оперирова- ния с векторными критериями необходимо нормализовать значения частных критериев, т. е. привести их к единому, безразмерному, масштабу измерения. К настоящему времени разработано большое число различных схем нормализации.
    Проблема 4 учет приоритета критериев. Частные крите- рии, составляющие векторный критерий, имеют различную важ- ность и значимость, что является основанием и позволяет упорядо- чить критерии. В связи с этим эта проблема сводится к рациональ- ному выбору схемы компромисса.

    Перечисленные проблемы являются наиболее важными и час- то встречающимися, но они не охватывают всего множества про- блем, связанных с решением многокритериальных задач принятия решений. Следует отметить, что рассмотренные проблемы 2 - 4 но- сят концептуальный характер, и при их реализации следует при- менять различные эвристические процедуры, основанные на науч- ной аргументации, в которых существенная роль принадлежит экс- пертам и консультантам.
    Перейдем от множества допустимых решений
    A
    D
    к множест- ву
    F
    D
    допустимых векторных оценок
    1
    ( ,...,
    )
    m
    f
    f
    f
    , задаваемых частными критериями
    k
    f ,
    1,...,
    k
    m
    Рассмотрим возможный принцип компромисса – принцип по- следовательных уступок.
    Метод последовательных уступок
    В основу метода последовательных уступок положено требо- вание расположения частных критериев по значимости. Предпола- гается, что все частные критерии, составляющие векторный крите- рий упорядочены по убыванию важности:
    1
    ,...,
    m
    f
    f
    . Будем также считать, что каждый из них нужно максимизировать.
    Процедура построения компромиссного решения сводится к следующему.
    Сначала находится решение, обращающее в максимум наибо- лее значимый частный критерий
    1
    f .
    Затем назначается, исходя из практических соображений и точности определения исходных данных, величина некоторой «ус- тупки»
    1
    f , которую ЛПР согласен сделать для того, чтобы обра- тить в максимум второй частный критерий
    2
    f .
    Налагаем на значение частного критерия
    1
    f ограничение, чтобы это значение было не меньше, чем
    1 1
    max –
    f
    f , и при этом ограничении находим решение, обращающее в максимум частный критерий
    2
    f .
    Аналогично назначается «уступка» для частного критерия
    2
    f , ценой которой можно максимизировать частный критерий
    3
    f
    , и так далее.

    Достоинство такого способа построения компромиссного ре- шения заключается в том, что известна цена «уступки» в одном по- казателе для приобретения выигрыша в другом. При этом важно отметить, что свобода выбора решения, приобретаемая ценой даже незначительных «уступок», может оказаться существенной, так как в районе максимума обычно эффективность решения меняется очень слабо.
    Практическая часть
    Рассмотрим применение метода последовательных уступок на примере двухкритериальной задачи принятия решений:
    1 1
    2
    ( ) 3
    max
    f x
    x
    x
    ,
    2 1
    2
    ( )
    7
    max
    f
    x
    x
    x
    , где
    1 2
    ( ,
    )
    x
    x x .
    Множество допустимых решений
    A
    D
    задается неравенствами:
    1 2
    2 4
    x
    x
    ,
    1 2
    10
    x
    x
    ,
    1 2
    ,
    0
    x x
    Пусть частные критерии, составляющие векторный критерий упорядочены по убыванию важности:
    1 2
    ,
    f f
    . Находим решение, об- ращающее в максимум наиболее значимый частный критерий
    1
    f .
    Первая задача имеет вид:
    1 1
    2
    ( ) 3
    max
    f x
    x
    x
    ,
    при ограничениях
    1 2
    2 4
    x
    x
    ,
    1 2
    10
    x
    x
    ,
    1 2
    ,
    0
    x x
    Найдем решение этой задачи геометрическим методом (рису- нок 2).
    Уравнение линии уровня функции
    1
    ( )
    f x
    имеет следующий вид:

    1 2
    3x
    x
    c
    , где
    c
    – const.
    Градиент функции
    1
    ( )
    f x
    – вектор
    1
    ( ) (3; 1)
    f x
    , показываю- щий направление наибольшего возрастания функции в точке
    x
    Максимум частного критерия
    1
    f достигается в вершине мно- гоугольника допустимых решений
    *
    (10;0)
    x
    . При этом
    *
    1
    (
    ) 30
    f x
    ,
    *
    2
    ( ) 10
    f x
    Рисунок 2 – Графическое решение первой задачи
    Назначим «уступку»
    1 6
    f
    (20% от максимального значения критерия
    1
    f ) и решим вторую задачу:
    2 1
    2
    ( )
    7
    max
    f
    x
    x
    x
    , при ограничениях
    1 2
    2 4
    x
    x
    ,
    1 2
    10
    x
    x
    ,
    1 2
    3 24
    x
    x
    ,
    1 2
    ,
    0
    x x

    Аналогично, геометрическим методом получим решение этой задачи (рисунок 3).
    Уравнение линии уровня функции
    2
    ( )
    f
    x
    имеет следующий вид:
    1 2
    7
    x
    x
    c
    , где
    c
    – const.
    Градиент функции
    2
    ( )
    f
    x
    – вектор
    2
    ( ) (1;7)
    f
    x
    Максимум частного критерия
    2
    f достигается в вершине мно- гоугольника допустимых решений
    **
    (8,5;1,5)
    x
    . При этом
    **
    2
    (
    ) 19
    f x
    ,
    **
    1
    (
    ) 24
    f x
    Рисунок 3 – Графическое решение второй задачи
    Отметим, что оптимальное решение последней задачи
    **
    (8,5;1,5)
    x
    принадлежит множеству Парето (
    точки отрезка, со- единяющего две вершины многоугольника допустимых решений первой задачи с координатами (0;10) и (10;0) ).

    Вопросы для самопроверки
    1. Многокритериальная модель ЗПР в условиях определен- ности.
    2. Множество допустимых решений.
    3. Множество достижимых целей.
    4. Система предпочтений ЛПР.
    5. Решающее правило.
    6. Проблемы, связанные с решением многокритериальных
    ЗПР.
    7. Область согласия.
    8. Область компромисса.
    9. Принцип последовательных уступок.
    Литература
    1.
    Лотов, В.А. Многокритериальные задачи принятия ре- шений [Текст]: учебное пособие / В.А. Лотов, И.И. Поспелова. – М:
    МАКС Пресс, 2008. – 197 с.
    2.
    Ногин, В.Д. Принятие решений в многокритериальной среде. Количественный подход / В.Д. Ногин. – 2-е изд., испр. и доп.
    – М.: ФИЗМАТЛИТ, 2005. –176 с.
    3. Петровский, А. Б. Теория принятия решений [Текст]: учеб- ник / А. Б. Петровский. – М.: Академия, 2009. – 400 с.
    4. Томакова, Р. А. Методы и алгоритмы теории принятия ре- шений [Текст]: учебное пособие / Р. А. Томакова, В. В. Апальков;
    Юго-Зап. гос. ун-т. – Курск: ЮЗГУ, 2015. – 164 с.
    5. Черноруцкий, И. Г. Методы принятия решений [Текст]: учебное пособие для студентов вузов / И. Г. Черноруцкий. – СПб.:
    БХВ-Петербург, 2005. – 416 с.


    написать администратору сайта