Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання
Досліджено деякі властивості векторних лексикографічних задач оптимізації. Встановлені необхідні та достатні умови існування й оптимальності лексикографічних розв’язків. Обгрунтовано зведення початкової задачі до скалярної з функціоналом, що є згорткою часткових критеріїв та описано метод знаходженн...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84757 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання / М.М. Ломага, В.В. Семенов // Компьютерная математика. — 2013. — № 2. — С. 134-143. — Бібліогр.: 7 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859820580168007680 |
|---|---|
| author | Ломага, М.М. Семенов, В.В. |
| author_facet | Ломага, М.М. Семенов, В.В. |
| citation_txt | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання / М.М. Ломага, В.В. Семенов // Компьютерная математика. — 2013. — № 2. — С. 134-143. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Досліджено деякі властивості векторних лексикографічних задач оптимізації. Встановлені необхідні та достатні умови існування й оптимальності лексикографічних розв’язків. Обгрунтовано зведення початкової задачі до скалярної з функціоналом, що є згорткою часткових критеріїв та описано метод знаходження коефіцієнтів цієї згортки для лексикографічних задач квадратичної оптимізації.
Исследованы некоторые свойства векторных лексикографических задач оптимизации. Получены необходимые и достаточные условия существования и оптимальности лексикографических решений. Обосновано сведение исходной задачи к скалярной с функционалом, который является сверткой частичных критериев. Описан метод нахождения коэффициентов этого функционала для лексикографических задач квадратичной оптимизации.
Some properties of vectorial lexicographic problems of optimization are explored. The necessary and sufficient conditions of existence and optimality of lexicographic decisions are got. Taking of initial problem is grounded to scalar with functional which is rolling up of partial criteria. The method for finding of coefficients of this functional is described for the lexicographic problems of quadratic optimization.
|
| first_indexed | 2025-12-07T15:25:32Z |
| format | Article |
| fulltext |
134 Компьютерная математика. 2013, № 2
Досліджено деякі властивості
векторних лексикографічних за-
дач оптимізації. Встановлені не-
обхідні та достатні умови існу-
вання й оптимальності лексиког-
рафічних розв’язків. Обгрунтова-
но зведення початкової задачі до
скалярної з функціоналом, що є
згорткою часткових критеріїв та
описано метод знаходження кое-
фіцієнтів цієї згортки для лекси-
кографічних задач квадратичної
оптимізації.
М.М. Ломага, В.В. Семенов,
2013
Компьютерная математика. 2013, № 2 135
УДК 519.8
М.М. ЛОМАГА, В.В.
СЕМЕНОВ
КВАДРАТИЧНІ
ЗАДАЧІ
ЛЕКСИКОГРАФІЧНО
Ї ОПТИМІЗАЦІЇ:
ВЛАСТИВОСТІ ТА
РОЗВ’ЯЗАННЯ
Вступ. Векторні задачі
оптимізації виникають при
доcлідженні багатьох теоре-
тичних
і прикладних проблем. Прак-
тично будь-яка задача опти-
мального проектування
складних економічних і
технічних систем, складання
мережевих графіків, плану-
вання й управління виробни-
чою і комерційною
діяльністю та ін. вимагає, щоб
шуканий розв’язок знаходився
з урахуванням багатьох
критеріїв [1, 2]. У ря-ді
випадків часткові критерії
можуть бути впорядковані за
важливістю, коли слід праг-
нути до поліпшення більш
важливого крите-рію за раху-
нок будь-яких втрат за всіма
іншими менш важливими [3].
У цьому разі розв’язок є уза-
гальненням поняття точки
максимуму (мінімуму) чис-
лової функції на випадок де-
кількох функцій при лексико-
графічному відношенні пере-
ваги. Властивостям і методам
пошуку лексикографічно оп-
ти-мальних розв’язків присвячено ряд робіт,
зокрема, [1 – 5]. Квадратичні задачі мають
широку область застосувань. Питання розв’я-
зання квадратичних задач лексикографічної
оптимізації займають важливе місце при ви-
рішенні проблем математичної економіки,
теорії ігр, оптимального керування, статис-
тичних рішень та інших наукових дисциплін,
в яких вивчаються різні багатокритеріальні
моделі прийняття раціональних рішень. Дана
робота присвячена дослідженню властивос-
тей векторних лексикографічних задач опти-
мізації, встановленню необхідних і достатніх
умов існування та оптимальності лексиког-
рафічних розв’язків, зведенню розв’язання
початкової задачі до однокритеріальної шля-
хом подання лексикографічного відношення
М.М. ЛОМАГА, В.В. СЕМЕНОВ
Компьютерная математика. 2013, № 2 136
за допомогою одного функціоналу, що являє собою згортку часткових критеріїв,
та відшукання коефіцієнтів цієї згортки для лексикографічної задачі квадратич-
ної оптимізації.
Розглянемо лексикографічну задачу оптимізації ( ){ }max ,L F x x X∈ , всі
часткові критерії ( ) , 1,2, ,if x i l= K якої утворюють векторний критерій
( ) ( ) ( ) ( ){ }1 2, , , lF x f x f x f x= K і упорядковані за важливістю. Таким чином при
порівнянні пари альтернатив із множини X всіх допустимих альтернатив,
у першу чергу використовується частковий критерій ( )1f x і кращою вважається
та альтернатива, для якої значення цього критерію більше; якщо значення пер-
шого критерію для обох альтернатив рівні, то застосовується другий частковий
критерій і перевага віддається тій альтернативі, для якої його значення більше;
якщо і за другим критерієм не вдається вибрати кращу альтернативу, то застосо-
вується третій і т. д. до останнього ( ).lf x Якщо значення кожного часткового
критерію для розглядуваних альтернатив рівні між собою, то ці альтернативи
вважаються еквівалентними у розумінні векторного критерію ( )F x . Формально
лексикографічне відношення переваги задається наступним чином: допустима
альтернатива x X∈ лексикографічно більша за допустиму альтернативу y X∈
(позначається: Lx y> ), якщо виконується одна з умов
1) ( ) ( )1 1f x f y> ; 2) ( ) ( )1 1f x f y= , ( ) ( )2 2f x f y> ; ………….,
r) ( ) ( )i if x f y= , 1,2, , 1i r= −K , ( ) ( )r rf x f y> ; ……….,
l) ( ) ( )i if x f y= , 1,2, , 1i l= −K , ( ) ( )l lf x f y> . (1)
Означення 1. Вектор lz R∈ називається лексикографічно додатним, якщо
перша його ненульова компонента в порядку зростання індексів компонент
додатна. Позначатимемо лексикографічну додатність вектора lz R∈ так: 0Lz > .
Означення 2. Альтернативу x X∗ ∈ називатимемо лексикографічно опти-
мальною, якщо вона не гірша за будь-яку іншу допустиму альтернативу y
у розумінні відношення L≥ , тобто якщо ( ) ( ) 0LF x F y∗ − ≥ .
У лексикографічній задачі оптимізації досягають як завгодно малого приро-
сту більш важливого критерію за рахунок будь-яких втрат за іншим менш
важливим критерієм.
Якщо в означенні 2 замість X підставити ( )X O xI , де ( )O x – деякий окіл
точки x , то лексикографічно оптимальну точку x називатимемо відповідно
локально лексикографічно оптимальним розв’язком.
КВАДРАТИЧНІ ЗАДАЧІ ЛЕКСИКОГРАФІЧНОЇ ОПТИМІЗАЦІЇ: ...
Компьютерная математика. 2013, № 2 137
Властивості множини лексикографічних оптимумів. Позначимо X ∗ −
множину всіх лексикографічно оптимальних альтернатив. Множина X ∗ має
наступні властивості: 1) всі альтернативи множини X ∗ еквівалентні між собою;
2) множину X ∗ можна задати за допомогою таких рекурентних співвідношень:
( ) ( )
1
1: ; sup ,
i
i i i i i
y X
X x x X f x f y f
∗
−
∗ ∗ ∗
−
∈
= ∈ = =
1,2, ,i l= K , 0X X∗ = , ;lX X∗ ∗= (2)
3) 1 1lX X X X∗ ∗ ∗
−⊆ ⊆ ⊆ ⊆K .
У загальному випадку множина X ∗ може бути порожньою. В одно-
критеріальних задачах зі скалярним критерієм f оптимальна альтернатива мо-
же не існувати, тоді розв’язком задачі є максимізуюча послідовність { } ,kx X⊆
яка визначається умовою ( ) ( )lim supk
k x X
f x f x
→∞ ∈
= . Поняття максимізуючої
послідовності для задач лексикографічної оптимізації вводиться таким чином.
Нехай множини ,iX ∗ = ∅ починаючи з деякого 1i p= ≥ .
Означення 3. Послідовність альтернатив { }kx називається лексикографічно
максимізуючою, якщо для всіх достатньо великих номерів k альтернативи
kx входять у множину 1iX ∗
− (так що при 1p > ( ) 1,2, , 1k
i if x f i p∗= ∀ = −K )
і ( )lim k
p p
k
f x f ∗
→∞
= . Якщо множина X ∗ ≠ ∅ , то лексикографічно максимізуючою
називається послідовність { }kx , всі члени якої, за винятком, можливо
скінченого їх числа, є елементами множини 1lX ∗
− і для якої ( )lim k
l l
k
f x f ∗
→∞
= .
У випадку, коли не існує оптимальної альтернативи, точну верхню (лексико-
графічну) межу критерію ,F яку позначатимемо ,F∗ теж можна визначити
за допомогою співвідношень (2), оскільки для порожньої множини
1iX ∗
− ( )
1
sup
i
i
x X
f x
∗
−∈
= −∞ . Отже, в загальному випадку компонентами вектора F∗
можуть бути −∞ та +∞ . Таким чином, лексикографічна задача оптимізації
полягає у відшуканні лексикографічно оптимальних альтернатив чи лексико-
графічно максимізуючих послідовностей альтернатив.
У квадратичній задачі лексикографічної оптимізації існують лексикографіч-
но оптимальні альтернативи, якщо множина допустимих альтернатив скінчена.
Тоді й усі множини iX ∗ , 1,2, ,i l= K , теж скінчені і непорожні. Задача лексиког-
рафічної оптимізації матиме єдиний розв’язок, якщо деякий критерій kf досягає
максимуму на 1kX ∗
− в одній точці.
М.М. ЛОМАГА, В.В. СЕМЕНОВ
Компьютерная математика. 2013, № 2 138
Еквівалентні трансформації критеріїв квадратичних задач лексиког-
рафічної оптимізації. Теоретичний та практичний інтерес представляє питання
можливості перетворення векторного критерію лексикографічної задачі, при
якому зберігається множина лексикографічно оптимальних розв’язків.
Твердження 1. Нехай функція ,g визначена на множині ( ){ }|k kY f x x X= ∈
значень часткового критерію kf , є строго зростаючою, тоді векторні критерії
( )1 2, , , lF f f f= K і ( )( )1 1 1, , , , , ,k k k lF f f g f f f− +′ = K K лексикографічно еквіва-
лентні, тобто множини оптимальних альтернатив, що визначаються цими крите-
ріями, рівні між собою.
Доведення. Покажемо, що для будь-яких альтернатив ,x z X∈ ( ) ( )LF x F z>
тоді й тільки тоді, коли ( ) ( )LF x F z′ ′> .
Необхідність. Нехай для будь-яких альтернатив ,x z X∈ виконується умова
( ) ( )LF x F z> . Отже, має місце одна з умов (2). Якщо функція g – строго зро-
стаюча, то має місце або ( )( ) ( )( )i ig f x g f z= при ( ) ( )i if x f z= , або
( )( ) ( )( )i ig f x g f z> при ( ) ( )i if x f z> . Отже, ( ) ( )LF x F z′ ′> .
Достатність. Якщо ( ) ( )LF x F z′ ′> , то ( ) ( )LF x F z> .
Це твердження дозволяє будувати для розглядуваної задачі нові векторні
критерії, лексикографічно еквівалентні вхідному, але більш зручні в обчислю-
вальному відношенні.
Наслідок 1. Якщо всі числа 0, const, 1,..., ,k kc d k l> − = то критерії F
і ( )1 1 1, , l l lc f d c f d+ +K лексикографічно еквівалентні.
Наслідок 2. Частковий критерій kf можна замінити на будь-який з
критеріїв kfa , ( )b
kf , kfd − ( 1a > , 0b > − непарне число, 0 1d< < ), оскільки при
таких умовах функції xa , bx і xd − є строго зростаючими на ( ),−∞ +∞ .
Наслідок 3. Якщо kf приймає лише додатні значення на X , то замість ньо-
го можна взяти ( )kf
α
( )0α > , 1 kf− або log kfβ ( )1β > , оскільки функції ,xα
1 x− і log xβ строго зростають на ( )0,+∞ .
Наслідок 4. Нехай nX R⊆ − опукла множина, а iφ , 1,2, ,i m= K − визначені
на X угнуті додатні функції. Критерій
1
m
k i
i
f
=
= φ∏ не є угнутою функцією,
але від нього можна перейти до угнутого критерію
1
ln ln .
m
k k i
i
f f
=
′ = = φ∑
КВАДРАТИЧНІ ЗАДАЧІ ЛЕКСИКОГРАФІЧНОЇ ОПТИМІЗАЦІЇ: ...
Компьютерная математика. 2013, № 2 139
Наслідок 5. Критерій ( )g x
kf e= ( ( )g x − додатна угнута функція), що не є
угнутою функцією, можна замінити угнутим критерієм ( )lnk kf f g x′ = = .
Твердження 2. Якщо η − довільна функція, визначена на множині значень
векторного критерію ( ) ( ){ }: ; ,lY F X y y R y F x x X= = ∈ = ∈ , то критерії F
і ( )( )1 2 1 2, , , , , , ,l lF f f f f f f′ = ηK K лексикографічно еквівалентні.
Доведення. Нехай ( ) ( )LF x F z> . Тоді за означенням ( ) ( ).LF x F z′ ′> Нехай
тепер ( ) ( )LF x F z′ ′> . Отже, виконуються умови (1) і також умова (l+1)
( ) ( )i if x f y= , 1, ,i l= K , ( ) ( ) ( )( ) ( ) ( ) ( )( )1 2 1 2, , , , , ,l lf x f x f x f z f z f zη > ηK K .
Звідси випливає, що ( ) ( )LF x F z> .
Властивості квадратичних задач лексикографічної оптимізації. Розгля-
немо задачу лексикографічної оптимізації:
( ) { }{ }max | | , 0L nF x x X x R Ax b x∈ = ∈ ≤ ≥ , (3)
де ( ) T T
i i if x x C x d x= + , 1,2, ,i l= K , де n n
iC R ×∈ − симетричні матриці, n
id R∈ ,
m nA R ×∈ , mb R∈ , X ≠ ∅ .
Теорема 1. Задача (3) має скінченний лексикографічно оптимальний
розв’язок, якщо хоча б одна з функцій векторного критерію є строго угнутою.
Доведення. Припустимо, що перший частковий критерій ( )1f x векторного
критерію строго угнутий. Позначимо ( )G ρ − гіперсфера радіуса ρ з центром у
початку координат, G − гіперсфера одиничного радіуса з тим же центром. Тоді
будь-який ( )x G∈ ρ можна представити у вигляді x r= ρ , де r G∈ . Квадратич-
на форма 1
Tr C r досягає на G максимуму. Позначимо 0
1r точку максимуму ви-
разу 1 .Tr C r З умови теореми випливає, що r G∀ ∈ 1 0Tr C r < ⇒
⇒ 0 0
1 1 1 1 0.Tr C r z= < Нехай 2
1 1 ,Т Tx C x r C r= σ r G∈ ⇒ 2
1 0.Tx C x z≤ σ <
( ) .x G∀ ∈ σ Отже, при x → ∞ 1
Tx C x → −∞ . Нехай 0x ≠ . Перепишемо
функцію ( )1f x у вигляді ( ) 1
1 1
1
1
T
T
T
d x
f x x C x
x C x
= +
. Вираз 1
1
T
T
d r
r C r
досягатиме
максимуму на G в точці 1z . 1 1 1 1
1 1 1 1 1
1 1
.
T T T
T T T
d x d r d z
x C x r C r z C z
= ≤
σ σ
Звідси отримуємо,
що при x → ∞ 0
Т
i
Т
i
d x
x C x
→ , ( )1 1 1
T Tf x x C x d x= + → −∞ . Отже, векторна
М.М. ЛОМАГА, В.В. СЕМЕНОВ
Компьютерная математика. 2013, № 2 140
функція ( )1f x є обмеженою зверху, тоді за схемою скаляризації задача
( ){ }1max |f x x X∈ має єдиний розв’язок. Нехай тепер строго угнутим є k -й час-
тковий критерій, 2 k l≤ ≤ . Відповідно єдину оптимальну альтернативу отримує-
мо, розв’язуючи задачу ( ) ( ){ }max | , , 1 1k i if x x X f x f i k∗∈ = = −K за схемою ска-
ляризації. Тоді задача (3) матиме скінченний розв’язок, що й треба було довести.
Наслідок 6. Якщо хоча б один з часткових критеріїв задачі (3) є строго
угнутий, то множина лексикографічних оптимумів містить єдиний елемент
( )1 .L =
Подання лексикографічного відношення за допомогою одного
функціоналу. Розв’язки лексикографічної задачі оптимізаціїї можна відшукати
за схемою скаляризації: 1-й крок. Розв’язується задача (P1): ( ){ }1max |f x x X∈ .
Якщо вона не має оптимального розв’язку, то задача (3) теж не має опти-
мального розв’язку. Якщо (P1) має оптимальний розв’язок ( 1f
∗ − максимум
функції 1f на X ), то переходимо до 2-го кроку. Опишемо k -й крок ( 2 k l≤ ≤ ).
Розв’язується задача (Pk): ( ) ( ){ }{ }1max | , , 1,2, , 1k i i if x X x X f x f i k∗
− = ∈ = = −K .
Якщо вона не має оптимального розв’язку, то задача (3) теж не має оптимально-
го розв’язку. Нехай задача (Pk) має оптимальний розв’язок ( if
∗ − максимум
функції if на 1iX − ). Якщо k l< , то переходимо до ( 1k + )-го кроку. Якщо k l= ,
то обчислений покомпонентно вектор ( )1 2, , , lf f f∗ ∗ ∗
K є лексикографічним мак-
симумом векторної функції F на ,X а множина оптимальних розв’язків kX
задачі (Pk) – це множина оптимальних розв’язків задачі (3).
Цей багатоетапний спосіб дозволяє знаходити лексикографічно оптимальні
альтернативи, але він є складним, оскільки приходиться розв’язувати l задач
оптимізації, що досить обтяжливо. Крім того, приєднання обмежень ( )k kf x f ∗=
до задачі (3) призводить до втрати задачею специфічних особливостей і як наслі-
док неможливості застостосування ефективних обчислювальних алгоритмів.
Постає питання про можливість одноетапного розв’язання лексикографічної
задачі, тобто зведення її до однокритеріальної, що пов’язано з проблемою пред-
ставлення лексикографічного відношення за допомогою одного функціоналу.
Питання про побудову функціоналу ,Φ визначеного на множині ,X що
дозволяє представити лексикографічне відношення, який має властивість:
,x y X∀ ∈ ( ) ( )x yΦ ≥ Φ тоді й тільки тоді, коли ,Lx y≥ (4)
має велике теоретичне і практичне значення. Якщо x∗ − лексикографічно
оптимальна альтернатива, то на ній досягає найбільшого значення функціонал
Ф ; справедливе і зворотне твердження: функціонал, що представляє лексиког-
КВАДРАТИЧНІ ЗАДАЧІ ЛЕКСИКОГРАФІЧНОЇ ОПТИМІЗАЦІЇ: ...
Компьютерная математика. 2013, № 2 141
рафічне відношення переваги, досягає найбільшого значення на множині
оптимальних альтернатив ( ) ( )| , max
y X
X x x X x y∗
∈
= ∈ Φ = Φ
. Це означає, що
відшукання лексикографічно оптимальних альтернатив зводиться до знахо-
дження максимуму Φ на .X
У роботах [4, 5] розглядалися питання про побудову функціоналу. Доведе-
но, що у випадку, коли множина альтернатив скінченна, питання про існування
шуканого функціоналу вирішується просто. Достатньо спочатку розбити мно-
жину альтернатив на класи, що складаються з еквівалентних альтернатив, потім
розташувати отримані класи відповідно до лексикографічного відношення пере-
ваги (тобто якщо Lx y≥ , то клас альтернатив, еквівалентних альтернативі ,y
має стояти перед класом альтернатив, еквівалентних альтернативі x ), послідов-
но перенумерувати класи відповідно до встановленого розташування (номер 1
буде мати перший, або молодший за порядком клас, а номер n , де n − число
класів, буде надано останньому, старшому класу − множині X ∗ ) і, нарешті, ви-
значити на X функціонала ,Φ поклавши для альтернативи x значення ( )xΦ
рівним номеру класу, в який входить x . Проведені міркування доводять існу-
вання шуканого ,Φ однак практично побудувати таким способом функціонал Φ
не можна, оскільки описана процедура має надмірну трудомісткість.
Виявляється, що існує досить простий і зручний для практичної реалізації
спосіб побудови функціоналу, що представляє лексикографічне відношення
переваги, якщо шукати його у вигляді
1
.
l
r r
r
L f
=
Φ = = α∑
Зрозуміло, що для побудови функціоналу Ф потрібно вміти вибирати кое-
фіцієнти .rα З’ясуємо, як можна призначити ці коефіцієнти, щоб функціонал L
мав властивість (4). Якщо ,x y⇔ тобто, якщо ( ) ( )F x F y= , то ( ) ( )L x L y= .
Функціонал L дозволяє представити лексикографічне відношення на ,X якщо
має таку властивість:
x∀ , y : ,Lx y> то ( ) ( )L x L y> . (5)
Властивість (5) можна записати таким чином. Для будь-яких , ,x y X∈ якщо:
1) ( ) ( )1 1f x f y> , то ( ) ( )L x L y> ; 2) ( ) ( )1 1f x f y= , ( ) ( )2 2f x f y> , то ( ) ( )L x L y> ;
.....………….
r) ( ) ( )i if x f y= , 1,2, , 1,i r= −K ( ) ( )r rf x f y> , то ( ) ( )L x L y> ;………. (6)
l) ( ) ( )i if x f y= , 1,2, , 1i l= −K , ( ) ( )l lf x f y> , то ( ) ( )L x L y> .
Для виконання вимоги )l потрібно лише, щоб коефіцієнт lα був додатній.
Конкретний вибір lα , як це видно з подальшого, слід здійснити з міркувань
зручності практичного застосування функціоналу .L Припустимо, що вже
вибрані додатні коефіцієнти 1,r+α 2 ,r+α …, ,lα так, що виконуються вимоги пу-
М.М. ЛОМАГА, В.В. СЕМЕНОВ
Компьютерная математика. 2013, № 2 142
нктів: 1)r + , 2)r + , …, )l із (6). З’ясуємо, як слід вибрати коефіцієнт rα , щоб
забезпечити виконання вимоги )r для критерію L.
Для критерію Φ цю вимогу можна записати таким чином: ,x y X∀ ∈
( ) ( )i if x f y= , 1,2, , 1i r= −K , ( ) ( )r rf x f y> , отже ( ) ( ).
l l
i i i i
i r i r
f x f y
= =
α > α∑ ∑
Призначимо коефіцієнт ,rα щоб виконувалася умова, сильніша, ніж
попередня: , :x y X∀ ∈ ( ) ( )r rf x f y> має виконуватися нерівність
( ) ( ) ( ) ( )
1
.
l
r r r i i i
i r
f x f y f y f x
= +
α − > α − ∑
Якщо rf – стала на X , тобто , ,x y X∃ ∈ для яких ( ) ( )r rf x f y> , то за rα
можна вибрати будь-яке число. Розглянемо випадок, коли rf на X не є сталою.
Легко бачити, що для виконання останньої умови досить узяти ,r rwα >
де
( ) ( )
( ) ( )
( ) ( )
1
,
max
r r
l
i i i
i r
r
x y X
r rf x f y
f y f x
w
f x f y
= +
∈
>
α −
=
−
∑
.
У багатьох задачах знайти величину rw важко. Тому оцінимо її зверху:
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
,
1 1 1
,
,
max
max
min
r r
r r
l l l
i i i i i i i i
x y X
i r i r i r
r r
x y X
r r r r rf x f y x y X
f x f y
f y f x f y f x M
w
f x f y f x f y
∈= + = + = +
∈
≠ ∈
≠
α − α − α
≤ ≤ ≤
− − µ
∑ ∑ ∑
,
де
( ) ( )
( ) ( )
,
0 inf ;
r r
r r r
x y X
f x f y
f x f y
∈
≠
< µ ≤ − ( ) ( )max min .i i i
x Xx X
M f u f u
∈∈
≥ −
Таким чином, для виконання умови )r достатньо, щоб
1
/ .
l
r i i r
i r
M
= +
α > α µ
∑ (7)
Описаний спосіб побудови шуканого функціоналу досить зручний, оскільки
вибрати величини rµ і rM порівняно легко вдається майже для будь-якої
практичної задачі. Зазначимо, що описаний підхід до побудови функціоналу
підходить і в тому випадку, коли скінченна не сама множина альтернатив ,X
а лише множина значень векторного критерію (достатньо навіть скінченності
множин лише перших 1l − часткових критеріїв, а lf був обмеженим).
КВАДРАТИЧНІ ЗАДАЧІ ЛЕКСИКОГРАФІЧНОЇ ОПТИМІЗАЦІЇ: ...
Компьютерная математика. 2013, № 2 143
Теорема 2 [5]. Якщо множина значень векторного критерію скінченна, то
можна побудувати функціонал L, що представляє лексикографічне відношення
переваги таким чином: досить узяти довільний коефіцієнт 0,lα > а решті
коефіцієнтів 1l−α , …, 1α послідовно надати значення відповідно до (7).
Для вирішення питання про можливість зведення лексикографічної задачі
до однієї задачі оптимізації з функціоналом ,Ф що задовольняє (4), доцільно
ознайомитися з деякими властивостями ефективних альтернатив.
Відшукання коефіцієнтів згортки в лексикографічній задачі квадра-
тичної оптимізації. Розглянемо лексикографічну задачу квадратичної оптиміза-
ції вигляду (3), задану на опуклому многограннику .nX R⊆ Тут n n
iC R ×∈ − си-
метричні невід’ємно визначені матриці, тобто функції критеріїв є опуклими.
Множину вершин многогранника позначимо ,VX отже X − опукла оболонка
множини .VX Розглянемо задачу
( ){ }( ) : max | ,P x x XΦ Φ ∈ де ( )
1
,
l
i i
i
f x
=
Φ = α∑ 0,lα >
( )
1
1
,
l
k i
i kk
M m
= +
α > α −
µ ∑
( ) ( )
( ) ( )
,
0 inf
V
k k
k k k
x y X
f x f y
f x f y
∈
≠
< µ ≤ − , 1,2, , 1,k l= −K
( ){ }max | 1,2, , , ,V
iM f x i l x X= = ∈K ( ){ }min | 1,2, , , .im f x i l x X= = ∈K
Теорема 3. Якщо X − обмежений многогранник, то розв’язок задачі ( )P Φ
є розв'язком задачі (3).
Таким чином для розв’язання задачі (3) можна застосовувати методи макси-
мізації опуклої функції на многограннику, наприклад [6, 7].
Висновки. Досліджено деякі властивості векторних лексикографічних задач
оптимізації. Встановлені необхідні та достатні умови існування й оптимальності
лексикографічних розв’язків. Обґрунтовано зведення початкової задачі до ска-
лярної з функціоналом, що є згорткою часткових критеріїв та описано метод
знаходження коефіцієнтів цього функціоналу для лексикографічних задач квад-
ратичної оптимізації. Для розв’язання лексикографічної задачі квадратичної
оптимізації можна застосовувати розроблені методи максимізації опуклої
функції на многограннику.
М.М. Ломага, В.В. Семенов
КВАДРАТИЧНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ:
СВОЙСТВА И РЕШЕНИЯ
Исследованы некоторые свойства векторных лексикографических задач оптимизации. Полу-
чены необходимые и достаточные условия существования и оптимальности лексикографиче-
ских решений. Обосновано сведение исходной задачи к скалярной с функционалом, который
является сверткой частичных критериев. Описан метод нахождения коэффициентов этого
функционала для лексикографических задач квадратичной оптимизации.
М.М. ЛОМАГА, В.В. СЕМЕНОВ
Компьютерная математика. 2013, № 2 144
M.M. Lomaga, V.V. Semenov
QUADRATIC PROBLEMS OF LEXICOGRAPHIC OPTIMIZATION:
PROPERTIES AND SOLVING
Some properties of vectorial lexicographic problems of optimization are explored. The necessary
and sufficient conditions of existence and optimality of lexicographic decisions are got. Taking of
initial problem is grounded to scalar with functional which is rolling up of partial criteria. The
method for finding of coefficients of this functional is described for the lexicographic problems of
quadratic optimization.
1. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач.
– М.: Наука, 1982. − 255 с.
2. Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних
множинах: методи дослідження та розв’язання. – К.: Наук. думка, 2009. – 266 с.
3. Червак Ю.Ю. Оптимізація. Непокращуваний вибір. – Ужгород: Ужгородський націо-
нальний університет, 2002. – 312 с.
4. Еремин И.И. Теория линейной оптимизации. − Екатеринбург: УрО РАН, 1999. − 312 c.
5. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым крите-
риям. – М.: Сов. радио, 1975. – 192 с.
6. Кузка О.І., Ломага М.М. Про один підхід до розв’язання задачі максимізації опуклої
функції на многограннику // Науковий вісник Ужгородського університету. – 2011. – № 2.
– С. 76–80.
7. Стрекаловский А.С. Элементы невыпуклой оптимизации. – Новосибирск: Наука, 2003. –
356 c.
Одержано 20.06.2013
Про авторів:
Ломага Марія Михайлівна,
асистент Ужгородського національного університету,
Е-mail: lomagamarija@yandex.ua
Семенов Віктор Вікторович,
молодший науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України.
Е-mail: hunt.semen@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-84757 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:25:32Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ломага, М.М. Семенов, В.В. 2015-07-14T16:02:34Z 2015-07-14T16:02:34Z 2013 Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання / М.М. Ломага, В.В. Семенов // Компьютерная математика. — 2013. — № 2. — С. 134-143. — Бібліогр.: 7 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84757 519.8 Досліджено деякі властивості векторних лексикографічних задач оптимізації. Встановлені необхідні та достатні умови існування й оптимальності лексикографічних розв’язків. Обгрунтовано зведення початкової задачі до скалярної з функціоналом, що є згорткою часткових критеріїв та описано метод знаходження коефіцієнтів цієї згортки для лексикографічних задач квадратичної оптимізації. Исследованы некоторые свойства векторных лексикографических задач оптимизации. Получены необходимые и достаточные условия существования и оптимальности лексикографических решений. Обосновано сведение исходной задачи к скалярной с функционалом, который является сверткой частичных критериев. Описан метод нахождения коэффициентов этого функционала для лексикографических задач квадратичной оптимизации. Some properties of vectorial lexicographic problems of optimization are explored. The necessary and sufficient conditions of existence and optimality of lexicographic decisions are got. Taking of initial problem is grounded to scalar with functional which is rolling up of partial criteria. The method for finding of coefficients of this functional is described for the lexicographic problems of quadratic optimization. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання Квадратичные задачи лексикографической оптимизации: свойства и решения Quadratic problems of lexicographic optimization: properties and solving Article published earlier |
| spellingShingle | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання Ломага, М.М. Семенов, В.В. Теория и методы оптимизации |
| title | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання |
| title_alt | Квадратичные задачи лексикографической оптимизации: свойства и решения Quadratic problems of lexicographic optimization: properties and solving |
| title_full | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання |
| title_fullStr | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання |
| title_full_unstemmed | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання |
| title_short | Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання |
| title_sort | квадратичні задачі лексикографічної оптимізації: властивості та розв’язання |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84757 |
| work_keys_str_mv | AT lomagamm kvadratičnízadačíleksikografíčnoíoptimízacíívlastivostítarozvâzannâ AT semenovvv kvadratičnízadačíleksikografíčnoíoptimízacíívlastivostítarozvâzannâ AT lomagamm kvadratičnyezadačileksikografičeskoioptimizaciisvoistvairešeniâ AT semenovvv kvadratičnyezadačileksikografičeskoioptimizaciisvoistvairešeniâ AT lomagamm quadraticproblemsoflexicographicoptimizationpropertiesandsolving AT semenovvv quadraticproblemsoflexicographicoptimizationpropertiesandsolving |