Методы решения задач векторной оптимизации

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

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

Пример 8.1. Решить задачу по двум критериям

f (х) = {/](х) = х, + Зх₂, /₂ (х) = 40х, +10х₂} -> шах при ограничениях

2х, + х₂ < 90, X] + х₂ < 60, х₂ < 50, х, ,х₂ > 0 методом последовательных уступок, если уступка по первому критерию составляет 10% от его оптимального значения.

Рис. 8.1. Графическое решение задачи по критерию f

Решим задачу по критерию f графическим методом (рис. 8.1). Получим х‘ = х(5) = (10.50), =/^(10,50) = 160. В соответствии с условием задачи величина уступки Д, = 16. Дополнительное ограничение будет иметь вид /₁(х)>/’-Д_|, т. е. х, +3х₂ > 160-16. Решаем задачу по второму критерию: /₂ (х) = 40Х] +10х₂ —> max, 2xj + х₂ < 90, х, + х₂ < 60, х₂ < 5 0. х_} + Зх₂ > 144. х₁, х₂ > 0. также графически (рис. 8.2). Получаем решение исходной задачи х° = х(А) = (18.42), /₂° = /₂(х^о) = П40, ^°=^(х°) = 144.

Рис. 8.2. Графическое решение задачи по критерию^

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

Пример 8.2. Решить методом идеальной точки задачу по двум критериям

/(х) = {f (х) = X] + х₂ + 2, /₂ (х) = X] - х₂ + 6} max

при ограничениях х, + 2х₂ <6, О < х, < 4. О < х₂ < 2.

Множество X плоскости (хь х₂), определяемом системой неравенств, представляет собой пятиугольник с вершинами в точках Л(0. 0). Л(0. 2), С(2. 2).

В силу линейности критериев f и fa пятиугольник ABCDE переходит в пятиугольник А В С D Е , координаты вершин которого вычисляются по формулам ^ и fa: А*(2, 6), Л*(4. 4), С*(6, 6), D (7. 9), Е*(6. 10) (рис. 8.4). Находим границу Парето. Это отрезок DE (рис. 8.4). Точка утопии Л/(7, 10) (ее координаты суть наибольшие значения/ иfa). Необходимо найти на множестве Парето точку, ближайшую к точке утопии М. Проведем через точки D иЕ прямую. Уравнение этой прямой / +/ =16. По условию задачи нам нужно определить на прямой/+/=16 точку М° = (/⁰,/₂°), расстояние которой от точки Л/(7. 10) минимально, т. е. решить экстремальную задачу:

(/i-7)² + (/-10)²->min.

Идеальная точка =(6,5,9,5) находится на расстоянии 1//2 от точки утопии М (7, 10). Соответствующие значения Xi их₂ легко находятся из системы линейных уравнений х+у+2 = 6.5, х-у+6 = 9,5.Имеемxi=4.х₂=0.5.

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

/(х) —> max, /(х) >/,,/ = 2,..., т, хе X.

Пример 8.3. Формализуем двухкритсриальную задачу из примера 8.2 методом О1раничений yj(x) —> max. /₂(х) > 8. хе X. Получаем задачу ЛП

/Дх) = х, +х₂ +2 —> max, Xj -х₂ +6 >8, х, + 2х₂ <6, 0 < х, <4, 0 < х₂ < 2.

Решив задачу ЛП. например, графическим методом, получаем х°=(4,1), Г =7. /₂°=9.

Лексикографическая оптимизация, или метод приоритетов, основан на введении отношения порядка критериев ио относительной важности. Критерии перенумеровываются таким образом, что функция f(x) считается самым важным показателем, а последняя по номеру функция f_m(x) - наименее важной. Далее рассматривается задача последовательной оптимизации Д(х).....fn(^xY

Сначала решается задача /Дх) -> max. хе X. Если множество полученных оптимальных стратегий содержит более одной точки, решается задача максимизации критерия /j(x) на этом множестве:

/₂(х) —> max. хе Arg max f (х). хеХ

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

Пример 8.4. Пусть в примере 8.1 критерии упорядочены по убыванию приоритетов/1(х),/₂(х). Тогда решением является точка х° = (10,50), при которой У]⁰ = 160, /₂° = 900. Если изменить порядок критериев, решение- точка х° = (45. 0). при которой у;⁰ = 45, /₂° = 1800.

Обобщением метода идеальной точки является целевое программирование. Этот термин был предложен А. Чарнсом и В. Купером для определенного типа задач математического программирования, состоящих в нахождении решений, обеспечивающих «как можно более близкое» приближение к множеству одновременно недостижимых целей. Обозначим )"* целевое множество в пространстве критериев. Данное множество может быть задано, например. /(х) = / или у](х)>/ (у](х) 2]. /-1, ...,т. Кандидатами в решение являются точки из У, ближайшие к У в смысле какой-то метрике р в пространстве критериев. Тогда в общем виде задача формулируется следующим образом: найти р(/(х),У*)-»min, где хеХ

р(/?(х), Y*) = min( f(x), у). Метрика может быть выбрана, например, полиэдральная yeY*

(обобщенная линейная): р₀(У'(х),у‘) = mina. |/(х)-у‘ |, р_|(/(х),у*)=^а,|у'(х)-у | i

или евклидова р₂(/(х),/) = ^а,(У(х)-у )². Если метрика полиэдральная, задача I

целевого программирования может быть сведена к задаче ЛП.

Пример 8.5. Рассмотрим задачу многокритериальной оптимизации: У^(х) = 2Х] + х₂, /₂(х) = Х| + 2х₂ , А" +х₂ <8, 0< х, <7, 0 <х₂ < 6.

Пусть заданы цели yj(x) = 16,/₂(х)>13(т. е. у, =16, у₂ = 13), а расстояние определяется как Р1(Лх),у’) = т|./)(х)-у_|* |+т1/₂(х)-у₂1. Обозначим yj(x) -16 = ф, min |/₂(х) -13,0} = J₂, получим задачу целевого программирования:

/(х) = j | d_] | -±d₂ —» min,

X] +x₂ < 8, 0 < X] < 7, 0 < x₂ < 6, 2X] +x₂ - d_} -16 = 0, x_] + 2x₂ - d₂ -13 = 0.

Выполнив замену переменных d_x = df-di, d₂ = -di, di,d_t ,d₂ >0. получаем задачу ЛП:

f (x) = у di + у di + yc/j —> min, x, +x₂ < 8, 0 < Xj < 7, 0 < x₂ < 6,

2Xj + x₂ - di + di -16 = 0, X]+2x₂+2-13 = 0, di,di,di > 0.

Найдем решение задачи целевого программирования графически. Множество А’ = {хе 77“ | X] +х₂ < 8, 0 < X] < 7, 0 < х₂ < 6} - пятиугольник OABCD с вершинами 69(0,0), Л(0, 6), 77(2,6). С(7. 1). 79(7,0). Множество Y- это образ X при линейном отображении f ?.(x_i,x₂)^>(fAx_i,x₂}, f₂(x_A,x₂)). Так как отображение линейное, то пятиугольник OABCD переходит в некоторый пятиугольник O'A'B'C'D'. Найдем координаты вершин: O'=fl(O) = (0,0), A'-f^A) = (6,12), B'=ffi) = (Ю, 14), С'=ДС) = (15,9), D'=ftP) = (14,7). Множество 1’ = {уел | у, = 16, y₂>13}- вертикальный луч (сонаправленный с осью

ординат) с вершиной F = (16, 13) (рис. 8.5). Требуется найти кратчайшее расстояние между множествами У и 1 в смысле заданной метрики.

Рис. 8.5. Множество оценок и целевое множество

Линии уровня функции Р1(у)=т1>’1-л |+т1у₂ “Уг I ~ это квадраты с центром (у'_},у₂) и сторонами, параллельными биссектрисам координатных четвертей. Поэтому множество точек из У, ближайших к У*, - это отрезок, лежащий на стороне В'С, соединяющий точки С'= (15. 9) и Е'= (11, 13). Решением в пространстве стратегий является прообраз отрезка СЕ'. Координаты точки Е удовлетворяют системе уравнений 2х, +х₂ = 11,Х] +2х₂ = 13, поэтому Е(3.5). Оптимальной является любая точка отрезка СЕ, т. е. х° = (7?₁+3р₂,р₁ + 5р₂), Р„Р₂>0, Р,+Р₂ = 1.