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