У загальному випадку під градієнтними методами розуміють методи, в яких напрямок руху до точки оптимуму функції збігається з напрямком градієнта цієї функції. Градієнтні методи відносяться до наближених методів вирішення завдань нелінійного програмування. У загальному випадку вони забезпечують отримання оптимального рішення за допомогою нескінченного процесу послідовних наближень. Однак, в деяких випадках процес може закінчитися і через кінцеве число ітерацій.
Градієнтні методи можуть застосовуватися до будь-якого завдання нелінійного програмування, приводячи лише до локального, а не глобального екстремуму. Тому вони виявляються більш ефективними при вирішенні задач опуклого програмування, де всякий локальний екстремум є одночасно і глобальний.
Загальна постановка задачі відповідає (5.1) і (5.2). Однак, не втрачаючи спільності, вона може бути перетворена до виду
Математична стратегія градиентного методу полягає в наступному. Вибирається довільна допустима точка. Для переходу в результаті ітерацій від точки до точки в визначають такий напрям. щоб при досить малому промінь належав допустимої області. Тобто наступна точка ітераційного процесу визначається за формулою:
Різниця градієнтних методів полягає в способі визначення напрямку і параметра.
1. Якщо - внутрішня точка області допустимих рішень, то
є градієнт функції в точці. Стратегія, що виражається співвідношенням (5.57) визначає рух зі змінним кроком, так як значення кроку залежить від значення градієнта. Оскільки значення градієнта зменшується поблизу оптимуму, то на деяких ділянках кроки будуть дрібними, що подовжує час пошуку. Від цього недоліку можна позбутися, якщо використовувати градієнтну стратегію з постійним кроком. У цьому випадку вектор градієнта замінюється на вектор напрямку градієнта:
2. не належить допустимої області. Це може мати місце в разі, якщо точка, рухаючись в сторону найбільшого зростання функції порушила i -е обмеження (5.54). В якості штрафу за порушення i -ого обмеження введемо множник Ri і вспомогателную цільову функцію.
Якщо під цільової функцією розуміти дохід підприємства, тобто ні що інше, як дохід підприємства за вирахуванням штрафних санкцій.
У найпростішому випадку Ri вибирається в такий спосіб:
Число R має бути досить великим, щоб змусити рухатися точку всередину допустимої області. Напрямок руху точки в цьому випадку задається вектором
Недолік цієї стратегії в тому, що точність обчислень безпосередньо залежить від вибору числа R. При невдалому виборі числа R ітераційний процес буде характеризуватися різкими коливаннями точки біля кордону.
Даного недоліку можна уникнути, якщо прийняти що штраф повинен бути тим менше, чим менша порушення може мати місце, то є доцільно припустити, що
1) Параметр число постійне на всіх ітераціях. Чим менше число. тим точніше обчислення. Відповідно збільшується і час пошуку оптимуму;
2) Параметр вибирають на кожному кроці з умови min # 955; ', # 955; ">, де # 955; '- значення параметра, при якому промінь + # 955; (K) S (k) перетинає ОДЗ; # 955; "- таке допустиме значення # 955 ;. при якому функція f (+ # 955; (k) S (k)) досягає максимуму на промені. Дана стратегія дозволяє перебувати в точці ОДЗ і оптимізувати кількість ітерацій. Однак, при нелінійних обмеженнях і нелінійної цільової функції обчислення # 955; ', # 955; "може виявитися досить трудомістким.
Для ілюстрації градиентного методу виберемо таку стратегію: # 955; - число постійне; величина штрафу пропорційна величині порушення обмеження; напрямок руху точки збігається з напрямком градієнта. Це так званий градієнтний метод Ерроу-Гурвіца. Якщо обмеження по знаку (5.55) відсутні, то координати нової точки можна розрахувати відповідно до (5.56), (5.60) за формулою:
З урахуванням умови невід'ємності (5.55), вираз (5.62) буде виглядати:
У виразах (5.62) і (5.63) функція штрафу обчислюється за формулою (5.61).
Приклад 5.3 Потрібно максимізувати функцію
нехай # 955; = 0.1; R1 (0) = 2; x1 (0) = 3; x2 (0) = 1.5, тобто ми вибрали початкову точку, свідомо не належить допустимої області.
Рівняння (5.62) мають такий вигляд:
Рівняння (5.61) мають такий вигляд:
Друга ітерація: Точка знаходиться вже всередині допустимої області, однак, множник. хоча і менше. але ще відмінний від 0 і кордон продовжує «підштовхувати» рухому точку всередину допустимої області (ця точка ще знаходиться на «небезпечній відстані» від кордону):
Подібним чином цей процес можна продовжити і далі. При збільшенні числа ітерацій точка при виконанні умови опуклості цільової функції прагне до вирішення поставленого завдання.
Список рекомендованої літератури
1. А. В. Кузнєцов, І. І. Холод. Математичне програмування. - Мінськ: «Вища школа». 984. - 221 с.
4. Зайченко Ю.П. Дослідження операцій: Учеб. посібник для студентів вузів. - 2-е вид. перераб. і доп. - Київ: Вища школа. Головне вид-во, 1979. 392 с.
5. І. А. Акуліч. Математичне програмування в прикладах і завданнях. - М. «Вища школа», 1986.- 319 с.
9. С. Гасс. Лінійне програмування. - М. «Наука», 1961.-303 с.
10. Сакович В.А. Дослідження операцій (детерміновані методи і моделі): Довідковий посібник. - Мн. Виш. шк. 1984.-256с.
11. Таха Х. Введення в дослідження операцій: в двох книгах. Кн.1,2 Пер. з англ. - М. Мир, 1985.