Основні способи формування цільової функції задачі

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

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

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

1. Частинні показники однієї і тієї ж задачі мають бути, за можливості, однієї розмірності.

2. Кожний частинний показник має відображати певну фізичну сутність об’єкта (процесу).

3. Загальну кількість частинних показників бажано мати найменшою.

4. Всі разом частинні показники мають з необхідною повнотою характеризувати, описувати об’єкт (процес).

5. Кожний частинний показник повинен виражатися можливо простою математичною залежністю.

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

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

2. Часто формують так звану адитивну цільову функцію, яка є сумою частинних показників к1, к2, ... , ке, помножених на вагові коефіцієнти a1, a2, ... , aе:

W (к₁, к₂, ... , к_е) = a₁, к₁ + ... + a_ек_е

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

Основною трудністю у процесі формування адитивної цільової функції є визначення вагових коефіцієнтів a1, a2, ... , aе, тобто постійних множників, які визначають значущість, “вагу” кожного частинного показника в цільовій функції задачі. Найчастіше їх визначають методом експертного оцінювання, тобто шляхом опитування експертів - досвідчених спеціалістів в даній галузі. На жаль, це вносить елементи суб’єктивізму у процес формування цільової функції, а в підсумку - в результати розв’язання задачі. З огляду на це такий спосіб формування цільової функції застосовують рідко.

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

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

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

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

К₂

К_{2 mах} 2

К_{2 р} 3

К₂⁽¹⁾1

К₁

0 К₁⁽²⁾К_{1 р} К_{1 mах}

Рис. 1.1

Потім розв’язуємо задачу з врахуванням тільки показника К2 і за одержаними значеннями змінних розраховуємо показник К1. Цей розв’язок на рис. 1.1 відображений точкою 2. Може виявитися, що в одержаних двох розв’язках задачі максимуму показника К1= К1mах відповідає неприйнятно мале значення показника К2= К2(1), а максимуму показника К2= К2 mах - неприйнятно мале значення показника К1 = К1(2). Тоді, керуючись умовами задачі і враховуючи порівняльну значимість показників К1 і К2, знаходять розв’язок, який забезпечує прийнятні значення обох показників і якому на рис. 1.1 відповідає точка 3. Формально такий розв’язок є раціональним, але не оптимальним, він тільки наближений до останнього.

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

Зазначимо, що задачу математичного програмування, в якій треба максимізувати цільову функцію W1 (х1, х2, ..., хn), можна легко перетворити в задачу мінімізації з цільовою функцією W2(х1, х2, …, хn)=1/W1(х1, х2, ,. хn).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
ОБСЛУГОВУВАННЯ ПОВІТРЯНОГО РУХУ 1.1 Основні відомості про математичне програмування	\|	Загальне формулювання і приклади задач лінійного програмування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.