Методи розв’язування екстремальних задач на комбінаторних конфігураціях

Размещено на http://allbest.ru

Методи розв'язування екстремальних задач на комбінаторних конфігураціях

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

структурування комбінаторний конфігурація конфігурація

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

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

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

На сьогоднішній день в області дослідження різних класів комбінаторних моделей і розробки нових методів їх розв'язання отримані істотні результати. Вагомий внесок у розвиток дискретної та комбінаторної оптимізації зробили такі закордонні учені: М. Гері, Д. Джонсон, X. Пападимитріу, К. Стайгліц, Р. Стенлі, Ф. Харарі, В.О. Ємелічев, В.М. Сачков, а також учені України: В.С. Михалевич, І.В. Сергієнко, Г.П. Донець, О.О. Ємець, В.О. Перепелиця, Ю.Г. Стоян, С.В. Яковлев, Н.З. Шор та багато інших.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України в відділі економічної кібернетики у відповідності з планами науково-дослідної роботи інституту та згідно індивідуального плану підготовки докторанта. Проведені дослідження виконувалися в рамках держбюджетних тем «Розробка моделей прогнозування структурних змін в економіці України» (номер теми за перспективним тематичним планом В.П. 110.11, № держреєстрації 0108U000279, виконувалася за постановою бюро відділення інформатики НАН України від 10.05.2007); «Розробка тематичних основ для створення паралельних ефективних алгоритмів розв'язання задач на графах великого об'єму» (номер теми за перспективним тематичним планом В.Ф. 110.10, № держреєстрації 0107U000797, виконувалася за постановою бюро відділення інформатики НАН України від 08.06.2006).

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

Для досягнення мети в роботі поставлені такі основні задачі:

- дослідження властивостей комбінаторних конфігурацій та побудова на основі цього графів конфігурацій;

- розробка методу упорядкування значень лінійної функції на комбінаторній конфігурації перестановок;

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

- побудова нових методів генерування комбінаторних об'єктів та загальної схеми методу направленного структурування для розв'язування задач на комбінаторних конфігураціях;

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

- розробка та реалізація нових методів розв'язання задач багатокритеріаль_

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

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

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

Методи дослідження - використовувалися для дослідження екстремаль_

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

Наукова новизна отриманих результатів, що виносяться до захисту, полягає у наступному:

· уперше розроблено нові методи генерування комбінаторних об'єктів: рекурсивний метод та метод переміщення максимального елемента, побудовано графи комбінаторних конфігурацій з використанням цих методів;

· уперше розроблено та досліджено властивості графів комбінаторних конфігурацій: гамільтоновість переставного многогранника при виконанні певних умов; застосовано властивості графів до розв'язування екстремальних комбінаторних задач;

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

· дістав подальший розвиток новий метод направленого структурування для розв'язування екстремальних задач з лінійними та дробово-лінійними цільовими функціями;

· побудовано загальну схему методу направленого структурування до розв'язування екстремальних задач з додатковими обмеженнями;

· уперше запропоновано постановку багатокритеріальної задачі оптимізації на комбінаторних конфігураціях та вивчено її властивості;

· розвинено метод направленого структурування до розв'язування екстремальних задач при наявності багатокритеріальності;

· уперше сформульовано і доведено ряд властивостей області допустимих розв'язків задачі з багатьма критеріями;

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

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

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

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи, яка подається до захисту, отримані автором особисто, сім робіт опубліковано без співавторів. У працях, що написані в співавторстві, дисертанту належать такі: [2] - розробка алгоритму і його теоретичне обґрунтування для задач багатокритеріальної оптимізації з використанням графів, постановка задач багатокритеріальної оптимізації на комбінаторних множинах, ідея обґрунтування, співавтору - дослідження та використання алгоритмів для розв'язування задач багатокритеріальної оптимізації; [3] - співавтору належить постановка задачі, встановлення властивостей та їх теоретичне обґрунтування, а дисертант розробив алгоритм, здійснив його програмну реалізацію та тестування; [4-6] - дисертанту належать обгрунтування задачі та розробка підходу до розв'язування задачі, дослідження властивостей, а співавтору постановка задачі, вибір напряму дослідження; [7] -автором доведено нові теоретичні положення про використання властивості комбінаторних конфігурацій при розв'язанні екстремальних задач комбінаторної оптимізації, співавтор встановив взаємозалежність у графах комбінаторних конфігурацій та їх використання при розв'язанні задач; [8, 9, 14, 15] - дисертанту належать постановка задачі та обґрунтування властивостей, а співавтор розробив алгоритми, здійснив програмну реалізацію та тестування, дослідив нові властивості задачі; [16-22] - дисертанту належать постановка задачі та дослідження нових властивостей області допустимих розв'язків, а співавторам - розробка підходу до розв'язування задачі, розробка алгоритмів, їх обґрунтування та дослідження; [23] - дисертанту належить постановка задачі, розробка підходу до розв'язування задачі, співавтору - розробка моделей, їх дослідження; [25] - автором зроблена постановка задачі та доведено нові теоретичні положення про використання властивості комбінаторних множин при розв'язанні задач комбінаторної оптимізації, [26] - автором розроблено нову математичну модель, співавтором - побудова алгоритму; [27] - автору належать побудова та реалізація алгоритмів, співавтору - постановка задачі та її обґрунтування; [29] - автору належить постановка задачі та її обґрунтування, співавтору - аналіз методів розв'язання задачі та вибір кращого.

Апробація результатів дисертації. Основні результати та положення дисертаційної роботи доповідалися і обговорювалися та отримали схвалення на наукових семінарах, симпозіумах, конференціях, серед яких: Міжнародний симпозіум «Питання оптимізації обчислень (ПОО-XXXV)», Інститут кібернетики імені В.М. Глушкова НАН України (Крим, Велика Ялта, смт. Кацивелі, 2009); 3-я Міжнародна науково-технічна конференція «Комп'ютерна математика в науці, інженерії та освіті. - CMSEE-2009» (Україна, Полтава, 2009); Міжнародна конференція «Математическое программирование и приложения» (Екатеринбург, 2007); Міжнародна конференція «International Conference PROBLEMS OF DECISION MAKING UNDER UNCERTAINTIES» (PDMU - 2003, 2005, 2006, 2007, 2008, 2009); Міжнародна конференція «Математичне та програмне забезпечення інтелектуальних систем» (MPZIS - 2007) (Дніпропетровськ); 9-а Міжнародна наукова конференція імені академіка М. Кравчука (Київ, 2006); Міжнародна конференція «XIII-th, XIV-th, XV-th International Conference Knowledge-Dialogue-Solution» ( Varna, Bulgaria, 2007, 2008, 2009); Міжнародна науково-технічна і методична конференція «Актуальные проблемы математики, механики и компьютерных технологий» (Хмельницький, 2005); 2-а Міжнародна науково-практична конференція “Управління в освіті”» (Львів, 2005).

Основні результати пройшли апробацію у провідних наукових установах України.

Публікації. Результати дисертації опубліковано в 45 наукових працях. З них 2 монографії, 20 статей у наукових виданнях, які входять до переліку фахових видань ВАК України, 6 - в інших виданнях, 17 - у матеріалах та тезах доповідей наукових конференцій.

Структура і обсяг роботи. Дисертаційна робота складається із вступу, шести розділів, висновків та списку використаних джерел (316 найменувань). Загальний обсяг роботи становить 292 сторінки, основний текст викладено на 268 сторінках.

ЗМІСТ РОБОТИ

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

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

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

На основі нових методів генерування запропоновано та описано схему нового методу направленого структурування.

Рекурсивний метод побудови перестановок - полягає у тому, що один елемент фіксується в кінці, а останні перебираються.

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

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

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

1. Генерування у певній послідовності всіх елементів заданої комбінаторної конфігурації.

2. Побудову на її елементах орієнтованого графа, де дуга відповідає спаданню значень цільової функції.

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

Цей метод було застосовано для розв'язання задач з лінійною та дробово-лінійною цільовими функціями на перестановках, розбиттях, сполученнях та розміщеннях.

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

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

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

, де . (1)

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

, .(2)

Розглянемо підхід до розв'язання задачі (1), (2) на основі властивостей графа перестановок - алгоритм локалізації значення лінійної функції на перестановках.

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

У розділі 4 оптимізується дробово-лінійна функція на комбінаторних конфігураціях, що представляється як відношення двох лінійних форм:

, де .

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

, .

Теорема 4.4. Граф перестановок для дробово-лінійної функції , коефіцієнти якої впорядковані за зростанням, збігається з графом перестановок для лінійної функції з точністю до орієнтації.

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

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

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

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

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

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

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

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

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

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

, де , , .

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

ВИСНОВКИ

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

Основні наукові результати дисертаційної роботи полягають у наступному:

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

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

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

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

5. Застосовано новий метод направленого структурування до розв'язування екстремальних задач з лінійними та дробово-лінійними цільовими функціями на комбінаторних конфігураціях перестановок та розміщень.

6. Побудовано загальну схему методу направленого структурування до розв'язування екстремальних задач з додатковими обмеженнями.

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

8. Розвинено метод направленого структурування до розв'язування екстремальних задач при наявності багатокритеріальності.

9. Уперше сформульовано і доведено ряд властивостей області допустимих розв'язків задачі з багатьма критеріями.

10. Побудовано методи розв'язування багатокритеріальних задач на комбінаторних конфігураціях і обґрунтовано їх застосування.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Колєчкіна Л. М. Властивості задач багатокритеріальної оптимізації на комбінаторних множинах та методи їх розв'язання / М. Л. Колєчкіна. - Полтава: РВВ ПУСКУ, 2008. -162 с.

2. Семенова Н. В. Векторні задачі дискретної оптимізації на комбінаторних множинах: методи їх дослідження та розв'язання / Н. В. Семенова, Л. М. Колєчкіна. - К.: Наук. думка, 2009. -266 с.

3. Донец Г. А. Алгоритм поиска значений линейной функции на лексикографически упорядоченных перестановках / Г. А. Донец, Л. Н. Колечкина // Теорія оптимальних рішень. - 2009 - № 8. - С. 3?8.

4. Донец Г. А. Локализация значения линейной функции заданной на перестановках / Г. А. Донец, Л. Н. Колечкина // Радиоэлектроника и информатика. - 2009. ? № 1. - С. 76-81.

5. Донец Г. А. Метод упорядочения значений линейной функции на множестве перестановок / Г. А. Донец, Л. Н. Колечкина // Кибернетика и системный анализ. - 2009. ?№ 2. - С. 50?61.

6. Донец Г. А. Об одном подходе к решению комбинаторной задачи оптимизации на графах / Г. А. Донец, Л. Н. Колечкина // Управляющие системы и машины. - 2009. ? № 4. - С. 36?42.

7. Донец Г. А. Построение гамильтонова пути в графах перестановочных многогранников / Г. А. Донец, Л. Н. Колечкина // Кибернетика и системный анализ. - 2010. - № 1. - С. 10-16.

8. Колечкина Л. Н. Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений / Л. Н. Колечкина, Е. А. Родионова // Кибернетика и системный анализ. - 2008. - № 2. - С. 152-160.

9. Колечкина Л. Н. Моделирование прикладных задач векторными задачами на комбинаторных конфигурациях / Л. Н .Колечкина, Е. А. Родионова // Радиоэлектроника и информатика. - 2009. - № 3. ? С. 62?68.

10. Колечкина Л. Н. О нахождении Парето-оптимальных решений в многокритериальных комбинаторных задачах на множестве размещений / Л. Н. Колечкина // Теорія оптимальних рішень. - 2008. - № 7. - С. 109-116.

11. Колечкина Л. Н. Об одном алгоритме решения комбинаторных задач векторной оптимизации на множестве размещений / Л. Н. Колечкина // Искусственный интелект. - 2010 - № 1. - С. 61-69.

12. Колечкина Л. Н. Обоснование структурированного метода локализации значения линейной функции, заданной на комбинаторной конфигурации перестановок / Л. Н. Колечкина // Динамические системы. - 2009. ? № 27. - С. 67-80.

13. Колечкина Л. Н. Оптимальные решения многокритериальных комбинаторных задач на размещениях / Л. Н. Колечкина // Теорія оптимальних рішень. - 2007. - № 6. - С. 67-73.

14. Колєчкіна Л. М. Моделювання та розв'язування економічних задач оптимізації відносних показників з урахуванням комбінаторних властивостей розв'язку / Л. М. Колєчкіна, А. М. Нагірна // Наукові вісті Національного технічного університету України «КПІ». - 2006. - № 5. - С. 34-40.

15. Колєчкіна Л. М. Постановка задачі багатокритеріальної комбінаторної оптимізації на полірозміщеннях та підхід до розв'язання / Л. М. Колєчкіна, О. А. Родіонова // Радиоэлектроника и информатика. - 2007. - №. 1. - С. 84-88.

16. Семенова Н. В. Многокритериальные задачи на комбинаторном множестве полиразмещений: полиэдральный подход к их решению / Н. В. Семенова, Л. Н. Колечкина // Кибернетика и системный анализ. - 2009. - № 3. - С. 118-126.

17. Семенова Н. В. Об одном подходе к решению векторных задач с дробно-линейными функциями критериев на комбинаторном множестве размещений / Н. В. Семенова, Л. Н. Колечкина, А. Н . Нагорная // Проблемы управления и информатики. - 2010. - № 1. - С. 131-144.

18. Семенова Н. В. Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок / Н. В. Семенова, Л. Н. Колечкина, А. Н. Нагорная // Кибернетика и системный анализ. - 2008. - № 3 - С. 158-172.

19. Семенова Н. В. Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації / Н. В. Семенова, Л. М. Колєчкіна // Доповіді НАН України. - 2009. - № 6. - С. 46-53.

20. Семенова Н. В. Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок / Н. В. Семенова, Л. Н. Колечкина, А. Н. Нагорная // Проблемы управления и информатики. - 2008. - № 6. - С. 26-41.

21. Семенова Н. В. Розв'язання багатокритеріальних задач оптимізації на множині поліперестановок / Н. В. Семенова, Л. М. Колєчкіна, А. М. Нагірна // Доповіді НАН України. - 2009. - № 2. - С. 41 48.

22. Семенова Н. В. Розв'язування задач векторної оптимізації з дробово-лінійними функціями критеріїв на комбінаторній множині розміщень / Н. В. Семенова, Л. М. Колєчкіна, А. М. Нагірна // Наукові вісті Національ_

ного технічного університету України «КПІ». - 2009. - № 2. - С. 53-60.

23. Колєчкіна Л. М. Моделювання прикладних задач багатокритеріальними комбінаторними задачами на поліперестановках / Л. М. Колєчкіна, О. А. Родіонова // Волинський математичний вісник. - 2009.? Вип. 6. ? С. 72?86. - (Серія «Прикладна математика»).

24. Колечкина Л. Н. Многокритериальные задачи на комбинаторном множестве полиразмещений: структурные свойства решений / Л. Н. Колеч-кина // Artificial Intelligence and Decision Making : Supplement to International Journal «Information Technologies and Knowledge». - 2008. - Vol. 2. ? P. 180186. - (Intern. Book Series «Information science and computing»; N 7).

25. Semenova N. Multicriterion problems on the combinatorial set of polyarrangements / N. Semenova, L. Kolechkina // Supplement to International J. «Information Technologies and Knowledge». - 2009. - Vol. 2. ? P. 115-127. - (Intern. Book Series «Information science and computing»; N 7).

26. Semenova N. V. Vector combinatorial problems in a space of combinations with linear fractional functions of criteria / N. V. Semenova, L. M. Kolechkina, A. M. Nagirna // Information Theories and Applications. - 2008. - Vol. 15, N 3. - P. 240245.

27. Семенова Н.В. Многокритериальные задачи лексикографической оптимизации c линейными функциями критериев на нечетком множестве альтернатив / Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. // Information Theories and Knowledge. - 2009. - 3. - P. 139-149. (Intern. Book Series “Information science and computing”, N7).

28. Колечкина Л. Н. Об одном алгоритме решения комбинаторных задач / Л. Н. Колечкина // Комп'ютерна математика в науці, інженерії та освіті : матеріали III - ї Mіжнар. наук.-технічної конф., (Полтава, 1?31 жовтня 2009 р). - К.: Вид-во НАН України, 2009.? С. 19.

29. Колєчкіна Л. М. Огляд комбінаторних задач та підходів до їх розв'язання за допомогою графів / Л. М. Колєчкіна, С. Є. Швачко // Економічне відродження України : матеріали VI Міжнар. наук.-практ. конф., 22 травня 2009 р. ? К.: Міжнародний науково-технічний університет ім. академіка Юрія Бугая, 2009. - С. 238?239.

30. Колєчкіна Л. М. Питання розв'язування комбінаторних багатокритеріаль_

них задач на множині полірозміщень / Л. М. Колєчкіна, О. А. Родіонова // Наука - практика - освіта: матеріали V міжвуз. наук.-практ. конф., 23 травня 2008р. / упоряд. Л. Т. Коломієць. - К.: ЗАТ «ДОРАДО», 2008. - С. 153?157.

31. Колєчкіна Л. М. Огляд методів розв'язування багатокритеріальної оптимізації / Л. М. Колєчкіна, А. М. Нагірна // Вісник Київськ. міжнар. наук.-техніч. ун-ту. - К.:, 2004.- № 2(2). - С.102-108.

32. Колєчкіна Л. М. Використання комбінаторної багатокритеріальної моделі при розв'язуванні задачі оптимізації швидкості передачі інформації / Л. М. Колєчкіна, А. М. Нагірна // В кн. «Problems of decision making under uncertainties» (PDMU-2006) - September 8-12, Alushta, Ukraine. - 2006.- С. 98.

33. Колєчкіна Л. М. Огляд методів розв'язування задач багатокритеріальної оптимізації / Л. М. Колєчкіна, А. М. Нагірна // В кн.: матеріали конф. IX Міжнар. наук. конф. імені академіка М. Кравчука (16-19 травня 2006). - К.: - 2006. - С. 431-432.

34. Семенова Н. В. Векторные комбинаторные задачи в пространстве сочетаний с дробно-линейными функциями критериев / Н. В. Семенова, Л. Н. Колечкина, А. Н. Нагорная // XIII-th International Conf. Knowledge-Dialogue-Solution June 18-24, 2007, Varna (Bulgaria). - P. 152-157.

35. Колечкина Л. Н. Подход к решению комбинаторной многокритериальной задачи на полиразмещениях / Л. Н. Колечкина, Е. А. Родионова // В кн. «Problems of decision making under uncertainties» (PDMU-2007). - May 21-25 Abstracts, Ukraine. - 2007. - С. 151 - 153.

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

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

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

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

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

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

42. Донець Г. П. Підхід до розв'язання комбінаторної задачі оптимізації за допомогою теорії графів / Г. П. Донець, Л. М. Колєчкіна // Праці міжнар. симпозіуму “Питання оптимізації обчислень (ПОО-XXXV)”. - К.: Інститут кібернетики імені В.М. Глушкова НАН України. - 2009. - Том. 1. - С. 221-227.

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

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