Напрями досліджень Проекти Кластер ІК

 

Завідувач відділу - Дейнека Василь Степанович, академік НАН України з 2006р., професор (1995р.), доктор фізико-математичних наук (1991р.).

 

 

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

 

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

 

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

 

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

 

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

 

Побудовані математичні моделі та ефективні чисельні методи їх дискретизації: склали теоретичну основу проблемних складових створених у відділі автоматизованих систем НАДРА, НАДРА-Д, НАДРА–3D, відповідно, автоматизованого комп’ютерного моделювання процесів руху рідини, дифузії тепла, в 2-во вимірних схематизаціях досліджуваних багатокомпонентних об’єктів та їх механічного деформування; НАДРА-3D –моделювання зазначених процесів в реальних 3-вимірних (просторових) постановках (функціонує на комплексі PENTIUM-СКІТ).

 

За допомогою комплексу НАДРА–3D та обчислювального комплексу PENTIUM-СКІТ вперше в просторовій постановці розв’язана задача аналізу динаміки підземних вод Київської промислово-міської агломерації до та в процесі інтенсивної експлуатації водоносних горизонтів.

 

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

 

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

 

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

 

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

 

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

 

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

 

Відомості про гранти від міжнародних програм та фондів

 

№	Назва проекту	Джерело фінансування	Український керівник проекту	Установи-партнери	Термін виконання
1	Математичне та програмне забезпечення оптимального проектування структур надійних мереж	Європейський союз	Н.З. Шор		2001- 2004рр.
2	Алгоритми виявлення клік із застосуванням до біомедичної техніки	ФЦДР США	І.В. Сергієнко	Університет Флориди, США	2004- 2006рр.
3	Інформаційна технологія інтелектуального аналізу великих масивів даних на основі ефективних алгоритмів дискретного програмування	Європейський союз	В.П. Шило		2007- 2009рр.
4	G031127 «Інтегрована система для моделювання катастрофічних повеней та мінімізації ризику: застосування до річок Тиса (Україна) та Ріоні (Грузія)	НТЦ	В.І. Норкін	Тбіліський університет, Грузія	2005- 2006рр.
5	Розробка ефективних GRID – технологій екологічного моніторингу на основі супутникових даних №3872	УНТЦ, Національна академія наук України	Н.М. Куссуль	Інститут космічних досліджень НКА та НАН України	2006- 2007рр.
6	Розробка Grid-технологій інтеграції даних різної природи. Створення моделей та методів аналізу процесів в багатокомпонентних середовищах	УНТЦ, Національна академія наук України	Н.М. Куссуль	Інститут космічних досліджень НКА та НАН України	2008- 2009рр.

 

 

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

 

 

ПIБ	Посада	Науковий  ступінь	Вчене   звання	Контакти
Білоус Максим  Володимирович	м.н.с.			526-15-89
Боярчук Дмитро  Олексійович	н.с.			526-74-18
Буряков Володимир  Григорович	головний інженер- програміст			526-14-03
Вагіс Олександра  Анатоліївна	с.н.с.	к.ф.-м.н.		526-15-11
Васильчук Світлана  Петрівна	м.н.с.			526-37-61
Вєщунов Валентин  Володимирович	провідний інженер- програміст			526-15-89
Вєщунова Наталія  Анатоліївна	с.н.с.	к.ф.-м.н.		526-15-89
Галба Євген  Федорович	п.н.с.	д.ф.-м.н.	с.н.с.	526-15-89
Гуляницький Леонід  Федорович	п.н.с.	д.ф.-м.н.	с.н.с.	526-15-89
Дейнека Василь  Степанович	завідувач відділу	д.ф.-м.н.	проф.	526-06-37,  dejneka@public.icyb.kiev.ua
Кошлай Людмила  Богданівна	с.н.с.	к.ф.-м.н.	с.н.с.	526-15-89
Лебедєва Тетяна  Тарасівна	с.н.с.	к.ек.н.	с.н.с.	526-15-11
Малишко Сергій  Олексійович	с.н.с.	к.ф.-м.н.		526-15-89
Митропан Оксана  Іванівна	головний інженер- програміст			526-15-11
Михалевич Михайло  Володимирович	п.н.с.	д.ф.-м.н.	проф.	526-15-89
Мороз Валерій  Костянтинович	провідний інженер- програміст			526-74-18
Назимко Юлія  Олександрів	провідний інженер- програміст			526-15-89
Нориця Ольга  Луківна	м.н.с.			526-15-11
Норкін Богдан  Володимирович	н.с.	к.ф.-м.н.		526-74-18
Нощенко Ольга  Едуардівна	с.н.с.	к.ф.-м.н.		526-15-89
Парасюк Оксана  Степанівна	провідний інженер- програміст			526-15-89
Пепеляєва Ольга  Петрівна	м.н.с.			526-15-11
Рощин Валентина  Олексіївна	с.н.с.	к.ф.-м.н.	с.н.с.	526-15-89
Рясна Ірина Іванівна	н.с.			526-21-28
Сапко Олексій  Володимирович	м.н.с.			526-15-89
Сахно Галина  Антонівна	провідний інженер- програміст			526-15-89
Семенова Наталія  Володимирівна	с.н.с.	к.ф.-м.н.	с.н.с.	526-15-11
Сергієнко Іван  Васильович	г.н.с.	д.ф.-м.н.	проф.	526-37-61,  aic@public.icyb.kiev.ua
Сергієнко Тетяна  Іванівна	н.с.	к.ф.-м.н.		526-15-11
Сіяниця Надія  Миколаївна	головний інженер- програміст			526-15-89
Скукіс Ірина  Григорівна	н.с.			526-14-03
Скукіс Олексій  Євгенійович	н.с.			526-14-03
Стецюк Марія  Григорівна	мат. І кат.			526-15-11
Тукалевська Нелля  Іванівна	с.н.с.	к.ф.-м.н.	с.н.с.	526-15-89
Ходзінський  Олександр  Миколайович	с.н.с.	к.ф.-м.н.	с.н.с.	526-22-34,  ho@cyber.kiev.ua
Шило Володимир  Петрович	п.н.с.	д.ф.-м.н.	с.н.с.	526-74-18,  aic@public.icyb.kiev.ua