Главная | Обратная связь | Поможем написать вашу работу!

Задачі випуклого програмування

Розглянемо задачу нелінійного програмування:

f (х₁; х₂;...; х_п)→ max (24)

g_i (х₁; х₂;...; х_п) ≤ b_i (i = ) (25)

х_j ≥ 0 (j = ) (26)

де f і g_i – деякі функції п змінних х₁; х₂;...; х_п.

Для Розв’язок сформульованої задачі в такій загальній постановці не існує універсальних методів. Однак для окремих класів задач, у яких зроблені додаткові обмеження щодо властивостей функцій f і g_i, розроблені ефективні методи їхнього Розв’язок. Зокрема, ряд таких методів існує для Розв’язок задач нелінійного програмування (24)-(26) за умови, що f – ввігнута (випукла) функція і область припустимих рішень, що визначається обмеженнями (25) і (26), – випукла.

Визначення 3.1. Функція f (х₁; х₂;...; х_п),задана на випуклій множині X,називається випуклою, якщо для будь-яких двох точок X₁ і X₂ з X і кожного 0 ≤ λ ≤1 виконується співвідношення

f [λ Х₂+ (1 – λ) X₁ ] ≤ λ f (Х₂)+(1–λ) f (X₁) (27)

Визначення 3.2. Функція f (х₁; х₂;...; х_п),задана на випуклій множині X,називається ввігнутою,якщо для будь-яких двох точок X₁ і X₂ з X і будь-якого 0 ≤ λ ≤1 виконується співвідношення

f [λ Х₂+ (1 – λ) X₁ ] ≥ λ f (Х₂)+(1–λ) f (X₁) (27)

Визначення 3.3. Говорять, що множина припустимих рішень задачі (24)-(26) задовольняє умові регулярності, якщо існує принаймні одна точка Х_i,щоналежить області припустимих рішень така, що g_i (X_i)≤ b_i (i = ).

Визначення 3.4. Задача (24)-(26) називається задачею випуклого програмування, якщо функція f (х₁, х₂,..., х_п) є ввігнутою (випуклою), а функції g_i (X_i)(i = )– випуклими.

Теорема 3.1. Будь-який локальний максимум (мінімум) задачі випуклого програмування є глобальним максимумом (мінімумом).

Визначення 3.5. Функцією Лагранжа задачі випуклого програмування (24)-(26) називається функція

L (х₁, х₂,..., х_п, y₁, y₂,..., y_m) = f (х₁, х₂,..., х_п) +

[ b_i–g_i (х₁, х₂,..., х_п)] (29)

де y₁, y₂,..., y_m – множники Лагранжа.

Визначення 3.6. Точка (Х₀; Y₀)=(х⁰₁; х⁰₂;...; х⁰_п; y⁰₁; y⁰₂;...; y⁰_m) називається сідловою точкою функції Лагранжа, якщо

L (х₁, х₂,..., х_п, х⁰_п, y⁰₁, y⁰₂,..., y⁰_m) ≤ L (х⁰₁, х⁰₂,..., х⁰_п,

y⁰₁, y⁰₂,..., y⁰_m) < L (х⁰₁, х⁰₂,..., х⁰_п, y₁, y₂,..., y_m)

для всіх х_j ≥ 0 (j = ) і y_i ≥ 0 (i = ).

Теорема 3.2 (теорема Куна-Таккера). Для задачі випуклого програмування (24)-(26), множина припустимих рішень якої має властивість регулярності, Х₀= (х⁰₁; х⁰₂;...; х⁰_п) є оптимальним планом тоді і тільки тоді, коли існує такий вектор Y₀ =(y⁰₁; y⁰₂;...; y⁰_m)(y⁰_i, i = ), що (Х₀; Y₀) – сідлова точка функції Лагранжа.

Якщо припустити, що цільова функція f і функція g_i можуть бути неперервно диференційовані, то теорема Куна-Таккера може бути доповнена аналітичними вираженнями, що визначають необхідні і достатні умови того, щоб точка (Х₀; Y₀) була сідловою точкою функції Лагранжа, тобто була Розв’язокм задачі випуклого програмування. Ці вираження мають такий вигляд:

де і – значення відповідних частинних похідних функції Лагранжа, обчислених у сідловій точці. Всім відзначеним вище вимогам, що дозволяють записати необхідні і достатні умови для сідлової точки (Х₀; Y₀)функції Лагранжа у вигляді виразів (30)-(35), задовольняє сформульована нижче задача квадратичного програмування. Перш ніж сформулювати цю задачу, дамо деякі визначення.

Визначення 3.7. Квадратичною формою щодо змінних х₁, х₂,..., х_п називається числова функція від цих змінних, що має вид

F=c₁₁x₁x₁ + c₁₂x₁x₂+c₁₃x₁x₃+... + c₂₁x₂x₁+c₂₂x₂x₂+ …=

Визначення 3.8. Квадратична форма F називається позитивно(негативно)-визначеною, якщо F (X) > 0 [ F (Х) < 0]для всіх значень змінних Х= (х₁, х₂,..., х_п),крім Х= 0.

Визначення 3.9. Квадратична форма F називається позитивно(негативно)-напіввизначеною, якщо F (X) ≥ 0[ F (Х) ≤ 0]для будь-якого набору значень змінних Х= (х₁, х₂,..., х_п)і, крім того, існує такий набір змінних Х′= (х′₁, х′₂,..., х′_п),де не всі значення змінних одночасно дорівнюють нулю, що F (Х′) = 0.

Теорема 3.3. Квадратична форма є випуклою функцією, якщо вона позитивно-напіввизначена, і ввігнутою функцією, якщо вона негативно-напіввизначена.

Визначення 3.10. Задача, що полягає у визначенні максимального (мінімального) значення функції

при обмеженнях

x_j ≥ 0 (j = ) (38)

де – негативно (позитивно)-напіввизначена квадратична форма, називається задачею квадратичного програмування.

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

Якщо функція L має сідлову точку (Х₀; Y₀)=(х⁰₁; х⁰₂;...; х⁰_п; y⁰₁; y⁰₂;...; y⁰_m),то в цій точці виконуються співвідношення (30)-(35). Вводячи тепер додаткові змінні υ_j (j = ) і ω_i (i = ), що перетворюють нерівності (30) і (33) у рівності, перепишемо вираження (30)-(35), записані для задачі квадратичного програмування, у такий спосіб:

х⁰_j ≥ 0, υ_j ≥ 0, y⁰_i ≥ 0, ω_i ≥ 0 (j = ; i = ) (43)

Таким чином, щоб знайти Розв’язок задачі квадратичного програмування (36)-(38), потрібно визначити невід’ємне Розв’язок систем лінійних рівнянь (39) і (40), що задовольняє умови (41) і (42). Це Розв’язок можна знайти за допомогою методу штучного базису, що застосований для знаходження максимального значення функції F= при умовах (39), (40), (43) з врахуванням (41) і (42). Тут в, - штучні змінні, введені в рівняння (39) і (40).

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

Отже, процес знаходження Розв’язок задачі квадратичного програмування (36)-(38) включає наступні етапи:

1. Складають функцію Лагранжа.

2. Записують у вигляді виразів (39)-(43) необхідні і достатні умови існування сідлової точки для функції Лагранжа.

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

4. Записують оптимальне Розв’язок вихідної задачі і знаходять значення цільової функції.

3.22. Знайти максимальне значення функції

f= 2 x₁ +4 x₂ – x₁ ² – 2 x₂ ² (44)

при умовах

x₁, x₂ ≥ 0 (46)

Розв’язок. Функція f є ввігнутою, так як являє собою суму лінійної функції f₁ = 2х₁ +4 х₂ (яку можна розглядати як ввігнуту) і квадратичної форми f₂= – x₁ ² – 2 x₂ ², що є від’ємно-визначеною і, отже, також ввігнутою. Система обмежень задачі включає лише лінійні нерівності. Отже, можна скористатися теоремою Куна-Таккера. Складемо функцію Лагранжа

L =2 х₁ +4 х₂ – x₁ ² – 2 x₂ ² +y₁ (8– х₁ –2 х₂) +y₂ (12–2 х₁ + х₂)

і запишемо у вигляді виражень (39)-(43) необхідні і достатні умови існування сідлової точки побудованої функції:

х₁, х₂, y₁, y₂ ≥ 0 (49)

Систему лінійних нерівностей (47) перепишемо в такий спосіб:

Уводячи тепер додаткові невід’ємні змінні υ₁, υ₂, ω₁ і ω₂, що перетворюють нерівності (47) у рівності, одержимо

х₁, х₂, y₁, y₂, υ₁, υ₂, ω₁, ω₂ ≥ 0 (52)

З огляду на рівності (51), можна записати:

υ₁х₁ =0, υ₂х₂ =0, ω₁y₁ =0, ω₂y₂ =0 (53)

Якщо тепер знайти базисне Розв’язок системи лінійних рівнянь (51) з урахуванням виконання рівностей (53), то буде отримана сідлова точка функції Лагранжа для вихідної задачі, тобто визначене оптимальне Розв’язок.

Для знаходження базисного Розв’язок системи лінійних рівнянь (51) скористаємося методом штучного базису. У перше і друге рівняння системи (51) відповідно додамо додаткову невід’ємну змінну z₁ і z₂ і розглянемо задачу лінійного програмування, що полягає у визначенні максимального значення функції

=–Мz₁–Мz₂ (54)

при умовах

х₁, х₂, y₁, y₂, υ₁, υ₂, ω₁, ω₂, z₁, z₂ ≥ 0 (52)

У результаті Розв’язок задачі (54)-(56) [відзначимо, що при цьому рішенні враховуються умови (53)] знаходимо припустиме базисне Розв’язок системи лінійних рівнянь (55) (табл. 3.1):

х⁰₁ =1; х⁰₂ =1; ω₁ =5; ω₂ =11; y⁰₁ = y⁰₂ = υ₁ = υ₂ =0.

Так як х⁰₁υ₁ =0; х⁰₂υ₂ =0; y⁰₁ω₁ =0; y⁰₂ω₂= 0,то (Х₀; Y₀)=(1; 1; 0; 0) є сідловою точкою функції Лагранжа для вихідної задачі. Отже, Х *=(1; 1) – оптимальний план вихідної задачі і f_тах =3.

Таблиця 3.1

Базис

C_б

P₀

–M

–M –M

–6

–2

–1 –4

–3

–1 –1

–1

–M

–2

1/2 –1 1/2 –1

–1/4 1/2 –1/4 –2

–1

–1/4 1/2 –1/4

1/4 –1/2 1/4

1/2

–1/2

1/2

ГРАДІЄНТНІ МЕТОДИ

Використовуючи градієнтні методи, можна знайти Розв’язок будь-якої задачі нелінійного програмування. Однак у загальному випадку застосування цих методів дозволяє знайти точку локального екстремуму. Тому більш доцільно використовувати градієнтні методи для знаходження Розв’язок задач випуклого програмування, у яких усякий локальний екстремум є одночасно і глобальним. Процес знаходження Розв’язок задачі за допомогою градієнтних методів полягає в тому, що починаючи з деякої точки X ⁽ ^k ⁾здійснюється послідовний перехід до деяких інших точок доти, доки не виявляється прийнятне Розв’язок вихідної задачі. При цьому градієнтні методи можуть бути підрозділені на дві групи.

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

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

При знаходженні Розв’язок задач градієнтними методами, у тому числі і названими, ітераційний процес здійснюється до того моменту, поки градієнт функції f (х₁, х₂,..., х_п)у черговій точці Х ⁽ ^k ⁺¹⁾ не стане рівним нулю або ж поки | f (Х ⁽ ^k ⁺¹⁾) –f (Х ⁽ ^k ⁾)| < ε,де ε – досить мале додатне число, що характеризує точність отриманого Розв’язок.

Зупинимося більш докладно на методах Франка-Вулфа, штрафних функцій і Эрроу-Гурвіца.

1. Метод Франка-Вулфа. Нехай потрібно знайти максимальне значення ввігнутої функції

f (х₁, х₂,..., х_п) (57)

при умовах

x_j ≥ 0 (j = ) (59)

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

Процес знаходження Розв’язок задачі починають із визначення точки, що належить області припустимих рішень задачі. Нехай це точка Х ⁽ ^k ⁾тоді в цій точці обчислюють градієнт функції (57)

і будують лінійну функцію

Потім знаходять максимальне значення цієї функції при обмеженнях (58) і (59). Нехай Розв’язок даної задачі визначається точкою Z ⁽ ^k ⁾. Тоді за нове припустиме Розв’язок вихідної задачі приймають координати точки Х ⁽ ^k+1 ⁾:

Х ⁽ ^k+1 ⁾= Х ⁽ ^k ⁾+λ _k (Z ⁽ ^k ⁾– X ⁽ ^k ⁾) (61)

де λ _k – деяке число, що називається кроком обчислень і знаходиться між нулем і одиницею (0 ≤ λ _k ≤ 1). Це число λ _k беруть довільно або визначають таким чином, щоб значення функції в точці Х ⁽ ^k+ ¹⁾ f (Х ⁽ ^k+ ¹⁾), що залежить від λ _k, було максимальним. Для цього необхідно знайти Розв’язок рівняння і вибрати його найменший корінь. Якщо його значення більше одиниці, то варто покласти λ _k =1. Після визначення числа λ _k знаходять координати точки Х ⁽ ^k+ ¹⁾, обчислюють значення цільової функції в ній і з’ясовують необхідність переходу до нової точки Х ⁽ ^k+ ²⁾Якщо така необхідність є, то обчислюють у точці Х ⁽ ^k+ ¹⁾ градієнт цільової функції, переходять до відповідної задачі лінійного програмування і знаходять її Розв’язок. Визначають координати точки Х ⁽ ^k+ ²⁾ і досліджують необхідність проведення подальших обчислень. Після кінцевого числа кроків одержують із необхідною точністю Розв’язок вихідної задачі.

Отже, процес знаходження Розв’язок задачі (57)-(59) методом Франка-Вулфа включає наступні етапи:

1. Визначають вихідне припустиме Розв’язок задачі.

2. Знаходять градієнт функції (57) у точці припустимого Розв’язок.

3. Будують функцію (60) і знаходять її максимальне значення при умовах (58) і (59).

4. Визначають крок обчислень.

5. По формулах (61) знаходять компоненти нового припустимого Розв’язок.

6. Перевіряють необхідність переходу до наступного припустимого Розв’язок. Якщо виникає потреба, переходять до етапу 2, у протилежному випадку знайдене прийнятне Розв’язок вихідної задачі.

3.27. Методом Франка-Вулфа знайти Розв’язок задачі 3.22, що полягає у визначенні максимального значення функції

f =2 x₁ +4 х₂ – x₁ ²–2 x₂ ² (62)

при умовах

x₁, x₂ ≥ 0 (64)

Розв’язок. Знайдемо градієнт функції

і в якості вихідного припустимого Розв’язок задачі візьмемо точку X ⁽⁰⁾=(0; 0), а, критерієм оцінки якості одержуваного Розв’язок – нерівність | f (Х ⁽ ^k ⁺¹⁾) –f (Х ⁽ ^k ⁾)| < ε,де ε = 0,01.

І ітерація. У точці X ⁽⁰⁾градієнт f (X ⁽⁰⁾)=(2; 4). Знаходимо максимум функції

F₁ =2 х₁ +4 х₂ (65)

при умовах (63) і (64)

x₁, x₂ ≥ 0 (67)

Задача (65)-(67) має оптимальний план Z ⁽⁰⁾=(0; 4). Знайдемо нове припустиме Розв’язок вихідної задачі за формулою (61):

Х ⁽¹⁾ =Х ⁽⁰⁾ + λ ₁ (Z ⁽⁰⁾– Х ⁽⁰⁾), де 0 ≤ λ ₁ ≤ 1 (68)

Підставивши замість Х ⁽⁰⁾і Z ⁽⁰⁾ їх значення, одержимо

Визначимо тепер число λ ₁ Підставивши в рівність (62) замість х₁ і х₂ їх значення відповідно до співвідношень (69)

f (λ ₁)=16λ ₁ –32λ ₁ ²,

знайдемо похідну цієї функції по λ ₁ і прирівняємо її до нуля: f′ (λ ₁)=16–64λ ₁ =0. Вирішуючи це рівняння, одержимо λ ₁ =1/4=0,25. Оскільки знайдене значення λ ₁ знаходиться між 0 і 1, приймаємо його за величину кроку. Таким чином, Х ⁽¹⁾=(0; 1), f (Х ⁽¹⁾) = 2, f (Х ⁽¹⁾)– f (Х ⁽⁰⁾)=2 > ε=0,01.

II ітерація. Градієнт цільової функції вихідної задачі в точці X ⁽¹⁾ є f (Х ⁽¹⁾)=(2; 0). Знаходимо максимум функції F₂= 2 х₁ при умовах (63) і (64). Розв’язокм Z ⁽¹⁾= (6, 4; 0, 8).

Визначаємо тепер Х ⁽²⁾= Х ⁽¹⁾+λ ₂ (Z ⁽¹⁾– Х ⁽¹⁾). Останню рівність перепишемо в такий спосіб:

Підставляючи тепер у функцію (62) замість х₁ і х₂ їх значення відповідно до співвідношень (70), одержуємо

f (λ ₂)=2+12,8λ ₂ –41,76λ ₂ ²,

звідки f′ (λ ₂)=12,8–83,52λ ₂. Прирівнюючи f′ (λ ₂) нулю і вирішуючи отримане рівняння, знаходимо λ ₂ ≈0,15. Таким чином,

тобто X ⁽²⁾=(0,96; 0,97), f (X ⁽²⁾)=2,9966, f (X ⁽²⁾)– f (X ⁽¹⁾)=2,9966–2=0,9966> ε = 0,01.

III ітерація. Градієнт функції f у точці Х ⁽²⁾є f (Х ⁽²⁾)=(0,08; 0,12). Знаходимо максимум функції F₃ =0,08 x₁ +0,12 x₂ при умовах (63) і (64). Розв’язокм є Z ⁽²⁾=(6; 0).

Визначаємо Х ⁽³⁾= Х ⁽²⁾+λ ₃ (Z ⁽²⁾– Х ⁽²⁾). Маємо

f (λ ₃)=2,9384+0,4032λ ₃ –27,3416λ ₃,

f (λ ₃)=0,4032–54,6832λ ₃.

Вирішуючи рівняння f′ (λ ₃)=0, знаходимо λ ₃ ≈0,007. Отже, Х ⁽³⁾=(0,99528; 0,96321), f (X ⁽³⁾)=2,99957, f (X ⁽³⁾)– f (X ⁽²⁾)=2,99957–2,9966=0,00297 < ε = 0,01.

Таким чином, X ⁽³⁾ = (0,99528; 0,96321) є шуканим Розв’язокм вихідної задачі. Дана точка X ⁽³⁾перебуває досить близько до точки максимального значення цільової функції Х *=(1; 1), знайденої при рішенні цієї задачі в § 3.3. Задавши меншу величину е, можна було, зробивши додаткові наближення, ще ближче підійти до точки максимального значення цільової функції.

2. Метод штрафних функцій. Розглянемо задачу визначення максимального значення ввігнутої функції f (х₁, х₂,..., х_п)при умовах g_i (х₁, х₂,..., х_п) < b_i (i = ), х_j ≥ 0 (j = ), де g_i (х₁, х₂,..., х_п)– випуклі функції.

Замість того щоб безпосередньо вирішувати цю задачу, знаходять максимальне значення функції F (х₁, х₂,..., х_п) =f (х₁, х₂,..., х_п) +Н (х₁, х₂,..., х_п),щоє сумою цільової функції задачі, і деякої функції Н (х₁, х₂,..., х_п),що визначена системою обмежень і називається штрафною функцією. Штрафну функцію можна побудувати різними способами. Однак найбільш часто вона має вигляд

Н (х₁, х₂,..., х_п)= (х₁, х₂,..., х_п) g_i (х₁, х₂,..., х_п),

де

α_i (х₁, х₂,..., х_п)= (71)

а α_i > 0 – деякі постійні числа, що представляють собою вагові коефіцієнти.

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

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

Отже, процес знаходження Розв’язок задачі випуклого програмування методом штрафних функцій включає наступні етапи:

1. Визначають вихідне припустиме Розв’язок.

2. Вибирають крок обчислень.

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

4. По формулі (72) знаходять координати точки, що визначає можливе нове Розв’язок задачі.

5. Перевіряють, чи задовольняють координати знайденої точки системі обмежень задачі. Якщо ні, то переходять до наступного етапу. Якщо координати знайденої точки визначають припустиме Розв’язок задачі, то досліджують необхідність переходу до наступного припустимого Розв’язок. У випадку такої необхідності переходять до етапу 2, у протилежному випадку знайдено прийнятне Розв’язок вихідної задачі.

6. Встановлюють значення вагових коефіцієнтів і переходять до етапу 4.

3.28. Знайти максимальне значення функції

f= – x₁ ²– x₂ ² (73)

при умовах

(х₁ –7)²+(х₂ –7)² ≤ 18, (74)

x₁, x₂ ≥ 0 (75)

Розв’язок. Цільова функція даної задачі являє собою від’ємно-визначену квадратичну форму і, отже, ввігнута. У той же час область припустимих рішень задачі, обумовлена обмеженнями (74) і (75), – випукла. Отже, задача (73)-(75) є задачею випуклого програмування. Для знаходження її Розв’язок застосуємо метод штрафних функцій. Перш ніж це зробити, побудуємо область припустимих рішень задачі (рис. 3.6) і лінії рівня, що визначаються цільовою функцією (73). Цими лініями служать окружності із центром у точці (0; 0). Точка дотику однієї із цих окружностей з областю припустимих рішень і є шуканою точкою максимального значення цільової функції.

Рис. 3.6

Покладемо Х ⁽⁰⁾ = (6,7). Візьмемо λ=0, 1, позначимо через g (х₁, х₂)=18–(х₁ –7)²––(х₂ –7)² і визначимо частинні похідні від функцій f (х₁, х₂) і g (х₁, х₂) по змінним х₁ і х₂:

Тепер, використовуючи формулу (72), приступаємо до побудови послідовності точок, одна з яких визначить прийнятне Розв’язок.

I ітерація. Так як точка Х ⁰=(6, 7) належить області припустимих рішень задачі, то другий доданок у квадратних дужках формули (72) дорівнює нулю. Отже, координати наступної точки X ¹обчислюємо за формулами

Перевіримо тепер, чи належить ця точка області припустимих рішень задачі. Для цього знайдемо g (X ¹)=18–4,84–1,96=11,2. Так як g (X ¹) > 0, то X¹ належить області припустимих рішень. У цій точці f (Х¹) =– 54,4.

II ітерація. Знаходимо

x₁ ⁽²⁾= тах {0; 0,48+0,1·(–2)·4,8}=3,84;

x₂ ⁽²⁾= тах {0; 0,56+0,1·(–2)·5,6}=4,48;

g (X ⁽²⁾)=18–9,9856–6,3504=1,664 > 0; f (X ⁽²⁾) = –34,816.

III ітерація. Знаходимо

x₁ ⁽³⁾= тах {0; 0,384+0,1·(–2)·3,84}=3,072;

x₂ ⁽³⁾= тах {0; 0, 4,48+0,1·(–2)·4,48}=3,584;

g (X ⁽³⁾)=18–15,429184–11,669056≈–9,0981.

IV ітерація. Точка X ⁽³⁾не належить області допустимих рішень задачі. Отже,

= тах {0; 3,072+0,1·[(–2)·3,072+ α [(–2)·3,072+14)]}= тах {0; 2,4576+ α ·0,7856};

= тах {0; 3,584+0,1·[(–2)·3,584+ α ((–2)·3,584+14)]}= тах {0; 2,8672+ α ·0,6832).

Тут виникає питання про вибір числа α. Найбільш доцільно обрати його так, щоб точка X ⁽⁴⁾ не занадто далеко віддалялася від границі області припустимих рішень, і, разом з тим, належала цій області. Цим вимогам задовольняє, зокрема, α =1,9. При даному значенні одержуємо

x₁ ⁽⁴⁾= тах {0; 2,4576+1,9·0,7856)≈3,950;

x₁ ⁽⁴⁾= тах {0; 2,8672+1,9·0,6832}≈4,165;

g (Х ⁽⁴⁾)=18–9,3025–8,037225≈0,660; f (Х ⁽⁴⁾)≈–32,950.

V ітерація. Маємо

x₁ ⁽⁵⁾= тах {0; 3,950+0,1·(–2)·3,950)=3,16;

x₂ ⁽⁵⁾= тах {0; 4,165+0,1·(–2)·4,165)=3,332;

g (Х ⁽⁵⁾) = 18–14,7456–13,454224≈–10,2.

VI ітерація. Знаходимо

x₁ ⁽⁶⁾= тах {0; 3,16+0,1·[(–2)·3,16+1,9·((–2)·3,16+ 14)]}≈3,987;

x₂ ⁽⁶⁾= тах {0; 3,332+0,1·[(–2)·3,332+1,9·((–2)·3,332+ 14)]}≈4,059;

g (Х ⁽⁶⁾)=18–9,078169–8,649481≈0,272; f (Х ⁽⁶⁾)≈–32,372.

VII ітерація. Знаходимо

x₁ ⁽⁷⁾= тах {0; 3,987+0,1·(–2)·3,987}≈3,189;

x₂ ⁽⁷⁾= тах {0; 4,059+0,1·(–2)·4,059}≈3,247;

g (Х ⁽⁷⁾) = 18–10,169721–10,543009≈–2,713.

VIII ітерація. Маємо

x₁ ⁽⁸⁾= тах {0; 3,189+0,1·[(–2)·3,189+1,9·((–2)·3,189+14)]}≈3,999;

x₂ ⁽⁸⁾= тах {0; 3,247+0,1·[(–2)·3,247+1,9·((–2)·3,247+14)]}≈4,027;

g (Х ⁽⁸⁾) = 18–9,006001–8,856576≈0,137; f (Х ⁽⁸⁾) = –32,185.

IX ітерація. Знаходимо

x₁ ⁽⁹⁾= тах {0; 3,999+0,1·[(–2)·3,99]}≈3,199;

x₂ ⁽⁹⁾= тах {0; 4,024+0,1·[(–2)·4,024]}≈3,219;

g (Х ⁽⁹⁾)=18–14,447601–14,295961≈–10,744.

X ітерація. Маємо

x₁ ⁽¹⁰⁾= тах {0; 3,199+0,1·[(–2)·3,199+1,9·((–2)·3,199+14)]}≈4,004;

x₂ ⁽¹⁰⁾= тах {0; 3,219+0,1·[(–2)·3,219+1,9·((–2)·3,219+14)]}≈4,012;

g (Х ⁽¹⁰⁾)=18–8,976016–8,928144≈0,096; f (Х ⁽¹⁰⁾)≈–32,128.

XI ітерація. Знаходимо

x₁ ⁽¹¹⁾=тах{0; 4,004+0,1·[(–2)·4,004]}≈3,203;

x₂ ⁽¹¹⁾= тах {0; 4,012+0,1·[(–2)·4,012]}≈3,210;

g (Х ⁽¹¹⁾)=18–14,417209–14,3641≈–10,781.

XII ітерація. Маємо

x₁ ⁽¹²⁾= тах {0; 3,203+0,1·[(–2)·3,203+1,9·((–2)·3,203+14)]}≈4,005;

x₂ ⁽¹²⁾= тах {0; 3,210+0,1·[(–2)·3,210+1,9·((–2)·3,210+14)]}≈4,008;

g (Х ⁽¹²⁾)≈–32,104.

Порівнюючи значення цільової функції, знайдені в точках, отриманих після X і XII ітерацій, бачимо, що вони з точністю до 10^-1 збігаються. Це говорить про близькість точки, знайденої на останній ітерації, до точки максимального значення цільової функції. Такий же висновок можна зробити, якщо досліджувати вектори-градієнти функцій f (Х)і g (Х)у точці Х ⁽¹²⁾. У цій точці

f (Х ⁽¹²⁾)=(-8,01; -8,016), g (Х ⁽¹²⁾)=(5,99; 5,984).

Обчислимо відношення однойменних координат векторів: –8,01/5,99≈–1,337; –8,016/5,984≈–1,339. Як видно, вони майже рівні між собою. Це означає, що вектори f (Х ⁽¹²⁾) і g (Х ⁽¹²⁾) практично колінеарні. Так як до того ж точка Х ⁽¹²⁾ перебуває поблизу границі області припустимих рішень (оскільки g (Х ⁽¹²⁾)≈0,078), то х₁ *=4,005 і х₂ *=4,012 можна вважати прийнятним Розв’язокм задачі. Це Розв’язок при необхідності можна уточнити подальшими кроками до повної колінеарності градієнтів цільової і обмежувальної функцій.

Послідовність точок, що одержують під час знаходження Розв’язок задачі, наочно ілюструється рис. 3.6.

3. Метод Эрроу-Гурвіца. При знаходженні Розв’язок задач нелінійного програмування методом штрафних функцій ми вибирали значення α_i довільно, що призводило до значних коливань віддаленості обумовлених точок від області припустимих рішень. Цей недолік усувається при рішенні задачі методом Эрроу-Гурвіца, відповідно до якого на черговому кроці числа α_i ⁽ ^k ⁾ обчислюють за формулою

α_i ⁽ ^k ⁾= тах {0; α_i ⁽ ^k ^-1)–λ g_i (X ⁽ ^k ⁾)} (i = ) (76)

Як початкові значення α_i ⁽⁰⁾ беруть довільні невід’ємні числа.

3.29. Використовуючи метод Эрроу-Гурвіца, знайти Розв’язок задачі 3.27, що полягає у визначенні максимального значення функції

f= –x₁ ²– x₂ ² (77)

при умовах

18–(x₁ –7)²–(x₂ –7)² ≥ 0, (78)

х₁, х₂ ≥ 0 (79)

Розв’язок. Як випливає з Розв’язок задачі 3.27, при знаходженні Розв’язок даної задачі методом Эрроу-Гурвіца перші три ітерації при однакових значеннях λ=0,1 в обох випадках збігаються. Це пояснюється тим, що кожна з точок, що одержують послідовно, належить області припустимих рішень, а тому α_i ⁽ ^k ⁾=0 (k = ) незалежно від того, знаходиться воно по формулі (71) чи (76).

IV ітерація. Так як g (Х ⁽³⁾) < 0, то координати наступної точки Х ⁽⁴⁾ знаходимо по формулі (72):

= тах {0; 3,072+0,1·[(–2)·3,072+α⁽⁴⁾((–2)·3,072+14)};

= тах {0; 3,584+0,1[(–2)·3,584+α⁽⁴⁾(–2)·3,584+14)]}.

Число α⁽⁴⁾ знайдемо за формулою (76):

α⁽⁴⁾= тах {0; α⁽³⁾–0,1 g (Х ⁽³⁾)}= тах {0; 0–0,1(–9,0981)}≈0,91.

Таким чином, x₁ ⁽⁴⁾≈3,172; x₂ ⁽⁴⁾≈3,489; g (Х ⁽⁴⁾)≈–8,981.

V ітерація. Знайдена точка Х ⁽⁴⁾=(3,172; 3,489) не належить області припустимих рішень вихідної задачі. Тому для знаходження координат наступної точки також використовуємо формулу (72). Однак перш ніж її застосувати, за формулою (76) знаходимо

α⁽⁵⁾= тах {0; 0,91–0,1(–8,981)}≈1,81.

Отже,

x₁ ⁽⁵⁾= тах {0; 3,172+0,1[(–2)·3,172+1,81((–2)·3,172+14]}≈3,923;

x₂ ⁽⁵⁾= тах {0; 3,489+0,1[(–2)·3,489+1,81((–2)·3,489+14)]}≈4,062;

g (Х ⁽⁵⁾)≈–0,1.

VI ітерація. Маємо

α⁽⁶⁾= тах {0; 1,81–0,1(–0,1)}≈1,82;

x₁ ⁽⁶⁾= тах {0; 3,923+0,1[(–2)·3,923+1,82((–2)·3,923+14)]}≈4,258;

x₂ ⁽⁶⁾= тах {0; 4,062+0,1[(–2)·4,062+1,82((–2)·4,062+14)]}≈4,319;

g (Х ⁽⁶⁾)≈1,294; а (Х ⁽⁶⁾)≈–36,784.

VII ітерація. Знаходимо

x₁ ⁽⁷⁾ =тах {0; 4,258+0,1·[(–2)·4,258]}≈3,406;

x₂ ⁽⁷⁾= тах {0; 4,319+0,1·[(–2)·4,319]}≈3,455;

g (Х ⁽⁷⁾)≈–7,484.

VIII ітерація. Маємо

α⁽⁸⁾= тах {0; 1,82–0,1·(–7,484)}≈2,57;

x₁ ⁽⁸⁾= тах {0; 3,406+0,1·[(–2)·3,406+2,57((–2)·3,406+14)]}≈4,572;

x₂ ⁽⁸⁾= тах {0; 3,455+0,1·[(–2)·3,455+2,57[(–2)·3,455+14)]}≈4,586;

g (Х ⁽⁸⁾)≈6,278; f (Х ⁽⁸⁾)≈–41,935.

IX ітерація. Знаходимо

x₁ ⁽⁹⁾= тах {0; 4,572+0,1·[(–2)·4,572]}≈3,658;

x₂ ⁽⁹⁾= тах {0; 4,586+0,1·[(–2)·4,586]}≈3,669;

g (Х ⁽⁹⁾)≈4,265.

X ітерація. Маємо

α⁽¹⁰⁾= тах {0; 2,57–0,1(–4,265))}≈3,0;

x₁ ⁽¹⁰⁾= тах {0; 3,658+0,1·(–2)·3,658+3,0((–2)·3,658+14)]}≈4,931;

x₂ ⁽¹⁰⁾= тах {0; 3,669+0,1·[(–2)·3,669+3,0((–2)·3,669+14)]}≈4,934

g (Х ⁽¹⁰⁾)≈9,451.

XI ітерація. Знаходимо

x₁ ⁽¹¹⁾= тах {0; 4,931+0,1·[(–2)·4,931]}≈3,945;

x₂ ⁽¹¹⁾= тах {0; 4,934+0,1·[(–2)·4,934]}≈3,947;

g (Х ⁽¹¹⁾)≈–0,654.

XII ітерація. Маємо

α⁽¹²⁾= тах {0; 3,0–0,1(–0,654)}≈3,06;

x₁ ⁽¹²⁾= тах {0; 3,945+0,1[(–2)·3,945+3,06((–2)·3,945+14)]}≈5,026;

x₂ ⁽¹²⁾= тах {0; 3,947+0,1[(–2)·3,947+3,06((–2)·3,947+14)]}≈5,026;

g (Х ⁽¹²⁾)≈10,207; f (Х ⁽¹²⁾)≈–50,521.

XIII ітерація. Знаходимо

x₁ ⁽¹³⁾= тах (0; 5,026+0,1[(–2)·5,026]}≈4,021;

x₂ ⁽¹³⁾= тах {0; 5,026+0,1[(–2)·5,026]}≈4,021;

g (Х ⁽¹³⁾)≈0,251; f (Х ⁽¹³⁾)≈–32,337.

Отримане на даній ітерації Розв’язок х₁ *=4,021 і х₂ *=4,021 можна вважати прийнятним. Це Розв’язок при необхідності варто поліпшити, продовживши ітераційний процес до одержання результату необхідної точності.

На закінчення відзначимо, що Розв’язок складних задач нелінійного програмування градієнтними методами пов’язане з більшим об’ємом обчислень і доцільне тільки з використанням ЕОМ.

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒