Головна
Банківська справа  |  БЖД  |  Біографії  |  Біологія  |  Біохімія  |  Ботаніка та с/г  |  Будівництво  |  Військова кафедра  |  Географія  |  Геологія  |  Екологія  |  Економіка  |  Етика  |  Журналістика  |  Історія техніки  |  Історія  |  Комунікації  |  Кулінарія  |  Культурологія  |  Література  |  Маркетинг  |  Математика  |  Медицина  |  Менеджмент  |  Мистецтво  |  Моделювання  |  Музика  |  Наука і техніка  |  Педагогіка  |  Підприємництво  |  Політекономія  |  Промисловість  |  Психологія, педагогіка  |  Психологія  |  Радіоелектроніка  |  Реклама  |  Релігія  |  Різне  |  Сексологія  |  Соціологія  |  Спорт  |  Технологія  |  Транспорт  |  Фізика  |  Філософія  |  Фінанси  |  Фінансові науки  |  Хімія

Порівняльний аналіз методів оптимізації - Математика

Міністерство освіти і науки Республіки Казахстан

Карагандинський Державний Технічний Університет

Кафедра

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

до курсової роботи з дисципліни: «Теорія прийняття рішень»

Тема: Порівняльний аналіз методів оптимізації

Виконала

Студентка групи ___

___

Керівник

___

Караганда-2009

Зміст

Введення

Постановка завдання

1 Прямі методи одновимірної оптимізації

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

1.2 Метод золотого перетину

2 Прямі методи безумовної оптимізації багатовимірної функції

2.1 Метод покоординатного циклічного спуску

2.2 Метод Хука - Дживса

2.3 Метод правильного симплекса

2.4 Метод деформованого симплекса

3. Умовна оптимізація

3.1 Метод перетворення цільової функції

3.2 Метод штрафних функцій

4. Симплекс таблиці

Висновок

Список використаної літератури

Додаток А Лістинг програм: Метод дихотомії, Метод золотого перетину, Метод покоординатного циклічного спуску, Метод Хука - Дживса, Метод правильного симплекса

Додаток Б Лістинг програми: Метод деформованого симплекса

Додаток В Лістинг програми: Метод правильного тривимірного симплекса (максимізація обсягу фігури)

Введення

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

Формулювання математичної задачі оптимізації.

У досить загальному вигляді математичну задачу оптимізації можна сформулювати наступним чином:

Мінімізувати (максимізувати) цільову функцію з урахуванням обмежень на керовані змінні.

Під мінімізацією (максимізацією) функції n змінних f (x) = f (x1, ..., xn) на заданій множині U n-мірного векторного простору En розуміється визначення хоча б однієї з точок мінімуму (максимуму) цієї функції на безлічі U, а також, якщо це необхідно, і мінімального (максимального) на U значення f (x).

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

f (x) -> min (max),

x належить U,

де f (x) - цільова функція, а U - допустима безліч, задане обмеженнями на керовані змінні.

Постановка завдання

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

1. Прямі методи одновимірної оптимізації

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

f (x) -> min,

x належить [a, b].

Максимізація цільової функції еквівалента мінімізації (f (x) -> max) еквівалентна мінімізації протилежної величини (-f (x) -> min), тому, не применшуючи спільності можна розглядати лише завдання мінімізації.

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

Для вирішення завдання мінімізації функції f (x) на відрізку [a, b] на практиці, як правило, застосовують наближені методи. Вони дозволяють знайти рішення цієї задачі з необхідною точністю в результаті визначення кінцевого числа значень функції f (x) та її похідних в деяких точках відрізка [a, b]. Методи, що використовують тільки значення функції і не потребують обчислення її похідних, називаються прямими методами мінімізації.

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

Розглянемо найбільш поширені на практиці прямі методи пошуку точки мінімуму. Найслабшим вимогою на функцію f (x), що дозволяє використовувати ці методи, є її унімодальне. Тому далі будемо вважати функцію f (x) унімодальної на відрізку [a, b].

Функція f (x) називається унімодальної на відрізку [a, b], якщо вона неперервна на [a, b] і існують числа ,, такі, що:

якщо, то на відрізку [a;] функція f (x) монотонно убуває;

якщо, то на відрізку [; b] функція f (x) монотонно зростає;

при

Для вивчення прямих методів одновимірної оптимізації була дана функція:

F (x) = 8 * cos (5 * x) + > min

a = 2.7 b = 3.9

І вибрано наближення ? = 0,01, = 0,02

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

У цьому методі точки x1 і х2 розташовуються близько до середини чергового відрізка [а; b], т.е:

, (2.11)

де d> 0 - мале число. При цьому відношення довжин нового і вихідного відрізків

близько до 1/2, цим і пояснюється назва методу.

Відзначимо, що для будь-яких точок x1 і х2 величина t> 1/2, тому зазначений вибір пробних точок пояснюється прагненням забезпечити максимально можливе відносне зменшення відрізка на кожній ітерації пошуку х *.

Наприкінці обчислень за методом дихотомії в якості наближеного значення х * беруть середину останнього зі знайдених відрізків [а; b], переконавшись попередньо, що досягнуто нерівність

.

Опишемо алгоритм методу розподілу відрізка навпіл.

Крок 1. Визначити x1 і х2 за формулами (2.11). Обчислити f (x1) і f (x2).

Крок 2. Порівняти f (x1) і f (x2). Якщо, то перейти до відрізка [а; x2], поклавши b = x2, інакше - до відрізка [x1; b], поклавши а = x1.

Крок 3. Знайти досягнуту точність

Якщо, то перейти до наступної ітерації, повернувшись до кроку 1. Якщо, то завершити пошук х *, перейшовши до кроку 4.

Крок 4. Покласти

.

Зауваження:

1. Число d з (2.11) вибирають на інтервалі (0; 2 e) з урахуванням таких міркувань:

а) чим менше d, тим більше відносне зменшення довжини відрізка на кожній ітерації, тобто при зменшенні d досягається більш висока швидкість збіжності методу дихотомії;

б) при надмірно малому d порівняння значень f (x) в точках x1 і х2, що відрізняються на величину d, стає скрутним. Тому вибір d повинен бути узгоджений з точністю визначення f (x) і з кількістю вірних десяткових знаків при завданні аргументу х.

У таблиці 1 наведено рішення завдання за варіантом.

Таблиця 1 - Метод дихотомії

 № кроку x1 x2 F (x1) F (x2) а b

 1 3.29 3.31 --3.3662671 -3.3081836 2.7 3.9 0.6

 2 2.995 3.0015 -3.9477432 -3.9985552 2.7 3.301 0.3

 3 3.1425 3.1525 -5.7966545 -5.7920936 2.995 3.301 0.15075

 4 2.9995 3.15125 -5.3956845 -5.4206115 3.06875 3.1625 0.04687

 5 3.1118125 3.1138125 -5.7344664 -5.7448499 3.074375 3.15125 0.03844

 6 3.1305312 3.1325312 -5.8005444 -5.8034734 3.1118125 3.15125 0.01972

 7 3.1398906 3.1418906 -5.8073633 -5.8065477 3.1305312 3.15125 0.01036

 8 3.1352109 3.1372109 -5.8061441 -5.8072013 3.1305312 3.1418906 5.67969E-3

 9 3.1309766 3.1509766 -5.8073015 -5.8074223 3.1352109 3.1418906 3.33984E-3

 10 3.1387207 3.1407207 -5.8074693 -5.807122 3.1375508 3.1465703 2.16992E-3

 11 3.1381357 3.1401357 -5.8074196 -5.8073064 3.1375508 3.1407207 1.585E-3

 12 3.1384282 3.1404282 -5.807453 -5.8072227 3.1381357 3.1407207 1.292E-3

| Ab | = 0.001 <= ?, x * = (a + b) /2=3.139282, f (x *) = - 5.8074527

Рисунок 1 - Результат виконання програми (Метод дихотомії).

1.2 Метод золотого перетину

Метод золотого перетину. Розглянемо таке симетричне розташування точок x1 і х2 на відрізку [а; b], при якому одна з них стає пробної точкою і на новому відрізку, отриманому після виключення частини вихідного відрізка. Використання таких точок дозволяє на кожній ітерації методу виключення відрізків, крім першої, обмежитися визначенням тільки одного значення f (x), так як інше значення вже знайдено на одній з попередніх ітерацій.

Знайдемо точки x1 і х2, що володіють зазначеним властивістю.

Розглянемо спочатку відрізок [0; 1] і для визначеності припустимо, що при його зменшенні виключається права частина цього відрізка. Нехай х2 = t, тоді симетрично розташована точка х1 = 1-t (рис. 2.7).

Рис. 2.7. Визначення пробних точок у методі золотого перетину

Пробна точка х1 відрізка [0; 1] перейде в пробну точку х2 ? = 1-t нового відрізка [0; т]. Щоб точки х2 = t, і х2 ? = 1-t ділили відрізки [0; 1] та [0; t] в одному і тому ж відношенні, має виконуватися рівність

або

,

звідки знаходимо позитивне значення

...

Таким чином,

х1 = 1-t = ,.

Для довільного відрізка [а; b] вирази для пробних точок приймуть вигляд

;

У таблиці 2 наведено рішення завдання за варіантом.

Опишемо алгоритм методу золотого перетину.

Крок 1. Знайти х1 і х2 за формулами (2.15). Обчислити f (x1) і f (x2). Покласти,

.

Крок 2. Перевірка на закінчення пошуку: якщо en> e, то перейти до кроку 3, інакше - до кроку 4.

Крок 3. Перехід до нового відрізку і новим пробним точкам. Якщо f (x1) ? f (x2) то покласти b = x2, x2 = x1, f (x2) ? f (x1), x1 = bt (ba) і обчислити f (x1), інакше - покласти a = x1, x1 = x2, f (x1) = f (x2), x2 = b + t (ba) і обчислити f (x2). Покласти en = ten і перейти до кроку 2.

Крок 4. Закінчення пошуку: покласти

,.

Результати обчислень на інших ітераціях представлені в таблиці 2.

Таблиця 2 - Метод золотого перетину

 № кроку a b x1 x2 F (x1) F (x2)

 1 2.7 3.9 3.1584 3.4416 -5.7694 1.79829 0.370820393

 2 2.7 3.4416 2.98329 3.1583 -3.1542 -5.7698 0.229179607

 3 2.9833 3.4416 3.158365 3.26652 -5.76957 -4.22659

 4 2.98329 3.266546 3.09148 3.15833 -5.58444 -5.769704

 5 3.09148 3.26652 3.15835 3.199661 -5.76962 -5.43999

 6 3.09148 3.19966 3.13281 3.15834 -5.8039 -5.76967

 7 3.09148 3.15834 3.11702 3.132801 -5.7600 -580399

 8 3.11702 3.15834 3.13281 3.14256 -5.8039 -5.80627

 9 3.13281 3.15834 3.14256 3.14859 -5.8063 -5.7982

 10 3.13281 3.14859 3.1388 3.14856 -5.08076 -5.8063

 11 3.13281 3.14256 3.13653 3.13883 -5.8071 -5.8076

 12 3.13653 3.142557 3.13883 3.140255 -5.80764 -5.80745

 13

| A-b | = 7.893370498E-3 f (x *) = - 5.807126299

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

2 Прямі методи безумовної оптимізації багатовимірної функції

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

Розглянемо методи вирішення мінімізації функції декількох змінних f, які спираються тільки на обчислення значень функції f (x), не використовують обчислення похідних, тобто прямі методи мінімізації. В основному всі методи полягають у наступному. При заданому векторі х визначається допустиме напрямок d. Потім, відправляючись з точки х, функція f мінімізується вздовж напрямку d одним з методів одновимірної мінімізації. Будемо припускати, що точка мінімуму існує. Однак у реальних задачах це припущення може не виконуватися.

Для вивчення прямих методів безумовної оптимізації багатовимірної функції була дана функція:

F (x1, x2) = a * x * y + (b * y + c * x) / x * y > min

a = 5 b = 3.5 c = 2.5

x1 =

x2 =

2.1 Метод покоординатного циклічного спуску

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

базисна точка переноситься в

,

базисна точка переноситься в

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

Для вирішення поставленого завдання вибрано наближення ? = 0,01 ? = 0,15

Таблиця 3 - Метод покоординатного циклічного спуску

 № кроку x1 x2 Z (x1, x2) ?

 0 2.1932884 1.6094917 20.7994602 0.5

 1 1.6932884 1.6094917 17.2469375 0,5

 2 1.1932884 1.6094917 14.0892956 0,5

 3 0.6932884 1.6094917 12.1808992 0,5

 4 0.6832884 1.6094917 12.1743085 0.01

 5 0.6732884 1.6094917 12.1699126 0.01

 6 0.6632884 1.6094917 12.1678107 0.01

 7 0.6632884 1.1094917 11.2095884 0.5

 8 0.6632884 1.0094917 11.1011539 0.1

 9 0.6632884 0.9094917 11.041804 0,1

 10 0.6632884 0.8094917 11.0497295 0,1

 11 -0,183 0,827 -0,2137796 0,15

 13 -0,183 0,677 -0,4082396 0,15

 14 -0,183 0,527 -0,4631996 0,15

 15 -0,108 0,527 -0,5887121 0,075

 16 -0,033 0,527 -0,6860996 0,075

 17 0,042 0,527 -0,7553621 0,075

 18 0,117 0,527 -0,7964996 0,075

 19 0,192 0,527 -0,8095121 0,075

 20 0,192 0,452 -0,8409296 0,075

 21 0,2295 0,452 -0,842513975 0,0375

 22 0,2295 0,4145 -0,8479571 0,0375

? / 2 2.2 Метод Хука - Дживса

Метод Хука і Дживса здійснює два типи пошуку - досліджує пошук та пошук за зразком. Перші дві ітерації процедури показані на малюнку 4.

Малюнок 4 - 1-пошук за зразком; 2- досліджує пошук вздовж координатних осей.

При заданому початковому векторі x1 досліджує пошук по координатним напрямками приводить в точку x2. Подальший пошук за зразком у напрямку x1- x2 приводить в точку y. Потім досліджує пошук, що починається з точки y, дає точку x3. Наступний етап пошуку за зразком вздовж напрямку x3- x2 дає y *. Потім процес повторюється.

Розглянемо варіант методу, який використовує одновимірну мінімізацію уздовж координатних напрямків d1, ..., dn і напрямків пошуку за зразком.

Початковий етап. Вибрати число eps> 0 для зупинки алгоритму. Вибрати початкову точку x1, покласти y1 = x1, k = j = 1 і перейти до основного етапу.

Основний етап.

Крок 1. Вичіліть lymj - оптимальне рішення задачі мінімізації f (yj + lym * dj) за умови lym належить E1. Покласти y [j + 1] = yj + lymj * dj. Якщо j Крок 2. Покласти d = x [k + 1] - xk і знайти lym - оптимальне рішення задачі мінімізації f (x [k + 1] + lym * d) за умови lym належить E1. Покласти y1 = x [k + 1] + lym * d, j = 1, замінити k на k + 1 і перейти до кроку 1. Для вирішення поставленого завдання вибрано наближення ? = 0,02, ? = 0,15

Таблиця 4 - Метод Хука-Дживса

 № кроку x1 x2 Z (x1, x2)

 1 1,147 1,257 5,0057324

 2 1,127 1,237 4,7420444

 3 1,107 1,217 4,4844364

 4 1,087 1,197 4,2329084

 5 1,067 1,177 3,9874604

 6 1,047 1,157 3,7480924

 7 1,027 1,137 3,5148044

 8 1,007 1,117 3,2875964

 9 0,987 1,097 3,0664684

 10 0,967 1,077 2,8514204

 11 0,947 1,057 2,6424524

 12 0,927 1,037 2,4395644

 13 0,907 1,017 2,2427564

 14 0,887 0,997 2,0520284

 15 0,867 0,977 1,8673804

 16 0,847 0,957 1,6888124

 17 0,827 0,937 1,5163244

 18 0,807 0,917 1,3499164

 19 0,787 0,897 1,1895884

 20 0,767 0,877 1,0353404

 21 0,747 0,857 +0,887172399999997

 22 0,727 0,837 +0,745084399999997

 23 0,707 0,817 +0,609076399999996

 24 0,687 +0,796999999999999 +0,479148399999997

 25 0,667 +0,776999999999999 +0,355300399999997

 26 0,647 +0,756999999999999 +0,237532399999997

 27 0,627 +0,736999999999999 +0,125844399999997

 28 0,607 +0,716999999999999 +0,0202363999999973

 29 0,587 +0,696999999999999 -0,0792916000000026

 30 0,567 +0,676999999999999 -0,172739600000002

 31 +0,546999999999999 +0,656999999999999 -0,260107600000002

 32 +0,526999999999999 +0,636999999999999 -0,341395600000002

 33 +0,506999999999999 +0,616999999999999 -0,416603600000002

 34 +0,486999999999999 +0,596999999999999 -0,485731600000002

 35 +0,466999999999999 +0,576999999999999 -0,548779600000002

 36 +0,446999999999999 +0,556999999999999 -0,605747600000002

 37 +0,426999999999999 +0,536999999999999 -0,656635600000002

 38 +0,406999999999999 +0,516999999999999 -0,701443600000001

 38 +0,426999999999999 +0,496999999999999 -0,699011600000001

Т.к в ? околиці отриманої на 38 кроці точці ми не отримуємо поліпшення (зменшення значення) функції, то приймемо x1 = +0,426999999999999 x2 = +0,496999999999999,

Z (x1, x2) = -0,699011600000001.

2.3 Метод правильного симплекса

Правильний симплекс в просторі En називається безліч з n + 1 рівновіддалених один від одного точок (вершин симплекса). У просторі Е2 правильним симплексом є сукупність вершин рівностороннього трикутника, Е3 - правильного тетраедра.

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

Початковий етап. Вибрати параметр точності eps, базову точку x0, ребро a і побудувати початковий симплекс. Обчислити f (x0).

Основний етап.

Крок 1. Обчислити значення f (x) у вершинах симплекса x1, ..., xn.

Крок 2. Упорядкувати вершини симплекса x0, ..., xn так, щоб f (x0) <= f (x1) <= ... <= f (x [n-1]) <= f (xn).

Крок 3. Перевіримо на закінчення пошуку

,

де

Це одне з можливих умов зупину. Його виконанні відповідає або малому ребру a симплекса, або потрапляння точки мінімуму x * всередину симплекса, або того й іншого одночасно.

Якщо ця умова виконана, то обчислення припинити, вважаючи x * = x0. В іншому випадку перейти до кроку 4.

Крок 4. Знайти xс і виконати відображення вершини xn: y = 2 * xс- xn. Якщо f (y)Крок 5. Перейти до нового правильному симплекс з удвічі меншою ребром, вважаючи базової вершиною x0. Решта n вершин симплекса знайти за формулою xi = (xi + x0) / 2, i = 1, ..., n. Перейти до кроку 1.

Для вирішення поставленого завдання вибрано наближення ? = 0,01, ? = 0,3

Таблиця 5 - Метод симплекса

 № кроку Z (x0, y0) Z (x1, y1) Z (x2, y2) ?

 1 5,2755004 7,4172004 5,62549807735416 0,3

 2 5,2755004 5,62549807735416 3,76366398915256 0,3

 3 3,76366398915256 5,2755004 3,5838004 0,3

 4 3,5838004 3,76366398915256 2,35182990095096 0,3

 5 2,35182990095096 3,5838004 2,3421004 0,3

 6 2,3421004 2,35182990095096 1,38999581274936 0,3

 7 1,38999581274936 2,3421004 1,5504004 0,3

 8 +1,38999581274936 1,5504004 +0,878161724547756 0,3

 9 +0,878161724547756 +1,38999581274936 +0,657100646520204 0,3

 10 +0,657100646520204 +0,878161724547756 +0,425132470117002 0,3

 11 +0,425132470117002 +0,657100646520204 +0,143414901312537 0,3

 12 +0,143414901312537 +0,425132470117002 +0,191312636707734 0,3

 13 +0,143414901312537 +0,191312636707734 -0,15106142287364 0,3

 14 -0,15106142287364 +0,143414901312537 -0,0288250700672363 0,3

 15 -0,15106142287364 -0,0288250700672363 -0,383957885030324 0,3

 16 -0,383957885030324 -0,15106142287364 -0,226328326038328 0,3

 17 -0,383957885030324 -0,226328326038328 -0,519881278971922 0,3

 18 -0,519881278971922 -0,383957885030324 -0,507376749762318 0,3

 19 -0,519881278971922 -0,507376749762318 -0,703956634480828 0,3

 20 -0,703956634480828 -0,521318017069623 -0,507376749762318 0,3

 21 -0,703956634480828 -0,521318017069623 -0,778554392565042 0,3

 22 -0,778554392565042 -0,703956634480828 -0,681327098177849 0,3

 23 -0,778554392565042 -0,816581347038974 -0,681327098177849 0,3

 24 -0,816581347038974 -0,778554392565042 -0,743674553224567 0,3

 25 -0,816581347038974 -0,842357998475409 -0,743674553224567 0,3

 26 -0,845848412956476 -0,846177360374865 -0,838238020383463 0,075

 27 -0,846177360374865 -0,845848412956476 -0,843154372435278 0,075

 28 -0,846616455690446 -0,845848412956476 -0,843154372435278 0,075

 29 -0,848017017695877 -0,847087728053341 -0,846597987664592 0,0375

 30 -0,848017017695877 -0,847980516275042 -0,847811621576176 0,01875

 31 -0,848017017695877 -0,848085062414109 -0,847811621576176 0,01875

Т.к подальше зменшення ? неможливо (? / 2 2.4 Метод деформованого симплекса

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

z1 = xc - a (xc - xn), 0z2 = xc + a (xc - xn), 0z3 = xc + b (xc - xn), b наближено дорівнює 1;

z4 = xc + g (xc - xn), g <1.

Геометрична ілюстрація цих процедур для двовимірного простору наведена на малюнку 7.

Нові симплекси отримані в результаті процедури стиснення (a, b); відбиття (c); розтягування (d)

Так як величина a належить інтервалу (0; 1), то вибір точок z1 і z2 відповідає стисненню симплекса; b наближено дорівнює 1, тому вибір точки z3 відповідає відображенню, а g> 1 і вибір точки z4 призводить до розтягування симплекса.

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

Алгоритм методу пошуку точки мінімуму функції по деформованість симплекс

Початковий етап. Вибрати параметр точності eps, параметри a, b і g, базову точку x0, параметр a і побудувати початковий симплекс. Обчислити значення функції f (x0).

Основний етап. Крок 1. Обчислити значення функції в вершинах симплекса x1, ..., xn.

Крок 2. Упорядкувати вершини симплекса x0, ..., xn так, щоб f (x0) <= f (x1) <= ... <= f (x [n-1]) <= f (xn).

Крок 3. Перевірити умова (1 / n) Sum [f (xi) -f (x0)] ^ 2 Це одне з можливих умов зупину. При його виконанні "дисперсія" значень f (x) у вершинах симплекса стає менше e2, що, як правило, відповідає або малому ребру a симплекса, або потрапляння точки мінімуму x * всередину симплекса, або того й іншого одновременно.Еслі ця умова виконана, то обчислення припинити, вважаючи x * = x0. В іншому випадку перейти до кроку 4.

Крок 4. Знайти xс і пробні точки zk, k = 1, ..., 4 за формулами (2). Знайти f (z *) = minf (zk). Якщо f (z *)Крок 5. Зменшити симплекс, вважаючи xi = (xi + x0) / 2, i = 1, ..., n перейти до кроку 1.

На практиці добре зарекомендував себе наступний набір параметрів a = 1/2, b = 1, g = 2, тому він і був використаний в програмі.

Таблиця 5 - Метод деформованого симплекса

 № кроку Z (x0, y0) Z (x1, y1) Z (x2, y2)

 1 5,25127562399313 5,35273629457997 4,72465845389651

 2 4,47048359472409 5,52371793491734 4,32427361628427

 3 4,26941489330181 4,56183485018145 2,53610076197985

 4 2,53610076197985 4,26941489330181 2,54614140634749

 5 2,60406550474582 +2,62414679348111 +0,650136727095332

 6 +0,873172338270091 4,78102989357106 -0,460995375774572

 7 -0,460995375774572 -0,183165198484471 -0,647802169588968

 8 -0,647802169588968 -0,460995375774572 -0,752046189909185

 9 -0,752046189909185 -0,647802169588968 -0,743774186218157

 10 -0,824978188986428 -0,820842187140914 -0,807869388437316

 11 -0,848148148136976 -0,848148148106495 -0,848148148103467

 12 -0,848148148146818 -0,848148148131578 -0,848148148135116

 13 -0,848148148146818 -0,848148148135116 -0,848148148139001

 14 -0,848148148136976 -0,848148148106495 -0,848148148103467

 15 -0,848148148148147 -0,848148148148145 -0,848148148148146

 16 -0,848148148148148 -0,848148148148147 -0,848148148148147

T.к.

то приймемо x = +0,237037034153931 і y = +0,407407409218273 Z (x, y) = -0,848148148148148

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

3. Умовна оптимізація

Завдання умовної оптимізації в загальному випадку записується у відомому вигляді:

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

На малюнку 12 представлена фігура, об'єм, якій необхідно максимізувати при заданій площі поверхні

Рисунок 12 - Фігура для максимізації обсягу при заданій площі поверхні

Знайдемо повну площу поверхні даної фігури (без верхньої поверхні):

,

знайдемо обсяг фігури:

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

Це завдання можна вирішити двома методами:

Метод перетворення цільової функції,

метод штрафних функцій.

3.1 Метод перетворення цільової функції

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

V = 4/3 - a2 - h2 + 7/3 - h1 - a2 > max (1)

S = 6 - a - h1 + 4 - h2 - a (2)

Висловимо a з (2) і підставимо в (1), отримаємо:

V = s2 - (4 - h2 + 7 - h1) / 3 - (6 - h1 + 4 - h2) 2

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

Візьмемо, наприклад, метод правильного симплекса, і задамо початкові умови: а = 1м, h1 = 3м, h2 = 4м, s = 34м. Для методу симплекса виберемо точність ? = 0,001.

Т.е максимальний обсяг V = +12,7151461307724, при заданій площі виходить при h1 = 2,946875, і h2 = +3,83229490168751

3.2 Метод штрафних функцій

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

f (x) -> min;

gi (x) 0, i1, ..., k;

hj (x) 0, j1, ..., m;

axb.

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

F (x, a) f (x) + rS (x)

Тут f (x) - цільова функція задачі оптимізації; S (x) - спеціальним чином обрана функція штрафу, де r- множник, значення якого можна змінювати в процесі оптимізації .. Крапку безумовного мінімуму функції F (x, a) будемо позначати через х (а).

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

3.2 Методи штрафних функцій

Ці методи застосовуються для вирішення задач нелінійного програмування з обмеженнями-нерівностями.

У розглянутих методах функції Ф (x, а) підбирають такими, щоб їх значення необмежено зростали при наближенні до кордону допустимої області G (Малюнок 14). Іншими словами, наближення до кордону "штрафується" різким збільшенням значення функції F (x, а). На кордоні G побудований "бар'єр", що перешкоджає порушенню обмеження в процесі безумовної мінімізації F (x, a). Пошук мінімуму допоміжної функції F (x, а) необхідно починати з внутрішньої точки області G.

Таким чином, внутрішня штрафна функція Ф (х, а) може бути визначена таким чином:

Тут dG -граніца області G.

Малюнок 14 - Внутрішня штрафна функція

Методи зовнішніх штрафних функцій

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

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

Малюнок - 15 Зовнішня штрафна функція

Зовнішня штрафна функція Ф (х, а) в загальному випадку може бути визначена таким чином:

Для даного курсового проекту штрафна функція для обсягу даної фігури має вигляд:

,

де- параметр штрафу, С - повна площа поверхні, задана спочатку, V (a, h1, h2) = 4/3 - a2 - h2 + 7/3 - h1 - a2, S (a, h1, h2) = 6 - a - h1 + 4 - h2 - a.

Задача була вирішена методом правильного тривимірного симплекса.

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

4. Симплекс таблиці

Для його застосування необхідно, щоб знаки в обмеженнях були виду «менше або дорівнює», а компоненти вектора b - позитивні.

Алгоритм рішення зводиться до наступного:

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

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

Формується симплекс-таблиця.

Розраховуються симплекс-різниці.

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

При необхідності виконуються ітерації.

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

Дана функція виду:

f (x) = 4x1 + 2x2

Підберемо k геометричним способом вирішення так, щоб область допустимих значень була п'ятикутником. k = 7

Малюнок - 16 Область допустимих значень

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

4у1 + 2у2 + 0у3 + 0у4 + 0у5

= (0; 0; 8; 12; 7) - початкові допустимі базисні рішення

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

 Ітерація Базисна змінна Значення у1 у2 у3 у4 у5

 0 у3 8 1 2 1 0 0

 У4 12 квітня 1 0 1 0

 У5 2 липня 1 0 0 1

 -f 0 4 2 0 0 0

Вводимо в базис в1, а виводимо з базису у4.

 Ітерація Базисна змінна Значення у1 у2 у3 у4 у5

 1 У3 5 0 1,75 1 -0,25 0

 У1 3 1 0,25 0 0,25 0

 У5 1 0 0,5 0 -0,5 1

 -f -12 0 1 0 -1 0

Вводимо в базис у2, а виводимо з базису у5.

 Ітерація Базисна змінна Значення у1 у2 у3 у4 у5

 2 У3 1,5 0 0 1 -2 -3,5

 У1 2,5 1 0 0 0,5 -0,5

 У2 2 0 1 0 -1 2

 -f -14 0 0 0 0 -2

Тому f <0, то зупиняємося на другий ітерації.

Виходячи з графіка ОДЗ, можна визначити, що оптимальним рішенням є відрізок прямої, що входить до

ОДЗ, перевіримо: 2,5 * 2 + 2 = 7.

x1 = 2,5, x2 = 2 f (x) = 14.

Висновок

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

Список використаної літератури

1. А.Г.Тріфонов. Постановка задачі оптимізації і чисельні методи її вирішення;

2. Б. Банді. Методи оптимізації. Вступний курс., 1988;

3. Мендікенов К.К. Лекції

Додаток А

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

namespace lab1

{

public partial class Form1: Form

{

class global

{

private global () {}

public static double a = 0.64;

public static double b = 1.77;

public static double e = 0.0001;

public static double al = 0.00001;

public static double x = 0;

public static double y = 0;

public static int iter = 0;

}

public Form1 ()

{InitializeComponent (); }

private void textBox1_TextChanged (object sender, EventArgs e)

{Global.e = Convert.ToDouble (textBox1.Text); }

private void textBox2_TextChanged (object sender, EventArgs e)

{Global.al = Convert.ToDouble (textBox2.Text); }

public double F (double x)

{Return (Math.Pow ((2.5 - x), 2) + 3.1 * x); }

public double Z (double x, double y)

{Return (2.5 * Math.Pow (x, 2) + 2 * x * y + 3.1 * Math.Pow (y, 2) -2 * x-3 * y); }

public double Dixotom ()

{

global.iter = 1;

global.a = Convert.ToDouble (textBox4.Text);

global.b = Convert.ToDouble (textBox3.Text);

richTextBox1.Text = richTextBox1.Text + "a =" + Convert.ToString (global.a) + "; b =" + Convert.ToString (global.b) + (char) 13;

while (true)

{

double x1 = (global.a + global.b) /2-global.al;

double x2 = (global.a + global.b) / 2 + global.al;

if (F (x1) richTextBox1.Text = richTextBox1.Text + Convert.ToString (global.iter) + ") x1 =" + Convert.ToString (x1) + "; x2 =" + Convert.ToString (x2) + "; f (x1) = "+ Convert.ToString (F (x1)) +"; f (x2) = "+ Convert.ToString (F (x2)) +"; a = "+ Convert.ToString (global.a) +"; b = "+ Convert.ToString (global.b) + (char) 13;

global.iter ++;

if (Math.Abs (global.b - global.a) } Return (global.a + global.b) / 2;

}

public double Zolot ()

{Global.iter = 1;

global.a = Convert.ToDouble (textBox4.Text);

global.b = Convert.ToDouble (textBox3.Text);

richTextBox1.Text = richTextBox1.Text + "a =" + Convert.ToString (global.a) + "; b =" + Convert.ToString (global.b) + (char) 13;

double x2 = global.a + 0.618 * (global.b - global.a);

double x1 = global.a + (1-0.618) * (global.b - global.a);

while (true)

{

if (Math.Abs (global.b - global.a) richTextBox1.Text = richTextBox1.Text + Convert.ToString (global.iter) + ") a =" + Convert.ToString (global.a) + "; b =" + Convert.ToString (global.b) + "; x1 = "+ Convert.ToString (x1) +"; x2 = "+ Convert.ToString (x2) +"; f (x1) = "+ Convert.ToString (F (x1)) +"; f (x2) = " + Convert.ToString (F (x2)) + (char) 13;

if (F (x2)> F (x1))

{Global.b = x2; x2 = x1; x1 = global.a + 0.372 * (global.b - global.a); }

else {global.a = x1; x1 = x2; x2 = global.a + 0.618 * (global.b - global.a); }

global.iter ++;

}

return (global.a + global.b) / 2;

}

private void button1_Click (object sender, EventArgs e)

{RichTextBox1.Text = "";

global.al = Convert.ToDouble (textBox2.Text);

global.e = Convert.ToDouble (textBox1.Text);

if (radioButton1.Checked) global.x = Dixotom ();

if (radioButton2.Checked) global.x = Zolot ();

label2.Text = "Мінімум: x * =" + Convert.ToString (global.x) + "; y (x *) =" + Convert.ToString (F (global.x)) + ", число ітерацій:" + Convert.ToString (global.iter-1);

}

public void Spusk (double x, double y)

{

while (true) // йдемо вправо

{X = x + global.al; if (Z (x, y)> Z (x - global.al, y)) break; global.iter ++;

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") x =" + Convert.ToString (x) + "; y =" + Convert.ToString (y) + "; z (x, y) = "+ Convert.ToString (Z (x, y)) +"; al = "+ Convert.ToString (global.al) + (char) 13;

x = x - global.al; // повертаємося на невдалий крок

while (true) // йдемо вліво

{X = x - global.al; if (Z (x, y)> Z (x + global.al, y)) break; global.iter ++;

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") x =" + Convert.ToString (x) + "; y =" + Convert.ToString (y) + "; z (x, y) = "+ Convert.ToString (Z (x, y)) +"; al = "+ Convert.ToString (global.al) + (char) 13; }

x = x + global.al; // повертаємося на невдалий крок

global.x = x; global.y = y;

SpuskV (x, y);

}

public void SpuskV (double x, double y)

{

while (true) // йдемо вгору

{Y = y + global.al; if (Z (x, y)> Z (x, y - global.al)) break; global.iter ++;

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") x =" + Convert.ToString (x) + "; y =" + Convert.ToString (y) + "; z (x, y) = "+ Convert.ToString (Z (x, y)) +"; al = "+ Convert.ToString (global.al) + (char) 13; }

y = y - global.al; // повертаємося на невдалий крок

while (true) // йдемо вниз

{Y = y - global.al; if (Z (x, y)> Z (x, y + global.al)) break; global.iter ++;

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") x =" + Convert.ToString (x) + "; y =" + Convert.ToString (y) + "; z (x, y) = "+ Convert.ToString (Z (x, y)) +"; al = "+ Convert.ToString (global.al) + (char) 13; }

y = y + global.al; // повертаємося на невдалий крок

global.x = x; global.y = y;

if (global.al/2> global.e) {global.al = global.al / 2; Spusk (x, y); }

}

public void Hyg (double x, double y)

{While (true)

{Int min = Vibor (x, y);

if (min == 1) {x = x + 2 * global.e; y = y + 2 * global.e; if (Z (x - 2 * global.e, y - 2 * global.e) if (min == 2) {x = x - 2 * global.e; y = y + 2 * global.e; if (Z (x + 2 * global.e, y - 2 * global.e) if (min == 3) {x = x - 2 * global.e; y = y - 2 * global.e; if (Z (x + 2 * global.e, y + 2 * global.e) if (min == 4) {x = x + 2 * global.e; y = y - 2 * global.e; if (Z (x - 2 * global.e, y + 2 * global.e) global.iter ++;

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") x =" + Convert.ToString (x) + "; y =" + Convert.ToString (y) + "; z (x, y) = "+ Convert.ToString (Z (x, y)) + (char) 13; }

global.x = x; global.y = y;

}

public int Vibor (double x, double y)

{Int min = 0;

if (Z (x + global.e, y + global.e) if (Z (x + global.e, y - global.e) if (Z (x - global.e, y - global.e) if (Z (x - global.e, y + global.e) return min; }

public void Sym (double x, double y)

{Double x0 = x; double y0 = y; double x1 = x0 + global.al; double y1 = y0;

double x2 = x0 + (global.al) / 2; double y2 = y0 + global.al * Math.Sin (60);

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") z (x0, y0) =" + Convert.ToString (Z (x0, y0)) + "z (x1, y1) =" + Convert.ToString (Z (x1, y1)) + "z (x2, y2) =" + Convert.ToString (Z (x2, y2)) + "al =" + Convert.ToString (global.al) + (char) 13;

while (true)

{// Пошук найменшого

double mx0 = x0; double my0 = y0; double mx1 = x1; double my1 = y1; double mx2 = x2; double my2 = y2;

double z1 = Z (mx0, my0); double z2 = Z (mx1, my1); double z3 = Z (mx2, my2);

if ((z1 z1)) {x0 = mx0; x1 = mx1; x2 = mx2; y0 = my0; y1 = my1; y2 = my2; }

if ((z1 z3) && (z3> z1)) {x0 = mx0; x1 = mx2; x2 = mx1; y0 = my0; y1 = my2; y2 = my1; }

if ((z1> z2) && (z2 if ((z1> z2) && (z2 z1)) {x0 = mx1; x1 = mx0; x2 = mx2; y0 = my1; y1 = my0; y2 = my2; }

if ((z1 z3) && (z3 if ((z1> z2) && (z2> z3) && (z3 // Перевірка на вихід

if (global.al <= global.e) break;

while (true)

{// Відображення відносно 3

double kx = (x0 + x1) -x2; double ky = (y0 + y1) - y2;

if (Z (x2, y2)> Z (kx, ky)) {x2 = kx; y2 = ky; global.iter ++; break; }

// Відображення відносно 2

kx = (x0 + x2) - x1; ky = (y0 + y2) - y1;

if (Z (x1, y1)> Z (kx, ky)) {x1 = kx; y1 = ky; global.iter ++; break; }

// Відображення відносно 1

kx = (x1 + x2) - x0; ky = (y1 + y2) - y0;

if (Z (x0, y0)> Z (kx, ky)) {x0 = kx; y0 = ky; global.iter ++; break; }

// Зменшуємо трикутник

global.al = global.al / 2;

x1 = (x0 + x1) / 2; y1 = (y0 + y1) / 2;

x2 = (x0 + x2) / 2; y2 = (y0 + y2) / 2;

}

richTextBox2.Text = richTextBox2.Text + Convert.ToString (global.iter) + ") x0 =" + Convert.ToString (x0) + "x1 =" + Convert.ToString (x1) + "x2 =" + Convert.ToString (x2) + "; y0 =" + Convert.ToString (y0) + "y1 =" + Convert.ToString (y1) + "y2 =" + Convert.ToString (y2) + "z (x0, y0) =" + Convert.ToString (Z (x0, y0)) + "z (x1, y1) =" + Convert.ToString (Z (x1, y1)) + "z (x2, y2) =" + Convert.ToString (Z (x2, y2)) + "al =" + Convert.ToString (global.al) + (char) 13; }

global.x = x0; global.y = y0; }

private void button2_Click (object sender, EventArgs e)

{Global.iter = 0;

global.al = Convert.ToDouble (textBox7.Text);

global.e = Convert.ToDouble (textBox8.Text);

if (radioButton4.Checked) {Spusk (Convert.ToDouble (textBox6.Text), Convert.ToDouble (textBox5.Text)); }

if (radioButton3.Checked)

Hyg (Convert.ToDouble (textBox6.Text), Convert.ToDouble (textBox5.Text));

if (radioButton5.Checked) Sym (Convert.ToDouble (textBox6.Text), Convert.ToDouble (textBox5.Text));

label9.Text = "Мінімум: (" + Convert.ToString (global.x) + ";" + Convert.ToString (global.y) + "f (x, y) =" + Convert.ToString (Z (global. x, global.y)) + "), число ітерацій:" + Convert.ToString (global.iter); }}}

Додаток Б

procedure TForm1.Button1Click (Sender: TObject);

begin

a: = false;

l: = 0.05;

al: = 1; e: = 0.01; gm: = 2; bt: = 0.5;

x: = 1.16166; y: = 1.15185;

iter: = 0;

xl: = x; yl: = y; xg: = xl + l; yg: = yl;

xh: = xl + l / 2; yh: = yl + l * Sin (60);

Sym (x, y);

ZZ (x, y); // Вважаємо значення функції в знайденій точці

end;

procedure TForm1.Sym (x, y: real);

label

ext, B;

begin

// Пошук найменшого

B: mx0: = xl; my0: = yl; mx1: = xg; my1: = yg; mx2: = xh; my2: = yh;

ZZ (mx0, my0); z1: = z; ZZ (mx1, my1); z2: = z; ZZ (mx2, my2); z3: = z;

if ((z1 z1)) then begin xl: = mx0; xg: = mx1; xh: = mx2; yl: = my0; yg: = my1; yh: = my2; end;

if ((z1 z3) and (z3> z1)) then begin xl: = mx0; xg: = mx2; xh: = mx1; yl: = my0; yg: = my2; yh: = my1; end;

if ((z1> z2) and (z2 if ((z1> z2) and (z2 z1)) then begin xl: = mx1; xg: = mx0; xh: = mx2; yl: = my1; yg: = my0; yh: = my2; end;

if ((z1 z3) and (z3 if ((z1> z2) and (z2> z3) and (z3 Richedit1.Lines.Add (IntToStr (iter));

Richedit1.Lines.Add (FloatToStr (xl) + '' + FloatToStr (yl) + '' + FloatToStr (zl));

Richedit1.Lines.Add (FloatToStr (xg) + '' + FloatToStr (yg) + '' + FloatToStr (zg));

Richedit1.Lines.Add (FloatToStr (xh) + '' + FloatToStr (yh) + '' + FloatToStr (zh));

Richedit1.Lines.Add ('');

x0: = (xl + xg) / 2; y0: = (yl + yg) / 2;

xr: = (1 + al) * x0-al * xh; yr: = (1 + al) * y0-al * yh;

ZZ (xl, yl); zl: = z; ZZ (xg, yg); zg: = Z; ZZ (xh, yh); zh: = z; ZZ (xr, yr); zr: = z;

if zr{1} begin

// Розтягнення

xe: = gm * xr + (1-gm) * x0; ye: = gm * yr + (1-gm) * y0; ZZ (xe, ye); ze: = z;

if ze{2} begin

xh: = xe; yh: = ye; ZZ (xh, yh); zh: = z;

xl: = gm * xl + (1-gm) * x0; yl: = gm * yl + (1-gm) * y0; ZZ (xl, yl); zl: = z;

xg: = gm * xg + (1-gm) * x0; yg: = gm * yg + (1-gm) * y0; ZZ (xg, yg); zg: = z;

Shod (xl, xg, xh, yl, yg, yh);

if a = true then goto ext else begin inc (iter); goto B; end;

{2} end

else

{3} begin

xh: = xr; yh: = yr; ZZ (xh, yh); zh: = z;

Shod (xl, xg, xh, yl, yg, yh);

if a = true then goto ext else begin inc (iter); goto B; end;

{3} end;

{1} end;

if ((zr> zl) and (zr <= zg)) then

begin

xh: = xr; yh: = yr; ZZ (xh, yh); zh: = z;

Shod (xl, xg, xh, yl, yg, yh);

if a = true then goto ext else begin inc (iter); goto B; end;

end;

if ((zr> zl) and (zr> zg)) then

{4E} begin

if zr// Стиск

xc: = bt * xh + (1-bt) * x0; yc: = bt * yh + (1-bt) * y0; ZZ (xc, yc); zc: = z;

if zc{5Ж} begin

xh: = xc; yh: = yc; ZZ (xh, yh); zh: = z;

xl: = bt * xl + (1-bt) * x0; yl: = bt * yl + (1-bt) * y0; ZZ (xl, yl); zl: = z;

xg: = bt * xg + (1-bt) * x0; yg: = bt * yg + (1-bt) * y0; ZZ (xg, yg); zg: = z;

Shod (xl, xg, xh, yl, yg, yh);

if a = true then goto ext else begin inc (iter); goto B; end;

{5} end

{6З} else begin

// Зменшення

l: = l / 2;

xh: = (xl + xh) / 2; xh: = (xl + xh) / 2; ZZ (xh, yh); zh: = z;

xg: = (xl + xg) / 2; yg: = (yl + yg) / 2; ZZ (xg, yg); zg: = z;

{6} end;

Shod (xl, xg, xh, yl, yg, yh);

if a = true then goto ext else begin inc (iter); goto B; end;

{4} end;

ext: Richedit1.Lines.Add (FloatToStr (xl));

Richedit1.Lines.Add (FloatToStr (yl));

Richedit1.Lines.Add (FloatToStr (zl));

Richedit1.Lines.Add (IntToStr (iter));

end;

procedure TForm1.ZZ (x, y: real);

begin

z: = 2.5 * x * x + 2 * x * y + 3.1 * y * y -2 * x-3 * y;

end;

procedure TForm1.Shod (xl, xg, xh, yl, yg, yh: real);

var

sigma: real;

begin

ZZ (xl, yl); zl: = z; ZZ (xg, yg); zg: = Z; ZZ (xh, yh); zh: = z;

sigma:=sqrt((sqr(zl-((zl+zg+zh)/2+1))+sqr(zl-((zl+zg+zh)/2+1))+sqr(zg-((zl+zg+zh)/2+1))+sqr(zh-((zl+zg+zh)/2+1)))/3); if sigmaДодаток В

unit Unit1;

type

procedure Button1Click (Sender: TObject);

procedure ZZ (x, y, z: real);

procedure Sym (x, y, z: real);

end;

var

X, y, z: real;

z_: real; // Значення функції

iter: integer; // Число ітерацій

s, gm, x0, x1, x2, x3: real; // Координати точок

y0, y1, y2, y3: real;

z0, z1, z2, z3: real; // Трикутника

al, e: real; // Довжина сторони сімплікса (трикутника)

kx, ky, kz, zz1, zz2: real; // Координати точки k

a, b: boolean; // Для циклу

implementation

procedure TForm1.Sym (x, y, z: real);

label

l;

var

a: array [1..4,1..4] of real; // z () xyz; 1234

k, i: integer;

buf: real;

changed: boolean;

{1} begin

x0: = x; y0: = y; z0: = z;

x1: = x0 + al; y1: = y0; z1: = z;

x2: = x0 + al / 2; y2: = y0 + al * Sin (60); z2: = z;

x3: = x0 + al / 2; y3: = y0; z3: = z0 + al * Sin (60);

while (true) do

// For i: = 1 to 100 do

{2} begin

ZZ (x0, y0, z0); a [1,1]: = z_; a [2,1]: = x0; a [3,1]: = y0; a [4,1]: = z0;

ZZ (x1, y1, z1); a [1,2]: = z_; a [2,2]: = x1; a [3,2]: = y1; a [4,2]: = z1;

ZZ (x2, y2, z2); a [1,3]: = z_; a [2,3]: = x2; a [3,3]: = y2; a [4,3]: = z2;

ZZ (x3, y3, z3); a [1,4]: = z_; a [2,4]: = x3; a [3,4]: = y3; a [4,4]: = z3;

// Сортування

repeat

changed: = FALSE;

for k: = 1 to 3 do

if a [1, k]> a [1, k + 1] then

begin

buf: = a [1, k]; a [1, k]: = a [1, k + 1]; a [1, k + 1]: = buf;

buf: = a [2, k]; a [2, k]: = a [2, k + 1]; a [2, k + 1]: = buf;

buf: = a [3, k]; a [3, k]: = a [3, k + 1]; a [3, k + 1]: = buf;

buf: = a [4, k]; a [4, k]: = a [4, k + 1]; a [4, k + 1]: = buf;

changed: = TRUE;

end;

until not changed;

x0: = a [2,1]; y0: = a [3,1]; z0: = a [4,1];

x1: = a [2,2]; y1: = a [3,2]; z1: = a [4,2];

x2: = a [2,3]; y2: = a [3,3]; z2: = a [4,3];

x3: = a [2,4]; y3: = a [3,4]; z3: = a [4,4];

ZZ (x3, y3, z3);

// Перевірка на вихід

if (al <= e) or (z_ <0) then break;

while (true) do

{3} begin

// Відображення відносно 0

kx: = 2/3 * (x2 + x1 + x3) -x0; ky: = 2/3 * (y2 + y1 + y3) -y0; kz: = 2/3 * (z2 + z1 + z3) -z0;

ZZ (x0, y0, z0); zz1: = z_; ZZ (kx, ky, kz); zz2: = z_;

if (z_ <0) then goto l;

if (zz1 0) and (ky> 0) and (kz> 0) and ((6 * kx * ky + 4 * kz * kx) <= s) then begin x0: = kx; y0: = ky; z0: = kz; inc (iter); break; end;

// Відображення відносно 1

kx: = 2/3 * (x2 + x0 + x3) -x1; ky: = 2/3 * (y2 + y0 + y3) -y1; kz: = 2/3 * (z2 + z0 + z3) -z1;

ZZ (x1, y1, z1); zz1: = z_; ZZ (kx, ky, kz); zz2: = z_; if (z_ <0) then goto l;

if (zz1 0) and (ky> 0) and (kz> 0) and ((6 * kx * ky + 4 * kz * kx) <= s) then begin x1: = kx; y1: = ky; z1: = kz; inc (iter); break; end;

// Відображення відносно 2

kx: = 2/3 * (x0 + x1 + x3) -x2; ky: = 2/3 * (y0 + y1 + y3) -y2; kz: = 2/3 * (z0 + z1 + z3) -z2;

ZZ (x2, y2, z2); zz1: = z_; ZZ (kx, ky, kz); zz2: = z_; if (z_ <0) then goto l;

if (zz1 0) and (ky> 0) and (kz> 0) and ((6 * kx * ky + 4 * kz * kx) <= s) then begin x2: = kx; y2: = ky; z2: = kz; inc (iter); break; end;

// Відображення відносно 3

kx: = 2/3 * (x2 + x1 + x0) -x3; ky: = 2/3 * (y2 + y1 + y0) -y3; kz: = 2/3 * (z2 + z1 + z0) -z3;

ZZ (x3, y3, z3); zz1: = z_; ZZ (kx, ky, kz); zz2: = z_; if (z_ <0) then goto l;

if (zz1 0) and (ky> 0) and (kz> 0) and ((6 * kx * ky + 4 * kz * kx) <= s) then begin x3: = kx; y3: = ky; z3: = kz; inc (iter); break; end;

// Зменшуємо трикутник

al: = al / 2;

x1: = x0 + al; y1: = y0; z1: = z0;

x2: = x0 + al / 2; y2: = y0 + al * Sin (60); z2: = z0;

x3: = x0 + al / 2; y3: = y0; z3: = z0 + al * Sin (60); break; inc (iter);

{3} end;

{2} end;

l: x: = x3; y: = y3;

{1} end;

procedure TForm1.ZZ (x, y, z: real);

begin z _: = (4/3 * x * x * z + 7/3 * y * x * x) -gm * sqr (s- (6 * x * y + 4 * z * x)); end;

procedure TForm1.Button1Click (Sender: TObject);

begin

RichEdit1.Text: = ''; iter: = 0;

gm: = StrToFloat (Edit1.Text); s: = StrToFloat (Edit2.Text); al: = 0.05; e: = 0.01;

x: = StrToFloat (Edit3.Text); y: = StrToFloat (Edit4.Text); z: = StrToFloat (Edit5.Text);

Sym (x, y, z); ZZ (x3, y3, z3); // Вважаємо значення функції в знайденій точці

RichEdit1.Text: = RichEdit1.Text + 'Кількість ітерацій' + IntToStr (iter) + # 13;

RichEdit1.Text: = RichEdit1.Text + 'x3 =' + FloatToStr (x1) + '; y3 = '+ FloatToStr (y1) +' z3 = '+ FloatToStr (z1) + # 13;

ZZ (x3, y3, z3); RichEdit1.Text: = RichEdit1.Text + 'f (x, y, z) =' + FloatToStr (z_) + '(' + FloatToStr (6 * x3 * y3 + 4 * z3 * x) + ')' + # 13; end; end.
Секрети дискус
Той, хто намагався розводити дискус, знає, що справа це непроста. І далеко не кожен може похвалитися тим, що отримав від цих чудових риб потомство. Труднощі полягають в особливостях їх біології та в багатьох інших тонкощах, які треба знати. Єдиного керівництва з розведення дискус немає і

Оцінка рівня забруднення автотранспортом повітря оксидом вуглецю м. Черкаси
Міністерство освіти і науки України Черкаський державний технологічний університет Будівельний факультет Кафедра екології КУРСОВА РОБОТА З дисципліни "Загальна екологія " Тема: "Оцінка рівня забруднення автотранспортом повітря оксидом вуглецю м. Черкаси" Керівник

Оцінка економічних збитків від різних видів порушень земельних та водних ресурсів
Міністерство освіти і науки України Національний університет водного господарства та природокористування Кафедра фінансів і економіки природокористування Контрольна робота з дисципліни "Економіка природокористування" Рівне - 2008 Зміст І. Теоретична частина 1. Оцінка економічних

Меланотении
"Хто повинен зробити вибір - той мучиться" - свідчить старе німецьке прислів'я. Не раз доводилося переконуватися в її справедливості. Виявившись одного разу безробітним, я повинен був зробити вибір: залишати домашнє аквариумное господарство або відмовитися від нього. До кінця порвати

Оцінка еколого-економічного збитку навколишньому природному середовищу при проектуванні напірного нафтопроводу від УПН Галяновского родовища на ЦПС Кам'яне ВАТ "Гіпротюменнефтегаз"
МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Югорськая ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНСТИТУТ ЕКОНОМІКИ І ФІНАНСІВ КАФЕДРА ЕКОНОМІКИ ТА УПРАВЛІННЯ НА ПІДПРИЄМСТВІ Курсова робота на тему: «Оцінка еколого-економічного збитку навколишньому природному середовищу при проектуванні напірного нафтопроводу

Оцінка від збитку стихійних лих
Оцінка збитку від стихійних природних явищ в Жалал-Абадской області Період вивчення і дослідження взятий з 1990 року по 2008 рік. При оцінці збитку розрізнюють два вигляду збитку: економічний і соціально-екологічний. Економічний збиток, що наноситься земельним ресурсам, являє собою вибуття

Хромосомні хвороби
Це група хвороб, в основі розвитку яких лежать порушення числа чи структури хромосом, що у гаметах батьків або на ранніх стадіях дроблення зиготи (заплідненої яйцеклітини). Історія вивчення ХБ бере початок з кинических досліджень, що проводилися задовго до опису хромосом і відкриття хромосомних

© 2014-2022  8ref.com - українські реферати