21821

ВЫБОР АЛЬТЕРНАТИВ В МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧАХ

Лекция

Менеджмент, консалтинг и предпринимательство

Выбор в условиях нескольких критериев. Например выбор конструкции самолета предполагает учет многих критериев технических высота скорость маневренность грузоподъемность безопасности полетов технологических экологических экономических эргономических. Итак пусть для оценивания альтернатив используется несколько критериев qix i= 123. Теоретически можно представить себе случай когда во множестве Х окажется одна альтернатива обладающая наибольшими значениями р всех критериев; она и является наилучшей.

Русский

2013-08-03

234 KB

56 чел.

PAGE  6


EMBED Word.Picture.8  

Рис.1

EMBED Word.Picture.8  

EMBED Word.Picture.8  

EMBED Word.Picture.8  

EMBED Word.Picture.8  

ТЕМА 6. Лекция 7.

ВЫБОР АЛЬТЕРНАТИВ В МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧАХ

  1.  Сведение многокритериальной задачи к однокритериальной
  2.  Условная максимизация
  3.  Поиск альтернативы с заданными свойствами
  4.  Нахождение множества Парето

Задача отыскания оптимального решения х*, соответствующего максимуму целевой функции часто оказывается сложной для решения. Метод решения определяется самим характером множества Х (размерностью вектора Х и типом, т.е. является ли множество конечным, континуальным или счетным), а также характером критерия: функционал или функция, какая именно (линейная, нелинейная и т.п.).

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

Итак, пусть для оценивания альтернатив используется несколько критериев qi(x), i= 1,2,3...,р. Теоретически можно представить себе случай, когда во множестве Х окажется одна альтернатива, обладающая наибольшими значениями р всех критериев; она и является наилучшей. Однако на практике такие случаи почти не встречаются, и возникает вопрос, как осуществлять выбор (например, на рис. 1 множеству Х соответствуют внутренние точки фигуры на плоскости значений двух критериев q1 и q2; оба критерия желательно максимизировать).

Существует несколько способов выбора альтернатив в условиях нескольких критериев. К ним, в частности, относятся такие как

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

условная максимизация

поиск альтернативы с заданными свойствами

нахождения множества Парето.

1. Сведение многокритериальной задачи к однокритериальной

Этот способ состоит в введении некоего суперкритерия, т.е. скалярной функции векторного аргумента и называется также линейной сверткой:

              q0(x)=q0(q1(x),q2(x),…qp(x))                                           (1)

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

                       q0(x) =                                                           (2)

                       1-q0(x) =                                               (3)

Коэффициенты Si обеспечивают, во-первых, безразмерность числа qi(x)/Si, так как частные критерии могут иметь различную размерность и тогда некоторые арифметические операции, например, сложение, могут не иметь смысла. Во-вторых, в необходимых случаях c их помощью выполняется условие нормировки. Коэффициенты  i,  i отражают относительный вклад частных критериев в суперкритерий, т.е. являются весовыми коэффициентами.

Если не требуется обеспечивать безразмерность, функция (2) записывается в более простом виде:

                        q0(x) =        (4)

Таким образом, задача сводится к максимизации суперкритерия:

x* = arg max q0(q1(x), q2(x),….qp(x)).     (5)

              xX

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

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

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

x* = arg max {min[],     (6)

              xX

что означает поиск вокруг направления   методом «подтягивания самого отстающего». Этот критерий называется также максиминным.

2. Условная максимизация

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

Задача выбора, таким образом, формулируется как задача нахождения условного экстремума основного критерия:

           x* = arg {max q1(x)|qi(x)=Ci},                                                            (7)

                             xX

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

             x* = arg {max q2(x)|q1(x)=C1},        

                               xX

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

На рис. 2  приведено  решение задачи

               x2* = arg {max q2(x)|q1(x) C1}.  

                             xX

Нетрудно увидеть, что здесь мы переходим к задаче математического программирования (линейного или нелинейного, в зависимости от вида q2(x)).

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

Пусть частные критерии упорядочены в порядке убывания их важности. Возьмем первый из них и найдем наилучшую по этому критерию альтернативу. Из рис. 2 видно, что если самым важным является критерий q2 наилучшая альтернатива - это х2*, если же самым важным является критерий q1, то    наилучшая альтернатива - х4. Затем определяется «уступка» qi, т.е. величина, на которую мы готовы уменьшить достигнутое значение самого важного критерия, чтобы за счет уступки попытаться увеличить значение следующего по важности критерия. На рисунке - альтернативы, полученные таким образом, изображены точками х3* и х5*.

3. Поиск альтернативы с заданными свойствами

Этот способ относится к случаю, когда значения частных критериев или их границы могут быть заданы, и задача состоит в  том, чтобы (одно из двух):

1) найти альтернативу, удовлетворяющую эти требованиям;

2) если установлено, что такая альтернатива на множестве Х отсутствует, найти в Х альтернативу,  которая подходит к поставленным целям более всего.

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

Удобство метода. Здесь возможно задавать желательные значения  критерия как точно, так и в виде верхних или нижних границ. Назначаемые таким образом значения  называют иногда «уровнями притязаний», а точка их пересечения в р-мерном  пространстве критериев - целью, опорной точкой, идеальной точкой. При этом важно отметить следующее:

поскольку уровни притязаний задаются без точного знания структуры множества Х в пространстве частных критериев, целевая точка может оказаться как внутри, так и вне Х. Это соответствует достижимой или недостижимой цели. На рис.3 приведены оба варианта - соответственно точки х1* и х2*.

Идея оптимизации состоит в том, чтобы, начав с определенной альтернативы, приближаться к х* по некоторой траектории в пространстве Х. Для этого вводится числовая мера близости между очередной альтернативой х и целью х*, т.е. между векторами q(x)=(q1(x),q2(x),….qp(x)) и    Количественно эта близость может быть описана по-разному, например, расстояния типа:

  S(q,) = mini(qi - )+p+1,                                               (9)

                      i

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

4. Нахождение множества Парето

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

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

Возникает вопрос, как можно провести сравнение и оценку отдельных альтернатив, т.е. провести композицию альтернатив. Для иллюстрации возможных подходов воспользуемся, как всегда, удобной графической интерпретацией критериального пространства при n = 2. Точками изобразим все имеющиеся альтернативы. Наилучшей альтернативой (рис. 5) будет та, что изображена точкой выше и правее других. Исключить все улучшаемые альтернативы, а также проверить  неулучшаемость альтернатив паретовского множества, можно следующим образом: из каждой точки–альтернативы провести лучи, параллельные положительному направлению обеих осей, и если в угле, образуемом этими лучами, оказываются другие точки, данная альтернативы отбрасывается. Нетрудно видеть, что если лучи проведены из точки, соответствующей неулучшаемой альтернативе, то в образованном углу других альтернатив нет (рис. 5а).

Следует иметь в виду, что этот подход годится для выпуклых множеств, однако множество Парето не всегда является выпуклым.

Примером множества Парето может служить диаграмма «грузоподъемность-дальность» для транспортных средств (рис.6).

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

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

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

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

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

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

                 fi(x)max, i=1,2,.......n.                                            

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

Однако, помимо критериев fi(х) в распоряжении проектировщика достаточно часто есть еще и некоторый общий критерий F(х). Иногда бывает возможно формализовать его, записать в явном виде. Например, таким критерием может быть стоимость проекта. В этом случае «исследователю операций» предоставляется возможность решить задачу до конца. Для этого достаточно определить вектор х, который дает решение задачи: F(x)  max при xPG(f1,f2,...fn), где PG(f1,f2,...fn) - множество Парето для функций f1,f2,...fn на множестве G допустимых векторов х. Например, в случае водохозяйственного комплекса множество G определяется таким распределением воды по объектам хi, при котором ее количество не превосходит притока Qi.

Важно отметить, что введение «общего» критерия F(x) и максимизация его значений на множестве Парето также является некоторой гипотезой, поскольку из совокупности критериев f1, f2,....,fn , F один из критериев мы специальным образом выделяем.

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


 

А также другие работы, которые могут Вас заинтересовать

15012. Алпамыс батыр дастанының зерттелуі 560 KB
  УДК 398.22 574 А 61 АЛПАМЫС БАТЫР ЖЫРЫНЫЊ ЗЕРТТЕЛУІ А. Аманбаева А. Мќашева Тараз мемлекеттік педагогикалыќ институты Тараз қ. Батырлар жыры ќазақ ауыз әдебиетінің өте ертеден келе жатқан күрделі саласының бірі. Батырлар жыры бір ғасырдың ғана жемісі емес.Ол...
15013. Алпамыс батыр жырын оқыту және тәрбие жұмыстары 42.5 KB
  ӘОЖ 373.371.83 АЛПАМЫС БАТЫР ЖЫРЫН ОҚЫТУ АРҚЫЛЫ ТӘРБИЕ ЖҰМЫСТАРЫНЫҢ ҚҰЗЫРЕТТІЛІГІН АРТТЫРУ З.Д. Көшімбетова Қ.А. Яссауи атындағы Халықаралық қазақтүрік университеті Тараз институты Тараз қ. Алпамыс батыр жыры қазақ халқының ауыз әдебиетіне жатады және жыр...
15014. Арқалық батыр жырының нұсқалары 230.5 KB
  Тақырыптың өзектілігі. Қазақ халқының кез келген халықтың эпикалық қазынасынан кем түспейтін телегей-теңіз мол, әрі көркемдігі кемел, танымдық-тағылымдық мәні зор жырларының басым көпшілігі, әлі де болса
15015. Асан Қайғы туралы аңыздар 176.5 KB
  Ұлттың рухы бейнеленген мұра халықтың асыл қазыналарының бірі екендігін тәуелсіздік мұраты жолында жаңа экономикалық және саяси-әлеуметтік реформаларды қарқынды...
15016. Ахмет Байтұрсынұлының Әдебиет танытқыш еңбегі ХХ ғасыр басындағы әдебиеттану ғылымының контексінде 190.5 KB
  ЖҰМЫСТЫҢ ЖАЛПЫ СИПАТТАМАСЫ Диссертациялық жұмыста ірі энциклопедист ғалым қазақ әдебиеттану ғылымындағы әдебиет теориясының негізін салушы Ахмет Байтұрсынұлының – сөз өнерінің теориялық сипаты жөніндегі тұжырымдары талқыланып отыр. Ол тұжырымдар ғалымның 1926 жыл
15017. БАУЫРЖАН МОМЫШҰЛЫ ШЫҒАРМАЛАРЫНДАҒЫ АБАЙ ДӘСТҮРІ 72 KB
  БАУЫРЖАН МОМЫШҰЛЫ ШЫҒАРМАЛАРЫНДАҒЫ АБАЙ ДӘСТҮРІ Даурбекова Ширинкуль Седазымқызы Б. Момышұлы атындағы №44 орта мектеп. Шымкент қаласы Туады ерлер ел үшін Өлмейді ісі мәңгілік Өшпейді абзал есімдер. Ұрпаққа жетіп м
15018. Балалар әдебиеті кейіпкерлерінің тілдік тұлғасы (Б.Соқпақбаев, М.Гумеров, М.Қабанбаевтың шығармалары бойынша) 191 KB
  КІРІСПЕ Жұмыстың өзектілігі. Қазақ балалар әдебиеті өз даму кезеңінде өзіндік тарихы бар сала. Балаларға арналған әдебиет ұлт тарихында сонау ауыз әдебиетінен бастау алып қазіргі кезеңге дейін өзінің тілдік стильдік жағынан мазмұны мен құрылымы жағынан үлкен б
15019. БАТЫРЛАР ЖЫРЫ МЕН «ШАҺНАМА» ДАСТАНЫНДАҒЫ ТАҚЫРЫП ҮНДЕСТІГІ 55 KB
  Батырлар жыры мен Шаһнама дастанындағы тақырып үндестігі Ж. Қ. Әбдібаева Қ.Жұбанов атындағы Ақтөбе мемлекеттік университеті Ақтөбе қ Көркемдік дамудыңәдеби процестің маңызды бір заңдылығыәдеби байланыстарәдебиет әлеміндегі тоғысулар мен қарымқатынаста
15020. Бауыржан Момышұлының артында қалған өсиет, нақыл, қанатты сөздер 94 KB
  Батырдан қалған өсиет Қазақтың Бауыржан Момышұлындай ұлы перзентін таныстырып жату артық. Ел оның ерлігін жазған кітаптарын біледі. Оның мірдің оғындай қанатты сөздері де халықтың аузында жүр. Сөйтсе де сол сөздерді жүйелеп беріп жинақтаса ол жаңа бір сипатқа еніп ...