Тема: Многокритериальные задачи

Лабораторная работа № 10

Рассматриваемые вопросы:

- методы решения задач многокритериальной оптимизации

- метод идеальной точки

- решение многокритериальных задач методом ограничений

1. Методы решения задач многокритериальной оптимизации

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

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

Метод свертывания – лицо, принимающее решения (руководитель), сводит многокритериальную задачу к задаче с одним критерием.

Метод ограничений – множество допустимых значений неизвестных уменьшается путем осмысленного введения дополнительных ограничений на заданные критерии.

Метод анализа иерархий – на основании суждений экспертов оценивается вклад в общую оценку каждого критерия.

2. Метод идеальной точки

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

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

Рассмотрим конкретный пример поиска идеальной точки.

Пример 1. Пусть на множестве плоскости , определяемом системой неравенств

заданы две линейные функции

(1)

Требуется найти решение задачи

при условии, что .

Множество представляет собой квадрат (рис. 1), вершины которого имеют координаты А (0, 0), В (0, 2), С (2, 2), D (2, 0).

Рис.1 Рис.2

В силу линейности критериев U и V квадрат ABCD переходит в параллелограмм PQRS (рис. 2), координаты вершин которого вычисляются по формулам (1) и равны: P (2, 2), Q (0, 8), R (10, 6), S (12, 0).

Точка утопии М* (12, 8) считается заданной (ее координаты равны наибольшим значениям U и V). Граница Парето параллелограмма PQRS состоит из двух отрезков – QR и RS (рис. 3).

Точка, ближайшая к точке утопии М*, принадлежит множеству Парето и должна лежать на одном из составляющих его отрезков – или на отрезке QR, или на отрезке RS.

Рис.3

Чтобы найти на отрезке QR точку, ближайшую к точке М*, воспользуемся прямой, проходящей через точки Q и R.

Подставляя в общее уравнение прямой координаты точек Q и R,

Найдем соответствующие значения параметров и . Из первого равенства получаем, что а из второго, что . Предположим, что . Тогда и U+5V=40 – уравнение искомой прямой.

Теперь стоит напомнить, что ищется расстояние между точками, заданными своими координатами. Пусть (U₁, V₂) и (U₂, V₂) – точки на плоскости (U, V). Для того, чтобы найти расстояние между ними, достаточно вычислить длину гипотенузы построенного прямоугольного треугольника (рис. 4).

Рис.4

Воспользовавшись теоремой Пифагора, получим, что расстояние между этими точками равно .Чтобы отыскать на прямой, описываемой уравнением U+5V=40, точку М⁰(U⁰, V⁰), ближайшую к точке М*(12, 8), нужно решить экстремальную задачу

(2)

при условии, что U+5V=40.

Заменяя в формуле (2) U на 40-5V, приходим к задаче .
Возводя в квадрат и приводя подобные члены, получаем, что .

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

Из рисунка 5 видно, что точка на прямой QR, ближайшая к точке утопии М*, лежит вне отрезка QR: справа от точки R (U> 10) и ниже ее (V< 6).

Рис.5.

Поиск точки, ближайшей к точке утопии М* на прямой RS приводит к аналогичному результату:

.

Найденная точка лежит вне отрезка RS: U< 10, V> 6. Возьмем окружность с центром в точке М* столь малого радиуса, чтобы она не пересекалась с множеством , и будем постепенно увеличивать радиус этой окружности (сохраняя центр в точке М*) до тех пор, пока она не коснется множества . Из полученных выше результатов ясно, что эта окружность встретит ломаную QRS в точке R(10, 6), которая и будет ближайшей к точке утопии М*, то есть идеальной точкой.

Найденная идеальная точка отстоит от точки утопии М* (12, 8) на расстоянии , равном радиусу построенной окружности (рис.6).

Рис.6.

Соответствующие значения x* и y* легко находятся из системы линейных уравнений

Имеем x*=2, y*=2.

Пример 2. Пусть на множестве

(рис 7, а) заданы две линейные функции:

U=2x и (3)

Требуется найти решение задачи
, (4)

при условии, что точка утопии М* имеет координаты (2, -2).

Рис.7 а, б, в

Введем новую функцию (5).
Тогда требование (4) можно записать так: .

Соответственно изменится и точка утопии - N*(2, 2).

Функции и линейны и преобразуют единичный квадрат в параллелограмм (рис 7 а, б), при этом вершины квадрата (0, 0), (1, 0), (1, 1), (0, 1) переходят в вершины параллелограмма (0, 1), (2, 0), (2, 1), (0, 2).

Множество Парето образуют точки отрезка с концами А(0, 2) и В(2, 1) (рис 7, в).

Проведем через эти точки прямую и найдем коэффициенты ее уравнения .

Подставляя в него координаты точек А и В, получаем, что и . Предположим, что . Тогда и . Тем самым уравнение искомой прямой имеет вид: U+2W=4.

Пусть О* (U, W) – точка этой прямой, ближайшая к точке N*(2, 2). Это значит, что должно выполняться условие

Так как U=4-2W, то оно принимает следующий вид:
Рис. 8.

Чтобы найти минимальное значение функции (рис. 8), приравняем к нулю ее производную. Имеем: .

Отсюда , .

Соответствующие значения и находятся из уравнений (3). Получаем, что , а .

Расстояние от найденной точки О* до точки утопии N*(2, 2) равно 2/ . Ответ: идеальная точка находится от заданной точки утопии М*(2, -2) на расстоянии 2/ .

Пример 3. Используя равномерную метрику, методом идеальной точки найдем решение следующей двухкритериальной задачи:

при ограничениях

Так как для данной задачи , , то соответствующая однокритериальная задача в пространстве критериев имеет вид:

Графическое решение задачи представлено на рисунке 9

.

Рис.9.

Как видно из рисунка, линии уровня функции имеют вид квадратов с центром в идеальной точке =(7, 14). Интересующая нас точка удовлетворяет условию и принадлежит отрезку в пространстве критериев, а соответствующая ей в пространстве решений точка x⁰- отрезку (x³, x⁴). Исходя из этих условий, находим x⁰=(19/5; 3), f⁰=(26/5; 61/5).

3. Решение многокритериальных задач методом ограничений.

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

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

Метод ограничений основан на теореме: если x₀ – эффективное решение для данного вектора предпочтений , то ему соответствует наименьшее значение , при котором система равенств

= выполняется для всех i=1, k (6)

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

Например, если принять и , то это означает, что по информации ЛПР первый критерий в 2 раза значимее по сравнению со вторым.

Тогда в качестве решения задачи можно принять компромиссное решение с заданным вектором предпочтений. Очевидно, что компромиссное решение – это такое эффективное решение x₀, которое обеспечивает одинаковые минимальные значения параметра , при котором система (6) совместна.

Таким образом, компромиссное решение может быть найдено как единственное решение системы неравенств вида

для минимального значения параметра , при котором эта система совместна.