Реферати, курсові, дисертації, дипломи

[ Програмна модель пошуку глобального мінімуму нелінійних яружних функцій двох змінних ]

<div style="font-size:16px;text-align:justify;">
	 Зміст Введення 1. Пояснювальна записка 1.1 Нелінійне програмування 1.2 <a href="Чисельні_методи" title="Чисельні методи">Чисельні методи</a> в задачах без обмежень 1.2.1 Загальна схема методів спуску 1.2.2 Градієнтні методи 1.2.3 Метод найшвидшого спуску 2. Інструментальні програмні засоби 3. Блок-схема алгоритму моделювання 4. Операційне середовище 5. Контрольна завдання Висновок Література Додаток Введення Проблема вибору оптимального варіанта рішення відноситься до числа найбільш актуальних техніко-економічних проблем. У <a href="Математика" title="Математика">математичній</a> постановці вона представляє собою завдання мінімізації (максимізації) деякого функціоналу, що описує ті чи інші характеристики системи. Чисельне рішення оптимізаційних задач на ЕОМ зводиться до пошуку екстремуму <a href="Функції" title="Функції">функції</a> багатьох змінних. Такі завдання оптимального <a href="Управління" title="Управління">управління</a> та ідентифікації, завдання супервизорного управління, оптимізаційного проектування і планування. Серед різних типів оптимізаційних задач особливе місце займають завдання оптимизирования неопуклих детерменірованних функцій з єдиною точкою екстремуму. Ці завдання представляють інтерес з різних точок зору. Перш за все не опуклість породжує великі аналітичні складності при розробці методів рішення унімодальних завдань. Як відомо, аналітичні методи розвинені для значно простих завдань. Для лінійних, квадратичних, опуклих задач розроблені різні <a href="Чисельні_методи" title="Чисельні методи">чисельні методи</a> рішення, доведена збіжність методів, отримані оцінки швидкості збіжності. Нічого подібного не зроблено для унімодальних завдань загального вигляду, виключаючи завдання мінімізації <a href="Функції" title="Функції">функції</a> однієї змінної. На практиці клас унімодальних завдань не є чимось незвичайним. Є численні приклади, коли в нас цікавить області визначення функції існує лише один екстремум. Якщо при цьому оптимізується <a href="функція" title="функція">функція</a> має складний вид чи задана неявно, то її опуклість нічим не гарантується. У цій ситуації <a href="Природа" title="Природа">природно</a> застосуємо метод оптимізації, орієнтований на гірший <a href="Випадок" title="Випадок">випадок</a>, тобто на не опуклість функції. При цьому, кількість робіт, присвячених унімодальному завданням, порівняно не велике. Аналітичні <a href="Методи_дослідження" title="Методи дослідження">методи дослідження</a> неопуклих завдань не розроблені через <a href="Принципат" title="Принципат">принципову</a> складності, чисельні методи, як правило, орієнтовані на більш прості класи завдань. 1. Пояснювальна записка 1.1 Нелінійне програмування Унімодальне функції. Виділимо клас функцій, що володіють, з обчислювальної точки зору, важливою властивістю. А <a href="Саме" title="Саме">саме</a>:<a href="Функції" title="Функції"> функція</a> f називається унімодальної на відрізку [a, b], якщо вона має на цьому відрізку єдину точку глобального мінімуму Xmin і ліворуч від цієї точки є строго спадною, а праворуч строго зростаючою (див. рис. 1). Іншими словами, <a href="функція" title="функція">функція</a> f унімодальному, якщо точка Xmin існує і єдина, причому для будь-яких двох точок х1, х2 Î [a, b] таких, що х1 <x 2 з <a href="Нерівності" title="Нерівності">нерівності</a> х1> Xmin завжди слід f (x 1) <f ( x 2), а з нерівності x 2 <Xmin необхідно випливає нерівність f (x 1)> f (x 2). <IMG SRC=dopc74142.zip ALIGN=LEFT><IMG SRC=dopc74143.zip ALIGN=LEFT><IMG SRC=dopc74144.zip ALIGN=LEFT><IMG SRC=dopc74145.zip ALIGN=LEFT><IMG SRC=dopc74146.zip ALIGN=LEFT> <IMG SRC=dopc74143.zip ALIGN=LEFT> <IMG SRC=dopc74148.zip ALIGN=LEFT><IMG SRC=dopc74149.zip ALIGN=LEFT><IMG SRC=dopc74148.zip ALIGN=LEFT><IMG SRC=dopc74148.zip ALIGN=LEFT><IMG SRC=dopc74152.zip ALIGN=LEFT><IMG SRC=dopc74143.zip ALIGN=LEFT><IMG SRC=dopc74143.zip ALIGN=LEFT><IMG SRC=dopc74155.zip ALIGN=LEFT><IMG SRC=dopc74155.zip ALIGN=LEFT> <IMG SRC=dopc74157.zip ALIGN=LEFT><IMG SRC=dopc74158.zip ALIGN=LEFT><IMG SRC=dopc74159.zip ALIGN=LEFT><IMG SRC=dopc74160.zip ALIGN=LEFT><IMG SRC=dopc74161.zip ALIGN=LEFT><IMG SRC=dopc74162.zip ALIGN=LEFT><IMG SRC=dopc74163.zip ALIGN=LEFT><IMG SRC=dopc74164.zip ALIGN=LEFT> <IMG SRC=dopc74165.zip ALIGN=LEFT> Самого факту унімодальному недостатньо для отримання аналітичних результатів або побудови ефективних числових методів. У теж час «поширене трактування опуклих задач як хорошого модального об'єкта для задач одноекстрімальних теоретично не спроможна - складність класів опуклих завдань незрівнянно нижче, ніж унімодальних.» [1] Інформаційна складність (нижня межа оцінки трудомісткості) задач мінімізації безперервних функцій загального вигляду украй велика, причому саме унімодальному (а не багатоекстремального) є причиною такої складності. У роботі [2] зазначено, що <a href="Інформація" title="Інформація">інформаційна</a> складність класу унімодальних завдань «фантастично велика». З точки зору авторів <a href="Книги" title="Книги">книги</a> [1], пошук універсальних методів вирішення унімодальних завдань безперспективний. Тому залишається один шлях - розробка спеціалізованих методів для більш вузьких класів задач. Завдання безумовної мінімізації унімодальної функції багатьох змінних записується звичайно таким чином: f (x) ® min, x Î R (1.1) Далі будемо вважати, що f (x)-достатню кількість раз дифференцируемая функція, яка в деякому діапазоні, розумному з точки зору змісту завдання, має один екстремум. Точка X, в якій досягається мінімум, називається рішенням завдання. Відомо, що Ñ f (x) = 0, де Ñ f (x) - градієнт f (x) в точці Х, а гессіан, якщо він існує в точці Х, є позитивно певної матрицею. Найбільш вивчений клас квадратичних функцій багатьох змінних: F (x) = (Ax, x) / 2 + (b, x) + e, (1.2) тут А - симетрична, позитивно певна матриця; b - вектор. Завдання мінімізації такої функції у принципі може бути вирішена аналітично, диференціювання F (x) і прирівнювання нулю похідних дають систему лінійних рівнянь. У силу невирожденості <a href="Матриці" title="Матриці">матриці</a> система має єдине рішення. Квадратичні одноекстрімальние <a href="Функції" title="Функції">функції </a>(1.2) належать до більш широкого класу суворо опуклих функцій. Функція f (x) називається строго опуклою, якщо для будь-яких точок х1 і х2 із області її визначення має місце нерівність: F (l x 1 + (1 - l) x 2) <l f (x 1) + (1 - l) f (x 2), lÎ (0,1). Строго опуклі функції унімодальному та володіють гідністю, полегшує дослідження і <a href="Процес" title="Процес">процес</a> чисельної мінімізації, - це чітка опуклість, а отже, одноекстрімальность уздовж будь-якого напрямку. Більш широким класом є клас лінійно унімодальних функцій [3]. Характерна властивість цього безлічі - унімодальному функцій вздовж будь-якої прямої в допустимій області. Функції, унімодальне по будь-якому напрямку, якщо цей напрям відбувається через точку мінімум, утворюючи клас строго унімодальних функцій [3]. На малюнку 2 представлені: А - строго опукла; Б - лінійно-унімодальному; В - суворо унімодальному функції. Специфіка кожного з описаних класів може бути використана при побудові методів мінімізації. У випадку, коли властивості опуклості, лінійної або строгої унімодальному невірні або не можуть бути перевірені, при виборі методу рішення доцільно скористатися завідомо неопуклих моделлю мінімізіруемой функції. На початку 60-х років І.М. Гельфонд і М.Л. Цетлін [4] був дескриптивної заданий клас неопуклих функцій багатьох змінних. Елементи класу характеризуються наступною структурою: у будь-якій точці деякого підмножини області визначення функції існує <a href="Такий" title="Такий">такий</a> базис, що всі незалежні <a href="Змінні" title="Змінні">змінні</a> можна розділити на дві групи. Перша група складається з тих аргументів, зміна яких призводить до значної зміни цільової функції (в [4] вони названі несуттєвими змінними). Зміна змінних другої групи (суттєвих змінних) призводить до незначної зміни функції. При цьому для будь-якої точки підмножини друга група містить лише невелике число параметрів. Функція, що допускає таке розбиття змінних в деякій області, називається добре організованою (яружної) <a href="Функції" title="Функції">функцією</a> в цій області, а число істотних змінних визначає розмірність яру [4]. Іншими словами, для яружної функції точність лінійного наближення f (x) + Ñ f (x) * Ñ x в значній мірі залежить від Ñ x [5]. У математичному енциклопедичному <a href="Словник" title="Словник">словнику</a> за <a href="Редакція" title="Редакція">редакцією</a> Ю.В. Прохорова дано суворе визначення яружної функції. Нехай «обмежена знизу функція багатьох змінних J * (x) = J (x1, x2, ..., xm) Î c ² (D), D Ì R, володіє тією особливістю, що в досліджуваній області <a href="Власні_значення" title="Власні значення">власні значення</a> матриці Гессе <IMG SRC=dopc74166.zip NAME=graphics1 ALIGN=BOTTOM WIDTH=115 HEIGHT=53 BORDER=0> , I, j = 1, 2, ..., m, впорядковані в будь-якій точці x Î D, задовольняють нерівності 0 <| min l i (x) | <<l 1 (x). У цьому випадку поверхня рівня J (x) = const мають структуру, що сильно відрізняється від сферичної. Такі функції J (x) називаються яружний. Ступінь яружно характеризується числом <IMG SRC=dopc74167.zip NAME=graphics2 ALIGN=BOTTOM WIDTH=52 HEIGHT=24 BORDER=0> S = l 1 (x) / | min l i (x) |, l i (x) ╪ 0. Якщо власні значення задовольняють нерівності | l m (x) | <= ... <= | l m - r +1 (x) | <<l m - r (x) <<l 1 (x), а відношення | l m - r +1 (x) | / | l m (x) | невелика, то число r називається розмірністю яру. » На відміну від локальних моделей, що описують функцію і її похідні в малій околиці заданої точки, овражная модель <a href="Характер" title="Характер">характеризує</a> глобальні властивості функції. «Звичайно, таке розбиття параметрів неможливо для будь-якої функції, яку міг би поставити математик. Однак, для функцій, що зустрічаються в практичній діяльності людини (тут маються на увазі розумні завдання фізики, техніки), таке розбиття, очевидно, має місце в дуже значному числі випадків. »[4] Р.П. Федоренко [5] зазначає, що "яр функції абсолютно закономірно виникають при кінцево-різницевої апроксимації функціоналів варіаційних задач оптимального управління, і ці завдання вимагають не загальних, а вузькоспеціальних методів рішення. Найпростішим прикладом яружної функції є квадратична функція (1.2), де А - погано обумовлена матриця. Число обумовленості симетричної матриці є важливою характеристикою її властивостей і визначається через власні значення: k (A) = max l A / min l 4. Якщо k (A) велике, то А є погано обумовлену матрицю, а завдання (1.2) називається погано обумовленої завданням мінімізації. У цьому випадку f (x) визначає багатовимірну поверхню прямим (неізогнутим) яром. Для неквадратічних функцій вводиться узагальнення цього визначення [6]: обумовленістю точки мінімум х називається число m = lim (sup | | x - x '| | ² (inf | | x - x' | | ²), x Î L, L = {x: f (x) = f (x ') + d}. Якщо m велике, функція має яружний <a href="Характер" title="Характер">характер</a>. Для наочності опишемо яружно функцію в графічних термінах. Дно яру можна представити як русло річки, що утворює якого визначає напрямок течії. Яр характеризується крутизною стінок, шириною дна, а також положистістю - ступенем зниження дна яру уздовж твірної. Особливо відзначимо, що дно яру може бути прямим або звивистим. Дно яру - це таке підмножина точок, де поділ на існуючі і неіснуючі змінні зникає, з будь-якого напрямку функції змінюється повільно. Відомо, що мінімізація яружних функцій пов'язана з великими обчислювальними труднощами. Тому Р.П. Федоренко [5] пропонує при розробці первинної постановки завдання уникати тих способів формалізації, які призводять до появи яружних функцій. Необхідність у яружної моделі з'являється тоді, коли дослідник не бачить можливості розглядати мінімізіруемую функцію як деяку спеціальну, менш загальну модель. Далеко не завжди практична завдання допускає <a href="Перетворення" title="Перетворення">перетворення</a>, що дозволяють перейти до сранітельно просто вирішуємо окремого випадку. У загальному випадку ми маємо яр функції, які заслуговують як уваги, так і спеціального дослідження. 1.2 Чисельні методи в задачах без обмежень 1.2.1 Загальна схема методів спуску Будемо розглядати задачу безумовної мінімізації, тобто завдання мінімізації цільової функції f на всьому просторі R. Сутність всіх методів наближеного рішення цього завдання полягає в побудові <a href="Послідовності" title="Послідовності">послідовності</a> точок х1, х2, х3, ..., х k, ..., монотонно зменшують значення цільової функції: f (x0)> = f (x1)> = f (x3)> = ...> = f (xk)> = ... (1.3) Такі методи (алгоритми) називають методами спуску. При використанні цих методів застосовують наступну схему. Нехай на k-й ітерації є точка х k. Тоді обирають напрямок спуску pk Î R і довжину кроку вздовж цього напрямку ak> 0. Наступну точку послідовності обчислюють за формулою: xk +1 = xk + ak * pk, k = 0, 1, 2, ... Відповідно до цієї формули, величина просування з точки xk в xk +1 залежить від як ak, так і від pk. Однак ak традиційно називають довжиною кроку. Формально розрізняють <a href="Методи_спуску" title="Методи спуску">методи спуску</a> відмінні один від одного способом вибору числа ak і вектора pk. Якщо для визначення ak і pk потрібно обчислювати лише значення цільової функції, <a href="Відповідь" title="Відповідь">відповідний</a> метод називають методом нульового порядку або методами пошуку. Методи першого порядку вимагають, крім <a href="Того" title="Того">того</a>, обчислення перших похідних цільової функції. Якщо ж метод передбачає використання і других похідних, то його називають методом другого порядку і т.д. За допомогою методу нульового порядку можна вирішувати завдання більш широкого класу, ніж за допомогою методів першого і другого порядків. Проте методи нульового порядку, як правило, вимагають великих обчислень для досягнення заданої точності, оскільки використання тільки значень цільової функції не дозволяє досить точно визначати напрям на точку мінімуму. Найважливішою характеристикою будь-яких методів спуску є їх збіжність. Збіжність тут розуміється в тому сенсі, що послідовність {xk} має сходитись до точки глобального (локального) мінімуму. Однак точки мінімуму можуть становити ціле безліч і багато алгоритмів дозволяють побудувати послідовність {xk}, яка сама не є збіжної, але будь-яка її сходиться послідовність має в якості граничної деяку точку мінімум (див. рис. 3). У цьому випадку говорять, що кожна гранична точка послідовності {xk} є точкою мінімуму. За допомогою подібних алгоритмів можна будувати послідовності точок, як завгодно близько наближаються до безлічі точок мінімуму. <IMG SRC=dopc74168.zip ALIGN=LEFT><IMG SRC=dopc74169.zip ALIGN=LEFT><IMG SRC=dopc74170.zip ALIGN=LEFT><IMG SRC=dopc74171.zip ALIGN=LEFT><IMG SRC=dopc74172.zip ALIGN=LEFT><IMG SRC=dopc74163.zip ALIGN=LEFT><IMG SRC=dopc74174.zip ALIGN=LEFT><IMG SRC=dopc74175.zip ALIGN=LEFT><IMG SRC=dopc74176.zip ALIGN=LEFT><IMG SRC=dopc74177.zip ALIGN=LEFT><IMG SRC=dopc74178.zip ALIGN=LEFT><IMG SRC=dopc74179.zip ALIGN=LEFT><IMG SRC=dopc74180.zip ALIGN=LEFT><IMG SRC=dopc74152.zip ALIGN=LEFT><IMG SRC=dopc74182.zip ALIGN=LEFT><IMG SRC=dopc74160.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74189.zip ALIGN=LEFT><IMG SRC=dopc74158.zip ALIGN=LEFT><IMG SRC=dopc74191.zip ALIGN=LEFT><IMG SRC=dopc74192.zip ALIGN=LEFT><IMG SRC=dopc74193.zip ALIGN=LEFT><IMG SRC=dopc74194.zip ALIGN=LEFT><IMG SRC=dopc74195.zip ALIGN=LEFT><IMG SRC=dopc74195.zip ALIGN=LEFT><IMG SRC=dopc74197.zip ALIGN=LEFT><IMG SRC=dopc74177.zip ALIGN=LEFT><IMG SRC=dopc74148.zip ALIGN=LEFT><IMG SRC=dopc74148.zip ALIGN=LEFT><IMG SRC=dopc74201.zip ALIGN=LEFT><IMG SRC=dopc74160.zip ALIGN=LEFT><IMG SRC=dopc74182.zip ALIGN=LEFT><IMG SRC=dopc74149.zip ALIGN=LEFT><IMG SRC=dopc74194.zip ALIGN=LEFT><IMG SRC=dopc74206.zip ALIGN=LEFT><IMG SRC=dopc74162.zip ALIGN=LEFT><IMG SRC=dopc74208.zip ALIGN=LEFT><IMG SRC=dopc74209.zip ALIGN=LEFT><IMG SRC=dopc74210.zip ALIGN=LEFT><IMG SRC=dopc74211.zip ALIGN=LEFT><IMG SRC=dopc74212.zip ALIGN=LEFT><IMG SRC=dopc74211.zip ALIGN=LEFT><IMG SRC=dopc74149.zip ALIGN=LEFT><IMG SRC=dopc74215.zip ALIGN=LEFT> Можливий випадок, коли нічого певного сказати і про збіжність <a href="Послідовності" title="Послідовності">послідовностей</a> не можна, проте відомо, що <a href="Відповідь" title="Відповідь">відповідна</a> послідовність значень при {f (xk)} збігається до точки мінімального значення (локальний або глобальний мінімум). Тоді кажуть, що послідовність {xk} збігається до мінімуму за функцією (див. рис. 4). Крім того, існують ще більш слабкі типи збіжності, коли, наприклад, послідовність {xk} (кожна її послідовність) має в якості граничної стаціонарну крапку (тобто точку, в якій градієнт дорівнює нульовому вектору), що є лише «підозрілої» на оптимальну. Як правило, тип збіжності одного і того ж методу залежить від конкретного виду цільової функції, тобто в різних завданнях метод може збігатись по-різному. При досить жорстких вимогах до функції f за допомогою методу можна будувати послідовність, сходящуюся в точці глобального мінімуму. Якщо ж цей метод застосувати до функцій, не задовольняє елементарним вимогам, то може бути отримана послідовність, що сходиться тільки по функції, або послідовність, яка не є збіжної ні в якому сенсі. Методи спуску в силу умови монотонності 1.3 зазвичай не призводить до точки локального (глобального) мінімуму. Відзначимо, що навіть у тих випадках, коли немає збіжності ні в одному сенсі, послідовне зменшення значення цільової функції може представляти практичний інтерес. 1.2.2 Градієнтні методи Ненульовий антіградіент - Ñ f (x 0) вказує напрямок, невелике переміщення уздовж якого з х0 призводить до значення функції f меншому, ніж f (x 0). Це чудова властивість лежить в основі градієнтних методів, згідно яких на k-й ітерації вважають pk = - Ñ f (xk), тобто xk +1 = xk - ak Ñ f (xk), ak> 0, k = 0, 1, 2, .... Ці методи відрізняються один від одного способом вибору величини кроку ak. Досить малий крок ak забезпечує спадання цільової функції f (xk +1) = f (xk - ak Ñ f (xk)) <f (xk), (1.4) але може призвести до надто великої кількості ітерацій для досягнення необхідної точності. З іншого боку, <a href="Вибір" title="Вибір">вибір</a> великого кроку може призвести до порушення нерівності 1.4. На практиці нерідко в якості величини кроку вибирають деякий а> 0, однакове для всіх ітерацій. При цьому якщо умова 1.4 (при ak = | a |) порушиться, то для поточної ітерації величину а зменшують до тих пір, поки вказане нерівність не стане здійсненним. Часто величину ak рекомендують вибирати так, щоб мало місце більш жорстку умову убування, ніж 1.4: f (xk) - f (xk - ak Ñ f (xk))> = e ak | | Ñ f (xk) | |, (1.5) де 0 <e <1 - деяка фіксується константа. Тут також спочатку фіксують деякий ak = a> 0 (наприклад, ak = 1), однакове для всіх ітерацій, а потім при необхідності зменшують його до тих пір, поки не буде виконано нерівність 1.5. При реалізації градієнтних методів в якості критеріїв закінчення рахунку використовують умова виду | | Ñ f (xk) | | <= e, де е> 0-фіксована точність обчислень. Точний зміст збіжності градієнтних методів розкриває наступне твердження. Нехай функція f обмежена знизу, неперервно диференційовна на R і її градієнт Ñ f (x) задовольняє умові Ліпшиця: | | Ñ f (x) - Ñ f (x ') | | <= L | | x - x' | | для всіх x, x 'Î R, де L> = 0 - деяка фіксована константа. Крім того, нехай вибір величини кроку ak виробляється на основі умови 1.5. Тоді, як і вона була початкова точка х0, обидва градієнтних методу призводять до побудови послідовності {xk}, володіє властивістю lim | | Ñ f (xk) | | = 0. Якщо, крім того, функція f двічі неперервно диференційовна і існує такі числа М> = m> 0, що m | | y | | ² <= (Ñ ² f (x) y, y) <= M | | y | | ² для всіх x, y, то для градієнтних методів послідовність {xk} буде сходиться до точки глобального мінімуму. Перша частина затвердження гарантує збіжність лише в сенсі lim | | Ñ f (xk) | | = 0, тобто збіжність за функції або до точної нижньої <a href="Межі" title="Межі">межі</a> inf f (x), або до значення функції f в деякій стаціонарної точці х. При цьому сама точка х не обов'язково є точкою локального мінімуму; вона може бути точкою сідлової типу. Однак на практиці подібна <a href="Ситуація" title="Ситуація">ситуація</a> малоймовірна і застосування градієнтних методів, як правило, дозволяє отримати наближене значення мінімуму цільової функції (взагалі кажучи, локального). Порівнюючи малюнки 5 і 6, можна зробити висновок, що для цільової функції, лінії рівня якої близькі до кіл, необхідна точність буде досягнута досить швидко, тоді як якщо лінії сильно витягнуті в околиці оптимальної точки, то <a href="Градієнтні_методи" title="Градієнтні методи">градієнтні методи</a> приведуть до повільного зигзагоподібному просування в напрямку на оптимальну точку. Про функцію, поверхня рівня якої сильно витягнуті, кажуть, що вона має «яружний» характер (у випадках двох змінних графік такої функції дійсно нагадує яр). <IMG SRC=dopc74216.zip ALIGN=LEFT><IMG SRC=dopc74216.zip ALIGN=LEFT><IMG SRC=dopc74218.zip ALIGN=LEFT><IMG SRC=dopc74219.zip ALIGN=LEFT><IMG SRC=dopc74220.zip ALIGN=LEFT><IMG SRC=dopc74221.zip ALIGN=LEFT><IMG SRC=dopc74222.zip ALIGN=LEFT><IMG SRC=dopc74223.zip ALIGN=LEFT><IMG SRC=dopc74224.zip ALIGN=LEFT><IMG SRC=dopc74225.zip ALIGN=LEFT><IMG SRC=dopc74226.zip ALIGN=LEFT><IMG SRC=dopc74227.zip ALIGN=LEFT><IMG SRC=dopc74228.zip ALIGN=LEFT><IMG SRC=dopc74222.zip ALIGN=LEFT><IMG SRC=dopc74230.zip ALIGN=LEFT><IMG SRC=dopc74231.zip ALIGN=LEFT><IMG SRC=dopc74232.zip ALIGN=LEFT><IMG SRC=dopc74233.zip ALIGN=LEFT><IMG SRC=dopc74234.zip ALIGN=LEFT><IMG SRC=dopc74235.zip ALIGN=LEFT><IMG SRC=dopc74236.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74184.zip ALIGN=LEFT><IMG SRC=dopc74239.zip ALIGN=LEFT><IMG SRC=dopc74240.zip ALIGN=LEFT><IMG SRC=dopc74241.zip ALIGN=LEFT><IMG SRC=dopc74242.zip ALIGN=LEFT> Про ступінь «яружно» функції f можна отримати уявлення, знаючи мінімальне (m) і максимальна (M) власні числа матриці Гессе Ñ ² f, обчисленої в оптимальній точці: чим менше ставлення m / M, тим більше "яр-даної функції. Застосування градієнтних методів до таких функцій призводить до спуску на «дно яру», після чого, оскільки напрям спуску майже <a href="Перпендикуляр" title="Перпендикуляр">перпендикулярно</a> «лінії дна», точки послідовності {xk} будуть по черзі стоїть то на одному «схилі яру», то на іншому і просування до оптимальної точці сильно сповільнюється. 1.2.3 Метод найшвидшого спуску Пошук мінімуму функції R (x) виконують по кроках починаючи з початкової точки. На першому кроці обчислюють значення функції, градієнт поля функції, шляхом обчислення приватної похідною за кожної змінної, модуль градієнта, значення змінних в кроці і величину кроку по кожній змінної. У напрямку градієнта шукають мінімум функції, оскільки напрям одне, то використовують один з методів оптимізації одномірної нелінійної функції. Наприклад, сканування з постійним кроком по кожній змінної до локального мінімуму функції. На другому й наступних кроків в точці локального мінімуму знову обчислюють градієнт поля, модуль градієнта, значення змінних в кроці і величину кроку. Обчислення закінчують при значенні модуля градієнта менше або рівного заданої похибки. 2. Інструментальні програмні засоби Перед початком <a href="Роботи" title="Роботи">роботи</a> над <a href="Курсова" title="Курсова">курсовим</a> проектом переді мною постало питання: в якій системі <a href="Програмування" title="Програмування">програмування</a> або за допомогою якого застосування я буду писати програму з даної мені тему. Мій вибір зупинився на додатку <a href="Microsoft_Excel" title="Microsoft Excel">Microsoft Excel</a>. В даний час даний програмний продукт можна знайти практично на будь-якому персональному комп'ютері, на якому встановлена операційна система <a href="Windows" title="Windows">Windows</a> 9 x, 2000, NT 4.0, XP. Microsoft <a href="Excel" title="Excel">Excel</a> володіє необхідним для <a href="Розрахунки" title="Розрахунки">розрахунків</a> моделі <a href="Математика" title="Математика">математичним</a> апаратом. Крім того, в даний програмний продукт вбудований редактор Visual <a href="Basic" title="Basic">Basic</a>, за допомогою якого можна писати макроси. Середа редактора Visual Basic. Visual Basic надає єдину закінчену середу редагування, схожу з середовищем автономної версії Visual Basic 5.0. Кожна <a href="Книга" title="Книга">книга</a> Microsoft Excel має пов'язаний з нею проект. Середа редагування Visual Basic включає поліпшений редактор коду, ієрархічне засіб перегляду об'єктів, багатовіконний відладчик, вікно відображення властивостей і засіб перегляду проектів для управління кодом і об'єктами проекту. Для полегшення створення <a href="Синтаксис" title="Синтаксис">синтаксично</a> правильного коду середу редагування Visual Basic має групу команд у <a href="Меню" title="Меню">меню</a> Правка, що включає команди Список властивостей / методів, Список констант і Параметри. Використання об'єктів ActiveX у формах. Visual Basic забезпечує узгоджені і розгортаються елементи управління і інтерфейс діалогових вікон для всіх програм Microsoft Office. Елементи ActiveX (раніше називалися елементами управління OLE) можуть бути впроваджені безпосередньо на листи, що дозволяє користувачеві створювати свої власні форми. Події Багатющі можливості обробки подій надають гнучкі засоби визначення реакції на дії користувача. 3. Блок-схема алгоритму моделювання <IMG SRC=dopc74243.zip ALIGN=LEFT><IMG SRC=dopc74243.zip ALIGN=LEFT><IMG SRC=dopc74245.zip ALIGN=LEFT><IMG SRC=dopc74245.zip ALIGN=LEFT><IMG SRC=dopc74245.zip ALIGN=LEFT><IMG SRC=dopc74245.zip ALIGN=LEFT><IMG SRC=dopc74249.zip ALIGN=LEFT><IMG SRC=dopc74245.zip ALIGN=LEFT><IMG SRC=dopc74243.zip ALIGN=LEFT><IMG SRC=dopc74249.zip ALIGN=LEFT><IMG SRC=dopc74253.zip ALIGN=LEFT><IMG SRC=dopc74254.zip ALIGN=LEFT><IMG SRC=dopc74255.zip ALIGN=LEFT><IMG SRC=dopc74256.zip ALIGN=LEFT><IMG SRC=dopc74257.zip ALIGN=LEFT><IMG SRC=dopc74258.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74262.zip ALIGN=LEFT><IMG SRC=dopc74263.zip ALIGN=LEFT><IMG SRC=dopc74264.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74195.zip ALIGN=LEFT><IMG SRC=dopc74195.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT><IMG SRC=dopc74272.zip ALIGN=LEFT><IMG SRC=dopc74273.zip ALIGN=LEFT><IMG SRC=dopc74274.zip ALIGN=LEFT><IMG SRC=dopc74275.zip ALIGN=LEFT><IMG SRC=dopc74276.zip ALIGN=LEFT><IMG SRC=dopc74277.zip ALIGN=LEFT><IMG SRC=dopc74278.zip ALIGN=LEFT><IMG SRC=dopc74279.zip ALIGN=LEFT><IMG SRC=dopc74280.zip ALIGN=LEFT><IMG SRC=dopc74281.zip ALIGN=LEFT><IMG SRC=dopc74282.zip ALIGN=LEFT><IMG SRC=dopc74259.zip ALIGN=LEFT> <IMG SRC=dopc74253.zip ALIGN=LEFT> <IMG SRC=dopc74243.zip ALIGN=LEFT><IMG SRC=dopc74286.zip ALIGN=LEFT> Введення даних здійснюється за допомогою діалогового вікна «Введення даних» (див. рис. 7). <IMG SRC=dopc74287.zip ALIGN=LEFT> Малюнок 7 Вид форми для введення даних Висновок проміжних і вихідних даних здійснюється в таблицю (див. табл. 1) Таблиця 1 Результати рішення <TABLE WIDTH=257 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=16><COL WIDTH=17><COL WIDTH=43><COL WIDTH=43><COL WIDTH=29><COL WIDTH=24><TR><TD WIDTH=16> X1 </TD><TD WIDTH=17> X2 </TD><TD WIDTH=43> dR/dX1 </TD><TD WIDTH=43> dR/dX2 </TD><TD WIDTH=29> | Grad | </TD><TD WIDTH=24> R (x) </TD></TR><TR VALIGN=TOP><TD WIDTH=16> </TD><TD WIDTH=17> </TD><TD WIDTH=43> </TD><TD WIDTH=43> </TD><TD WIDTH=29> </TD><TD WIDTH=24> </TD></TR><TR VALIGN=TOP><TD WIDTH=16> </TD><TD WIDTH=17> </TD><TD WIDTH=43> </TD><TD WIDTH=43> </TD><TD WIDTH=29> </TD><TD WIDTH=24> </TD></TR></TABLE> 4. Операційне середовище Мінімальні вимоги пред'являеми до апаратної частини: Процесор - 486 DX / лютий 1980 Mz ОЗУ - 12Мб Відеоадаптер - VGA 640-480 Монітор Клавіатура Миша В якості операційного середовища на персональному комп'ютері повинна бути встановлена одна з версій Windows (9 x, 2000, NT 4.0, XP, Me), а також програмний пакет Microsoft Office (97, 2000) або, хоча б, Microsoft Excel. Для того, щоб почати роботу з моделлю потрібно скопіювати <a href="Файл" title="Файл">файл</a> «Метод найшвидшого спуску" в папку «Мої документи» та з допомогою програмного забезпечення Microsoft Excel відкрити файл. 5. Контрольна завдання Завдання. Знайти мінімум функції R (x) = a * x1 ^ 3 + b * x2 ^ 2-c * x1-d * x2, де a = 1, b = 2, c = 3, d = 4. Початкові точки: х1 = -0,5; х2 = -1. Пробний крок g = 0,01. Коефіцієнт пробного кроку h = 0,1. Похибка е = 0,01. Рішення. У початкових точках х1 =- 0,5, х2 =- 1 обчислимо за методом градієнта значення функції, градієнт поля функції, значення змінних в кроці і величину кроку. Отримані дані занесемо в таблицю і поставимо номер кроку. Потім за формулою xi +1 = xi - h * (dR / dxi) знайдемо нові значення змінних х1 і х2 і обчислимо значення функції. Останні операції будемо повторювати до тих пір, поки значення функції не почне зростати. Коли це станеться, попереднє значення функції будемо вважати локальним мінімумом. Обчислимо значення градієнта поля, модуль градієнта, занесемо результати в таблицю і вкажемо наступний номер кроку. Всі обчислення закінчимо, коли значення модуля градієнта буде менше або дорівнює значенню похибки. Результати рішення наведені в <a href="Таблиці" title="Таблиці">таблиці</a> 2. Таблиця 2 Результати рішення <a href="Контроль" title="Контроль">контрольної</a> задачі <TABLE WIDTH=439 BORDER=1 BORDERCOLOR=#000000 CELLPADDING=7 CELLSPACING=0><COL WIDTH=49><COL WIDTH=44><COL WIDTH=50><COL WIDTH=48><COL WIDTH=50><COL WIDTH=50><COL WIDTH=46><TR VALIGN=TOP><TD WIDTH=49> Х1 </TD><TD WIDTH=44> X2 </TD><TD WIDTH=50> dR/dx1 </TD><TD WIDTH=48> DR/dx1 </TD><TD WIDTH=50> | R | </TD><TD WIDTH=50> R (X) </TD><TD WIDTH=46> № Кроку </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> -0,5 </TD><TD WIDTH=44> -1 </TD><TD WIDTH=50> -2,2499 </TD><TD WIDTH=48> -8 </TD><TD WIDTH=50> 8,310358 </TD><TD WIDTH=50> 7,375 </TD><TD WIDTH=46> 1 </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=7> -0,27501 </TD><TD WIDTH=44> -0,2 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> 1,684231 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> -0,05002 </TD><TD WIDTH=44> 0,6 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -1,53007 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,17497 </TD><TD WIDTH=44> 1,4 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -2,19955 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,17497 </TD><TD WIDTH=44> 1,4 </TD><TD WIDTH=50> -2,90806 </TD><TD WIDTH=48> 1,6 </TD><TD WIDTH=50> 3,319155 </TD><TD WIDTH=50> -2,19955 </TD><TD WIDTH=46> 2 </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,465776 </TD><TD WIDTH=44> 1,24 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,18108 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,756581 </TD><TD WIDTH=44> 1,08 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,82387 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 1,047387 </TD><TD WIDTH=44> 0,92 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,98036 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 1,047387 </TD><TD WIDTH=44> 0,92 </TD><TD WIDTH=50> 0,291158 </TD><TD WIDTH=48> -0,32 </TD><TD WIDTH=50> 0,432635 </TD><TD WIDTH=50> -3,98036 </TD><TD WIDTH=46> 3 </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 1,018271 </TD><TD WIDTH=44> 0,952 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,99438 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,989155 </TD><TD WIDTH=44> 0,984 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,99914 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,989155 </TD><TD WIDTH=44> 0,984 </TD><TD WIDTH=50> -0,06462 </TD><TD WIDTH=48> -0,064 </TD><TD WIDTH=50> 0,090946 </TD><TD WIDTH=50> -3,99914 </TD><TD WIDTH=46> 4 </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,995617 </TD><TD WIDTH=44> 0,9904 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,99976 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 1,002078 </TD><TD WIDTH=44> 0,9968 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,99997 </TD><TD WIDTH=46> </COL></COL></COL></COL></COL></COL></COL></TD></TR></COL></COL></COL></COL></COL></COL></TABLE><TABLE><TR><TD></TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 1,002078 </TD><TD WIDTH=44> 0,9968 </TD><TD WIDTH=50> 0,012583 </TD><TD WIDTH=48> -0,0128 </TD><TD WIDTH=50> 0,017949 </TD><TD WIDTH=50> -3,99997 </TD><TD WIDTH=46> 5 </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 1,00082 </TD><TD WIDTH=44> 0,99808 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -3,99999 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=3> 0,999562 </TD><TD WIDTH=44> 0,99936 </TD><TD WIDTH=50> </TD><TD WIDTH=48> </TD><TD WIDTH=50> </TD><TD WIDTH=50> -4 </TD><TD WIDTH=46> </TD></TR><TR VALIGN=TOP><TD WIDTH=49 HEIGHT=2> 0,999562 </TD><TD WIDTH=44> 0,99936 </TD><TD WIDTH=50> -0,00253 </TD><TD WIDTH=48> -0,00256 </TD><TD WIDTH=50> 0,003599 </TD><TD WIDTH=50> -4 </TD><TD WIDTH=46> 6 </TD></TR></TABLE> Проаналізувавши результати в таблиці 2, ми бачимо, що якщо не враховувати проміжні значення, мінімум функції R (x) знайдено на 6-му кроці. Якщо порівняти результати, отримані при пошуку мінімуму методом градієнта і методом найшвидшого спуску, ми помітимо, що метод найшвидшого спуску виправдовує свою назву, тому що мінімум функції знайдений на 6-му кроці, а метод градієнта знайде цьому мінімум тільки на 15-му. Звідси висновок, метод найшвидшого спуску також ефективний, але <a href="Працює" title="Працює">працює</a> набагато швидше. Висновок Універсального методу (алгоритму), за допомогою якого можна було б успішно вирішувати різноманітні <a href="Завдання_оптимізації" title="Завдання оптимізації">завдання оптимізації</a>, не існує. Тому для вирішення кожного конкретного класу задач використовують (і, як правило, не один) «свій» чисельний метод. Слід пам'ятати, що ефективність чисельного рішення залежить від того, наскільки повно і точно відбивається в застосовуваному методі специфіка даної задачі, її «індивідуальні» особливості. Дану програмну модель рекомендується використовувати для пошуку глобального мінімуму нелінійних «яружних» функції двох змінних. Звичайно, на цьому можна було б і зупинитися. Метод успішно працює, досить швидко знаходить мінімум функції, але цей пошук можна було б ще прискорити. Слід розробити спосіб вибору яружного кроку, тобто величина кроку повинна змінюватися від етапу до етапу в залежності від розташування локального мінімуму функції. Ефективність розглянутого методу зросла б ще більше, тому що метод залежить від величин яружних кроків h 1, h 2. Але тут є свої труднощі, якщо яружний крок занадто великий, то можна досить далеко відійти від лінії «дна яру», коли ж цей крок малий, то просування буде незначним. Величину кроку потрібно підбирати емпірично, враховуючи відомі властивості мінімізіруемой функції. Література 1. Юдін Д.Б., Юдін А.Д. «Кількість і думка» М.: <a href="Знання" title="Знання">Знання</a>, 2005. С.190 2. Немирівський А.С., Юдін Д.Б. «Інформаційна складність математичного моделювання» Изв. АНСССР. Тих. Кібернетика. 2003 № 1 С.88-117 3. Уайнд Д. «Методи пошуку екстремуму». М.: <a href="Наука" title="Наука">Наука</a>, 2007. С.267 4. Гельфонд І.М., Цетлін М.Л. «Про деякі способи управління складними системами». УМН, 2002. Т.27. С.3-26 5. Федоренко Р.П. «Про один алгоритм рішення завдань математичного програмування». Журнал обчислювальна <a href="Математика" title="Математика">математика</a>, 2006. Т.22 № 6 С.1331-1343 6. Поляк Б.Т. «Введення в оптимізацію» М.: Наука, 2003. С.384 7. Ногін В.Д. «Основи теорії оптимізації» М.: Знання, 2007. С99-122 8. Ларичев О.І., Горвіц Г.Г. «Методи пошуку локальних екстремумів яружних функцій» М.: Наука, 2003. З .5-12 Додаток Код модуля Option Explicit Dim i, s, j, h1, h2 Sub Кнопка2_Щелкнуть () Form 1. Show 'Введення вихідних даних End Sub Sub Кнопка3_Щелкнуть () j = 1 i = 2 'Номер кроку (етапу) Do 'Цикл знаходження мінімуму функції h 1 = Range ("aa 3") 'Присвоєння змінним h 2 = Range ("aa 4") 'h 1, h 2 значення кроку Do Range ("z 1"). <a href="SELECT" title="SELECT">Select</a> "Збереження попереднього s = ActiveCell 'значення функції 'Обчислення нових початкових точок Range ("v1"). Select ActiveCell = Range ("x1") Range ("v2"). Select ActiveCell = Range ("x2") Range ("x1"). Select ActiveCell = ActiveCell - h1 Range ("x2"). Select ActiveCell = ActiveCell - h2 'Висновок в таблицю нових початкових 'Точок і значення функції в цих точках Range ("a3", "f23"). Select ActiveCell (j, "a") = Range ("x1") ActiveCell (j, "b") = Range ("x2") ActiveCell (j, "f") = Range ("z1") j = j + 1 'C рівняння нового значення функції з попереднім Loop While Range ("z1") <s j = j - 1 Range ("x1"). Select ActiveCell = Range ("v1") Range ("x2"). Select ActiveCell = Range ("v2") 'Висновок в таблицю нових початкових точок, 'Градієнт поля функції, модуль градієнта 'І значення функції в нових початкових точках Range ("a3", "g23"). Select ActiveCell (j, "a") = Range ("x1") ActiveCell (j, "b") = Range ("x2") ActiveCell (j, "c") = Range ("w1") ActiveCell (j, "d") = Range ("w2") ActiveCell (j, "e") = Range ("w3") ActiveCell (j, "f") = Range ("z1") 'Висновок номера кроку (етапу) обчислення мінімуму функції ActiveCell (j, "g") = i j = j + 1 i = i + 1 Range ("w 3"). Select 'Порівняння значення модуля градієнта і похибки Loop While ActiveCell> Range ("y3") End Sub Sub Кнопка4_Щелкнуть () "Видалення діапазону комірок Range ("a2", "g40"). Clear Range ("x1", "x2"). Clear Range ("y1", "y3"). Clear Range ("v1", "v2"). Clear Range ("z1"). Clear End Sub Код форми "Метод найшвидшого спуску" Private Sub CB1_Click () End End Sub Private Sub CB2_Click () Range ("Z1"). Select Lbl1.Caption = ActiveCell Range ("c2"). Select ActiveCell = Range ("w1") Range ("d2"). Select ActiveCell = Range ("w2") Range ("e2"). Select ActiveCell = Range ("w 3") 'Висновок номери кроку знаходження мінімуму функції Range ("g2"). Select ActiveCell = 1 End Sub Private Sub TB1_Change () Range ("X1"). Select ActiveCell = TB1.Text Range ("a2"). Select ActiveCell = Range ("x1") End Sub Private Sub TB2_Change () Range ("X2"). Select ActiveCell = TB2.Text Range ("b2"). Select ActiveCell = Range ("x2") End Sub Private Sub TB3_Change () Range ("Y1"). Select ActiveCell = TB3.Text End Sub Private Sub TB5_Change () Range ("Y3"). Select ActiveCell = TB5.Text End Sub Private Sub TB4_Change () Range ("Y2"). Select ActiveCell = TB4.Text End Sub Private Sub TB6_Change () Range ("Z1"). Select ActiveCell = TB6.Text Range ("f2"). Select ActiveCell = Range ("z1") End Sub 
	</div>

Будь ласка, не зберігайте тестовий текст.
Ваш ip: 3.145.17.20 буде збережений.

категорії
за типом
за алфавітом
завантажені