Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
15. Метод найшвидшого спуску (градієнтний метод) — ітераційний метод пошуку локального мінімуму функції багатьох змінних f(x). Метод полягає в кроковому переміщенні в напрямі оберненому до градієнту функції в актуальній точці на відстань пропорційну величині цього градієнта.
Геометричне представлення методу в . Синім кольором показані лінії рівня функції.
Метод полягає в побудові послідовності {xk} за формулою:
. (1)
де ∇ f(xk) — градієнт функції f(x) в точці xk, а t(xk) вибирається виходячи із умови:
. (2)
Вперше метод був запропонований французьким математиком Оґюстеном Коші. Широке застосування цього методу обумовлено тим, що в напряму антиградієнту — ∇ f(x) похідна функції за напрямом досягає найменшого значення.
Якщо градієнт ∇ f(x) неперервний по x а f(x) → ∞ при x → ∞, то при довільному початковому наближенні ∇ f(xk) → 0 приk→ ∞. Якщо при цьому x* — єдина стаціонарна точка, то xk → x*, де f(x*) = minxf(x).
Якщо f(x) неопукла і стаціонарних точок декілька, то послідовність {xk} може, взагалі кажучи, не сходитись навіть долокального екстремуму функції f(x).
Нехай існує матриця Гессе
,
додатньо визначена в кожній точці x. Тоді для послідовності (1) xk → x*, та, починаючи з деякого номеру N, виконується нерівність
при k ≥ N,
де
,
xki — i-та координата xk, M(x*) та m(x*) — відповідно найбільше та найменше власні значення матриці H(x*).
Існує модифікація методу, коли t(xk) = τ > 0 — const, тобто
. (3)
Якщо градієнт ∇ f(x) задовольняє умові Ліпшиця, то для послідовності (3) при виконанні перелічених припущень вірні відповідні властивості послідовності (1).
16. канонічна форма задачі лінійного програмування
Задачі лінійного програмування охоплюють велику кількість різ-номанітних варіантів управлінських завдань, що відрізняються між со-бою як вимогами до цільових функцій (знайти максимум чи мінімум),так і структурою системи обмежень (самі лише нерівності, рівності чипоєднання рівностей і нерівностей).
Один з варіантів задачі лінійного програмування взято за стандарт— канонічну форму задачі лінійного програмування, тобто коли в сис-темі обмежень усі bt (і = 1, m) невід'ємні; всі обмеження є рівностями,a n1 = n. Будь-яку задачу лінійного програмування можна звести доканонічного вигляду. Якщо якесь bt від'ємне, то, помноживши і-теобмеження на (— 1), дістанемо у правій частині відповідної рівностідодатне значення. Коли i-те обмеження має вигляд нерівностіai1 x1 + ai2 +... + ainxn < bt, то її завжди можна звести до рівності, ввів-ши додаткову змінну xn+1 > 0 : ai1 x1 + ai2 +... + ainxn + xn+1 = bi.
У найпростішому випадку, коли задача лінійного програмуваннямістить лише дві змінні, неважко отримати її геометричну інтерпрета-цію і розв'язати задачу графічним методом. Такий метод розв'язанняочевидний і дозволяє проаналізувати чутливість прийнятих рішень дозміни вхідних даних.
Ідея методу множників Лагранжа полягає в заміні початкової задачі простішою. Для цього цільову функцію замінюють іншою, з більшою кількістю змінних, тобто такою, яка включає в себе умови, що подані як обмеження. Після такого перетворення дальше розв’язування задачі полягає в знаходженні екстремуму нової функції, на змінні якої не накладено ніяких обмежень. Тобто від початкової задачі пошуку умовного екстремуму переходимо до задачі відшукання безумовного екстремального значення іншої функції. Отже, завдяки такому перетворенню можливе застосування методів класичного знаходження екстремуму функції кількох змінних.
У попередньому параграфі наведена необхідна умова існування локального екстремуму неперервної та диференційовної функції двох змінних.
Узагальнення необхідної умови існування локального екстремуму функції n змінних має аналогічний вигляд. Отже, для розв’язування задачі необхідно знайти вирази частинних похідних нової цільової функції за кожною змінною і прирівняти їх до нуля. В результаті отримаємо систему рівнянь. Її розв’язок визначає так звані стаціонарні точки, серед яких є і шукані екстремальні значення функції.
Розглянемо метод множників Лагранжа для розв’язування задачі нелінійного програмування, що має вигляд:
(8.6)
за умов:
, (8.7)
де функції і мають бути диференційовними.
Задача (8.6), (8.7) полягає в знаходженні екстремуму функції за умов виконання обмежень .
Переходимо до задачі пошуку безумовного екстремуму. В літературі [13, 28] теоретично доведено, що постановки та розв’язання таких задач еквівалентні.
Замінюємо цільову функцію (8.6) на складнішу. Ця функція називається функцією Лагранжа і має такий вигляд:
(8.8)
де — деякі невідомі величини, що називаються множниками Лагранжа.
Знайдемо частинні похідні і прирівняємо їх до нуля:
(8.9)
Друга група рівнянь системи (8.9) забезпечує виконання умов (8.7) початкової задачі нелінійного програмування.
Система (8.9), як правило, нелінійна.
Розв’язками її є і — стаціонарні точки. Оскільки, ці розв’язки отримані з необхідної умови екстремуму, то вони визначають максимум, мінімум задачі (8.6), (8.7) або можуть бути точками перегину (сідловими точками).
Для діагностування стаціонарних точок і визначення типу екстремуму необхідно перевірити виконання достатніх умов екстремуму, тобто дослідити в околі стаціонарних точок диференціали другого порядку (якщо для функцій існують другі частинні похідні і вони неперервні).
Узагальнення достатньої умови існування локального екстремуму для функції n змінних приводить до такого правила: за функцією Лагранжа виду (8.8) будується матриця Гессе, що має блочну структуру розмірністю :
де О — матриця розмірністю , що складається з нульових елементів,
Р — матриця розмірністю , елементи якої визначаються так:
,
— транспонована матриця до Р розмірністю ,
Q — матриця розмірністю виду:
, де .
Розглянемо ознаки виду екстремуму розв’язку системи (8.9). Нехай стаціонарна точка має координати і .
1. Точка є точкою максимуму, якщо, починаючи з головного мінору порядку (m + 1), наступні (n – m) головних мінорів матриці Н утворюють знакозмінний числовий ряд, знак першого члена якого визначається множником .
2. Точка є точкою мінімуму, якщо, починаючи з головного мінору порядку (m + 1), знак наступних (n – m) головних мінорів матриці Н визначається множником .