Побудовано квадратичну оптимізаційну задачу для знаходження максимального k-плекса у неорієнтованому графі. Наведено 2 сімейства функціонально надлишкових квадратичних обмежень, які отримано за допомогою обмежень Булевої задачі для максимального k-плекса. Досліджено вплив функціонально надлишкових обмежень на покращання точності Лагранжевих двоїстих оцінок для цільової функції квадратичної задачі. Розроблено алгоритм пошуку всіх максимальних k-плексів і наведено результати тестових експериментів для його реалізації за допомогою програмного пакета GLPK (GNU Linear Programming Kit).

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

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

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

Лексикографический подход к решению многокритериальных задач (МКЗ) состоит в строгом ранжировании критериев по относительной важности и позволяет добиться оптимизации более важного критерия за счет любых потерь по всем иным, менее важным критериям. Чаще всего такие МКЗ возникают при последовательном введении дополнительных критериев в обычные скалярные задачи оптимизации, которые могут иметь неединственное решение. Задачи лексикографической оптимизации (ЛГО) возникают также при моделировании иерархических структур, в стохастическом программировании, при решении некоторых задач динамического характера и др. Установлены условия существования решений МКЗ ЛГО с неограниченным выпуклым допустимым множеством и условия оптимальности решений на основе использования свойств рецессивного конуса выпуклого допустимого множества, конуса, лексикографически упорядочивающего допустимое множество относительно критериев оптимизации, и коэффициентами вида локальных шатров, построенных в граничных точках допустимого множества. Приведены свойства лексикографически оптимальных решений. Полученные условия и свойства можно успешно использовать при разработке алгоритмов поиска оптимальных решений указанных задач ЛГО. На основании идей методов линеаризации и отсекающих плоскостей Келли построен и обоснован метод нахождения лексикографически оптимальных решений выпуклых задач ЛГО.

Розглянуто задачу генерування сфероїдних порожнин у тривимірній області, що має складну геометрію з урахуванням обмежень на "розрідженість" розміщення порожнин та умови рівноваги. Задачу зведено до оптимізаційної задачі компонування еліпсоїдів обертання в опуклому контейнері (циліндрі або кубоїді) з урахуванням зон заборони, обмежень на допустимі відстані між еліпсоїдами та умов балансу з метою максимізації мінімальної відстані між кожною парою еліпсоїдів та еліпсоїдом і межею контейнера. Визначено псевдонормалізовані квазі-phi-функції для аналітичного опису обмежень розміщення. Побудовано математичну модель у вигляді задачі нелінійного програмування. Запропоновано метод розв'язання зі стратегією мультистарту, алгоритми пошуку допустимих і локально-оптимальних розв'язків. Наведено результати обчислювальних експериментів.

Розглянуто адаптивний підхід до числового диференціювання важкообчислювальних функцій. Складні залежності, які є результатом багаторазових суперпозицій функцій або різних алгоритмічних процесів, складні для безпосереднього дослідження. Для встановлення характеру поведінки таких залежностей доводиться вдаватися до числового аналізу. Однією з важливих характеристик функцій є похідна, яка вказує напрям і швидкість зміни залежності. Однак при складнообчислювальних функціях наявної апріорно інформації не завжди достатньо, щоб відомими засобами можна було б досягти належної точності розв'язку. Втрата точності відбувається внаслідок накопичення помилок округлення, які зростають пропорційно кількості задіяних значень функції. У цьому випадку доводиться переходити до апостеріорного підходу для того, щоб визначити поведінку функції та відійти від схеми рівновіддалених вузлів, спираючись на адаптивний спосіб вивчення локальної обстановки в області визначення функції. У роботі реалізовано адаптивний метод пошуку похідних функції за мінімуму обмежувальних вимог до класу функцій і форми їх задання. Завдяки цьому значно зменшилися витрати на обчислення функції, в результаті чого кількість обчислень було доведено майже до оптимального рівня. При цьому різко знизився обсяг використовуваної оперативної пам'яті. Немає потреби у проведенні попереднього аналізу зі встановлення класу досліджуваної функції, в залученні спецфункцій або перетворенні початкових умов для використання стандартних таблиць вагових коефіцієнтів і т.п. Для дослідження достатньо задати неперервну і обмежену функцію на фіксованому сегменті і мінімальний крок, якій побічно відповідає за забезпечення необхідної точності диференціювання. Ефективність запропонованого методу демонструється на ряді тестових прикладів. Розроблений метод може бути використано у більш складних задачах, наприклад, при розв'язанні деяких типів диференціальних та інтегральних рівнянь, а також для широкого ряду задач оптимізації в найрізноманітніших областях прикладного аналізу та синтезу.

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

The paper presents a new powerful technique to linearize the quadratic assignment problem. There are so many techniques available in the literature that are used to linearize the quadratic assignment problem. In all these linear formulations, both the number of variables and the linear constraints significantly increase. The quadratic assignment problem (QAP) is a well-known problem whereby a set of facilities are allocated to a set of locations in such a way that the cost is a function of the distance and flow between the facilities. In this problem, the costs are associated with a facility being placed at a certain location. The objective is to minimize the assignment of each facility to a location. There are three main categories of methods for solving the quadratic assignment problem. These categories are heuristics, bounding techniques and exact algorithms. Heuristics quickly give near-optimal solutions to the quadratic assignment problem. The five main types of heuristics are construction methods, limited enumeration methods, improvement methods, simulated annealing techniques and genetic algorithms. For every formulated QAP, a lower bound can be calculated. We have Gilmore-Lawler bounds, eigenvalue related bounds and bounds based on reformulations as bounding techniques. There are four main classes of methods for solving the quadratic assignment problem exactly, which are dynamic programming, cutting plane techniques, branch and bound procedures and hybrids of the last two. The QAP has application in computer backboard wiring, hospital layout, dartboard design, typewriter keyboard design, production process, scheduling, etc. The technique proposed in this paper has the strength that the number of linear constraints increases by only one after the linearization process.

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

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

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

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

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

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

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

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

Розглянуто оптимізаційну задачу з квадратичною функцією цілі та додатковими лінійними обмеженнями на множині сполучень. Запропоновано метод розв'язання такого класу задач. Алгоритм розв'язування враховує специфічні властивості комбінаторної множини сполучень і забезпечує знаходження оптимального розв'язку за лічені кроки. Наведено числовий приклад застосування цього методу.

Запропоновано алгоритм розв'язку задачі оптимізації ціни за допомогою зворотних обчислень. Алгоритм включає 2 етапи: розв'язок задачі безумовної оптимізації та розв'язок зворотної задачі за допомогою зворотних обчислень за мінімізації зміни аргументів функції. У цьому випадку розв'язок зворотного завдання може бути виконано багаторазово протягом заданого числа ітерацій для послідовного наближення до встановленого значення обмеження, а для визначення збільшень аргументів використовуються значення елементів вектора градієнта/антиградієнта функції обмеження. Для врахування впливу аргументів на зміну цільової функції використовуються її другі частні похідні. Розглянуто 5 варіантів завдання оптимізації ціни, які є завданням нелінійного програмування з одним обмеженням. У завданнях враховується залежність попиту від ціни та передбачається, що вона має лінійний вигляд. Як цільову функцію розглянуто виручку підприємства, відхилення попиту від обсягу виробництва, відхилення шуканої ціни від її поточного значення. Показано, що одержувані у цьому випадку розв'язки узгоджуються з результатом використання класичних методів (множників Лагранжа, штрафів), також виконано порівняння результатів із розв'язком задач за допомогою математичного пакету MathCad. Перевагою методу є більш проста комп'ютерна реалізація, можливість отримати розв'язок за менше число ітерацій в порівнянні з відомими методами. Метод можна використати для вирішення інших завдань представленого виду з наступними вимогами до цільової функції та обмежень: частні похідні цільової функції першого порядку - лінійні одновимірні функції; обмеження має вид рівності; обмеження має лінійний вигляд або обмеження має квадратичний вигляд, а частні похідні першого порядку функції обмеження - лінійні одновимірні функції.

Описан численный алгоритм сведения обратных задач статики распределенных протяженных систем в поле массовых и поверхностных сил к задаче нелинейного программирования, для решения которых апробированы численные методы. Изменение размерности решаемой физической задачи не приводит к модификации всего численного алгоритма, а лишь к замене некоторых его блоков. В качестве примеров численного решения задач нелинейного программирования исследованы задачи определения силовых и геометрических характеристик глубинного водозабора АЭС, коэффициента жесткости якорной связи полупогруженной буровой платформы и оценки качества отводителя.