21821

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

Лекция

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

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

Русский

2013-08-03

234 KB

57 чел.

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 один из критериев мы специальным образом выделяем.

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


 

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

58111. Инструктаж по техники безопасности. Электромонтажные материалы. Оказание первой помощи пострадавшему под воздействием электрического тока 65.5 KB
  Оказание первой помощи пострадавшему под воздействием электрического тока. Воздействие электрического тока на организм человека: При прохождении электрического тока через тело человека он оказывает следующие виды воздействия: механическое электролитическое термическое биологическое электрическое психологическое. Общее воздействие характеризуется воздействием различных величин электрического тока на организм человека. 1520мА сильные судороги по пути прохождения электрического тока в организме человека.
58112. Из истории появления компьютерных коммуникаций 26 KB
  Устный пересказ которым пользовались для передачи информации в дописьменный период опирался на такое ненадежное устройство хранения информации как человеческая память Второй информационной революцией по праву считают изобретение книгопечатания.
58113. История развития слесарного дела 23 KB
  Качество выполнения слесарных работ во многом зависит от слесарного инструмента и умения его правильно применять. Слесарномонтажный инструмент должен быть качественным и надежным а начинающему слесарю нужно прежде всего изучить инструмент которым ему придется пользоваться. При холодной ручной обработке металлов слесарь наиболее часто использует такой слесарномонтажный инструмент как молотки зубила ножовки напильники и др.
58114. Общество и общественные отношения 226 KB
  ОБЩЕСТВО - обособившееся от природы, но тесно с ней связанная часть мира, которая включает в себя способы взаимодействия людей и формы их объединений.
58115. Значение здоровья для человека 41 KB
  Цель: ознакомить с задачами и содержанием курса Основы здоровья; формировать представление о значении здоровья для обучения труда общения с родными; развивать память мотивацию основ сохранения и укрепления здоровья; воспитывать любовь к жизни к людям.
58116. Військові звання і знаки розрізнення. Начальники та підлеглі, старші та молодші, їх права і обовязки 182.5 KB
  Мета: Вивчити поняття щодо суті і значення військової дисципліни; Назвати статути Збройних сил України основні їх вимоги. Статути Збройних Сил України це зведення законів військової служби на основі яких проходять повсякденне життя виховання навчання бойова діяльність військ...
58118. Функции финансов, как экономической категории 15.22 KB
  Именно через эту функцию реализуется общественное назначение финансов – обеспечение каждого субъекта хозяйствования и государства необходимыми ресурсами, использ. в форме денежных фондов целевого назначения.
58119. Финансы как экономическая категория в системе социально-экономических категорий 15.17 KB
  Каждая наука оперирует определенным кругом понятий, имеет особые, специфические категории, которые являются концентрированным выражением общих, наиболее существенных признаков, качеств, закономерностей и взаимосвязей объектов той сферы