Контакти Карта сайту

Відділ методів дискретної оптимізації, математичного моделювання та аналізу складних систем (Н.І. Тукалевська)

 

Завідувач відділу - Тукалевська Нелля Іванівна, кандидат фізико-математичних наук, старший науковий співробітник.

 

Відділ заснований у 1965 р. (Постанова Президії АН УРСР №199 від 22.07.1965р.) академіком НАН України Сергiєнком Іваном Васильовичем. З 1999 р. по 17.02.2014 р. відділ очолював Дейнека Василь Степанович, академік НАН України, професор, доктор фізико-математичних наук.  

 

1. Наукові напрями відділу:

 

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

 

2. Поточні дослідження, проблеми, задачі, що вирішуються.

 

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

 

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

 

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

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

 

Дослідження, що стосуються розвинення теоретичних засад системного аналізу багатокомпонентних середовищ та реалізація їх в нових інформаційних технологіях (в тім числі таких, що функціонують на обчислювальних комплексах PENTIUM-суперкомп’ютер СКІТ). Застосування створених інформаційних технологій до розв’язання нових складних практичних задач.

 

Розробка комп’ютерних технологій для дослідження соціально-економічних процесів на пізніх стадіях ринкових реформ.

 

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

 

3. Основні наукові та практичні результати відділу, експонати (у т.ч. ІТ), що можуть бути продемонстровані на виставках.

 

Співробітники відділу - вчені наукової школи під керівництвом академіка HAH України І.В. Сергієнка - внесли вагомий вклад у розвиток дискретної оптимізації та системного аналізу багатокомпонентних розподілених систем. Оскільки більшість прикладних задач дискретного програмування, що виникають при прийнятті оптимальних економічних, проектних і технологічних рішень, є NP-складними, властиві їм труднощі вимагають розробки і обґрунтування ефективних підходів до їх розв'язання.

 

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

 

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

 

Створено теоретичні основи для прискорення процесу розв'язання складних задач дискретної оптимізації. Зокрема, розроблено РЕСТАРТ-технологію, яка базується на використанні нових понять РЕСТАРТ-розподілу і РЕСТАРТ-критерію зупину алгоритму та дозволяє істотно зменшити час розв'язання задач.

 

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

 

На основі виконаних теоретичних досліджень та розпаралелювання операцій вдалося розв'язати важливі практичні задачі побудови повадозахищених кодів максимального об'єму. Зазначимо, що світовий рівень досягнень у цій галузі відображається, наприклад, на сайті http://www.research.att.eom/.nias/doc/graphs.html (науково-дослідний центр інформатики AT&T Labs, Нью-Джерсі, США).

 

Вперше отримано повадозахищені коди максимального об'єму для графів Itc512 (об'єм 110), 1ІСІ024 (об'єм 196), Itc2048 (об'єм 352), let 1024 (об'єм 171), Iet2048 (об'єм 316), Izc4096 (об'єм 379), Izc8192 (об'єм 701), для графів Izc з кількістю вершин 2W, n = 14-25. Вперше точно розв'язано задачу знаходження повадозахищеного коду максимального об'єму для графів Idc512, Itc512, Iet512, Ietl024, Izcl024. Перераховані графи, взяті із вказаного сайту, є вихідними даними для актуальних нерозв'язаних задач. Отримані повадозахищені коди максимального об'єму передано в науково-дослідний центр інформатики AT&T Labs (Нью-Джерсі, США).

 

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

 

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

 

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

 

Для розв`язання задач комбінаторної оптимізації із різних класів запропоновані метод прискореного імовірнісного моделювання (G-алгоритм), що належить до класу стохастичних методів локального пошуку, та дискретний метод деформованого многогранника, який реалізує оригінальну стратегію глобального пошуку у просторі розв`язків задач оптимізації. На основі поєднання переваг розроблених алгоритмів запропоновані нові метаевристичні (гібридні) алгоритми комбінаторної оптимізації. Досліджені умови їх ефективної реалізації як на комп`ютерах з традиційною архітектурою, так і на багатопроцесорних обчислювальних комплексах, зокрема, суперкомп`ютері СКІТ. Теоретичні висновки підтверджені результатами проведених обчислювальних експериментів та розв`язанням задач оптимізації рішень в різних сферах застосуваннь.

 

В напрямку наукових досліджень, що стосуються системного аналізу багатокомпонентних розподілених систем, побудовані математичні моделі основних процесів, що характерні для багатокомпонентних ґрунтових середовищ, що вміщують довільно розташовані у просторі тонкі прошарки та включення природного та штучного походжень як нові класи крайових та початково-крайових задач в частинних похідних з розривними розв’язками.

 

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

 

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

 

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

 

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

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

 

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

 

На основі побудованого за цією методологією математичного апарату створено програмний пакет Nadra-3D, призначений для чисельного розв’язання за методом скінченних елементів стаціонарних та нестаціонарних задач фільтрації, теплопровідності, теорії пружності в багатокомпонентних середовищах (в тривимірних постановках). Пакетом підтримуються різні алгоритми розв’язання результуючих систем лінійних алгебраїчних рівнянь з великим числом невідомих (порядки систем – 10– 107 невідомих), які використовують паралельні обчислення та обчислення на графічних процесорах. В якості обчислювального ресурсу можливе використання як персональних комп’ютерів, так і багатопроцесорних кластерних комплексів, зокрема – кластерних комплексів сімейства СКІТ Інституту кібернетики імені В.М. Глушкова НАН України.

 

Програмний пакет Nadra-3D використовується в роботах з оцінки запасів підземних вод регіонів України, що виконуються спільно з фахівцями Інституту геологічних наук НАН України.

 

У відділі ведуться роботи з математичного моделювання та ідентифікації параметрів складних фізичних об’єктів, що зазнають значних силових та температурних впливів. Такі проблеми виникають при проектуванні складних сучасних споруд (атомних реакторів, космічних об’єктів, об’єктів машинобудування, енергетики, цивільного та промислового будівництва, тощо) та при розв’язуванні задач продовження їх ресурсів.

 

Персональний склад наукових працівників відділу методів дискретної оптимізації, математичного моделювання та аналізу складних систем (№135)

 

 

ПIБ Посада

 Науковий 

ступінь 

 Вчене 

 звання 

Контакти

 Аралова Альбіна Андріївна

м.н.с.

к.ф.-м.н.

 

 (044) 526-15-89

 Білоус Максим Володимирович

c.н.с.

к.ф.-м.н.

 

 (044) 526-15-89

 Боярчук Дмитро Олексійович

н.с.

 

 

 (044) 526-22-60

 Вагіс Олександра Анатоліївна

с.н.с.

д.ф.-м.н.

 с.н.с.

 (044) 526-22-60

 Васильчук Світлана Петрівна

м.н.с.

 

 

 (044) 526-37-61

 Вєщунова Наталія Анатоліївна

с.н.с.

к.ф.-м.н.

 

 (044) 526-15-89

 Галба Євген Федорович

с.н.с.

д.ф.-м.н.

с.н.с.

 (044) 526-15-89

 Гупал Микита Анатолійович

н.с.

 

 

 (044) 526-22-60

 Лебедєва Тетяна Тарасівна

с.н.с.

к.ек.н.

с.н.с.

 (044) 526-22-60

 Митропан Оксана Іванівна

гол.ін.-пр.

 

 

 (044) 526-22-60

 Мороз Валерій  Костянтинович

гол.ін.-пр.

 

 

 (044) 526-22-60

 Нориця Ольга Луківна

м.н.с.

 

 

 (044) 526-22-60

 Парасюк Оксана Степанівна

пр.ін.-пр.

 

 

 (044) 526-15-89

 Пепеляєва Ольга Петрівна

м.н.с.

 

 

 (044) 526-22-60

 Рощин Валентина Олексіївна

с.н.с.

к.ф.-м.н.

с.н.с.

 (044) 526-22-60

 Семенов Віктор Вікторович

м.н.с.

 

 

 (044) 526-22-60

 Семенова Наталія  Володимирівна

п.н.с.

д.ф.-м.н.

с.н.с.

 (044) 526-22-60

 Сергієнко Іван Васильович

г.н.с.

д.ф.-м.н.

проф.

 (044) 526-37-61

 Сергієнко Тетяна Іванівна

с.н.с.

к.ф.-м.н.

с.н.с.

 (044) 526-22-60

 Сіяниця Надія Миколаївна

гол.ін.-пр.

 

 

 (044) 526-15-89

 Тукалевська Нелля Іванівна

зав. від.

к.ф.-м.н.

с.н.с.

 (044) 526-15-89

 Шило Володимир  Петрович

п.н.с.

д.ф.-м.н.

с.н.с.

 (044) 526-22-60,

 aic@public.icyb.kiev.ua

 Шило Петро Володимирович м.н.с.    

 (044) 526-22-60

 Цибенко Маріанна Василівна пр.ін.-пр.    

 (044) 526-15-89

 

 

 

 

Пошук
 
Пошта

 
 3d принтери та станки з ЧПУ в Україні