РОЗДІЛ 2
РІЗНІ ТИПИ СТІЙКОСТІ ЗА ВЕКТОРНИМ КРИТЕРІЄМ ЗАДАЧ
ЦІЛОЧИСЛОВОЇ ТА ЧАСТКОВО ЦІЛОЧИСЛОВОЇ ОПТИМІЗАЦІЇ
З ЛІНІЙНИМИ ЧАСТКОВИМИ КРИТЕРІЯМИ.
РЕГУЛЯРИЗАЦІЯ ЗА ВЕКТОРНИМ КРИТЕРІЄМ
2.1. Стійкість за векторним критерієм багатокритеріальної задачі цілочислової оптимізації з лінійними частковими критеріями
Розглянемо наступну задачу векторної оптимізації з лінійними частковими критеріями
(2.1)
де - матриця коефіцієнтів всіх часткових лінійних критеріїв оптимальності ; кількість часткових критеріїв; ; , , ; для будь-якого натурального числа ; Х - непорожня множина в яка містить не менше двох елементів.
Означимо ряд понять [71, 76 110], необхідних для подальшого викладення одержаних результатів.
Означення 2.1. Точка називається ефективним (або оптимальним за Парето) розв'язком задачі якщо
Множину всіх ефективних розв'язків задачі , що зветься множиною Парето, позначимо а саму задачу у конкретному випадку пошуку елементів множини Парето - .
Означення 2.2. Точка називається слабо ефективним (напівефективним або оптимальним за Слейтером) розв'язком задачі якщо
Позначимо множину всіх слабо ефективних розв'язків (множину Слейтера) задачі . (Зауважимо, що для однокритеріальної задачі, тобто при , множина Парето співпадає з множиною Слейтера і називається, звичайно, множиною оптимальних розв'язків). Задачу у випадку, коли відшукуються елементи множини , будемо позначати .
Згідно з [71] скінченність непорожньої множини Х є достатньою умовою існування Парето-оптимальних розв'язків векторної задачі і зовнішньої стійкості множин Парето і Слейтера. Нагадаємо, що множина () називається зовнішньо стійкою, якщо для будь-якого (відповідно ) знайдеться такий розв'язок (відповідно ), для якого (відповідно). Проте за умови нескінченності допустимої області Х множини Парето і Слейтера можуть не бути зовнішньо стійкими і, взагалі, можуть бути порожніми. За теоремою В.В. Подиновського [71] множина Парето є непорожньою і зовнішньо стійкою, якщо допустима множина Х задачі є непорожньою, замкненою і обмеженою, а вектор-функція задачі - напівнеперервною зверху (покомпонентно) на Х.
Означення 2.3. Точка називається строго ефективним (або оптимальним за Смейлом) розв'язком задачі якщо
Множину всіх строго ефективних розв'язків задачі яка називається множиною Смейла, позначимо , а задачу пошуку таких розв'язків - .
Очевидно, справедливі включення
(2.2)
Аналіз стійкості задачі до збурень вхідних даних у векторному критерії, тобто до збурень елементів матриці будемо проводити з урахуванням властивостей конуса перспективних напрямків задачі [76]:
Очевидно, що перехід з довільної точки у будь-яку точку , де х - точка конуса , приводить до нерівності тобто до можливого зростання значень всіх часткових критеріїв задачі.
Введемо до розгляду також
- лінійну підмножину конуса K,
- внутрішність конуса K і такі допоміжні множини
які можна визначити для будь-якої точки Очевидно,
(2.3)
Враховуючи означення 2.1 - 2.3, приходимо до висновку, що для будь-якого справедливі наступні твердження:
(2.4)
Тут і далі для будь-якого натурального числа q q-вимірний дійсний векторний простір будемо розглядати як нормований. Норму в задамо формулою
, (2.5)
де , . Під нормою деякої матриці будемо розуміти норму вектора Нагадаємо [47], що у скінченно-вимірному просторі будь-які дві норми , еквівалентні, тобто існують такі числа і , що виконуються нерівності
Враховуючи цю еквівалентність, зауважимо, що викладені далі результати справедливі і для інших норм у скінченно-вимірних просторах, які будуть розглянуті.
Для матриці і довільного числа визначимо множину збурених матриць як -окіл точки С у просторі вхідних даних векторного критерія:
Очевидно, що Позначимо і-й рядок збуреної матриці , .
Задачу , де - збурена матриця з околу , назвемо збуреною (за векторним критерієм) задачею.
Введемо таке додаткове обмеження стосовно множини Х допустимих розв'язків задачі (2.1): нехай Х - обмежена множина в , де множина всіх цілочислових векторів з простору . Отже, Х - скінченна множина.
Дослідимо різні варіанти означення стійкості цілочислової задачі пошуку Парето-оптимальних розв'язків до збурень вхідних даних її векторного критерію, тобто до збурень елементів матриці С.
Означення 2.4. Задачу назвемо -стійкою за векторним критерієм, якщо існує таке число , що для будь-якої збуреної матриці справджується нерівність
Даний тип стійкості пов'язаний з існуванням такого околу початкових даних задачі , для кожної збуреної матриці з якого відповідна збурена задача хоча і може мати нові Парето-оптимальні розв'язки у порівнянні із початковою задачею , але напевно має хоча б один ефективний розв'язок (не обов'язково один і той самий для всіх збурених задач з ), що зберігає оптимальність за Парето, притаманну йому як розв'язку початкової задачі.
Відмітимо, що поняття -стійкості за векторним критерієм під назвою "сильної стійкості" вперше було введено В.К. Леонтьєвим у роботі [62] для однокритеріальних лінійних дискретних задач, а для цілочислової задачі з багатьма критеріями було вивчено В.О. Ємелічевим та його учнями. Справедливе наступне твердження, доведення якого міститься в [99, 112].
Теорема 2.1. Будь-яка задача , де Х - обмежена множина в , є -стійкою за векторним критерієм.
Означення 2.5. Задачу назвемо -стійкою за векторним критерієм, якщо існує таке число , для якого справедлива нерівність
Другий тип стійкості векторної задачі характеризує той випадок, коли існує такий окіл її початкових даних, що для кожної збуреної задачі з матрицею коефіцієнтів векторного критерію з цього околу хоча й можлива втрата деяких Парето-оптимальних розв'язків з множини Парето задачі , але принаймні один з них збереже оптимальність за Парето для всіх в