Загальна характеристика методів розв’язування задач нелінійного програмування.

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

Математична модель задачі нелінійного програмування (НЛП) має такий вигляд:

(3.1) за умов обмежень

(3.2)

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

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

Широка сукупність методів розв’язування задач нелінійного програмування базується на використанні диференційного числення для знаходження точок екстремумів функцій.

Сутність згаданих щойно методів розв’язування нелінійних задач розкриємо в межах їх класифікації, згідно з якою вирізняють такі методи:

1) класичної математики знаходження екстремумів функцій;

2) для задач з обмеженнями-рівностями;

3) для задач з обмеженнями-нерівностями.

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

До методів другої групи можна віднести метод зведеного градієнта (метод Якобі), який є узагальненням симплексного методу лінійного програмування, а також найпоширеніший метод множників Лангранжа, який докладніше буде розглянуто далі.

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

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

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

Так, для задач з опуклими цільовими функціями у вигляді квадратичної форми

використовуються методи квадратичного програмування, які ґрунтуються на теоремі Куна-Таккера про існування екстремуму функції Лагранжа для досліджуваної задачі.

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

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

 

Метод множників Лагранжа.

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

Розв’язується загальна задача нелінійного програмування (3.1) – (3.2) за припущення, що система обмежень містить лише рівняння, а функції неперервні і диференційовані, тобто:

Розв’язувати задачу НЛП починаємо з побудови функції Лагранжа. Щоб побудувати функцію Лагранжа, вводимо сукупність змінних , які називаються множниками Лагранжа. Тоді функція Лагранжа набирає вигляду:

Для визначення безумовного екстремуму цієї функції (згідно з необхідною умовою його існування) слід знайти частинні похідні від функції Лагранжа по всіх n+m змінних та .

Прирівнявши ці похідні до нуля, маємо таку систему рівнянь:

;

Будь-який розв’язок цієї системи визначає точку яка є екстремальною для цільової функції Z.

Приклад 3.1. Д ля виробництва двох видів продукції А і В використовуються два типи обмежених ресурсів. Прибуток від реалізації цих виробів є нелінійною функцією від обсягів виробництва. Вихідні дані щодо норм витрат ресурсів на одиницю продукції, запасу ресурсів у виробника, а також прибутку за одиницю продукції в табл. 3.1.

 

Таблиця 3.1.

Вихідні дані	Продукція А В	Запас ресурсів
Ресурси І П	І 4	3 2
Обсяг виробництва
Прибуток

 

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

Розв’язування.

Математична модель цієї задачі нелінійного програмування така:

за умов

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

Знайдемо частинні похідні від цієї функції за всіма невідомими параметрами:

Розв’язавши цю систему рівнянь, отримаємо:

Отже, точка екстремуму для функції сумарного прибутку Z є , яка визначає обсяги виробництва продукції А і В у кількості відповідно 0,6 та 2,1 одиниці.

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

Приклад 3.2. Знайти оптимальне рішення нелінійної задачі методом множників Лагранжа.

при обмеженні .

Складемо функцію Лагранжа:

Візьмемо похідні від функції Лагранжа:

Отримали три рівняння з трьома невідомими, з яких з третього рівняння випливає:

X₁=8–X₂ (3.3)

Підставляємо (3.3) у перше рівняння і вирішуємо далі сумісно з другим:

Таким чином, отримуємо оптимальне значення функції мети:

,

при обмеженні .

Після цього досліджують оптимум на мінімум та максимум. Для цього збільшуємо та зменшуємо змінну :

1) Але ми повинні врахувати обмеження (8.3), з якого випливає . Тоді — функція мети збільшилась.

2) З врахуванням обмеження (8.3) отримуємо і тоді — функція мети збільшилась.

Тоді робимо висновок: у точці ; отриманий мінімум функції мети і остаточно

.

 

3.3. Задачі для самостійного розв’язання:

№1. Розв’язати такі задачі квадратичного програмування.

1. Z = – X₁ – 2X₂ + X₂² а Min; 2. Z = - 8X₁ - 10X₂ + X₁² + X₂² а Min;

3X₁ +2X₂ < 6+A

X₁ +2X₂ < 4 +A, 3X₁ + 2X₂ + X₃ = 6 +A,

X₁ > 0, X₂ > 0. X₁ > 0, X₂ > 0, X₃ > 0.

2. Z = 3X₁ –3X₂ – X₁² – 3X₂² а Max; 4. Z = 2X₁X₂ – X₁² – X₂² а Max;

3X₁ +X₂ +X₃ +X₄ = 16+A, 2X₁ – X₂ < 6 +A,

– X₁ + 3X₂ –X₃ –X₄ = 4 +A, X₁ + 2X₂ <10+ A,

X₁ > 0, X₂ > 0, X₃ > 0, X₄ > 0. X₁ > 0, X₂ > 0.

№2. Розв’язати задачу нелінійного програмування методом множників Лагранжа.

Z = 3X₁ – 3X₂ – X₁² – 3X₂² à Max;

3X₁ +X₂ = 16,

– X₁ + 3X₂= 4,

X₁ > 0, X₂ > 0.

№3. Розв’язати задачу нелінійного програмування методом множників Лагранжа.

Z = 2X₁X₂ – X₁² – X₂² à Max;

2X₁ – X₂ = 6,

3X₁ + 2X₂ = 10,

X₁ > 0, X₂ > 0.

№4. Розв’язати задачу нелінійного програмування методом множників Лагранжа.

Z = (X₁ + X₂)² à Min;

X₁ + 7 X₂ = 2;

X₁ + 2X₂= 6;

X₁ > 0, X₂ > 0.

№5. Розв’язати задачу нелінійного програмування методом множників Лагранжа.

Z = (5X₁ + 3X₂)² à Min;

2X₁ + 5 X₂ = 9;

3X₁ + 4X₂= 15;

X₁ > 0, X₂ > 0.

№6. Розв’язати задачу нелінійного програмування методом множників Лагранжа.

Z = 7X₁² + 3X₂² à Max;

4X₁ – 5 X₂ = 9;

X₁ + 5X₂= 15;

X₁ > 0, X₂ > 0.

 

№7. Методом множників Лагранжа розв’язати задачі.

1. F=(4X₁–N)² + (X₂ –3N)à min;

2. F=(X₁–A)² + (3X₂ – N)²à min

3X₁ + AX₂=N;

6X₁ + 3X₂=N

Тут N – порядковий номер студента у групі. А=

№8. Методом множників Лагранжа розв’язати задачі.

ТЕСТИ

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

а) дотику

б) сідловою

в) локального або глобального екстремуму функції Z

г) цільового призначення

2. Опукле програмування – це:

а) розділ математичного програмування, який вивчає методи розв'язання задач цілеспрямованого характеру

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