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

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

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

Автореферат

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

01.05.01 - теоретичні основи інформатики та кібернетики

Брила Андрій Юрійович

Київ - 2008

Дисертацією є рукопис.

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

Науковий керівник: доктор фізико-математичних наук

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

Інститут кібернетики імені В.М. Глушкова

НАН України, провідний науковий співробітник.

Офіційні опоненти: доктор фізико-математичних наук

Донець Георгій Панасович,

Інститут кібернетики імені В.М. Глушкова

НАН України, завідувач відділу,

кандидат фізико-математичних наук

Максишко Наталія Костянтинівна,

Запорізький національний університет, доцент.

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

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

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

Векторним згорткам критеріїв відповідають задачі векторної оптимізації. Для більшості таких задач не розроблено прямих методів розв'язання. Це стосується, зокрема, і лінійних задач багатокритеріальної оптимізації у транзитивній субординації, яка визначається транзитивною системою попарного підпорядкування критеріїв. Один із підходів до знаходження досяжних оптимальних розв'язків лінійних задач векторної оптимізації ґрунтується на розв'язанні відповідних задач лінійного програмування. Він досліджувався в роботах Подіновського В.В., Ногіна В.Д., Перепелиці В.О., Сергієнка І.В., Червака Ю.Ю., Ємелічева В.О., Вороніна А.М., Максишко Н.К., Лебедєвої Т.Т., Семенової Н.В., Червак О.Ю. та ін.

У прикладних задачах багатокритеріальної оптимізації часто розв'язком є ціла множина непорівнянних оптимальних альтернатив. Це пов'язано з тим, що на множині альтернатив визначається частковий порядок віддачі переваги (наприклад, у задачі паретівської оптимізації). Проблема вибору деякої однієї оптимальної альтернативи може бути розв'язана введенням додаткового критерію і потребує розробки спеціальних методів. Деякі підходи до розв'язання цієї проблеми розглянуто в роботах Червака Ю.Ю., Вороніна А.М., Гренджі В.І. та ін.

Практичні задачі багатокритеріального вибору мають, як правило, велику кількість критеріїв. Це ускладнює задачу вибору, оскільки із збільшенням кількості критеріїв зростає об'єм обчислень у відповідних алгоритмах її розв'язання. У зв'язку з цим актуальною є проблема зведення задач багатокритеріальної оптимізації до задач з меншою кількістю критеріїв. Такі дослідження проводились у роботах Сергієнка І.В., Червака Ю.Ю., Лебедєвої Т.Т., Семенової Н.В. та ін.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась у відповідності з планами наукових досліджень кафедри системного аналізу і теорії оптимізації Ужгородського національного університету в рамках наукової теми “Розв'язання багатокритеріальних задач вибору методами лексикографічної оптимізації” (№ держреєстрації 0100U005663, 2000-2002 рр.).

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

Для досягнення поставленої мети в процесі досліджень були розв'язані такі задачі:

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

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

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

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

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

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

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

Методи дослідження. При розв'язанні поставлених задач використовувалися методи теорії оптимізації.

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

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

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

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

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

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

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

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

Апробація результатів дисертації. Результати дисертаційної роботи пройшли апробацію на Міжнародних конференціях “Discrete and Global Optimization” (Ялта, 2008р.), “Problems of decision making under uncertainties ” (Новий світ, Крим, 2008 р.), на ІІ та ІV міжнародних школах-семінарах “Теорія прийняття рішень” (Ужгород, 2004р., 2008р.), на науковому семінарі в Інституті кібернетики імені В.М. Глушкова НАН України (Київ, 2008р.), на підсумкових наукових конференціях професорсько-викладацького складу Ужгородського національного університету (Ужгород, 2003-2007 р.р.).

Публікації. Основні результати дисертації опубліковано у 9 наукових роботах. Із них 5 це статті у наукових фахових виданнях, 4 роботи у матеріалах наукових конференцій і семінарів.

Структура та обсяг роботи. Дисертаційна робота складається із вступу, п'яти розділів, висновку та списку використаних джерел, який містить 81 найменування. Повний обсяг роботи - 124 сторінки, основний текст викладено на 113 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

У підрозділі 2.1 здійснюється дослідження досяжності оптимальних розв'язків для лінійної задачі паретівської оптимізації

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

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

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

Оптимальний розв'язок лінійної паретівської задачі може бути отриманий шляхом розв'язання відповідної задачі лінійного програмування (3). Нехай розв'язку , де - множина оптимальних розв'язків задачі (1), відповідає оптимальна канонічна форма

де , та - множини індексів відповідно небазисних та базисних змінних.

Зазначимо, що згідно з симплексним алгоритмом маємо

Нехай - розв'язок, отриманий з розв'язку в результаті виконання одного перетворення Жордана-Гауса, і . Йому відповідає канонічна форма

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

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

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

Нехай - множина крайніх точок множини допустимих розв'язків . Введемо наступні величини:

Розглянемо задачу лінійного програмуваннявибрано довільним чином, а інші числа визначені згідно умов

.Теорема 2.5 Розв'язок задачі (10) є розв'язком лексикографічної задачі (9) для довільної перестановки номерів критеріїв.

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

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

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

Теорема 3.2. При довільних,розв'язок задачі лінійного програмування,є розв'язком лексикографічно-паретівської задачі (11).

У цьому ж підрозділі досліджується задача

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

Розглянемо функціонал

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

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

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

Теорема 3.5. При довільних, розв'язок задачі лінійного програмування, є розв'язком парето-лексикографічної задачі (13).

У підрозділі 3.2 досліджується також задача

Введемо величини :

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

В підрозділі 3.3 здійснюється дослідження досяжності оптимальних розв'язків для лінійної задачі парето-паретівської максимізації

У підрозділі 3.3. досліджується також лінійна задача паретівської максимізації

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

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

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

Теорема 3.7. Розв'язок задачі лінійного програмування є розв'язком лексикографічно-лексикографічної задачі (17).

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

Визначимо функціонал де знаходяться згідно з (18).

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

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

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

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

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

Нехай - довільне додатне число, а всі інші знаходяться з умов

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

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

Кожна з підмножин (22) вважається множиною взаємно не підпорядкованих один одному критеріїв. Ранг критеріїв підмножини вищий за ранг критеріїв підмножини , якщо .

Розглянемо задачу лексикографічної оптимізації є ланцюгом критеріїв, у якому з кожної із множин (22) взято по одному критерію .

Розглянемо функціонал

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

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

У підрозділі 4.1 досліджено підхід до зменшення кількості критеріїв для лінійної задачі лексикографічно-паретівської максимізації:

Нехай - множина оптимальних розв'язків задачі (25), -множина оптимальних розв'язків цієї задачі, які є крайніми точками допустимої множини .

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

Нехай - множина оптимальних розв'язків задачі (26), - множина оптимальних розв'язків задачі (26), які є крайніми точками допустимої множини.

Теорема 4.1. Якщо серед функцій , є лінійно незалежних, то =.

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

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

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

Лема 4.1. .

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

Теорема 4.2. Якщо серед функцій , є лінійно незалежних, то .

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

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

Розглянемо лексикографічні задачі оптимізації:

Лема 4.2. Нехай . Якщо серед векторів , є лінійно незалежних, то розв'язок задачі (33) є розв'язком задачі (32).

Теорема 4.3. Якщо серед функцій , є лінійно незалежних, то .

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

ВИСНОВКИ

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

Основні наукові результати дисертації такі:

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

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

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

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

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

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

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

1. Брила А.Ю. До питання про максимізацію лінійної функції на множині Парето за допомогою симплексного алгоритму/ А.Ю. Брила // Наук. вісник Ужгород. ун-ту. Сер. матем. і інформ. - 2003. - Вип. 8. - С. 149-152.

2. Брила А.Ю. Про одну умову існування крайніх точок допустимої множини парето-лексикографічної оптимізації, які є її оптимальними розв'язками/ А.Ю. Брила // Наук. вісник Ужгород. ун-ту. Сер. матем. і інформ. - 2005. - Вип. 10-11. - С. 41-43.

3. Брила А.Ю. Досяжність оптимальних розв'язків лексикографічно-паретівської та парето-лексикографічних задач оптимізації за зваженою сумою різноважливих критеріїв/ А.Ю. Брила // Наук. вісник Ужгород. ун-ту. Сер. матем. і інформ. - 2007. - Вип. 14-15. - С. 13-17.

4. Брила А.Ю. Досяжність оптимальних розв'язків лінійної задачі лексикографічно-лексикографічної багатокритеріальної оптимізації за зваженою сумою різноважливих критеріїв/ А.Ю. Брила // Наук. вісник Ужгород. ун-ту. Сер. матем. і інформ. - 2008. - Вип. 16 - С. 40-43.

5. Брила А.Ю. Достижимость оптимальных решений линейной задачи многокритериальной оптимизации по взвешенной сумме критериев разной важности в транзитивной субординации/ А.Ю. Брила // Кибернетика и системный анализ. - 2008. - № 5. - С. 135-138.

6. Брила А.Ю. Застосування симплексного алгоритму для розв'язання задачі максимізації лінійної функції на множині Парето/ А.Ю. Брила //Теорія прийняття рішень: ІІ-га міжнародна школа-семінар, Ужгород, 27 вересня - 2 жовтня 2004 р.: праці школи-семінару. - Ужгород, 2004. - С. 11-12.

7. Brila A.Y. Attainbility of optimum sulutions of lexicographical maximization problem with convex criterion functions on their weighed sum/ A.Y Brila // Discrete and Global Optimization : International Conference, Yalta, July 31 - August 2, 2008: abstracts. - Kyiv, 2008. - P. 10-11.

8. Брила А.Ю. Досяжність оптимальних розв'язків задач багатокритеріальної максимізації з опуклими критеріальними функціями за їх зваженою сумою в транзитивній субординації / А.Ю. Брила // Problems of decision making under uncertainties (PDMU-2008): International Conference, Crimea(Novy Svit), September 22-27, 2008: abstracts. - Kyiv, 2008. P. 63-64.

9. Брила А.Ю. Досяжність оптимальних розв'язків задачі лексикографічно-лексикографічної багатокритеріальної максимізації з опуклими критеріальними функціями за їх зваженою сумою/ А.Ю. Брила //Теорія прийняття рішень: ІV-та міжнародна школа-семінар, Ужгород, 29 вересня - 4 жовтня 2008 р.: праці школи семінару. Ужгород, 2008. С. 30-31.

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2008.

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

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

Брила А.Ю. Достижимость оптимальных решений многокритериальных задач линейного программирования по взвешенным суммам равнозначных критериев. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики им. В.М.Глушкова НАН Украины, Киев, 2008.

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

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

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

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

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

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

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

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

Ключевые слова: линейная задача многокритериальной оптимизации, достижимость, субординация, цепь критериев.

Brila A.Yu. Attainability of optimum solutions of the multicriteria optimization problems of linear programming on the weighed sum of criteria of equal importance. - Manuscript.

Thesis for Candidate Degree in Physics and Mathematics; speciality 01.05.01 - theoretical Bases of Computer Science and Cibernetics. - V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2008.

The thesis is devoted to the problem of attainbility of optimum solutions of lexicographic, lexicographic-lexicographical, pareto-lexicographical and lexicographic-pareto optimization problems on the weighed sum of criteria of equal importance. The method of finding of attainable optimum solutions of multicriteria optimization problems in transitional subordination are developed. It consists in the reducing of these problems to the proper linear programming problems. The approach for solving of multicriteria optimization problems in complete transitional subordination by their reducing to the proper multicriteria problems with smaller quantity of criteria is suggested. Based on the use of symplex method the approach for improvement of value of some scalar criterion on the Pareto set, is grounded. This method allows to solve some problems of lexicografic-pareto optimization.

Keywords: linear problem of multicriteria optimization, attainability, subordination, chain of criteria.

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

...