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

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


 

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

1363. Температура и тепловое равновесие 154.5 KB
  Температура характеризует состояние теплового равновесия системы тел: все тела системы, находящиеся друг с другом в тепловом равновесии, имеют одну и ту же температуру.
1364. Анализ автоматизированных систем муниципального общеобразовательного учреждения Сигаевская средняя общеобразовательная школа № 58 142 KB
  Описание автоматизированных систем, используемых в управлении предприятием. Подбор материалов по всем пунктам дипломного задания с указанием первоисточников. Изучение прав и обязанностей, системного администратора, программиста.
1365. Строительство гостиницы на территории жилого района Западная поляна в городе Пенза. 123 KB
  Описание территории жилого района Западная поляна в городе Пенза. Основные принципы проектирования. Инженерное оборудование здания. Расчет количества мест в образовательных учреждениях района Западная поляна. Предварительный баланс территории функциональной зоны жилого района.
1366. Деятельность мирового суда. Судебный участок № 1 144 KB
  Мировой суд – это первичное (низшее звено) судебной системы (судов общей юрисдикции), рассматривающее в упрощенной процедуре незначительные гражданские, административные и уголовные дела.
1367. Карданная передача 120.5 KB
  Введение, виды, классификация, особенности конструкции. Кулачковый карданный шарнир. Неисправности карданной передачи, причины и способы их устранения. Технологический процесс технического обслуживания. Охрана труда и техника безопасности при проведении ТО и ремонта.
1368. Разработка программы на языке высокого уровня 130.5 KB
  Разработать программу на языке высокого уровня и блок-схему для вычисления арифметического выражения при заданных значениях исходных данных. Составить блок-схему алгоритма и программу для вычис-ления значения функции U, зависящей от нескольких аргументов, значения которых выбираются произвольно и задаются по вводу.
1369. Информационные системы в экономике. Информационные ресурсы 127.5 KB
  Экономическая информация. Информационные ресурсы. Структура автоматизированной информационной системы. Тенденции развития рынка информационных технологий. Информационные ресурсы - это совокупность данных, организованных для получения достоверной информации в самых разных областях знаний и практической деятельности. Отдельные документы и отдельные массивы документов в информационных системах.
1370. Экономике предприятия 120 KB
  Уставной капитал акционерного общества. Длительность технологического цикла партии деталей при последовательном виде движения. Коэффициент оборачиваемости. Производственная себестоимость
1371. Перечень тестовых вопросов для подготовки к государственному экзамену по дисциплине Базы данных и распределенные базы данных 127.5 KB
  Элементарные описания предметов, событий, действий, которые сохранены, классифицированы, но не организованы для передачи какого-либо специального содержания. Согласно какому из перечисленных SQL-предписаний будет выбрана запись со значением MARINA в поле Name таблицы Personal