 |
Властивості нелінійних задач
|
|
|
|
У процесі дослідження задач планування та керування економічними явищами зустрічаються задачі з нелінійними залежностями. При цьому припущення про лінійні залежності і згідно з цим використання методів лінійного програмування для цих задач, приводить до того, що такий розв’язок, як правило не відповідає оптимальному варіанту.
Тому задачі, які мають або обмеження, або цільову функцію, або те і друге разом у вигляді нелінійних залежностей, виділяються до окремого класу задач, для якого існує низка спеціальних методів розв’язування, які об’єднуються до класу задач нелінійного програмування.
Ці методи поки що знаходяться у процесі розвитку, тому використання їх обмежене, оскільки за нашого часу знайдено ефективні методи тільки для окремих груп задач оптимізації нелінійного типу, тобто універсального алгоритму розв’язування задач нелінійного програмування не існує.
Найчіткіше розроблено методи розв’язування нелінійних задач з опуклою областю допустимих розв’язків та увігнутою чи опуклою цільовою функцією 
, тому що в таких задачах глобальний екстремум завжди збігається з локальним. Такі задачі складають клас задач опуклого програмування і є частковим випадком задач нелінійного програмування.
Загальний вигляд математичної моделі нелінійного типу такий:
де 
та усі 
, або хоча б одне з них має нелінійну залежність.
За мірою важкості задачі нелінійного програмування можна класифікувати, наприклад, як показано на рис. 9.1.
Задачі нелінійного програмування
 |
напрям зростаючої важкості розв’язування задач.
Рис. 9.1
У процесі роз’вязування задач нелінійного програмування зустрічаються значні перешкоди, пов’язані з такими властивостями нелінійних задач.
|
|
|
1. Наявність множини локальних точок екстремуму поряд з глобальними. При цьому з’являється небезпечність прийняття одного з локальних екстремумів за глобальний, наприклад, геометрично це має вигляд, як зображено на рис. 9.2.
20
50 30
40 40
30
40 30
20
Рис. 9.2
На рис. 9.2. є кілька точок, де похідна дорівнює нулю. На жаль, це є необхідна, але не достатня умова існування глобального оптимуму.
2. Оптимальний розв’язок нелінійних задач може розміщуватися не тільки на межі або у крайніх точках області допустимих розв’язків, а й усередині цієї області.
3. 
Область допустимих розв’язків у нелінійних задачах може мати незв’язані підобласті, тобто розпадатися на кілька окремих частин, наприклад, як на рис. 9.3.
Рис. 9.3
Методи розв’язування нелінійних задач опуклого характеру можна поділити на дві групи. При цьому кожний з розроблених методів розв’язування використовується тільки для певного типу нелінійних задач.
До першої групи згруповуються методи, що зводяться до розв’язування за допомогою безумовної оптимізації. У цьому випадку розв’язок задачі знаходиться як межа послідовності безумовних екстремумів за допомогою спеціально складених допоміжних функцій. До них відносять метод штрафних функцій, метод центрів, метод множників Лагранжа.
Для знаходження стаціонарної точки цими методами треба розв’язати п рівнянь з п змінними. Проте така система складається з ряду нелінійних рівнянь, а тому розв’язування такої системи є складною самостійною задачею. Крім того, задачі, що зустрічаються на практиці, мають цільову функцію не завжди диференційовну, що також утруднює процес розв’язування задачі,
До другої групи входять методи, що базуються на ідеї поступового наближення до точки екстремуму. При цьому має виконуватися умова монотонної зміни цільової функції 
, якщо 
інавпаки, якщо 
. Такі методи розв’язування нелінійних задач називають ітеративними.
|
|
|
Основним класом цієї групи є градієнтні методи: метод покоординатного спуску (метод Гаусса-Зейделя), метод крутого сходу (метод Бокса-Уілсона) або метод найшвидшого спуску та інші.
Треба зауважити, що такий розподіл методів надто умовний.
У випадку, коли для задач нелінійного програмування не вдається побудувати ефективний алгоритм розв’язування, то іноді використовують деякі штучні підходи:
1) зведення нелінійної задачі до задачі лінійного програмування, якщо це можливо, не впливаючи на точність і зміст розв’язку; це має місце у випадках слабкої нелінійної залежності;
2) зведення нелінійної задачі до структури багатокрокових задач, що дозволяє використовувати метод динамічного програмування.
|
|
|
I Приклади розв’язання задач
II Анализ задачного материала
II. Типовые задачи.
Агрохімічні та фізико-хімічні властивості лучно-чорноземного карбонатного ґрунту
Алгоритм розв’язання задач на рівновагу
Алергени, їх природа та властивості
Аналіз рівнянь лінійної регресії і властивості вибіркового коефіцієнту кореляції
Арифметические задачи
В задаче об оптимальном распределении ресурсов критерием оптимальности является
Взаємно двоїсті задачі
