Головна

Метод Франка-Вулфа

  1. I метод.
  2. I. Методика бухгалтерського обліку
  3. I. МЕТОДОЛОГІЯ
  4. I. ОРГАНІЗАЦІЙНО-МЕТОДИЧНИЙ РОЗДІЛ
  5. II метод.
  6. Ii. Методики зовнішньої іммобілізації
  7. II. Методичні вказівки для студентів по виконанню індивідуальних завдань

Нехай потрібно знайти максимальне значення увігнутою функціонально

f (x1, x2, ..., Xn) (2.10)

при умовах

(i= 1, ..., m), (2.11)

xj?0 (j= 1, ..., n). (2.12)

Характерною особливістю цього завдання є те, що її система обмежень містить тільки лінійні нерівності.

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

Процес знаходження рішення задач починається з визначення точки, що належить ОДР завдання.

 
 

Нехай ця точка X(K), Тоді в цій точці обчислюють градієнт функції (2.10)

і будують лінійну функцію

F= (2.13)

Потім знаходять максимальне значення цієї функції при обмеженнях (2.10-2.11). Нехай рішення даної задачі визначається точкою Z(K). Тоді за нове допустиме рішення вихідної завдання беруть координати точки X(K + 1)

X(K + 1)= X(K)+ lk (Z(K)-X(K)), (2.14)

де lk - Деяке число, зване кроком обчислень і укладену між нулем і одиницею (0 ? lk? 1).

це число lk беруть довільно або визначають таким чином, щоб значення функції в точці X(K + 1) f (X(K + 1)), Залежне від lk, було максимальним. Для цього необхідно знайти рішення рівняння і вибрати його найменший корінь.

Якщо його значення більше одиниці, то слід покласти lk= 1.

Після визначення числа lk знаходять координати точки X(K + 1), обчислюють значення цільової функції в ній і з'ясовують необхідність переходу до нової точки X(K + 2).

Якщо така необхідність є, то обчислюють в точці X(K + 1) градієнт цільової функції, переходять до відповідної ЗЛП і знаходять її рішення. Визначають координати точки X(K + 2) і досліджують необхідність проведення подальших обчислень.

Після кінцевого числа кроків отримують з необхідною точністю рішення вихідної завдання.

Отже, процес знаходження рішення задачі методом Франка-Вулфа включає наступні етапи:

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

2.Знаходять градієнт функції (2.10) в точці допустимого рішення.

3.Будують функцію (2.13) і знаходять її максимальне значення за умов (2.11 - 2.12).

4.Визначають крок обчислень.

5.За формулами (2.14) знаходять компоненти нового допустимого рішення.

6.Перевіряють необхідність переходу до наступного допустимому рішенням. У разі необхідності переходять до етапу 2, В іншому випадку знайдено прийнятне рішення вихідної завдання.

П р и м і р 1. Методом Франка-Вулфа знайти рішення задачі, що складається визначенні максимального значення функції

 (2.15)

при умовах

 (2.16)

x1, x2?0. (2.17)

 Рішення. Знайдемо градієнт функції

 
 

і в якості вихідного допустимого рішення задачі візьмемо точку X(0)=(0; 0), а в якості критерію оцінки якості одержуваного рішення - нерівність

де e= 0.01.

1 ітерація. У точці X(0) градієнт Nf (X(0))= (2; 4). Знаходимо максимум функції

F1= 2x1+ 4x2 (2.18)

 за умов (2) і (3)

(2.19)

x1, x2?0. (2.20)

Завдання (2.18) - (2.20) має оптимальний план Z(0)= (0; 4).

Знайдемо нове допустиме рішення вихідної завдання по формулі (2.14):

X(1)= X(0)+ l1(Z(0)-X(0)),

де 0 ?l1? 1. Підставивши замість X(0) и Z(0) їх значення, отримаємо

 
 

Визначимо тепер число l1.

Підставивши в рівність (2.15) замість x1 и x2 їх значення відповідно до співвідношеннями (2.16)

 
 

знайдемо похідну цієї функції по l1 і прирівняємо її до нуля:

 
 

Вирішуючи це рівняння, отримаємо l1= 1/4 = 0.25.

Оскільки знайдене значення l1 укладено між 0 і 1, приймаємо його за величину кроку. Таким чином, X(1)= (0; 1), f (X(1)) =2, f (X(1)) -f (X(0)) =2>e= 0,01.

Повторюючи описані вище дії, через дві ітерації приходимо до того, що l3 »0,007, X(3)= (0,99528; 0,96321), f (X(3))= 2,99957, f (X(3)) -f (X(2))= 2,99957-2,9966 = 0,00297 < e = 0,01.

Таким чином, X(3)=(0,99528; 0,96321) є шуканим рішенням вихідної задачі.

Метод штрафних функцій.Розглянемо задачу визначення максимального значення увігнутою функції f (x1, x2, ..., Xn)

при умовах

gi(x1, x2, ..., Xn) ? bi (I = 1, ..., m), xj?0 (j= 1, ..., n), Де gi(x1, x2, ..., Xn) - опуклі функції.

Замість того, щоб безпосередньо вирішувати цю задачу, знаходять максимальне значення функції F (x1, x2, ..., Xn) = Fi(x1, x2, ..., Xn) + H (x1, x2, ..., Xn), що є сумою цільової функції завдання, і деякої функції H (x1, x2, ..., Xn),яка визначається системою обмежень і званої штрафний функцією.

Штрафну функцію можна побудувати різними способами.

Найбільш часто вона має вигляд

 де

а ai 0 - деякі постійні числа, що представляють

собою вагові коефіцієнти.

Використовуючи штрафну функцію, послідовно переходять від однієї точки в іншу до тих пір, поки не отримають прийнятне рішення. При цьому координати наступної точки знаходять за формулою

(2.21)

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

При цьому чим менше ai, Тим швидше знаходиться прийнятне рішення, проте точність визначення його знижується. Тому ітераційний процес зазвичай починають при порівняно малих значеннях ai і, продовжуючи його, ці значення поступово збільшують.

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

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

2. Вибирають крок обчислень.

6. Знаходять по всім змінним приватні похідні від цільової функції і функцій, що визначають ОДР завдання.

4. За формулою (2.21) знаходять координати точки, яка визначає можливе нове рішення задачі.

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

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

У разі такої необхідності переходять до етапу 2, В іншому випадку знайдено прийнятне рішення вихідної завдання.

6. Встановлюють значення вагових коефіцієнтів і переходять до етапу 4.

П р и м і р 2.  Знайти максимальне значення функції

 (2.22)

при умовах

 (2.23)

 (2.24)

Рішення. Цільова функція даного завдання є негативно-певну квадратич-ву форму і, отже, увігнута.

У той же час ОДР завдання, що визначається обмеженнями (2.23) - (2.24), - опукла.

Отже, завдання (2.22) - (2.24) є завданням опуклого програмування.

Для знаходження її рішення можна застосувати метод штрафних функцій.

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

Цими лініями служать окружності з центром в точці (0; 0).

Точка дотику однієї з цих кіл ОДР і є шуканої точкою максимального значення цільової функції.

покладемо X0 = (6, 7).

Візьмемо l = 0, 1,

позначимо через

g (x1, x2)= 18- (x1-7)2- (x2-7)2

і визначимо приватні похідні від функцій f (x1, x2) и g (x1, x2) по змінним x1 и x2:

 
 

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

1 ітерація. Так як точка X0 = (6,7) належить ОДР завдання, то другий доданок в квадратних дужках формули (2.21) дорівнює нулю. Значить, координати наступної точки X1 обчислюємо за формулами

Перевіримо тепер, чи належить ця точка ОДР завдання. Для цього знайдемо g (X1) = 18-4,84-1,96 = 11,2. Так як g (X1) 0, то X1 належить ОДР. У цій точці f (X1) = - 54,4.

2 ітерація. знаходимо

f (X2) = -34,816.

Перевіряючи таким чином інші точки, на 12 ітерації маємо:

Порівнюючи значення цільової функції, знайдені в точках, отриманих після 10 и 12 ітерацій, Видно, що вони з точністю до 10-1 збігаються. Це говорить про близькість точки, знайденої на останній ітерації, до точки максимального значення цільової функції. Такий же висновок можна зробити, якщо досліджувати вектори-градієнти функцій f (X) и g (X) в точці X(12).

У цій точці

Обчислимо відношення однойменних координат векторів:

-8,01 / 5,99 »-1,337;

-8,016 / 5,984 »-1,339.

Як видно, вони майже рівні між собою.

Це означає, що вектори и  практично колінеарні.

Так як до того ж точка X(12) знаходиться поблизу кордону ОДР (оскільки  , то и  можна вважати прийнятним рішенням задачі.

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

Послідовність точок, одержуваних під час знаходження рішення задачі, наочно ілюструється рис. (3.2).




ГЕОМЕТРИЧНИЙ МЕТОД | Складання першого опорного плаву. | Визначення провідних шпальти і рядки. | МЕТОД ШТУЧНОГО БАЗИСУ | метод потенціалів | Приклади завдань нелінійного програмування (економічні). | Постановка завдання опуклого програмування. | ПОХІДНА ПО НАПРЯМКУ І ГРАДІЄНТ | Класичний метод диференціальних числень. | Метод невизначених множників |

© 2016-2022  um.co.ua - учбові матеріали та реферати