Навігація
Головна
Задачі багатокритеріальної оптимізаціїОднокритеріальні і багатокритеріальні задачі прийняття рішень в...Методи оптимізації рішень для ризик-менеджменту за допомогою...Приклад рішення канонічної транспортної задачіМетоди рішення багатокритеріальних задачРішення задачі оптимізації потоків платежівБагатокритеріальні задами прийняття рішеньАлгоритми розв'язання задачМоделі оптимізації потоківОптимізація співвідношення постійної і змінної частин оборотних коштів
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Задачі багатокритеріальної оптимізації

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

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

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

(3.28)

(3.29)

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

- Оптимізація одного визнаного найбільш важливим критерію, решта критерії при цьому відіграють роль додаткових обмежень;

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

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

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

data-override-format="true" data-page-url = "http://stud.com.ua">

Визначення 3.1. Вектор називається ефективним (оптимальним за Парето) рішенням задачі (3.28), (3.29), якщо не існує такого вектора, що

(3.30)

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

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

data-override-format="true" data-page-url = "http://stud.com.ua">

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

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

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

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

Знову призначається величина поступки за другим критерієм, яка разом з першою поступкою використовується для знаходження умовного максимуму третього приватного критерію:

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

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

Рішення. Нехай задача трехкрітеріальной оптимізації має вигляд

(3.31)

(3.32)

(3.33)

(3.34)

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

Для визначеності будемо вважати, що допустимі поступки за першими двома критеріями задані:,

Максимізували функцію Z1 в області допустимих рішень, тобто вирішуємо одну критеріальну задачу (3.31), (3.34). Це нескладно зробити розглянутим у розділі 2 графічним методом рішення задач лінійного програмування (рис. 3.3).

Мал. 3. 3

Максимум функції Z1 при умовах (3.34) досягається в точці А області Q з координатами (1; 4), так що в даному випадку

Переходимо до максимізації функції Z1 при умовах (3.34) і додаткове обмеження, що дозволяє врахувати, що за критерієм Z1 можна поступатися більш ніж на δ1. Так як у нашому прикладі, то додаткове обмеження буде мати вигляд

(3.35)

Задачу (3.32), (3.34), (3.35) також вирішуємо графічно (рис. 3.4).

Отримуємо, що максимум функції Ζ2 при умовах (3.34), (3.35) досягається в точці В частині Q 1 області Q, так що

Тепер поступаємося за критерієм Ζ2 на величину поступки δ2 = 5/3 і отримуємо другий додаткове обмеження:

(3.36)

Максимізували функцію Ζ3 при умовах (3.34), (3.35) і (3.36). Вирішення цього завдання представлено на рис 3.5.

Мал. 3.4

Мал. 3. 5

Таким чином, отримуємо оптимальне рішення розглянутої трехкрітеріальной завдання (точка С на рис. 3.5):

Відповідні значення приватних критеріїв при цьому складають:

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >

Cхожі теми

Задачі багатокритеріальної оптимізації
Однокритеріальні і багатокритеріальні задачі прийняття рішень в умовах ризику
Методи оптимізації рішень для ризик-менеджменту за допомогою екстремальних задач
Приклад рішення канонічної транспортної задачі
Методи рішення багатокритеріальних задач
Рішення задачі оптимізації потоків платежів
Багатокритеріальні задами прийняття рішень
Алгоритми розв'язання задач
Моделі оптимізації потоків
Оптимізація співвідношення постійної і змінної частин оборотних коштів
 
Дисципліни
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук