Укр
Eng
Журнал
Автору

Лексикографічні задачі опуклої оптимізації: умови розв’язуваності та оптимальності, метод відсікаючих площин

УДК 519.8

Volume 66, Issue 1, 2021, pages 30-40

DOI: https://doi.org/10.34229/0572-2691-2021-1-3

Завантажити статтю

Семенова Наталя Володимирівна, доктор фізико-мате­матичних наук, провідний науковий співробітник, старший науковий співробітник Институту кібернетики ім. В.М. Глушкова НАН України, Київ

Ломага Марія Михайлівна, старший викладач Ужгородського національного університету

Семенов Віктор Вікторович, молодший науковий співробітник Институту кібернетики ім. В.М. Глушкова НАН України, Київ

Abstract

Лексикографічний підхід до розв'язання багатокритеріальних задач полягає в строгому ранжируванні критеріїв за відносною важливістю і дозволяє домог­тися оптимізації більш важливого критерію за рахунок будь-яких втрат за всіма іншими менш важливими критеріями. Найчастіше такі багатокритеріальні задачі виникають при послідовному введенні додаткових критеріїв у звичайні скалярні задачі оптимізації, які можуть мати не єдиний розв'язок. Задачі лек­сикографічної оптимізації виникають також при моделюванні ієрархічних структур, у стохастичному програмуванні, при розв'язанні деяких задач дина­мічного характеру тощо. В даній статті отримано умови існування розв’язків багатокритеріальних задач лексикографічної оптимізації з необмеженою опук­лою допустимою множиною та умови оптимальності розв’язків на основі використання властивостей рецесивного конусу опуклої допустимої множини, конусу, що лексикографічно упорядковує допустиму множину щодо критеріїв оптимізації, та локальних шатрів, побудованих у граничних точках допустимої множини. Наведено властивості лексикографічно оптимальних розв’язків. Отримані умови та властивості можна успішно використовувати при розробці алгоритмів пошуку оптимальних розв’язків зазначених задач лексикографічної оптимізації. На основі ідей методів лінеаризації та відсікаючих площин Келлі побудовано та обґрунтовано метод знаходження лексикографічно оптимальних розв’язків опуклих задач лексикографічної оптимізації.

REFERENCES

  1. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым крите-риям. М. : Сов. радио, 1975. 192 с.
  2.  Червак Ю.Ю. Оптимізація. Непокращуваний вибір. Ужгород: Ужгородський національний університет, 2002. 312 с.
  3. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. 2-е изд., испр. и доп. М. : Физматлит, 2007. 256 с.
  4.  Ломага М.М., Семенов В.В. Квадратичные задачи лексикографической оптимизации: свой-ства и решения. Компьютерная математика. 2013. № 2. С. 134−143.
  5. Семенова Н.В., Ломага М.М., Семенов В.В. Алгоритм решения многокритериальных задач лексикографической оптимизации с выпуклыми функциями критериев. International Journal «Information Theories and Applications». 2014. 21, N 3. P. 254−262.
  6. Ломага М.М. Розв’язання задач лексикографічної оптимізації з лінійними функціями крите-ріїв на опуклій множині. Науковий вісник Ужгородського університету. Сер. матем. і ін-форм. 2015. № 2 (27). С. 66−72.
  7.  Ломага М.М., Семенова Н.В. Квадратичні лексикографічні задачі оптимізації і відображен-ня Лагранжа. Науковий вісник Ужгородського університету. Сер. матем. і інформ. 2019. № 2 (35). С. 127−133.
  8. Рокафеллар Р. Выпуклый анализ. М. : Мир, 1973. 470 с.
  9. Болтянский В.Г. Метод шатров в теории экстремальных задач. Успехи математических наук. 1975. 30, № 3(183). С. 3–55.
  10.  Kelley I.E. The cutting plane method for solving convex programs. SIAM J. 1960. 8. P. 703–712.
  11. Сергиенко И.В., Козерацкая Л.Н., Лебедева T.T. Исследование устойчивости и параметри-ческий анализ дискретных оптимизационных задач. Киев : Наук. думка, 1995. 171 с.
  12. Сергиенко И.В., Козерацкая Л.Н., Кононова А.А. Устойчивость и неограниченность задач векторной оптимизации. Кибернетика и систем. анализ. 1997. № 1. С. 3–10.
  13. Sergienko I.V., Lebedeva T.T. & Semenova N.V. Existence of solutions in vector optimization problems. Cybernetics and Systems Analysis. 2000. 36, N 6. P. 823-828.
  14. Сергiєнко Т.I. Про iснування парето-оптимальних розв’язкiв задачi векторної оптимiзацiї з необмеженою допустимою областю. Доповiдi НАН України. 2015. № 10. С. 27−31.
  15.  Лебєдєва Т.Т., Семенова Н.В., Сергiєнко Т.I. Умови оптимальностi та розв’язуваностi в за-дачах лiнiйної векторної оптимiзацiї з опуклою допустимою множиною. Доповiдi НАН України. 2003. № 10. С. 80–85.
  16.  Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М. : Наука, 1980. 320 с.