Тема 1. 5. Нелінійні статичні моделі

1.5.1. Загальні поняття про нелінійну модель

Якщо зв’язок між змінними величинами, які входять у модель, або функція мети є нелінійними, то модель належить до класу нелінійних.

Можливі такі випадки:

 

 

а)

 

б)

 

в)

 

У випадку а) функція мети є лінійною, а обмеження нелінійними. У випадку б) функція мети є нелінійною, а обмеження - лінійними. У випадку в) і функція мети, і обмеження є нелінійними.

Нелінійна модель на відміну від лінійної має такі особливості:

· область допустимих розв’язків може бути неопуклою, складатися з відокремлених підмножин;

· функція мети може бути неопуклою;

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

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

 

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

Розглянемо частинний випадок нелінійної задачі:

 

(1.107)

, (1.108)

 

де (1.107) - нелінійна функція мети від n змінних величин;

(1.108) - нелінійні обмеження;

b_i - сталі величини.

На змінні величини x_j не покладається умова невід’ємності, що дає змогу розглядати задачу (1.107) - (1.108) як класичну задачу умовної оптимізації.

Допустимо, що функції f(x), g_i(x) є неперервними разом із своїми частинними похідними.

Перейдемо від задачі умовної до задачі безумовної оптимізації шляхом побудови функції Лагранжа:

 

(1.109)

 

Необхідною умовою існування екстремуму функції Лагранжа буде:

 

(1.110)

 

Кожен розв’язок системи рівнянь (1.110) визначає можливу точку екстремуму Х⁰=(х₁⁰,...,х_n⁰).

Для лінійної задачі

 

, (1.111)

 

, (1.112)

 

функція Лагранжа прийме такий вигляд:

 

(1.113)

 

Необхідною умовою існування екстремуму функції Лагранжа буде:

 

(1.114)

 

(1.115)

 

Якщо задачу (1.107) - (1.108) доповнити умовою x_j³0, що є типовим обмеженням в економічних задачах, то необхідна умова існування екстремуму функції Лагранжа для задачі:

 

(1.116)

 

(1.117)

 

(1.118)

 

описується теоремою Куна-Такера.

За теоремою Куна-Такера точка Х⁰=(х₁⁰,...,х_n⁰) буде розв’язком задачі (1.116) - (1.118) лише тоді, коли знайдеться такий вектор l⁰=(l₁⁰,...,l_m⁰) при якому для функції Лагранжа

 

 

в точці (Х⁰; l⁰) будуть виконуватися такі умови:

 

 

(1.119)

 

(1.120)

 

(1.121)

 

(1.122)

 

(1.123)

 

Для загальної задачі лінійного програмування

 

 

 

 

функція Лагранжа набере вигляду

 

(1.124)

 

а необхідна умова існування екстремуму функції опишеться системою обмежень:

 

(1.125)

 

(1.126)

 

(1.127)

 

(1.128)

 

(1.129)

 

(1.130)

 

1.5.3. Множники Лагранжа і двоїсті оцінки задачі лінійного програмування

 

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

 

(1.131)

 

(1.132)

 

(1.133)

 

яку перетворимо до вигляду

 

(1.134)

 

(1.136)

 

(1.137)

 

Позначимо множники Лагранжа для задачі (1.134) - (1.137) через х_j і побудуємо функцію Лагранжа:

 

(1.138)

 

Умови Куна-Такера для функції Лагранжа (1.138) можна записати в такому вигляді:

 

(1.139)

 

(1.140)

 

(1.141)

 

(1.142)

 

(1.143)

 

(1.144)

 

Очевидно, що умови (1.139), (1.141), (1.144) для задачі (1.131) - (1.133) співпадають з обмеженнями (1.126), (1.128), (1.129) для загальної задачі лінійного програмування, а обмеження (1.140), (1.142), (1.143) - з обмеженнями (1.125), (1.127), (1.130). Подібна пара задач називається двоїстою. Множники Лагранжа l_і - суть не що інше як двоїсті змінні (двоїсті оцінки), які характеризують чутливість функції мети щодо зміни значень b_i.

 

Приклад 7. Графічне розв’язування нелінійних задач

Знайти оптимальний розв’язок таких задач:

а)

б)

в)

У випадку а) максимальне значення функції мети досягається в точці В(1; 0), тобто f_max =f(B)=1.

Мінімальне значення f(х) досягається в точці А(0;1) і дорівнює f_min =f(А)=-1.

У випадку б) максимальне значення ФМ досягається в точці С(0; 4), тобто f_max =f(С)=(0-4)²+(4-1)²=25.

Мінімальне значення f(х) досягається у внутрішній точці Е(4;1) і дорівнює f_min =f(Е)=0.

У випадку в) максимальне значення ФМ досягається в точці М(7; 4/7), тобто f_max =f(М)=49+16/49=2417/49.

Мінімальне значення функції мети досягається в точках А(1;4) та L(4;1) і дорівнює f_min =f(L)=17.

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

Для задачі

Знайти оптимальний розв’язок.

Будуємо функцію Лагранжа

За необхідною умовою існування екстремуму функції Лагранжа отримаємо:

Звідки слідує:

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

Для задачі

побудуємо функцію Лагранжа

і запишемо необхідні умови Куна-Такера існування екстремуму функції:

Пересвідчуємося, що ці умови виконуються для Х⁰=(6/7; 4/7) при l⁰=(3/7; 1/7), а значить точка Х⁰=(6/7; 4/7) є точкою максимуму функції мети в заданій області допустимих розв’язків.

Оскільки l₁⁰=3/7, l₂⁰=1/7, то це означає, що збільшення b₁ в умові задачі на одиницю (b₁^¢ =3) призведе до зростання функції мети на 3/7, а збільшення b₂=4 на одиницю (b₂^¢ =5), призведе до зростання функції мети на 1/7.