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

Определим формально условие эффективности решения по Парето.

Пусть имеем множество альтернатив X, для каждого элемента xÎX которого определен вектор критериев .

Пусть критерии ui(х) и альтернативы x,yÎX обладают следующим свойством:

ui(х)³ ui(y), i=1,…,n; u(x) ≠ u(y) Þ x f y,

т.е. решение x предпочтительнее решения y всякий раз, когда значения всех критериев для альтернативы x не меньше, чем для y. В этом случае говорят, что решение x доми­нирует над решением y.

Если для некоторого решения xÎX не существует решения yÎX, такого что , то решение x называется эффективным на множестве X, а множество всех эффек­тивных решений – множеством Парето или эффективной границей мно­жества X.

Из данного определения следует, что если решение x не является эффективным, то для него в множестве Парето найдется решение y, доминирующее над x. Поэтому луч­шее среди решений из X будет принадлежать множеству Парето при любых (разумных) предпочтениях ЛПР. Это в свою очередь позволяет при решении оптимизационных задач иссле­довать не все множество X, а лишь его эффективную границу.

Нахождение множества Парето – самостоятельная, иногда дово­льно сложная задача, для решения которой имеются многочисленные методы. Простейший из них основан на следующем резуль­тате [20].

Теорема 2.1. Пусть множество векторных оценок U решений из X строго выпукло, ограничено и замкнуто. Для того чтобы решение x*ÎX было эффективным, необходимо и достаточно, чтобы существовали такие неотрицательные коэффициенты , для которых для любого другого решения xÎX.

Множество векторных оценок U строится путем отображе­ния множества сравниваемых альтернатив X из пространства альтернатив X* в пространство критериев , где Ui ( i = 1,…,n ) – множество возможных для альтернатив из X значений i-го крите­рия. Ограниченность и замкнутость множества U гарантирует существование эффективных решений, а условие необходимо для того, чтобы исключить из рассмотрения тривиальный случай .

, где К – константа.

По мере увеличения значения К прямая бу­дет перемещаться вверх параллельно самой себе, пока не превратится в касательную A* к границе множества U в точке u*. Соответствующее этой точке решение x* согласно теореме будет эффективным.

Изменяя значения коэффициентов α1 и α2 легко найти и другие эффективные точки. В результате будет найдено множество Парето, выделенное на рис. 3-9 жирной линией. Граничные точки мно­жества Парето определяются перемещением прямых, для которых α1=0, α2=1 (точка B) и α1=1, α2=0 (точка С).

Рассмотрим теперь случай, когда множество U не является выпуклым (рис.3-10). Тогда для точки u*, лежащей на границе множе­ства U, нельзя подобрать коэффициенты α1 и α2, при которых выполняется условие теоремы 2.1. Тем не менее северо-восточный угол Y(u*) с вершиной в точке u* не содержит точек из U (кроме точки u*) и, следовательно, решение u* является эффективным. Условие, позволяющее находить эффективные решения для невыпуклых множеств U, получено Гермейером [7].

Теорема 2.2. Пусть множество Парето ограничено и замкнуто, a ui(x) > 0 для всех i=1,…,n для всех xÎX. Для того чтобы решение x* было эффективным, необходимо и дос­таточно, чтобы существовали строго положительные коэффициенты

, удовлетворяющие условию

, для всех xÎX, причем равенство имеет место тогда и только тогда, когда ui(x*) = ui(x) для всех i=1,..,n.

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

Пример 3-9. Пусть X представлено двумерной областью, удовле­творяющей неравенствам

а каждое решение xÎX оценивается по критериям .

В X выберем решение x*=(0,2; 0,5). Если x* является эффективным решением, то из теоремы 2.2 имеем

для всех xÎX.

Неизвестные коэффициенты α1 и α2 можно оп­ределить, решив систему уравнений

.

Поскольку u1(x*)=1,2, u2(x*)=0,9, то из системы имеем α1 = 0,43, α2=0,57. Уравнение

задает прямую A (рис.3-11), проходящую через начало координат и точку x* . Если x* лежит на границе множества X, то наше предположение верно и x* – эффективное решение. В против­ном случае эффективное решение , доминирующее над x*, найдем, двигаясь по прямой А до пересечения с границей множе­ства X.

Чтобы найти достаточно определить

при условии выполнения ограничений

.

В общем случае для этого требуется решить соответствующую задачу линейного про­граммирования. В данном примере = (0,3; 0,7) легко опреде­лить непосредственно из рис. 3-11.

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

Следуя [10] опишем один из простейших алгоритмов приближенного на хождения множества Парето. Алгоритм содержит следующие шаги.

1. В пространстве критериев с по­мощью случайной последовательности генерируются пробные точки . Если соот­ветствующее вектору u(x) решение x принадлежит множеству X, то u(x)ÎU. Множество таких точек обозначим через D.

2. Выбирается произвольный вектор uⁱ и сравнивается со всеми остальными векторами из D. Все векторы u^j такие, что uⁱ u^j, исключаются из множества D.

3. Шаг 2 повторяется до тех пор, пока в D не окажутся только векторы, не доминирующие друг над другом. Соединив остав­шиеся в D точки (рис.3-12), получим ломаную, являющуюся приб­лижением к множеству Парето, показанному жирной линией.

С увеличением числа точек, генерируемых в D на шаге 1, ломаная, построенная на шаге 3, будет приближаться к точной эф­фективной границе.

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

Очевидным недостатком данного алгоритма является необходимость генерировать пробные точки во всем пространстве U*. Это представляется излишним и существенно увеличивает трудоемкость шага 2. Чтобы сократить объем вычислений, производимых на этом шаге, модифицируем процедуру построения множества пробных точек следующим образом.

1. С помощью случайной последовательности в (n-1)-мерном простра­нстве генерируется точка , не содержащая n-й компоненты.

2. Значение n-го критерия un(x) полагается равным и формиру­ется начальная пробная точка .

3. Если точке u(х) соответствует решение xÎX, то она включается в множество D. В противном случае значение n-го критерия в u(x) уменьшается с некоторым шагом h до тех пор, пока условие xÎX не окажется выполненным. Полученная таким образом пробная точка включается в множе­ство D.

При таком способе построения множества D пробные точки как бы опускаются вдоль n-ой координаты пространства крите­риев U* на границу множества U(рис.3-13).

Поэтому в множество D включаются только точки, приближенно описывающие эту границу. Из 6 точек, составляющих согласно рис.3-13 множество в множество Парето войдут только U¹,U²,U³,U⁴.

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

3.4.Подход исследования операций

Модели, связанные с принятием решений, активно исполь­зуются в исследовании операций. Исследование операций — сложившаяся научная дисциплина, хорошо известная в совре­менном мире. Как определяет Е.С. Вентцель [1], под исследо­ванием операций понимают применение математических, ко­личественных методов для обоснования решений во всех облас­тях целенаправленной человеческой деятельности.

Основными этапами решения любой задачи в исследовании операций являются:

1) построение модели;

2) выбор критерия оптимальности;

3) нахождение оптимального решения.

Для подхода исследования операций характерны следую­щие особенности.

1. Используемые модели носят объективный характер. Построение моделей рассматривается в рамках исследования операций как средство отражения объективно существующей реальности. Когда модель, правильно отражающая действи­тельность, найдена, критерий оптимальности установлен, оп­тимальное решение может быть получено единственно возмож­ным образом. «Другими словами, опираясь на одни и те же данные, различные специалисты-аналитики должны получать одинаковые результаты» [2]. Это требование, предложенное Г. Вагнером, весьма примечательно. Оно определяет, что дея­тельность людей, описываемая моделью, подчинена требовани­ям целесообразности.

2. Существует объективный критерий успехов в примене­нии методов исследования операций. Если проблема, требующая решения, ясна и критерий определен, то аналитический метод сразу показывает, насколько новое решение лучше старого. Оп­тимальное решение проблемы бессмысленно оспаривать.

Опишем две классические задачи исследования операций.

Первая из них получила название обобщенной транспорт­ной задачи [2]. Пусть имеется большая авиакомпания, перево­зящая пассажиров по различным маршрутам. Руководство компании определяет, какие самолеты (по вместительности) и сколько самолетов должны обслуживать различные маршруты. Считается, что известны потоки пассажиров между разными городами и общее число имеющихся самолетов различного ти­па. Требуется распределить самолеты по маршрутам так, чтобы минимизировать расходы на их обслуживание.

Вторая задача получила название задачи о назначениях. Предполагается, что необходимо распределить заданное число работ среди исполнителей так, чтобы каждый исполнитель вы­полнял одну работу. Стоимость выполнения каждой из работ каждым исполнителем известна. Нужно распределить работы так, чтобы суммарная стоимость их выполнения была мини­мальной.

Словесному описанию этих двух задач соответствует четкое математическое описание [2], представляющее собой математи­ческую модель.

Дата добавления: 2015-07-26; просмотров: 681; Нарушение авторских прав

Мы поможем в написании ваших работ!