Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод дихотомії




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

Рисунок 13.9 – Позначення, які використовуються в методі дихотомії

Якщо значення цільової функції при х1 більше, ніж при х2, то новий інтервал невизначеності дорівнює Z1 = z1 + z2. В протилежному випадку він визначається виразом Z2 = z2 + z3. Задача полягає в тому, щоб одночасно мінімізувати Z1 i Z2, задовольнивши умовам

z1+z2+z3 = Z,

z1 > 0,

z2 > 0,

z3 > 0.

Із рівності можна виключити z2. Тоді

Z – z3 = min, Z – z1 = min.

Так як величина Z задана, то праві частини цих рівнянь будуть тим менше, чим більше z1 i z3. Отже, оптимум відповідає умові

z1 = z3 = 0,5Z.

Але тоді z2 = 0, що суперечить умові z2 > 0.

Рисунок 13.10 – Метод дихотомії

Нехай z2 має деяке дуже маленьке значення . Тоді із z1 i z3 віднімемо по . В результаті після обчислення першої пари значень цільової функції при близьких значеннях х інтервал невизначеності звузиться, як показано на рис. 13.10, і коефіцієнт ділення буде дорівнювати

.

В межах, при , . Надалі при використанні метода дихотомії виконуються ті операції, що і при використанні методу ділення відрізка навпіл.

13.4 Метод “золотого перетину”

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

Рисунок 13.11 – Позначення, які використовуються в методі золотого перетину

Суть цього методу полягає в наступному. Інтервал невизначеності ділиться на дві нерівні частини, відношення довжини більшого відрізку до довжини всього інтервалу дорівнює відношенню довжини меншого відрізку до довжини більшого відрізку. На рис. 13.11 показаний інтервал невизначеності Z, який складається з відрізків z1 i z2, відношення довжин яких визначається правилом золотого перетину.

Крім того, z1 + z2 = Z. Із першого рівняння витікає . Підставивши значення Z з другого рівняння і поділивши обидві частини на , отримаємо

Розв’язуючи це квадратне рівняння, знаходимо для додатнього кореня значення

На рис. 13.12 показано ділення інтервалу невизначеності в цьому відношенні і нанесені відповідні значення цільової функції, які дозволяють зменшити інтервал невизначеності в 1/ 0,618 раз.

Рисунок 13.12 – Метод золотого перетину

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

При n > 2 ефективність методу золотого перетину вища, ніж у метода дихотомії, так як при кожному наступному обчисленні цільової функції інтервал невизначеності скорочується в 1/ 0,618 раз. Після обчислення N значень цільової функції коефіцієнт дроблення інтервалу невизначеності складає

f = 0,618 N-1.

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

ZJ-2 = ZJ-1 + ZJ, 1 <="" n,<="" i="">

де ZJ довжина інтервалу невизначеності після обчислення J-го значення цільової функції.

На рис. 13.13 представлений алгоритм вибору наступної точки пошуку. Задана точність може, звичайно, змінюватися вибором значення. Для функції , пошук відбувався в інтервалі (0, 2).

Рисунок 13.13 - Послідовність етапів вибору наступної точки пошуку

Істинний мінімум знаходиться в точці 1,76322211, де значення функції дорівнює -0, 0972601313.

Рисунок 13.14 - Схема алгоритму метода „золотого перетину”

При розробці програм для рішення задач однопораметричної оптмізації використовують наступні співвідношення:




Поделиться с друзьями:


Дата добавления: 2014-11-08; Просмотров: 644; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.