Розглянемо ще один метод призначений для знаходження розв’язку задачі нелінійного програмування, а саме метод Франка-Вульфа, який відноситься до категорії градієнтних методів і процедура якого передбачає визначення оптимального плану шляхом перебору розв’язків, які є допустимими планами задачі. Розглянемо даний процес більш детально і припустимо, що нам необхідно відшукати максимальне значення функції мети:
при наступних обмеженнях:
Тобто, як Ви вже встигли помітити, характерною особливістю розв’язуваних з допомогою даного методу задач є те, що їх система обмежень повинна містити тільки лінійні нерівності. Ця особливість є основою для заміни в зоні досліджуваної точки нелінійної цільової функції лінійною, завдяки чому рішення вихідної задачі зводиться до послідовного рішення задач лінійного програмування.
Отже, процес відшукання розв’язку задачі починається з визначення точки, що належить області допустимих рішень. Нехай це буде точка . Тоді в даній точці обчислимо градієнт функції (1):
та побудуємо лінійну функцію:
На наступному кроці, переходимо до новї задачі, яка полягає у максимізації функції (4) при обмеженнях (2) і (3). Нехай розв’язок даної задачі визначається точкою . Тоді за нове допустиме рішення вихідної задачі (1)-(3) беремо координати точки :
де – деяке число, яке називається кроком обчислень і значення якого повинно міститися між нулем і одиницею, тобто . Відмітимо, що даний крок зазвичай береться довільно або визначається таким чином, щоб значення функції в точці (), залежне від , було максимальним. Для цього необхідно знайти розв’язок рівняння і вибрати його максимальний корінь. Якщо отримане таким чином значення виявиться більшим за одиницю, то слід покласти .
Після визначення знаходимо координати точки , обчислюємо значення цільової функції в ній та скориставшись нерівністю (де – достатньо мале число), з’ясовуємо необхідність переходу до нової точки . Якщо така необхідність є (нерівність не виконується), то обчислюємо в точці градієнт цільової функції. Потім переходимо до відповідної задачі лінійного програмування, знаходимо її рішення, визначаємо координати точки і досліджуємо необхідність проведення подальших обчислень. Відмітимо, що після виконання кінцевого числа таких кроків отримаємо, з необхідною точністю, розв’язок вихідної задачі нелінійного програмування (1)-(3).
Розв’язку задачі нелінійного програмування методом Франка-Вульфа – приклад:
Використовуючи метод Франка-Вульфа знайти розв’язок задачі нелінійного програмування, який полягає у визначенні максимального значення функції:
при наступних обмеженнях:
Для цього, на першому кроці, обчислемо градієнт функції:
Далі, вибравши в якості початкового допустимого розв’язку задачі точку , та обчисливши в даній точці градієнт , переходимо до нової задачі, яка полягає у максимізації функції мети при вищевказаних обмеженнях (8). Відмітимо, що виходячи з того, що число невідомих останньої задачі не перевищує два, то для відшукання її оптимального розв’язку будемо використовувати графічний метод. В результаті отримаємо, що функція мети досягає свого максимального значення в точці , тобто .
Знаходження максимального значення функції F1
На наступному кроці, скориставшись формулою (5), де в якості параметра візьмемо значення , знайдемо нове допустиме рішення вихідної задачі .
Далі, перевіривши виконання умови закінчення ітераційного процесу (6) () бачимо, що отриманий на першій ітерації план не являється оптимальним, тому переходимо до ітерації номер два, де знову-таки обчисливши графієнт функції, але на цей раз в точці (), переходимо до нової задачі лінійного програмування, яка полягає у максимізації функції , при обмеженнях (8), і яку також розв’язжемо графічно – .
Знаходження максимального значення функції F2
Далі, знайшовши нове допустиме рішення задачі (7), (8) () та перевіривши умову закінчення ітераційного процесу () бачимо, що отримане на другій ітерації рішення також не є оптимальним, тому продовжуючи ітераційний процес методу Франка-Вульфа далі, на одинадцятій ітерації отримуємо план, для якого умова зупинки виконується і який приймаємо в якості шуканого розв’язку задачі (7), (8), тобто .