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

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

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

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

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

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

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

Індекс рубрикатора НБУВ: В173.115

Рубрики:

Геометричне програмування

Шифр НБУВ: Ж14024 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.115

Рубрики:

Геометричне програмування

Шифр НБУВ: Ж29114 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.115

Рубрики:

Геометричне програмування

Шифр НБУВ: Ж15477 Пошук видання у каталогах НБУВ 

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

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

Досліджено збіжність методу розв'язку задачі геометричного програмування з одним вимушеним обмеженням. Запропонований алгоритм можна використати для пошуку хімічної рівноваги ідеальної системи газів.

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

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

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

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

  Скачати повний текст

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

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