На головну

Метод сплайнів 1-го порядку (знаходження точки глобального мінімуму)

  1. Стандартний алгоритм симплекс-методу
  2. DFD - методологія в проектуванні ІС
  3. I.3.3. Методи виносу в натуру проектних точок.
  4. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  5. III. Опис експериментальної установки та методу вимірювання
  6. III. Опис експериментальної установки та методу вимірювання
  7. III. Опис експериментальної установки та методу вимірювання

Будемо розглядати задачу

, (1)

де  - Деякі числа (  ).

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

Якщо в якості шматків вибирається лінійна функція, то сплайн вдає із себе деяку ламану і називається сплайном 1-го порядку.

Якщо в якості шматків вибирається квадратичні функції (шматки парабол), то говорять про сплайне 2-го порядку.

Метод полягає в наступному: нехай дана задача (1), задана  - Початкове наближення.

Припускаємо, що виконується умова

(2)

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

1-ша ітерація: по  будується найпростіший сплайн

На малюнку сплайн ламана 1-2-3. найпростіший сплайн  вдає із себе ламану 1-2-3, причому кутовий коефіцієнт [1,2] =  , А [2,3] =  . Так як виконується нерівність (2), то  аппроксимирует знизу функцію  , (Лежить не вище неї), потім вирішуємо завдання  і нехай  - Оптимальний план цієї задачі. Потім проводиться аналіз.

a
 нехай  - Рекордний план, тоді якщо  , де  0 - мале (необхідна точність обчислень), тоді рекордний план приймається за  оптимальне.

В іншому випадку переходимо до 2-ий ітерації: будуємо сплайн. спочатку по  - найпростіший

потім  і вирішується завдання  , Її рішення приймається за .

Потім відбувається аналіз: якщо  , То рекордний план  приймається за наближене рішення, в іншому випадку 3-тя ітерація і так далі.

опишемо  -у ітерацію: нехай побудована точка  і сплайн  тоді будуємо найпростіший сплайн по

;

потім  . Потім розглядається задача  і рішення приймається за .

Аналіз: якщо виконується нерівність  , то  служить наближеним значенням завдання, в іншому випадку приходимо до  -ітераціі.

Зауваження. Зазвичай при реалізації схеми перебору  включаються в неї і перебирались плани і вони вибираються з околиці цієї точки.

послідовність  сходиться до оптимального плану:  - Оптимальний план задачі (1).

З ростом ітерацій сплайн все точніше описує цільову функцію  в околиці точки мінімуму.

Чим точніше підібрано  в (2), тим швидше сходиться метод.

Зауваження. Екщо в методі замість лінійних сплайнів використовувати квадратичні (за певними 3-м точкам будуються шматки парабол з гілками спрямованими вгору і вниз в залежності від кривизни), то приходимо до методу сплайнів 2-го порядку, які точніше апроксимують функцію  в околиці оптимального плану. Цей метод швидше сходиться.




Завдання цілочисельного лінійного програмування | Методи мінімізації унімодальних функцій. Метод рівномірного пошуку

МЕТОДИ ПОШУКУ | Завдання обслуговування заявок на одному приладі | Метод гілок і меж. Загальна схема Завдання про рюкзаку | Загальна схема | Завдання про рюкзаку | Метод гілок і меж. Загальна схема Завдання цілочисельного лінійного програмування | Метод рівномірного пошуку | Методи двухточечного пошуку | метод Фібоначчі | Метод золотого перерізу |

© um.co.ua - учбові матеріали та реферати