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

Зміст

Введення

1. Пояснювальна записка

1.1 Нелінійне програмування

1.2 Чисельні методи в задачах без обмежень

1.2.1 Загальна схема методів спуску

1.2.2 Градієнтні методи

1.2.3 Метод найшвидшого спуску

2. Інструментальні програмні засоби

3. Блок-схема алгоритму моделювання

4. Операційне середовище

5. Контрольна завдання

Висновок

Література

Додаток

Введення

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

Чисельне рішення оптимізаційних задач на ЕОМ зводиться до пошуку екстремуму функції багатьох змінних. Такі завдання оптимального управління та ідентифікації, завдання супервизорного управління, оптимізаційного проектування і планування.

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

Ці завдання представляють інтерес з різних точок зору. Перш за все не опуклість породжує великі аналітичні складності при розробці методів рішення унімодальних завдань. Як відомо, аналітичні методи розвинені для значно простих завдань.

Для лінійних, квадратичних, опуклих задач розроблені різні чисельні методи рішення, доведена збіжність методів, отримані оцінки швидкості збіжності.

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

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

1. Пояснювальна записка

1.1 Нелінійне програмування

Унімодальне функції. Виділимо клас функцій, що володіють, з обчислювальної точки зору, важливою властивістю. А саме: функція f називається унімодальної на відрізку [a, b], якщо вона має на цьому відрізку єдину точку глобального мінімуму Xmin і ліворуч від цієї точки є строго спадною, а праворуч строго зростаючою (див. рис. 1). Іншими словами, функція f унімодальному, якщо точка Xmin існує і єдина, причому для будь-яких двох точок х1, х2 Î [a, b] таких, що х1 <x 2 з нерівності х1> Xmin завжди слід f (x 1) <f ( x 2), а з нерівності x 2 <Xmin необхідно випливає нерівність f (x 1)> f (x 2).

Самого факту унімодальному недостатньо для отримання аналітичних результатів або побудови ефективних числових методів. У теж час «поширене трактування опуклих задач як хорошого модального об'єкта для задач одноекстрімальних теоретично не спроможна - складність класів опуклих завдань незрівнянно нижче, ніж унімодальних.» [1]

Інформаційна складність (нижня межа оцінки трудомісткості) задач мінімізації безперервних функцій загального вигляду украй велика, причому саме унімодальному (а не багатоекстремального) є причиною такої складності. У роботі [2] зазначено, що інформаційна складність класу унімодальних завдань «фантастично велика». З точки зору авторів книги [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) і прирівнювання нулю похідних дають систему лінійних рівнянь. У силу невирожденості матриці система має єдине рішення.

Квадратичні одноекстрімальние функції (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).

Строго опуклі функції унімодальному та володіють гідністю, полегшує дослідження і процес чисельної мінімізації, - це чітка опуклість, а отже, одноекстрімальность уздовж будь-якого напрямку. Більш широким класом є клас лінійно унімодальних функцій [3]. Характерна властивість цього безлічі - унімодальному функцій вздовж будь-якої прямої в допустимій області. Функції, унімодальне по будь-якому напрямку, якщо цей напрям відбувається через точку мінімум, утворюючи клас строго унімодальних функцій [3].

На малюнку 2 представлені: А - строго опукла; Б - лінійно-унімодальному; В - суворо унімодальному функції.

Специфіка кожного з описаних класів може бути використана при побудові методів мінімізації.

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

На початку 60-х років І.М. Гельфонд і М.Л. Цетлін [4] був дескриптивної заданий клас неопуклих функцій багатьох змінних. Елементи класу характеризуються наступною структурою: у будь-якій точці деякого підмножини області визначення функції існує такий базис, що всі незалежні змінні можна розділити на дві групи. Перша група складається з тих аргументів, зміна яких призводить до значної зміни цільової функції (в [4] вони названі несуттєвими змінними). Зміна змінних другої групи (суттєвих змінних) призводить до незначної зміни функції. При цьому для будь-якої точки підмножини друга група містить лише невелике число параметрів. Функція, що допускає таке розбиття змінних в деякій області, називається добре організованою (яружної) функцією в цій області, а число істотних змінних визначає розмірність яру [4]. Іншими словами, для яружної функції точність лінійного наближення

f (x) + Ñ f (x) * Ñ x в значній мірі залежить від Ñ x [5].

У математичному енциклопедичному словнику за редакцією Ю.В. Прохорова дано суворе визначення яружної функції.

Нехай «обмежена знизу функція багатьох змінних

J * (x) = J (x1, x2, ..., xm) Î c ² (D), D Ì R,

володіє тією особливістю, що в досліджуваній області власні значення матриці Гессе

, I, j = 1, 2, ..., m,

впорядковані в будь-якій точці x Î D, задовольняють нерівності

0 <| min l i (x) | <<l 1 (x).

У цьому випадку поверхня рівня J (x) = const мають структуру, що сильно відрізняється від сферичної. Такі функції J (x) називаються яружний. Ступінь яружно характеризується числом

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 називається розмірністю яру. »

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

«Звичайно, таке розбиття параметрів неможливо для будь-якої функції, яку міг би поставити математик. Однак, для функцій, що зустрічаються в практичній діяльності людини (тут маються на увазі розумні завдання фізики, техніки), таке розбиття, очевидно, має місце в дуже значному числі випадків. »[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 велике, функція має яружний характер.

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

Відомо, що мінімізація яружних функцій пов'язана з великими обчислювальними труднощами. Тому Р.П. Федоренко [5] пропонує при розробці первинної постановки завдання уникати тих способів формалізації, які призводять до появи яружних функцій.

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

1.2 Чисельні методи в задачах без обмежень

1.2.1 Загальна схема методів спуску

Будемо розглядати задачу безумовної мінімізації, тобто завдання мінімізації цільової функції f на всьому просторі R. Сутність всіх методів наближеного рішення цього завдання полягає в побудові послідовності точок х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 традиційно називають довжиною кроку.

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

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

Найважливішою характеристикою будь-яких методів спуску є їх збіжність. Збіжність тут розуміється в тому сенсі, що послідовність {xk} має сходитись до точки глобального (локального) мінімуму. Однак точки мінімуму можуть становити ціле безліч і багато алгоритмів дозволяють побудувати послідовність {xk}, яка сама не є збіжної, але будь-яка її сходиться послідовність має в якості граничної деяку точку мінімум (див. рис. 3).

У цьому випадку говорять, що кожна гранична точка послідовності {xk} є точкою мінімуму. За допомогою подібних алгоритмів можна будувати послідовності точок, як завгодно близько наближаються до безлічі точок мінімуму.

Можливий випадок, коли нічого певного сказати і про збіжність послідовностей не можна, проте відомо, що відповідна послідовність значень при {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)

але може призвести до надто великої кількості ітерацій для досягнення необхідної точності. З іншого боку, вибір великого кроку може призвести до порушення нерівності 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, тобто збіжність за функції або до точної нижньої межі inf f (x), або до значення функції f в деякій стаціонарної точці х. При цьому сама точка х не обов'язково є точкою локального мінімуму; вона може бути точкою сідлової типу. Однак на практиці подібна ситуація малоймовірна і застосування градієнтних методів, як правило, дозволяє отримати наближене значення мінімуму цільової функції (взагалі кажучи, локального).

Порівнюючи малюнки 5 і 6, можна зробити висновок, що для цільової функції, лінії рівня якої близькі до кіл, необхідна точність буде досягнута досить швидко, тоді як якщо лінії сильно витягнуті в околиці оптимальної точки, то градієнтні методи приведуть до повільного зигзагоподібному просування в напрямку на оптимальну точку. Про функцію, поверхня рівня якої сильно витягнуті, кажуть, що вона має «яружний» характер (у випадках двох змінних графік такої функції дійсно нагадує яр).

Про ступінь «яружно» функції f можна отримати уявлення, знаючи мінімальне (m) і максимальна (M) власні числа матриці Гессе Ñ ² f, обчисленої в оптимальній точці: чим менше ставлення m / M, тим більше "яр-даної функції. Застосування градієнтних методів до таких функцій призводить до спуску на «дно яру», після чого, оскільки напрям спуску майже перпендикулярно «лінії дна», точки послідовності {xk} будуть по черзі стоїть то на одному «схилі яру», то на іншому і просування до оптимальної точці сильно сповільнюється.

1.2.3 Метод найшвидшого спуску

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

У напрямку градієнта шукають мінімум функції, оскільки напрям одне, то використовують один з методів оптимізації одномірної нелінійної функції. Наприклад, сканування з постійним кроком по кожній змінної до локального мінімуму функції.

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

2. Інструментальні програмні засоби

Перед початком роботи над курсовим проектом переді мною постало питання: в якій системі програмування або за допомогою якого застосування я буду писати програму з даної мені тему. Мій вибір зупинився на додатку Microsoft Excel. В даний час даний програмний продукт можна знайти практично на будь-якому персональному комп'ютері, на якому встановлена ​​операційна система Windows 9 x, 2000, NT 4.0, XP. Microsoft Excel володіє необхідним для розрахунків моделі математичним апаратом. Крім того, в даний програмний продукт вбудований редактор Visual Basic, за допомогою якого можна писати макроси.

Середа редактора Visual Basic.

Visual Basic надає єдину закінчену середу редагування, схожу з середовищем автономної версії Visual Basic 5.0. Кожна книга Microsoft Excel має пов'язаний з нею проект. Середа редагування Visual Basic включає поліпшений редактор коду, ієрархічне засіб перегляду об'єктів, багатовіконний відладчик, вікно відображення властивостей і засіб перегляду проектів для управління кодом і об'єктами проекту. Для полегшення створення синтаксично правильного коду середу редагування Visual Basic має групу команд у меню Правка, що включає команди Список властивостей / методів, Список констант і Параметри.

Використання об'єктів ActiveX у формах.

Visual Basic забезпечує узгоджені і розгортаються елементи управління і інтерфейс діалогових вікон для всіх програм Microsoft Office. Елементи ActiveX (раніше називалися елементами управління OLE) можуть бути впроваджені безпосередньо на листи, що дозволяє користувачеві створювати свої власні форми.

Події

Багатющі можливості обробки подій надають гнучкі засоби визначення реакції на дії користувача.

3. Блок-схема алгоритму моделювання

Введення даних здійснюється за допомогою діалогового вікна «Введення даних» (див. рис. 7).

Малюнок 7 Вид форми для введення даних

Висновок проміжних і вихідних даних здійснюється в таблицю (див. табл. 1)

Таблиця 1

Результати рішення

4. Операційне середовище

Мінімальні вимоги пред'являеми до апаратної частини:

Процесор - 486 DX / лютий 1980 Mz

ОЗУ - 12Мб

Відеоадаптер - VGA 640-480

Монітор

Клавіатура

Миша

В якості операційного середовища на персональному комп'ютері повинна бути встановлена ​​одна з версій Windows (9 x, 2000, NT 4.0, XP, Me), а також програмний пакет Microsoft Office (97, 2000) або, хоча б, Microsoft Excel.

Для того, щоб почати роботу з моделлю потрібно скопіювати файл «Метод найшвидшого спуску" в папку «Мої документи» та з допомогою програмного забезпечення 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 і обчислимо значення функції. Останні операції будемо повторювати до тих пір, поки значення функції не почне зростати. Коли це станеться, попереднє значення функції будемо вважати локальним мінімумом. Обчислимо значення градієнта поля, модуль градієнта, занесемо результати в таблицю і вкажемо наступний номер кроку.

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

Таблиця 2

Результати рішення контрольної задачі

Проаналізувавши результати в таблиці 2, ми бачимо, що якщо не враховувати проміжні значення, мінімум функції R (x) знайдено на 6-му кроці. Якщо порівняти результати, отримані при пошуку мінімуму методом градієнта і методом найшвидшого спуску, ми помітимо, що метод найшвидшого спуску виправдовує свою назву, тому що мінімум функції знайдений на 6-му кроці, а метод градієнта знайде цьому мінімум тільки на 15-му. Звідси висновок, метод найшвидшого спуску також ефективний, але працює набагато швидше.

Висновок

Універсального методу (алгоритму), за допомогою якого можна було б успішно вирішувати різноманітні завдання оптимізації, не існує. Тому для вирішення кожного конкретного класу задач використовують (і, як правило, не один) «свій» чисельний метод. Слід пам'ятати, що ефективність чисельного рішення залежить від того, наскільки повно і точно відбивається в застосовуваному методі специфіка даної задачі, її «індивідуальні» особливості. Дану програмну модель рекомендується використовувати для пошуку глобального мінімуму нелінійних «яружних» функції двох змінних.

Звичайно, на цьому можна було б і зупинитися. Метод успішно працює, досить швидко знаходить мінімум функції, але цей пошук можна було б ще прискорити. Слід розробити спосіб вибору яружного кроку, тобто величина кроку повинна змінюватися від етапу до етапу в залежності від розташування локального мінімуму функції. Ефективність розглянутого методу зросла б ще більше, тому що метод залежить від величин яружних кроків h 1, h 2. Але тут є свої труднощі, якщо яружний крок занадто великий, то можна досить далеко відійти від лінії «дна яру», коли ж цей крок малий, то просування буде незначним. Величину кроку потрібно підбирати емпірично, враховуючи відомі властивості мінімізіруемой функції.

Література

1. Юдін Д.Б., Юдін А.Д. «Кількість і думка» М.: Знання, 2005. С.190

2. Немирівський А.С., Юдін Д.Б. «Інформаційна складність математичного моделювання» Изв. АНСССР. Тих. Кібернетика. 2003 № 1 С.88-117

3. Уайнд Д. «Методи пошуку екстремуму». М.: Наука, 2007. С.267

4. Гельфонд І.М., Цетлін М.Л. «Про деякі способи управління складними системами». УМН, 2002. Т.27. С.3-26

5. Федоренко Р.П. «Про один алгоритм рішення завдань математичного програмування». Журнал обчислювальна математика, 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"). Select "Збереження попереднього

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