WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 12 |

3.1.4. Пример (задача о выборе наилучшего проектного решения) Предположим, что для участия в конкурсе представлено пять вариантов строительства предприятий различного типа (это могут быть машиностроительный завод, текстильная фабрика, молочный завод и т.п.) на территории, непосредственно прилегающей к жилому району. Оценивание качества проекта производится по четырем критериям: f1 – стоимость реализации проекта, f2 – величина прибыли проектируемого предприятия, f3 – величина экологического ущерба от строительства и f4 – заинтересованность жителей района в строительстве данного предприятия. Для простоты будем считать, что для оценки всех критериев была использована пятибалльная шкала в 1, 2, 3, 4 и 5 баллов. Поскольку первый и третий критерии желательно минимизировать, а не максимизировать как остальные, то вместо них введем и будем использовать критерии f1 = 5 - f1 и f3 = 5 - f3, подлежащие максимизации.

Принятие решения при многих критериях Число критериев m = 4. Обозначим множество из пяти возможных векторов (оценок) соответствующих проектов через Y = {y(1), y(2),..., y(5)} и допустим, что в результате экспертизы проектов были получены результаты, представленные в табл. 1.1.

Табл. 1.1.

Первый Второй Третий Четвертый критерий критерий критерий критерий 434 y(1) 533 y(2) 242 y(3) 532 y(4) 343 y(5) В соответствии с описанным выше алгоритмом полагаем P(Y ) =Y и начинаем сравнивать первый вектор с остальными. Нетрудно заметить, что все пары y(1), y(2) ; y(1), y(3) ; y(1), y(4) ; y(1), y(5) оказываются несравнимыми по отношению.

Далее сравниваем вектор y(2) с векторами y(3), y(4), y(5). Пара y(2), y(3) не сравнима по отношению. Поскольку y(2) y(4), вектор y(4) удаляем из множества P(Y ). Оставшаяся пара векторов y(2), y(5) не сравнима по отношению.

Теперь сравниваем вектор y(3). Поскольку y(5) y(3), то вектор y(3) удаляется из P(Y ). Так как вектор y(4) был удален как доминируемый, то для сравнения остается один вектор y(5). Поскольку он остался один, то его уже не с чем сравнивать. Следовательно, P(Y ) = {y(1), y(2), y(5)}.

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

Свойства множества Парето 3.2. Задачи с бесконечным множеством возможных векторов 3.2.1. Отыскание множества парето-оптимальных векторов Построение множества Парето в задачах с бесконечным множеством возможных векторов оказывается значительно сложнее, чем аналогичная задача в случае конечного множества. Какого-либо универсального метода (алгоритма) для решения этой задачи не существует. Исключение составляют различного рода специальные задачи, рассмотреть которые здесь не представляется возможным.

Отметим лишь простейший случай, когда критериев всего лишь два, т.е.

m = 2. Тогда множество возможных векторов представляет собой некоторое множество точек плоскости, а множество Парето обычно образует «северовосточную» часть границы этого множества. Так, на рис. 3.3 изображено множество возможных решений, имеющее вид невыпуклой фигуры. Здесь множество Парето образует дуга AB (без точки B) и отдельно взятая точка C.

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

Рис. 3.3. Геометрия парето-оптимальных векторов.

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

Формулируемый ниже результат можно рассматривать как обобщение на случай векторного критерия известной из курса математического анализа теоремы Вейерштрасса о том, что непрерывная функция нескольких переменных всегда достигает своего максимального значения на непустом компактном6 множестве.

Теорема 3.2 (в терминах решений). Предположим, что непустое множество возможных решений X представляет собой некоторое компактное подмножество пространства Rn, т.е. X Rn. Если компоненты векторного критерия f являются непрерывными функциями на множестве X, то множество Парето (как решений, так и векторов) не пусто.

Рассмотрим сумму всех компонент векторного критерия, т.е. числоm вую функцию F(x) = fi (x). Она будет непрерывной на множестве X i=как сумма непрерывных функций. Согласно упомянутой выше теоремы Вейерштрасса из курса математического анализа эта функция достигает своего максимального значения на множестве X. Обозначим указанную точку максимума через x* X :

F(x*) F(x) для всех x X. (3.1) Точка x* является парето-оптимальной, а значит множество Парето не пусто. Действительно, если это не так, то должна найтись точка x X, для которой верно векторное неравенство f(x) f (x*). Почленно суммируя компоненты векторов в обеих частях этого неравенства, придем к строгому неравенству F(x) > F(x*), которое не совместимо (3.1) Формально положим в последней теореме X =Y и fi (x) = yi, i = 12,...,m.

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



Теорема 3.2 (в терминах векторов). Предположим, что непустое множество возможных векторов Y является компактным подмножеством пространства Rn. Тогда множество парето-оптимальных векторов не пусто.

Напоминаем, что компактным называется замкнутое и ограниченное множество.

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

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

Теорема 3.3 (достаточное условие парето-оптимальности). Пусть m = (m1,m2,...,mm ) – произвольный вектор с положительными компонентами в сумме составляющими единицу, т.е.

m mi > 0, i = 12,...,m, = 1.

, m i i=Тогда всякая точка максимума на множестве X аддитивной свертки Fm критериев, определяемой равенством m Fm (x) = fi (x), (3.2) m i i=является парето-оптимальной.

Обозначим через x* X произвольную точку максимума функции Fm на множестве X. Таким образом, Fm (x*) Fm (x) для всех x X. (3.3) Установим парето-оптимальность точки x*. Для доказательства предположим противное: существует такая точка x X, что имеет место векторное неравенство f(x) f (x*). Покомпонентно последнее неравенство можно переписать в виде f1(x) f1(x*), f2(x) f2(x*), ……………….

fm (x) fm (x*), Принятие решения при многих критериях где хотя бы одно из неравенств – строгое. Умножим первое из приведенных неравенств на число m1, второе – на число m2 и т.д. последнее – на mm. Так как все числа mi положительны, то после выполнения указанной операции умножения смысл знаков неравенств не нарушится. Далее, почленно складывая все образованные неравенства, придем к неравенству Fm (x) > Fm (x*), которое не совместимо с (3.3). Полученное противоречие свидетельствует о том, что на самом деле x* Pf (X) Прежде чем формулировать следующий результат, напомним два определения. Множество X, X Rn, называют выпуклым, если оно вместе с каждой парой своих точек содержит и весь отрезок, соединяющий эти точки. Иными словами, множество X выпукло, если для любых точек x, x X и для любого числа l[0,1] выполнено включение l x + (1- l)x X. Очевидно, само пространство Rn является выпуклым множеством. Простым примером выпуклого множества может служить многомерный параллелепипед, который задается системой неравенств ai xi bi, i = 12,...,n, где все ai и bi, – фиксированные числа.

Числовую функцию g(x), заданную на выпуклом множестве X, X Rn, называют вогнутой, если для любых точек x, x X и для любого числа l[0,1] выполняется неравенство g(l x + (1- l)x) l g(x) + (1- l)g(x). Нетрудно проверить (см. ниже упр. 1), что, например, линейная функция g(x1, x2,..., xn ) = c1x1 + c2x2 +... + cn xn является вогнутой на всем пространстве Rn.

Теорема 3.4 (необходимое условие парето-оптимальности в форме аддитивной свертки критериев). Пусть множество X выпукло и все компоненты вектор-функции f вогнуты на нем. Для любой парето-оптимальной точки x* Pf (X) существует такой вектор m = (m1,m2,...,mm ) с компонентами, обладающими свойством m mi 0, i = 12,...,m, = 1, (3.4), m i i=что аддитивная свертка Fm (x) вида (3.2) в точке x* достигает своего максимума на множестве X.

Доказательство этой теоремы можно найти в [18].

Согласно теоремам 3.3 и 3.4 отыскание множества парето-оптимальных точек при определенных условиях сводится к задаче максимизации аддитивной свертки Fm (x) на множестве X. Иначе говоря, варьируя вектор m в указанных границах и решая соответствующие задачи максимизации аддитивной свертки, в принципе можно построить все множество точек Парето. Такой прием носит название скаляризации многокритериальной задачи и состоит он в сведении многокритериальной задачи к семейству Свойства множества Парето обычных (скалярных) экстремальных задач. Сложность реализации этого приема состоит в том, что возможных значений для вектора m бесконечное число, и перебрать их все невозможно. Поэтому здесь можно говорить лишь о принципиальном свед которое реализовать на практике не просто.

ении, И еще одно обстоятельство, на которое следует обратить внимание. В теореме 3.3 вектор m имеет строго положительные компоненты, в сумме дающие единицу, а в теореме 3.4 эти компоненты лишь неотрицательны, а значит, в необходимом условии некоторые из них могут принимать нулевые значения.

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





Пример 3.1. Пусть X = {(x1, x2) R2 | (x1)2 + (x2)2 1} (см. рис. 3.4) и f1(x) = x1, f2(x) = x2. Множество возможных решений X представляет собой круг единичного радиуса с центром в начале координат (рис. 3.4) Здесь множество X выпукло, а критерии линейны. Парето-оптимальными являются все точки окружности, расположенные в первой четверти.

Каждую из этих точек (кроме (0,1) и (1,0)) можно получить в результате максимизации аддитивной свертки Fm (x) = m1x1 + m2x2 на множестве X с положительными коэффициентами m1,m2 в сумме, составляющей единицу.

В то же время точки (0,1) и (1,0) невозможно получить в результате максимизации аддитивной свертки со строго положительными коэффициентами. Эти точки являются итогом максимизации линейной свертки Fm лишь с парами коэффициентов m1 = 0, m2 = 1 и m1 = 1, m2 = 0 соответственно.

Рис. 3.4. Множество возможных векторов X.

Принятие решения при многих критериях Один из самых распространенных подходов к решению практических многокритериальных задач – метод аддитивной (линейной) свертки критериев – заключается в назначении из тех или иных соображений величин коэффициентов m1,m2,...,mm аддитивной свертки Fm и последующей ее максимизации на множестве возможных решений X. При этом необходимо отметить, что такой подход не всегда является обоснованным. Существуют примеры, показывающие, что его применение в некоторых задачах может приводить к далеко не лучшим результатам.

3.3. Шкалы критериев и инвариантность множества Парето 3.3.1. Количественные шкалы Когда речь идет о той или иной прикладной многокритериальной задаче, значения критериев f1, f2,..., fm представляют собой результаты измерения в некоторой шкале. Например, если рассматриваемый критерий выражает стоимость проекта, прибыль или затраты, то все эти величины могут быть выражены в рублях, миллионах рублей, долларах, евро или каких-то других денежных единицах. При измерении длин предметов результаты, как известно, получают в метрах, дюймах, футах, ярдах и т.п. Для указания временного промежутка используют часы, секунды, годы, миллионы лет и т.д. Таким образом, при решении конкретных прикладных задачи значения критериев измеряются в пределах той или иной шкалы и выражаются в определенных единицах измерения.

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

При измерении, например, такой физической характеристики, как масса предмета, используют различные единицы измерения. Известно, что масса предмета может быть выражена в килограммах, фунтах, тоннах, пудах и т.д. Здесь фиксированным для всех измеряющих оказывается лишь начало отсчета – нуль, который соответствует отсутствию какой-либо массы, тогда как единица измерения может оказаться различной для разных измеряющих. Точнее говоря, результаты измерений yi и yi массы одного и того же объекта для двух различных измеряющих, пользующихся разными единица измерений, могут отличаться на некоторый фиксированный положительный Свойства множества Парето множитель ai, т.е. они связаны соотношением yi = ai yi. В этом случае говорят, что результаты измерений определяются с точностью до преобразования вида fi (yi ) = ai yi, где ai > 0. Шкала такого типа называется шкалой отношений. Название этой шкалы связано с тем, что при измерении в этой шкале независимо от единицы измерения отношения измерений будут одинаковыми для различных измеряющих. Действительно, пусть один измеряющий для двух объектов получил два числа yi и yi, а другой для тех же объектов – yi и yi соответственно. Поскольку yi = ai yi и yi= ai yi при некотором положительном ai, то выполняются равенства yi a yi yi i = =, yi a yi yi i которые и означают сохранение отношений измерений для различных измеряющих в шкале отношений. Таким образом, если какой-то измеряющий пришел к выводу, что, например, масса одного предмета в два раза больше массы другого предмета, то и другой измеряющий (использующий другие единицы измерения) должен прийти к тому же самому выводу. Это свидетельствует о том, что, при сравнении результатов измерения в шкале отношений, высказывание «во столько-то раз больше (меньше)» является осмысленным.

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

Шкалой разностей называется такая шкала, в которой результаты измерений определяются с точностью до преобразования fi (yi ) = yi + ci, где ci – фиксированное число. Измерения в этой шкале характеризуются сохранением разностей между двумя разными измерениями, выполненными различными измеряющими. Другими словами, для измерений, выполненных в шкале разностей, осмысленным является высказывание «на столько-то больше (меньше)».

Шкалой интервалов называется шкала, в которой результаты измерений определяются с точностью до линейного положительного преобразования вида fi (yi ) = a yi + ci, где ai > 0 и ci – фиксированные числа. Типичным i примером такой шкалы может служить шкала температур. Для измерения температуры существуют, например, шкалы Цельсия и Фаренгейта. Переход от результатов измерений в одной шкале к результатам в другой происходит как раз по формулам вида yi = ai yi + ci.

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 12 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.