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

Теорема 3. Якщовстаціонарнійкрапці в₀перші (n - 1) похідних функцій

звертається в нуль, а

, то при в=у₀функція

має:

(1) крапку перегину, якщо n – непарне;

(2) екстремальну крапку, якщо n – парне. Екстремальній крапці відповідаємаксимумпри

і мінімум при

.

1.3. Екстремальні задачі при наявності обмежень у виді рівності

Існує два методи оптимізації при наявності обмежень у виді рівностей. Один з них — метод Якобі. Він являє собою узагальнення симплекса-методу лінійного програмування. Дійсно, усі процедури, зв'язані з реалізацією симплекса-методу, можна обґрунтувати, користаючись методом Якобі. Інший метод, метод множників Лагранжа, тісно зв'язаний з методом Якобі і є його логічним розвитком.

2. АНАЛІЗ ЧУТЛИВОСТІ ЗА ДОПОМОГОЮ МЕТОДУ ЯКОБІ

2.1 Метод Якобі

Метод Якобі може бути використаний для дослідження чутливості оптимального значення f м малим змінам у правих частинах обмеження. Припустимо, наприклад, що в правій частині i-го обмеження gi(x)=0 фігурує величина

, а не нуль. Як це відіб'ється на оптимальному значенні f. Дослідження такого роду носять назви аналізу чутливості; вони мають визначену подібність з відповідними процедурами в лінійному програмуванні. Однак слід зазначити, що результати, одержувані при аналізі чутливості в нелінійному програмуванні, справедливі лише для малої околиці екстремальної крапки, і обумовлені можливістю локальної лінеаризації. Проте, знайомство з такими процедурами виявляється корисним при вивченні методу множників Лагранжа. Вище було показано, що

Нехай

; тоді

Підставивши останнє вираження в рівняння для

одержавши рівняння

що відповідає введеному раніше визначенню. Вираження для

(Y,Z) може бути використане при аналізі змін у припустимій околиці крапки Х⁰, викликуваних такими змінами і . В екстремальній (точніше, у будь-якій стаціонарній) крапці Хо=(Уо, Zо) приведений градієнт повинний звертатися в нуль. Таким чином, у крапці Хо справедлива рівність

чи

Отже, вплив малих змін на оптимальне значення f можна досліджувати шляхом оцінювання швидкості зміни f стосовно змін д. Ці величини звичайно називають коефіцієнтом чутливості.

В екстремальній крапці коефіцієнти

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

Тому розбивка вектора Х на Y і Z у даному випадку не є істотним чинником. Таким чином, зазначені коефіцієнти залишаються постійними при будь-якому виборі вектора Y. Вище показано, що коефіцієнти чутливості

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

відкіля .

Це рівняння відбивають необхідні умови стаціонарності крапок, тому що формула

була отримана з урахуванням припущення про те, що . Рівняння можна записати в більш зручній формі, якщо перейти до часток похідним по всім Xj, що приводить до системи J=1,2…n

Отримані рівняння разом з обмеженнями g=0 дають можливість визначити припустимі вектори х і

, що задовольняють необхідні умови стаціонарності.

2.1 Метод Лагранжа

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

L(x,)=

(x, ) - g(x) .

Функція L називається функцією Лагранжа. Параметри

звуться множників Лагранжа і, як випливає з визначення, мають той же зміст, що і коефіцієнти чутливості описані вище. Рівняння

і

виражають розглянуті вище необхідні умови наявності єкстремуми, що породжуються функцією Лагранжа безпосередньо. Це означає, що задача оптимізації з цільовою функцією f(x) при наявності обмеження g(х)=0 еквівалентна задачі перебування безумовного єкстремуми функції Лагранжа

L(x,

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

, де і для всіх i і J

= +

Матриця Н^B являє собою так називану облямовану матрицю Гессе.

Нехай дана стаціонарна крапка (х₀,

₀₎ функції Лагранжа L (х, ), а облямована матриця Гессе Н^В сформована зі значень відповідних елементів у крапці (Хо, ₀). Тоді Х₀ є:

1) крапкою максимуму, якщо, починаючи з головного мінору порядку (m+l), наступні (n-m) головних мінорів матриці Н^В утворять знакоперемінний числовий ряд, знак першого члена якого визначається множником ,(-1)^м+1;

2) крапкою мінімуму, якщо, починаючи з головного мінору порядку (m+1), знак наступних (n-m) головних мінорів матриці Н^В визначається множником (-1)^м. Сформульовані умови виявляються достатніми для ідентифікації екстремальної крапки, але не є необхідними. Іншими Словами, стаціонарна крапка, що не задовольняє цим умовам, може бути екстремальною. Існують інші умови для ідентифікації екстремальних крапок, що є як необхідними, так і достатніми. Однак практичне використання цих умов у ряді випадків зв'язано зі значними обчислювальними труднощями. Визначимо матрицю

утворену значеннями відповідних функцій у стаціонарній крапці (Хо,

₀). Тут µ - невідомий параметр, а Р и Q визначені вище. Нехай | |-визначник матриці ; тоді кожний з (n-m) дійсних коренів і i полінома | |=0 повинний бути:

1)негативним, якщо хо - крапка максимуму;

2)позитивним, якщо хо- крапка мінімуму.

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

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