Векторні задачі дискретної оптимізації: коректність та методи розв'язання

45. Семенова Н.В. SP-методы решения минимаксных задач на одном классе невыпуклых множеств / Н.В. Семенова, В.В. Семенов // “Обчислювальна та прикл. математика”. Зб. тез міжн. конф., присв. 80-річчю акад. НАНУ І.І. Ляшка. (9.09 - 10.08. 2002). Київ. 2002. С. 87.

46. Лебедева Т.Т. Некоторые условия оптимальности и разрешимости в задачах линей-ной векторной оптимизации с выпуклой допустимой областью / Т.Т. Лебедева, Н.В. Семенова, Т.И. Сергиенко // Ассоциация матем. прогр. Информ. бюлетень №10, конф. “Математическое программирование и приложения”. Тезисы докл. Екатеринбург: Ин-т математики и механики, Урал. отд. РАН, 2003. С. 170-171.

47. Лебедева Т.Т. Об устойчивости векторных задач целочисленной оптимизации / Т.Т. Лебедева, Н.В. Семенова, Т.И. Сергиенко // Intern. Conf. “Dynamical systems modelling and stability investigation”. Thesis of conf. reports. Kyiv. 2003. P.193.

48. Lebedeva T.T. On stability in integer vector optimization problems / T.T. Lebedeva, N.V. Semenova, T.I. Sergienko // Intern. Summer Seminar “Stochastic Dinamical Systems”. Abstract. Kyiv, Institute of Mathematics of NASU. 2003. P. 51-52.

49. Semenova N.V. Condition of stability of vector discrete optimization problems with quadratic criterion functions / N.V. Semenova, T.T. Lebedeva, T.I. Sergienko // Intern. Workshop “Prediction and decision making under uncertainties”. Abstracts. Ternopil. 2004. P. 49-51.

50. Лебєдєва Т.Т. Деякі умови оптимальності та стійкості в задачах векторної дискретної оптимізації з квадратичними функціями критеріїв / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // ІІ-а міжн. школа-семінар “Теорія прийняття рішень”. Праці. Ужгород. 2004. С. 55-56.

51. Лебєдєва Т.Т. Про топологічні властивості областей стійкості множин вихідних даних задач векторної цілочислової оптимізації з квадратичними функціями критеріїв / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Міжн. конф. “Питання оптимізації обчислень (ПОО-ХХХII). Kиїв. 2005. С. 121.

52. Семенова Н.В. Розв'язання задач цілочислової оптимізації на опуклих множинах в умовах невизначеності даних / Н.В. Семенова // Intern. Ukrainian - Polish Workshop “Problems of stochastic and discrete optimization”. Abstracts. Kyiv.- 2005. P. 90-92.

53. Lebedeva T.T. Stability of optimal and non-optimal sets of solutions to vector discrete optimization problems / T.T. Lebedeva, N.V. Semenova, T.I. Sergienko // International conference “Problems of decision making under uncertainties”. Abstracts. Berdyansk. 2005. P. 34-36.

54. Dolgopolov I.N. New information technologies of control in the clinical medicine / I.N. Dolgopolov, N.V. Semenova // Intern. conference “Problems of decision making under uncertainties”. Abstracts. Berdyansk. 2005. P. 25-26.

55. Семенова Н.В. Про структурні властивості деяких підмножин простору вхідних даних векторних задач цілочислової оптимізації / Н.В. Семенова // Intern. Workshop “Problems of decision making under uncertainties”. Abstracts. Skhidnytsia. 2006. P. 117-120.

56. Семенова Н.В. Оцінка рівня фінансування соціальної інфраструктури за методом рангової домінованості / Н.В. Семенова, В.В. Семенов // Intern. Workshop “Problems of decision making under uncertainties”. Abstracts. Skhidnytsia. 2006. P. 148-150.

57. Семенова Н.В. Метод рангової домінованості та його використання при аналізі бюджетного процесу / Н.В. Семенова, В.В. Семенов // II-а Міжнародна науково-практична конференція “Трансформаційні процеси в економіці держави та регіонів”. Запоріжжя. 2006. С. 132133.

58. Semenova N.V. Optimal and approximate solution to integer optimization problems with convex quadratic constraints / N.V. Semenova // Applied Optimization and Metaheuristic Innovations”: Intern. Conference in Honor of the 70-th Birthday of Academician I.V. Sergienko. Abstracts. Kyiv. 2006. P. 39.

59. Семенова Н.В. Необхідні і достатні умови стійкості за обмеженнями векторних задач цілочислової оптимізації з диз'юнктивними лінійними функціями обмежень / Н.В. Семенова // International Conference “Problems of decision making under uncertainties”. Abstracts. Aluschta. 2006. P. 168-170.

60. Семенова Н.В. О многокритериальной задаче комбинаторной оптимизации на перестановках / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Ассоциация математ. прогр. Инф. бюл. №11, конф. “Математическое программирование и приложения”. Тез. докл. Екатеринбург: Ин-т математики и механики, Урал. отд. РАН, 2007. С. 211-212.

61. Долгополов И.Н. Основные аспекты математического моделирования управляемого диагностического процесса в рамках единого информационного пространства системы здравоохранения / И.Н. Долгополов, Н.В. Семенова // XIII-th. International Conference “Knowledge - Dialogue - Solution“. Proceedings. Sofia. 2007. P. 210-213.

62. Лебєдєва Т.Т. Про п'ять типів стійкості за векторним критерієм і обмеженнями векторної задачі дискретного квадратичного програмування / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Intern. сonf. “Problems of decision making under uncertainties”. Abstracts. Chernivtsy. (May 21-25, 2007). P. 164-165.

63. Семенова Н.В. Умови оптимальності розв'язків багатокритеріальних задач комбінаторної оптимізації на перестановках / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Міжн. Симпозіум “Питання оптимізації обчислень (ПОО-ХХХIII)“. Праці симпозіуму Kиїв. 2007. С. 258.

64. Семенова Н.В. Багатокритеріальні задачі дискретної оптимізації на евклідових комбінаторних множинах / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Intern. Worcshop “Problems of decision making under uncertainties”. Abstracts. Crimea (Novy Svit, September 17-22, 2007). 2007. P. 114-115.

65. Сергієнко І.В. Декомпозиційні методи пошуку розв'язків задач дискретної оптимізації в умовах невизначеності та керованості даними / І.В. Сергієнко, Н.В. Семенова // Intern. Worcshop “Problems of decision making under uncertainties”. Abstracts. (Novy Svit, September 17-22, 2007). 2007. P. 118-119.

66. Семенова Н.В. Про розв'язання задач векторної оптимізації з дробово-лінійними функціями критеріїв на комбінаторній множині перестановок / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Математичне та програмне забезпечення інтелектуальних систем (MPZIS-2007). П'ята міжнародна науково-практична конференція (Дніпропетровськ, 14-16 листопада, 2007). 2007. С. 171-176.

67. Семенова Н.В. Векторні задачі комбінаторної оптимізації з дробово-лінійними функціями критеріїв / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Intern. Conference “Problems of decision making under uncertainties”. Abstracts. Rivne. (May 21-25, 2008). P. 164-165.

68. Sergienko I.V. Discrete optimization of retrial queues in set of multithresholds and hysteresis strategies / I.V. Sergienko, E.О. Lebedev, N.V. Semenova // Discrete and Global Optimization. International Conference in honor of 50-th Anniversary of Glushkov Institute of Cybernetics Abstracts. Yalta. (July 31-August 2, 2008). Kyiv-2008. P. 35-36.

69. Сергієнко І.В. Оптимізація марковських систем з повторними викликами / І.В. Сергієнко, Є.О. Лебєдєв, Н.В. Семенова // Intern. Workshop “Problems of decision making under uncertainties”. Abstracts. Crimea (Novy Svit, September 22-27, 2008). 2008. P. 114-116.

70. Семенова Н.В. Принятие оптимальных решений клинической диагностики в условиях неопределенности / Н.В. Семенова, И.Н. Долгополов // Intern. Workshop “Problems of decision making under uncertainties”. Abstracts. (Novy Svit, September 22-27, 2008). 2008. P. 110-111.

71. Семенова Н.В. Знаходження Парето-оптимальних розв'язків векторних задач комбінаторної оптимизації на множині поліперестановок / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Intern. Workshop “Problems of decision making under uncertainties”. Abstracts. Crimea (Novy Svit, September 22-27, 2008). 2008. P. 112-113.

72. Семенова Н.В. Розв'язання задачі векторної оптимізації з дробово-лінійними функціями критеріїв на комбінаторній множині / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Праці міжн. симпозіуму “Питання оптимізації обчислень” (ПОО-XXXV). Київ: Інститут кібернетики імені В.М. Глушкова НАН України, 2009.2. С. 294 - 299.

73. Семенова Н.В. Багатокритеріальні задачі комбінаторної оптимізації на нечіткій множині альтернатив / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Intern. Conf. “Problems of decision making under uncertainties”. PDMU-2009. Skhidnytsia (April 27-30, 2009). С.170-171.

74. Семенова Н.В. Розв'язання задачі векторної оптимізації з дробово-лінійними функціями критеріїв на комбінаторній множині / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Праці міжнародного симпозіуму “Питання оптимізації обчислень” (ПОО-XXXV). Київ: Інститут кібернетики імені В.М. Глушкова НАН України, 2009.2. С. 294-299.

75. Долгополов И.Н. Построение планов оптимальных диагностических траекторий в компъютерных сетях на основе использования методов многокритериальной оптимизации / И.Н. Долгополов, Н.В. Семенова // Системи підтримки прийняття рішень. Теорія і практика. Збірник доп. науково-практичної конференції з міжнар. участю. Київ: Інститут проблем математичних машин і систем. 2009.2. С. 71-74.

76. Семенова Н.В. Розв'язання задач дискретної оптимізації з дробово-лінійною функцією за умов керованості та невизначеності даними / Н.В. Семенова // Intern. Workshop “Problems of decision making under uncertainties”. Abstracts. (Kamyanets-Podilsky, October 5-9, 2009). 2009. P. 108-109.

АнотаціЯ

Семенова Н.В. Векторні задачі дискретної оптимізації: коректність та методи розв'язання. - Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2010.

Дисертаційна робота присвячена розробці теоретичних основ математичного апарату дослідження коректності та розв'язання різних класів задач дискретної оптимізації за умов багатокритеріальності, можливих збурень, керованості і невизначеності вхідних даних. Дисертація є новим комплексним дослідженням, що розв'язує важливі актуальні наукові проблеми як теоретичного напряму, пов'язані як з якісним аналізом векторних задач дискретної оптимізації: визначенням та дослідженням умов коректності, так і конструктивного: побудови та обґрунтування точних та наближених методів розв'язання різних класів задач цілочислової оптимізації за умов невизначених і керованих даних та векторних задач комбінаторної оптимізації. Розроблено та обґрунтовано поліедральний підхід до розв'язання векторних задач дискретної оптимізації на різних комбінаторних множинах: перестановок, розміщень, поліперестановок, полірозміщень та ін. з лінійними та дробово-лінійними функціями критеріїв. Побудовані та досліджені точні й наближені декомпозиційні методи знаходження гарантуючих і оптимісти-чних розв'язків різних класів задач цілочислової оптимізації з опуклими функціями обмежень в умовах невизначеності даних, які поєднують пошук оптимальних або наближених розв'язків з вирішенням проблеми знаходження невизначених даних моделi. Встановлено критерії допустимості та оптимальності розв'язків. Досліджено деякі класи множин невизначеності, що описують вхідні дані розглянутих задач.

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

АННОТАЦИЯ

Семенова Н.В. Векторные задачи дискретной оптимизации: корректность и методы решения. - Рукопись.

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.01- теоретические основы информатики и кибернетики. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2010.

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

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

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

Основные научные результы диссертации состоят в следующем.

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

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

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

Исследованы сложные задачи дискретной оптимизации с неточно заданными коэффициентами целевой функции и выпуклыми функциями ограничений.

Рассмотрены некоторые классы множеств неопределенности, описывающих исходные данные задач, при которых такие задачи могут быть сформулированы как задачи с точно заданными данными.

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

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

SUMMARY

Semenova N.V. Vector problems of discrete optimization: correctness and methods of solution. - Manuscript.

Thesis submitted for a Doctor's degree of physics and mathematics by speciality 01.05.01 - theoretical bases of informatics and cybernetics. - V.M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, 2010.

The thesis is devoted to the problems of development of the new mathematical models and methods used to solving of discrete and combinatorial vector optimization problems. Theoretical bases development of mathematical tools for research of well-posedness and solution methods of discrete optimization problems with conditions of multi-objective, possible perturbations, controllability and uncertainty of initial data are offered.

The purpose of thesis is development and ground of new mathematical models, exact and approximate methods of solution of different vector problems classes of discrete optimization with the conditions of definiteness and discrete optimization problems with the conditions of uncertainty, of controllability and ambiguously set information with different principles of optimality, and also working out problems of quantitative nature: research of well-posedness and stability of vector discrete optimization problems with conditions of possible perturbations of initial data.

The thesis establishes the necessary and sufficient conditions of existence for various kinds of efficient solutions of vector optimization problems with an unbounded convex closed feasible set. The research is based on applying of properties of recessive cones of feasible set and cones of perspective directions of optimization problems. Stability with respect to vector criterion and with respect to constraints for different classes of vector problems of discrete optimization is investigated. Conditions of optimality for different types of solutions are proved. The topological properties of sets of initial data for discrete optimization problem with a vector criterion are investigated.

Keywords: discrete optimization, combinatorial sets, vector criteria, well-posedness, stability, inexact data, controlled data, perturbations of initial data, approximate algorithms, integer variables.

Размещено на Allbest.ru