Знаходження розв'язку задачі нелінійного програмування методом Франка-Вульфа

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

при наступних обмеженнях:

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

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

та побудуємо лінійну функцію:

На наступному кроці, переходимо до новї задачі, яка полягає у максимізації функції (4) при обмеженнях (2) і (3). Нехай розв'язок даної задачі визначається точкою . Тоді за нове допустиме рішення вихідної задачі (1) — (3) беремо координати точки :

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

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

Розв'язку задачі нелінійного програмування методом Франка-Вульфа — приклад:

Методом Франка-Вульфа знайти розв'язок задачі нелінійного програмування, який полягає у визначенні максимального значення функції:

при наступних обмеженнях:

Для цього, на першому кроці, обчислемо градієнт функції:

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

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

Далі, провіривши виконання умови закінчення ітераційного процесу (6) () бачимо, що отриманий на першій ітерації план не являється оптимальним, тому переходимо до ітерації номер два, де знову-таки обчисливши графієнт функції, але на цей раз в точці (), переходимо до нової задачі лінійного програмування, яка полягає у максимізації функції , при обмеженнях (8), і яку знову-таки розв'язжемо графічно — .

Далі, знайшовши нове допустиме рішення задачі (7), (8) () та провіривши умову закінчення ітераційного процесу () бачимо, що отримане на другій ітерації рішення також не є оптимальним, тому продовжуючи ітераційний процес методу Франка-Вульфа далі, на одинадцятій ітерації отримуємо план, для якого умова зупинки виконується і який приймаємо в якості шуканого розв'язку заданої задачі (7), (8), тобто .