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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Аналіз чутливості використання методу Якобі для рішення задач лінійного програмування

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

2

ЗМІСТ

УВЕДЕННЯ

1. ЗАГАЛЬНІ ЗВЕДЕННЯ ПРО КЛАСИЧНУ ТЕОРІЮ ОПТИМІЗАЦІЇ

1.1. Екстремальні задачі без обмежень

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

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

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

2.1. Метод Якобі

2.2. Метод Лагранжа

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

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

5. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

5.1. Постановка задачі

5.2. Рішення задачі

УВЕДЕННЯ

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

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

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

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

З вищевикладеного випливає, що необхідна умова наявності єкстремума еквівалентно твердженню про те, що для перебування оптимального рішення потрібно перевірити тільки "базисні" (припустимі рішення). У цьому випадку незалежні перемінні відіграють роль небазисних перемінні задачі лінійного програмування.

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

1.ЗАГАЛЬНІ ЗВЕДЕННЯ ПРО КЛАСИЧНУ ТЕОРІЮ

ОПТИМІЗАЦІЇ

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

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

1.1.Екстремальні задачі без обмежень

Екстремальна крапка функції визначає або максимум, або мінімум цієї функції. Крапка X0=(x1,…,xj,…,xn)є крапкою максимуму, якщо нерівність

(X0=h)<

виконується для всіх h=(h1,…,hj,…,hn)таких, що |hj| досить мало для всіх j. Іншими словами, X0 є крапкою максимуму, якщо значення функції в кожній крапці досить малої околиці X0 не перевищує (X0). Аналогічно X0 є крапкою мінімуму, якщо для вектора h, визначеного вище, справедлива нерівність

На мал. I показані максимуми і мінімуми функції одному перемінної (x) на відрізку /a, b/. (Умова a<x<b не означає, що на (x) накладені обмеження.) Крапки x1, x2, x3, x4 і x6 визначають єкстремуми (x), причому x1, x3 і x6-- максимуми, a x2 і x4-- мінімуми. Тому що

те являє собою глобальний, чи абсолютний, максимум, а і є локальними, чи відносними, максимумами. Аналогічно є локальний мінімум, -- глобальний мінімум.

Максимум у крапці x1 відрізняється від інших локальних максимумів тим, що значення функції принаймні в одній крапці околиці x1 дорівнює . З цієї причини x1 називають крапкою нестрогого максимуму у відмінність, наприклад, від крапки x3, що визначає строгий максимум . Під нестрогим максимумом, таким чином, розуміється наявність (нескінченної кількості) незбіжних крапок, яким відповідає те саме максимальне значення функції. У крапці x4 спостерігається нестрогий мінімум, що визначається аналогічним образом. Узагалі говорячи, X0 є крапкою нестрогого максимуму, якщо (X0=h)< , і крапкою строгого максимуму, якщо (X0=h)< , де h -- вектор, визначення якого дано вище.

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

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

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

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

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

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

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

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

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

Теорема 3. Якщо в стаціонарній крапці в0 перші (n - 1) похідних функцій звертається в нуль, а , то при в=у0 функція має:

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

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

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

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

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

2.1 Метод Якобі

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

Нехай ; тоді

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

що відповідає введеному раніше визначенню. Вираження для (Y,Z) може бути використане при аналізі змін у припустимій околиці крапки Х0, викликуваних такими змінами і . В екстремальній (точніше, у будь-якій стаціонарній) крапці Хо=(Уо, 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

2

=2

+2

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

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

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

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

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

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

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

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

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

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

при обмеженнях х1+х2+х3=5

х1-х2+х4=3

х1,х2,х3,х4>0

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

максимізувати z=2W12+3W22

при обмеженнях W12+W22+W32=5,

W12-W22+W42=3.

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

Y=(W1,W2) і Z=(W3,W4).

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

W1 і W2 ???

Рішення рівняння з обмеженнями дозволяє визначити стаціонарну крапку (w1=2, w2=1, w3= 0, w4= 0) . При цьому матриця Гессе має вид

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

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

W2 =?5, W3 =0 ,W4 =?8.

Матриця

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

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

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

(W1=0, W2 =?5, W3 =0 ,W4 =?8.) обчислюються по формулі:

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

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

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

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

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

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

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

де X=(x1,x2,…,xn),g=(g1,g2,…,gm)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=(y1,y2,…,ym)і Z=(z1,z2,…,zn-m)є відповідно залежний і незалежний перемінний, утворюючий вектор Х. У нових позначеннях градієнти функцій ? і g мають наступний вид:

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

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

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

Тому що матриця J-- невирождена, існує зворотна матриця J-1. Отже,

Ці рівняння визначають як функцію (нагадаємо, що Z є вектором незалежних перемінних). Заміна в рівнянні дозволяє виразити через :

З цього рівняння випливає, що диференціювання функції по векторі незалежних перемінних Z дає формулу:

де -приведений градієнт функції. Вектор (Y,Z) повинний звертатися в нуль у стаціонарних крапках.

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

Вектор задає i-ю рядок (приведеної) матриці Гессе. Помітимо, що W є функцією Y, а Y-- функцією Z; при цьому

Таким чином, при обчисленні частинної похідної по zi, варто застосувати до компонентів W правило диференціювання складної функції. Це означає, що

5. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

5.1. Постановка задачі.

Розглядається наступна задача:

максимізувати ??X?=x12+2x22+10x32+5x1x2,

при

g1 (X)=x1+x2+3x2x3-5=0

g2 (X)=x12+5x1x2+x3x2+x32-7=0

Застосувати метод Якобі для перебування дс ?(х) у припустимій околиці припустимої крапки X0 (1,1,1). Припустити, що зазначена околиця визначається умовою

5.2. Рішення задачі

Нехай Y=(X2,X3), Z=X3 має:

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

Отже

Тому що:

Якщо задана величина зміни незалежної перемінний Х1, то припустимі значення і залежних перемінних Х2 і Х3 визначаються відповідно до формули

.

При одержуємо

Для перевірки точності отриманої вище оцінки обчислимо іншим способом:

Знайдемо ?(?X) і ?(Х0+ ).

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