 |
Знаходження розв’язку задач нелінійного програмування, що містять сепарабельні функції
|
|
|
|
Розглянемо задачу нелінійного програмування, у якій цільова функція і функції в системі обмежень є сепарабельними.
Визначення 3.11. Функція F (х1, х2,..., хп)називається сепарабельною, якщо вона може бути представлена у вигляді суми функцій, кожна з яких є функцією однієї змінної, тобто якщо
Якщо цільова функція і функції в системі обмежень задачі нелінійного програмування є сепарабельними, то наближене Розв’язок такої задачі можна знайти із використанням методу кусково-лінійної апроксимації. Однак його застосування в загальному випадку дозволяє одержати наближений локальний екстремум. Тому розглянемо використання методу кусково-лінійної апроксимації для Розв’язок задачі випуклого програмування.
1. Метод кусково-лінійної апроксимації. Нехай потрібно визначити максимальне значення ввігнутої функції
при умовах
хj ≥ 0(j = 
) (82)
Щоб знайти Розв’язок задачі (80)-(82), замінимо функції fj (xj) і gij (xj)кусково-лінійними функціями 
і 
і перейдемо від задачі (80)-(82) до задачі, що полягає у визначенні максимального значення функції
при умовах
хj ≥ 0(j = ) (85)
У задачі (83)-(85) поки не визначений вид функцій. Щоб зробити це, будемо вважати, що змінна хj може приймати значення із проміжку [0; αj ](αj – максимальне значення змінної хj). Розіб’ємо проміжок [0; αj ]на rj проміжків за допомогою rj +1 точок так, що x0j =0, 
= αj. Тоді функції fj (xj) і gij (xj)можна записати у вигляді
де
fkj= fj (xk); gkij=gij (xk) (i = 
) (87)
λ kj ≥ 0 для всіх k і j, причому для даного хj, не більше двох чисел λ kj ≥ 0 можуть бути додатними і повинні бути сусідніми.
Підставляючи тепер у рівності (83) і (84) вираження функцій 
і у відповідності з формулами (86), приходимо до наступної задачі:
|
|
|
Знайти максимальне значення функції
при умовах
λ kj ≥ 0 для всіх k і j (91)
Отримана задача відрізняється від звичайної задачі лінійного програмування тим, що накладено додаткове обмеження на змінну λ kj, що полягає в тому, щоб для кожного j не більше двох λ kj були додатними і ці додатні λ kj були сусідніми. Виконання цих умов може бути дотримано при рішенні задачі (88)-(91) симплексним методом за рахунок відповідного вибору базису, що визначає як кожний опорний, так і оптимальний план даної задачі. При цьому в загальному випадку точність отриманого Розв’язок залежить від прийнятого кроку розбивки проміжку [0, αj ]. Чим менше крок, тим більш точним є отримане Розв’язок.
Таким чином, процес знаходження Розв’язок задачі нелінійного програмування методом кусково-лінійної апроксимації включає наступні етапи:
1. Кожну із сепарабельних функцій заміняють кусково-лінійною функцією.
2. Будують задачу лінійного програмування (88)-(91).
3. За допомогою симплексного методу знаходять Розв’язок задачі (88)-(91).
4. Визначають оптимальний план задачі (80)-(82) і знаходять значення цільової функції при цьому плані.
Використовуючи метод кусково-лінійної апроксимації, знайти максимальне значення функції F=x2 – x1 2+6 x1 –9 при умовах
x1, x2 ≥ 0
Розв’язок. У даному випадку цільову функцію F можна представити як суму двох функцій f1 (x1) = – x1 2+6 x1– 9 і f2 (x2) =x2,кожна з яких є функцією однієї змінної. Отже, функція F є сепарабельною. Крім того, вона є ввігнутою (як сума двох ввігнутих функцій), а область припустимих рішень – випуклою. Отже, використовуючи метод кусково-лінійної апроксимації, можна знайти приблизно глобальний максимум цільової функції.
Тут нелінійною функцією є тільки цільова функція. Виходить, кусково-лінійною функцією варто замінити тільки її. При цьому так як функція f2 (x2) лінійна, то апроксимувати будемо функцію f1 (x1).
|
|
|
На рис. 3.1, де побудована область припустимих рішень задачі, видно, що змінна х1 може приймати значення в проміжку [0; 8]. Розіб’ємо цей проміжок на вісім частин точками х01 =0, х11 =1, х21 =2, х31 =3, х41= 4, х51= 5, х61 =6, х71= 7, х81 =8. Обчислимо тепер значення функції f1 (x1) у цих точках (табл. 3.2).
Таблиця 3.2
| xk1 | |||||||||
| f1 (xk1) | –9 | –4 | –1 | –1 | –4 | –9 | –16 | –25 |
Використовуючи формули (86) і (87), знаходимо
=–9λ 01 –4λ 11 –λ 21 –λ 41 –4λ 51 –9λ 61 –16λ 71 –25λ 81,
x1 =0·λ 01 +1λ 11 +2λ 21 +3λ 31 +4λ 41 +5λ 51 +6λ 61 +7λ 71 +8λ 81.
Підставляючи знайдені вираження f1 (x1)і x1 у вихідні дані, одержимо:
= –9λ 01 –4λ 11 –λ 21 –λ 41 –4λ 51 –9λ 61 –16λ 71 –25λ 81 + х2 → тах,
2λ 11 +4λ 21 +6λ 31 +8λ 41 +10λ 51 +12λ 61 +14λ 71 +16λ 81 +3 х2 + х3 =24,
λ 11 +2λ 21 +3λ 31 +4λ 41 +5λ 51 +6λ 61 +7λ 71 +8λ 81 +2 х2 + х4 =15,
3λ 11 +6λ 21 +9λ 31 +12λ 41 +15λ 51 +18λ 61 +21λ 71 +24λ 81 +2 х2 + х5 =24,
х2 + х6= 4, = λ 01+ λ 11 +λ 21 +λ 31 +λ 41 +λ 51 +λ 61 +16λ 71 +λ 81 =1,
х2, х3, х4, х5, х6 ≥ 0. λ k ≥ 0 (k = 
).
Для отриманої задачі п’ять векторів Р01, Р3, Р4, Р5 і Р6 є одиничними. Виходить, її Розв’язок може бути знайдено симплексним методом. Визначаємо його (табл. 3.3).
Таблиця 3.3
| i | Базис | Cб | P0 | –9 | –4 | –1 | –1 | –4 | –9 | –16 | – 25 | ||||||
| P01 | P11 | P21 | P31 | P41 | P51 | P61 | P71 | P81 | P2 | P3 | P4 | P5 | P6 | ||||
| P3 P4 P5 P6 P01 | –9 | –9 | –5 | –8 | –9 | –8 | –5 | –1 | |||||||||
| P3 P4 P5 P6 P31 | –6 –3 –9 | –4 –2 –6 | –2 –1 –3 | –1 | –1 | ||||||||||||
| P3 P4 P5 P2 P31 | –6 –3 –9 | –4 –2 –6 | –2 –1 –3 | –3 –2 –2 |
По знайденим у табл. 3.3 значенням λ k1 знаходимо x1 *=3. Далі, з табл. 3.3 бачимо, що x2 * = 4. Виходить, X*= (3; 4) є наближеним оптимальним Розв’язокм, що випадково збіглося з точним Розв’язокм. При даному рішенні Fтах =4.
ТЕОРІЯ РИЗИКУ
|
|
|
E) тело, размерами которого можно пренебречь в условиях данной задачи
I Приклади розв’язання задач
I ЭТАП. Постановка задачи
I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
I. Цели и задачи учебной дисциплины
I. Цель задачи дисциплины «История государства и права зарубежных стран»
II Анализ задачного материала
II Раздаточный материал из сборника задач по технологии горячей и холодной прокатки стали и сплавов. Протасов А.А. Изд-во «Металлургия» М.1972, 320 с.
II. Задачи работы с классом
II. Типовые задачи.
