Курсовая работа: Аналіз чутливості використання методу Якобі для рішення задач лінійного програмування

За допомогою мал. 1 неважко помітити, що перша похідна (тангенс кута нахилу дотичної до графіка) функції прагне до нуля в міру наближення до екстремальних крапок. Однак це характерно не тільки для єкстремумів. Наприклад, тангенс кута нахилу дотичної до графіка в крапці x₅ також дорівнює нулю.

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

1.2. Необхідні і достатні умови існування єкстремумів

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

Теорема I. Якщо крапка Х₀ є екстремальною крапкою функції, то

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

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

будемо називати стаціонарними. Наступна теорема встановлює достатні умови для того, щоб Х₀ була екстремальною крапкою.

Теорема 2. стаціонарна крапкаХ₀ є екстремальною, коли матриця Гессе Н^В крапціХ₀ виявляється (1) позитивно визначеною(тодіХ₀ – крапка мінімуму); (2) негативно визначеною (тодіХ₀ – крапка максимуму)

Теорема 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