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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Знаходження максимального значення функції F1

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

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

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

Знаходження максимального значення функції F2

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

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

Розв’язок задачі нелінійного програмування методом Франка-Вульфа – ітерація №3-11 (знаходження максимального значення функцій F3-F11)
Блок-схема алгоритму знаходження розв’язку задачі нелінійного програмування використовуючи метод Франка-Вульфа

Метод Франка-Вульфа блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*