Аналіз чутливості використання методу Якобі для рішення задач лінійного програмування (стр. 3 из 4)

3. ВИКОРИСТАННЯ МЕТОДУ ЯКОБІ ДЛЯ РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Дано задачу лінійного програмування, у якій потрібно максимізувати z=2xi+3xa

при обмеженнях х₁+х₂+х₃=5

х_1-х2+х₄=3

х₁,х₂,х₃,х₄>0

Розглянемо обмеження x_j>0 устанавлюючи не заперечність перемінних. Нехай W_J²- відповідна (ненегативна) додаткова перемінна. При цьому x- W_J² чи x=W_J² .Така заміна робить надлишковим умову не заперечності перемінних, і вихідна задача приймає наступний вид:

максимізувати z=2W₁²+3W₂²

при обмеженнях W₁²+W₂²+W₃²=5,

W₁²-W₂²+W₄²=3.

Щоб застосувати метод Якобі, покладемо

Y=(W₁,W₂) і Z=(W₃,W₄).

(Помітимо, що вектори Y і Z, якщо використовувати термінологію лінійного програмування, утворені базисними і небазисними перемінними відповідно). Маємо

W₁ і W₂

Рішення рівняння

з обмеженнями дозволяє визначити стаціонарну крапку (w₁=2, w₂=1, w₃= 0, w₄= 0) . При цьому матриця Гессе має вид

Тому що Н_c- невизначена матриця, те стаціонарна крапка не є крапкою максимуму. Справді отриманий результат не є несподіваним, оскільки з теорії лінійного програмування випливає, що (небазисні) перемінні w₃ і w₄ (і, отже, х₃ і х₄ ) дорівнюють нулю. Це означає, що в залежності від конкретного вибору Y і Z рішення, отримане за допомогою методу Якобі, визначає відповідну екстремальну крапку багатогранника припустимих рішень. При цьому рішення може не бути оптимальним. Однак метод Якобі дозволяє ідентифікувати крапку оптимуму шляхом використання достатніх умов.

Відповідна стаціонарна крапка визначається набором значень W₁=0,

W₂ =5, W₃ =0 ,W₄ =8.

Матриця

є негативно визначеною. Таким чином, цьому рішенню відповідає крапка максимуму.

Отриманий результат можна перевірити графічно, користаючись, мал.2. Перше рішення (х₁=4, х₂=1) не є оптимальним на відміну від другого (х₁=0, х₂=5), що виявляється оптимальним, читачу надається можливість перевірити, що дві екстремальні крапки багатогранника, що залишилися, припустимих рішень не є крапками максимуму. Крім того, використовуючи достатні умови, можна показати, що в екстремальній крапці (х₁=0, х₂=0) має місце мінімум.

Слід зазначити, що у випадку рішення задачі лілейного програмування, уведені раніше, коефіцієнти чутливості

відіграють роль перемінних двоїстий задачі. Проілюструємо цей факт на розглянутому чисельному прикладі. Нехай u₁ і u_g - відповідні перемінні двоїстої задачі, значення яких у крапці оптимуму

(W₁=0, W₂ =5, W₃ =0 ,W₄ =8.) обчислюються по формулі:

Відповідне значення цільової функції двоїстої задачі дорівнює 5u₁+3u₂= 15 і збігається з оптимальним значенням цільової функції прямої задачі. Отримане рішення також задовольняє обмеженням двоїстої задачі, і , отже, є оптимальним. Це означає, що коефіцієнти чутливості збігаються з перемінними двоїстої задачі. Справді, неважко помітити, що і ті й інші допускають однакову інтерпретацію.

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

Таким чином, усі діагональні елементи цієї матриці повинні бути позитивними у випадку наявності мінімуму і негативними у випадку наявності максимуму. З вищевикладеного випливає, що необхідна умова наявності екстремума еквівалентно твердженню про те, що для перебування оптимального рішення потрібно перевірити тільки "базисні" (припустимі) рішення. У цьому випадку незалежні перемінні відіграють роль небазисних перемінні задачі лінійного програмування. Достатня умова приводить до висновку про можливу наявність точної відповідності між діагональними елементами матриці Гессе і двоїстими оцінками Z_J-C_J, одержуваними за допомогою симплекса-методу. Отримане рішення також задовольняє обмеженням двоїстої задачі. Справді, неважко помітити, що і ті й інші допускають однакові інтерпретації. Це означає, що коефіцієнти чутливості збігаються з перемінними двоїстої задачі.

4. АЛГОРИТМ РІШЕННЯ ЕКСТРЕМАЛЬНИХ ЗАДАЧ МЕТОДОМ ЯКОБІ

Розглянемо наступну задачу:

мінімізувати

при обмеженнях g(X) =0,

де X=(x₁,x₂,…,x_n),g=(g₁,g₂,…,g_m)^T...

Функції

і i=1,2,..., m, передбачаються двічі безупинно дифференційними.

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

у всіх крапках, що задовольняють обмеженню g(X) =0. При цьому стаціонарними будуть крапки, у яких зазначені частки похідні звертаються в нуль. Для класифікації стаціонарних крапок можна користатися достатніми умовами існування екстремумів.

З теореми Тейлора випливає, що для крапки

з припустимої околиці крапки X можна записати наступні формули:

При

маємо

Тому що g(X)=0, те

=0 у припустимій області. Звідси

Отримана система містить (m+1) рівнянь з (n+1) невідомими, котрими є

і . Невідому величину можна визначити, якщо знайдений вектор . Це означає, що в нас мається m рівнянь з n невідомими.

Якщо m>n то принаймні (m-n) рівнянь виявляються надлишковими. Після усунення надмірності кількість незалежних рівнянь у системі стає рівним m<n. У випадку коли m=n рішення тривіальне:

=0. При цьому крапка X не має припустимої околиці, і, отже, простір рішень складається з єдиної крапки. Така ситуація не представляє інтересу. Випадок, що залишився, коли m<n, необхідно розглянути докладно. Нехай X(Y,Z), де Y=(y₁,y₂,…,y_m)і Z=(z₁,z₂,…,z_n-m)є відповідно залежний і незалежний перемінний, утворюючий вектор Х. У нових позначеннях градієнти функцій  і g мають наступний вид:

Уведемо визначення двох матриць:

Матрицю J_mxm: називають матрицею Якобі, а C_{mx (n-m)} -матрицею керування. Передбачається, що матриця Якобі J невирождена. Цей факт завжди має місце, оскільки m рівнянь незалежні по визначенню. Отже, компоненти вектора J можна вибрати серед компонентів X таким чином, що матриця J виявиться невирожденою.

Використовуючи дані вище визначення, перепишемо вихідну систему рівнянь з невідомими

й у наступному виді: