Файл: Численные методы получения множеств Парето.pdf

Рис. 5. Примеры КК (компромиссная кривая выделена красным цветом)

1.3 Расчёт компромиссных кривых

Аналитический подход. Если функции F1(X) и F2(X) дифференцируемы, то можно попытаться найти геометрическое место точек соприкосновения поверхностей уровня F1(X)=b1 и F2(X)=b2. В таких точках gradF1=-λgradF2, 0≤ λ< ∞.

Последнее векторное уравнение равносильно n скалярным алгебраическим уравнениям которые определяет кривую в пространстве параметров x1=ϕ1(λ), ..., xn=ϕn(λ). Если участок этой кривой, на котором λ≥0 принадлежит множеству D, то он принадлежит и множеству P (P - множество Парето). Участок КК в этом случае определяется параметрическими уравнениями:

F1=F1(ϕ1(λ), ..., ϕn(λ)),

F2=F1(ϕ1(λ), ..., ϕn(λ)), λ≥0.

Пример 1. В квадрате D={-1≤ x1 ≤ 1, -1≤ x2 ≤ 1} заданы два критерия

которые желательно минимизировать.

1. Находим минимумы функций F1 и F2 . Абсолютные минимумы находятся в точках (0,0) и (-1,1) и принадлежат области D.

2. Находим частные производные

составляем систему уравнений

4x1=-λ (x1+1)

x2=-λ (x2-1).

Отсюда получаем параметрическое уравнение кривой в пространстве параметров

В данном случае можно получить уравнение этой кривой в декартовых прямоугольных координатах. Для этого решаем эти уравнения относительно параметра λ. Получим

Приравнивая правые части и разрешая относительно x2, получим уравнение паретовской кривой P: .

Параметрическое уравнение КК будет иметь следующий вид

F1(λ)=

F2(λ)=.

Закономерность КК: F1 возрастает от 0 до 5, а F2 убывает от 2 до 0.

Построим графики паретовских кривых в области D и пространстве критериев (рис. 6 и 7).

Рис. 6. Область D и множество P Рис. 7. Компромиссная кривая

Пример 2. В области D={-0.5 ≤ x1 ≤ 0.5, 0 ≤ x2 ≤ 1} заданы два критерия

которые нужно минимизировать с учетом функциональных ограничений ⎥x2-x1-0.375⎥ ≥ 0.125.

---

а) рассмотрим сначала случай без функциональных ограничений

1. Находим минимумы функций F1 и F2. Абсолютные минимумы находятся в точках X1opt=(0,0) и X2opt=(-1,1) и первая точка принадлежат D, а вторая нет. Находим условный минимум для функции F2: X2услов=(-0.5, 1); находим значения F2(-0.5,1)=0.25, F1(-0.5,1)=4.25.

2. Находим частные производные

составляем систему уравнений

2x1=-λ (x1+1),

8x2=-λ (x2-1).

Отсюда получаем параметрическое уравнение кривой в пространстве параметров

В данном случае можно получить уравнение этой кривой в декартовых прямоугольных координатах. Для этого решаем эти уравнения относительно параметра λ. Получим

Приравнивая правые части и разрешая относительно x2, получим уравнение паретовской кривой P: . Найдём точку пересечения кривой с x1=-0.5. Получим Xп=(-0.5; 0.2). Это соответствует случаю, когда λ меняется от 0 до 1 (0≤ λ≤1).

Параметрическое уравнение КК будет иметь следующий вид (когда точки X1opt=(0,0) и X2opt=(-1,1) принадлежат области D)

F1(λ)=

F2(λ)=.

Закономерность КК: F1 возрастает от 0 до 4.25, а F2 убывает от 2 до 0.

Построим графики паретовских кривых в области D и пространстве критериев (рис. 8 и 9).

Xп

Рис. 8. Область D и множество P Рис. 9. Компромиссная кривая

Рис. 10. Пространство оценок и компромиссная кривая

б) введём функциональные ограничения. Область D в этом случае будет иметь вид (рис. 11). Находим условный минимум для функции F1 и F2 . Они лежат в точках X1opt=(0,0) и X2opt=(-0.5, 1). Как видно из полученных результатов точки минимумов не изменились.

Рис. 11. Область D Рис. 12. Пространство оценок

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

---

1.4 Способы сужения Парето-оптимального множества

Выделение множества Парето МЗО часто не является удовлетворительным решением. Это связано с тем, что при достаточно большом исходном множестве вариантов множество Парето оказывается недопустимо большим для того, чтобы ЛПР было бы в состоянии осуществить выбор самостоятельно. Таким образом, выделение множества Парето можно рассматривать лишь как предварительный этап оптимизации, и налицо проблема дальнейшего сокращения этого множества.

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

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

Необходимо отметить, что необоснованность сужения множества Парето является существенным недостатком многих методов многокритериальной оптимизации. Многокритериальная оптимизация: Математические аспекты /Б.А Березовский, Ю.М. Барышников и др. - М.: Наука, 1989. - 128 с.

Таким образом, общая методика исследования задач принятия решения на основе математического моделирования для МЗО может быть реализована в рамках одного из следующих подходов.

Первый подход. Для заданной многокритериальной задачи оптимизации находится множество её Парето-оптимальных решений, а выбор конкретного оптимального варианта из множества Парето-оптимальных предоставляется ЛПР.

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

---

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

Указание верхних границ критериев. Дополнительная информация об оптимальном исходе Xopt∈D в этом случае имеет вид

(1)

Число Ci рассматривается здесь как верхняя граница по i – му критерию.

Отметим, что указание верхних границ по критериям не может быть "извлечено" из математической модели задачи принятия решения; набор ограничений (C1, C2, , Cm) представляет собой дополнительную информацию, полученную от ЛПР.

Задача. Выбор места работы

Предположим, что Вам предстоит выбрать место работы из девяти вариантов, представленных в табл.1. В качестве основных критериев взяты: зарплата З, длительность отпуска Д, время поездки на работу В. Из смысла задачи следует, что критерии З и Д следует максимизировать, а критерий В – минимизировать. Какой вариант является оптимальным?

Таблица 1

Варианты	Критерий
	Зарплата, (руб.)	Длительность отпуска, (дни)	Время поездки, (мин)
1	900	20	60
2	500	30	20
3	700	36	40
4	800	40	50
5	400	60	15
6	600	30	10
7	900	35	60
8	600	24	10
9	650	35	40

Решение. Выделим вначале Парето-оптимальные варианты. Отбрасывая доминируемые по Парето варианты {1, 2, 8, 9}, получаем Парето-оптимальное множество {3, 4, 5, 6, 7}. При отсутствии информации об относительной важности рассматриваемых критериев, а также о каких-либо дополнительных свойствах оптимального решения дальнейшее сужение Парето-оптимального множества произвести нельзя. Тогда формальный анализ заканчивается указанием Парето-оптимального множества и окончательный выбор оптимального варианта производится ЛПР из этих пяти вариантов на основе каких-то дополнительных соображений.

Рассмотрим теперь второй подход, который приводит к сужению Парето-оптимального множества на основе дополнительной информации, получаемой от ЛПР.

а) Указание нижних границ критериев. Наложим, например, следующие ограничения на оптимальное решение:

---

зарплата — не менее 600 рублей;

длительность отпуска — не менее 30 дней;

время поездки — не более 40 минут.

Варианты, удовлетворяющие этим дополнительным ограничения: {3, 6, 9}; из них оптимальными по Парето являются варианты 3 и 6. Остаётся сделать окончательный выбор между вариантами 3 и 6.

б) Субоптимизация. Пусть в качестве выделенного (главного, важнейшего) критерия выступает критерий зарплата; ограничения длительность отпуска — не менее 30 дней, время поездки — не более 40 минут. Отбросим варианты, которые не удовлетворяют данным ограничениям; остаются варианты: {2, 3, 5, 6, 9}. Из них максимальную зарплату имеет вариант 3. Этот вариант и будет оптимальным.

в) Лексикографическая оптимизация. Упорядочим критерии по относительной важности. Например, следующим образом: (т.е. важнейший критерий — зарплата, следующий за ним по важности время поездки, наименее важный критерий длительность отпуска). Максимальное значение по критерию З имеют варианты 1 и 7. Далее сравниваем эти варианты по второму по важности критерию В. Так как время поездки для этих вариантов одинакова, переходим к третьему критерию Д; по критерию длительность отпуска лучшим является вариант 7, который и является здесь оптимальным.

2. Численные методы получения множеств Парето

Часто используют следующий подход. Во множестве D выбирается некоторая сетка, например, координаты которой определяются с помощью датчика случайных чисел, распределённых по равномерному закону. Потом вычисляют значения векторного критерия F в точках этой сетки, после чего за конечное число сравнений, используя функцию выбора по Парето, строится множество Парето на указанной сетке, являющееся при большом N приближением множества Парето относительно D (N – число точек сетки).

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

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

---