Студопедия

КАТЕГОРИИ:


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

Моделювання процесу в шару каталiзатора. 3 страница

Читайте также:
  1. A Введение 1 страница
  2. A Введение 2 страница
  3. A) катаральді ангина 1 страница
  4. A) катаральді ангина 2 страница
  5. A) катаральді ангина 3 страница
  6. A) катаральді ангина 4 страница
  7. A) катаральді ангина 5 страница
  8. A) Объем 1 страница
  9. A) Объем 2 страница
  10. A) элементтері болса 1 страница
  11. A) элементтері болса 10 страница
  12. A) элементтері болса 11 страница



а) при наявності обмежень пошук оптимуму може "застрягати" в будь-якій точці межі (рис. 5.19).

б) при наявності "байраків", напрями яких не співпадають з осями (рис. 5.20).

 

Рис.5.19 Рис.5.20

5.6.4. Метод градієнту

 

У даному засобі використовується градієнт цільової функції.

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

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

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

Алгоритм градiєнтного пошуку може бути записаний наступним образом :

 

 

(5.43)

 

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

Можна використовувати інший алгоритм градiєнтного засобу у виді:

Uk+1j=Ukj - h0 dR(Uk)/dUj(5.44)

 

В цьому випадку величина кроку ΔUKj= -h0 dR(UK)/dUj при постійному значенні параметра hзмінюється автоматично відповідно до зміною абсолютної величини градієнту. Алгоритм (5.44) володіє отим достоїнством , що при наближенні до оптимуму величина кроку ΔUкj автоматично зменшується. Взагалі, задача вибору стратегії зміни величини кроку у градієнтнім пошуку більш важна, чим в засобі релаксації, тому що після кожного кроку тут необхідно знаходити похідні цільової функції, розрахунок яких пов'язаний з обчисленням n значень цільової функції. Дрібний крок вимагає великого обсягу вичислений, при великому кроці - можливо " рисканiє " в районі оптимуму.

Момент закінчення пошуку визначається по заздалегідь заданим умовам. Один з можливих варіантів - виконання нерівняння (5. 40). Інший варіант після кожної серії з заданим числом кроків S запам’ятається значення цільової функції. Число кроків S у серії вибирається таким, щоб на початкових етапах пошуку діялося помітна зміна значення цільової функції (R). Якщо наступна серія кроків дає менше значення R, отже пошук продовжується. Якщо ж при виконанні слідкуючої серії менше значення R не знаходиться, отже пошук припиняється таі одержане найменше значення роздивляється як iскомий оптимум.



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

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

Розглянемо один з простіших алгоритмів реалізації засобу градієнту.

Вибираємо координати початкової точки U1n U2n, величину кроку H1 та H2, припущення e1 та e2 .

Визначимо градієнт цільової функції

 

(5.45)

 

 

Для розрахунку ΔR необхідно обчислити величини похідних dR/dUi.

Визначимо їх численними засобами . Біля початкової крапки 1 з координатами (U1n ,U2n ) ставляться дві допоміжні крапки: 1’- на відстані ε1 уздовж осі U1 і 1''- на відстані ε2 уздовж осі U2(рис. 5.21)
У цих крапках розраховуються значення цільової функції R(Х1, Х2). Похідні знаходяться по наступним формулах:

 

(5. 46)

 

(5. 47)

 

Рис 5.21

 

Після цього роблять крок в точку 2 для наступного розрахунку R(Х1 Х2). Координати цієї точки визначаються по формулі:

 

(5.48)

 

 

Подальший алгоритм розрахунків будують по-різному. В простому варіанті можна просто повторювати описану вище процедуру. Однак, частіше роблять інакше. Якщо крок опинився вдалим, отже роблять ще крок в тому ж напрямку, використовуючи знайдені значення похідних на попереднім кроці. Практично це вже не буде напрямком градієнту, але якщо наступний крок дає потрібне припущення R (Х1 Х2), отже це дозволить "зекономити" на розрахунку похідних. Якщо і цей крок удалий, отже можна зробити крок ще раз і так далі.

Якщо ж крок невдалий - в цьому випадку крок зменшують вдвічі та розраховують точку i+2. Тепер, якщо зменшений крок був удалий, отже рухатися по отому ж напрямку немає змісту , тому що прийдемо в "погану " точку i+1.

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

 

5. 6. 5. Засіб найскорішого спуска

 

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

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

Поєднання основних ідей засобу релаксації та градієнту дає засіб

найскорішого спуска, суть якого укладається у слідкуючому.

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

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

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

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

Важливою особливістю засобу найскорішого спуска є отже, що при його застосуванні Рис. 5.22

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

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

 

(5.49)

 

де UАj , UBj - координати початкової та кінцевої точок останнього

відтинку спуска.

Цей же критерій може використовуватися у поєднанні з контролем значень цільової функції у точках UA та UB:

| R(U(F))-R(U(B)) | (5.50)

 

5.7. Безградiєнтні методи рішення задач оптимiзації

 

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

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

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

Методи многомірного пошуку - покоордiнатного спуска, многомірного сканiрованiя, Хука-Джiвса, сiмплексний можуть використовувати методи одномірного пошуку як допоміжні.

Спершу розглянемо методи одномірного пошуку. Для всіх методів постановка завдання наступна - визначити стан екстремуму на iнтервалі [Umin, Umax ].

 

5. 7. 1. Метод сканiрованiя

 

Алгоритм методу слідуючи й . Iнтервал пошуку [Umin, Umax] розбивається на N рівних дільниць, кожний з яких равен кроку пошуку h. Далі послідовно визначається R(Uj) значення цільової функції у всіх точках розбивки, включаючи граничні точки та запам’ятається максимальне чи мінімальне значення цільової функції (рис.5.23).

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

Рис. 5. 23

 

5. 7. 2. Метод локалiзації екстремума

Iнтервал пошуку [Umin, Umax] розбивається на 4 рівні частини та у точках розбивки та на кордонах інтервалу вираховуються значення цільової функції - у точках 0, 1, 2, 3 та 4 (рис. 5.24). Локалізується положення екстремума (мінімуму) на інтервалі в два разу меншому [2 – 4], чим попередній [0 – 4]. Отриманий інтервал знову поділяємо на 4 рівні частини. Рис 5.24

Неважко помітити, що розбивка інтервалу на 4 - найбільш зручний варіант, так як на кожному наступному кроці необхідно обчислювати тільки 2 нових значення цільової функції. У наданому випадку у точках 5 та 6.

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

Δ=(Umax-Umin)*2-(S-1)/2(5.51)

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

Так, наприклад, при S=21 відносна помилка у знаходженні стану екстремуму складе:

Δ=(Umax-Umin)*2-10 ≈ 0.001

 


 

5. 7. 3. Метод "золотого перетину"

 

Результати пошуку можуть бути краще, якщо ділення iнтервала [Umin, Umax], у якому знаходиться екстремум, виробляти не на ціле число, а у певному ірраціональному відношенні.

(a / b) = (b / c) або a*c = b2 (5.52)

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

Оскільки c = a – b, отой підставив вираз для с в (5.52) та запровадивши нову перемінну k = b / a, після перетворень одержимо:

K2 + K – 1 = 0 (5.53)

Вирішив (5.53), одержимо близьке значення K ~ 0. 62.

Порядок пошуку екстремуму методом "золотого перетину" наступний . На досліджуваним iнтервалі визначаються дві точки Umin та Umах:

U1=Umin+(1-K).a

U2=Umin+K.a (5.54)

де а - довжина інтервалу Umin – Umax.

 

У точках U1 і U2 розраховується цільова функція. За знайденим значенням R(U1і U2) з обліком R(Umin і Umax) визначається подінтервал, у якому локалізований екстремум. У даному випадку це [Umin ,U2 ] (рис. 5.25).

Далі усередині великого подінтервалу [Umin ,U1 ]

знаходиться крапка, що відстоїть від загального кінця Рис.5.25

подінтервалу на відстані (1–К)Wb= K2 .b,

де b - довжина подінтервалу [Umin ,U2 ], у якому локалізований екстремум, причому b = K.a. Тоді:

U3=Umin+K2.b =Umin+K2.(K.a)=Umin+K3.a (5.55)

Неважко показати, що в інтервалі [Umin ,U2 ] також дотримується "золотий перетин". Далі обчислюється значення цільової функції R(U3) і порівнюються значення R(U2), R(U1), R(U3). Знаходиться мінімальне значення (у даному випадку R(U3) ) і процедура продовжується - визначається аналогічно крапка R(U4) і т.д., поки не буде знайдений екстремум із заданою точністю. Абсолютна помилка у визначенні положення екстремуму після S обчислень складе

(5.56)

При S=21 відносна помилка : Δ/(Umax -Umin)= 0,5*0.6218 ≈ 0.9*10-4 Отже, точність розрахунку по методу "золотого перетину" практично на порядок перевершує точність розрахунку по методу локалізації екстремуму при тому самому кількості обчислень.

Розглянемо тепер деякі з методів багатомірного пошуку.

5. 7. 4. Метод покоординатного спуска Гаусса - Зейделя

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

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

Основним достоїнством наданого методу є його простота.

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

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

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

5. 7. 5. Метод Хука - Джiвса

 

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

Алгоритм методу наступний .

1. Вибирається початкова базисна точка B1 і крок hj для кожної

перемінної Xj (j=1, 2, ..., n). Можна використовувати й однаковий крок h для всіх перемінних.

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

2.1. Обчислюється значення цільової функції R(B1) у базисній точці.

2.2. Кожну незалежну перемінну по черзі змінюємо на розмір кроку. Таким чином, обчислюється значення цільової функції R(B1 +h1 e1 ), де e1 - одиничний вектор у напрямку осі x1 . Якщо це призводить до зменшення значення цільової функції (в випадку пошуку минимума), то B1 змінюють на B1 +h1 e1. У противному випадку обчислюється значення функції R(B1 -h1e1 ) і якщо її значення зменшилося, те B1 заміняють на B1 -h1 e1. Якщо жодний із пророблених кроків не призводить до зменшення значення цільової функції, то точка B1 залишається незмінної і розглядаються зміни в напрямку осі x2, тобто знаходять значення функції R(B1 +h2 e2 ) і т.д. Коли будуть розглянуті усе n перемінних, то одержимо нову базисну точку B2.

2.3. Якщо B2 =B1 , тобто зменшення функції не було досягнуто, те дослідження повторюється навколо тієї ж базисної точки B1, але зі зменшеним розміром кроку. На практику задовільним рахується зменшення розміру кроку (кроків) у десять разів від початкової довжини.

2.4. Якщо B2 ≠ B1 , те провадиться пошук за зразком.

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

3.1. Розумно рухатися з базисної точки B2 у напрямку B2 -B1, оскільки пошук у цьому напрямку вже призвів до зменшення значення цільової функції. Точка зразка може бути обчислена в такий спосіб:

P1 = B1 +2*(B2 - B1) (5.57)

У загальному випадку:

Pi = Bi +2*(Bi+1 - Bi ) (5.58)

3.2. Проводиться дослідження в округах точки P1(Pi ).

3.3. Якщо найменше значення на кроку 3.2 менше значення в базисній точці B2 (у загальному випадку Bi+1), те одержують нову базисну точку B3 (Bi+2), після чого варто повторити крок 3.1. У противному випадку не провадиться пошук за зразком, а заміняється базисна точка. У якості нової базисної точки вибирається та точка, у якому на попередньому кроку значення цільової функції було мінімальним. Потім виконується дослідження навколо нової базисної точки.

4. Процес пошуку завершується, коли довжина кроку (довжини кроків) стануть менше заданого малого значення.

5. 7. 6. Метод сканiрованiя

 

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

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

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

Найбільш простий алгоритм пошуку екстремуму методом сканiрованiя "пошук на сітці перемінних" укладається в тому, що по кожної незалежної перемінної задаються припущення у відповідному порядку, що забезпечує " заповнення" всієї досліджуваної області рівномірною та достатньо густою сіткою. Так, наприклад, для пошуку екстремуму функції двох перемінних спершу при фіксованому значенні Uk2 розраховуються значення R(Uj)при UK1 = UK-11 для всього діапазону зміни незалежної перемінної Uj та фіксує значення екстремуму. Після цього друга перемінна змінюється на крок ΔU2 UK2= UK-12U+ΔU2 і розрахунки повторюються при варіюванні перемінної Uj

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

Обсяг обчислювань при використанні методу сканiрованiя можна оцінити по наступній формулі :

(5.59)

де Δ - точність визначення екстремума

n - кількість незалежних перемінних.

При n = 2 та Δ = 10 кількість обчислювань S = 10-6, а при тому ж значенні точності n = 3 S = 10-6.

Тому метод сканiрованiя ефективно використовується при числі перемінних не більш трьох.

Існують різноманітні модiфикації методу сканiрованiя, що застосовуються в основному для скорочування обсягу обчислювань. Розглянемо одну з них - сканiрованiє з перемінним кроком. Спершу задається достатньо великий крок (ΔU > e) та виконується " грубий " пошук, що локалiзує область існування глобального екстремуму ( P ) (рiс. 5.26). Рис 5.26

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

При використанні наданого алгоритму обсяг обчислювань істотно але скорочує і може бути визначений по наступній формулі :

(5.60)

де r - число етапів уточнення пошуку, на якому крок зменшувався в К раз

n - число незалежних перемінних;

Δ - точність визначення екстремуму.

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

Δo=Kr Δ ( 5. 59 )

При n = 2, Δ = 10-3 , r = 2, K = 10 и Δo = 0,1 кількість обчислювань S=900.

При постійному кроці сканiрованiя для отих же умов вимагалося 106 обчислювань, т. є. обсяг обчислювань скоротився більш ніж у 1000 раз. Ще більш чималий виграш спостерігається при більшому числі незалежних перемінних. Так, для отих же наданих, але при n = 3 число обчислювань з перемінним кроком сканiрованiя складе S = 17000, а для постійного кроку S = 109.

 

5. 7. 7. Симплексний метод

 

Основна ідея цього методу укладається в тому, що по відомим значенням цільової функції у вершинах опуклого многогранника, що називається симплексом, знаходиться напрямок, у якому вимагається зробити наступний крок, щоб одержати найбільше зменшення (збільшення) значення цільової функції. При цьому під симплексом в n-мірним просторі розуміється многогранник, що має n+1 вершину. Прикладом симплекса в двомірним просторі, т. є. на площині, є трикутник. В трьохмірним просторі - тетраедр. Симплекс володіє наступною властивістю - проти будь-який з його вершин Sj розміщена тільки одна грань, на якої можна збудувати новий симплекс, що відрізняється від колишнього розміщенням нової вершини Sj тоді як інші вершини обох симплексів співпадають. Вершина нового симплекса S, взагалі кажучи, може знаходитися і по іншу сторону грані від вершини Sj.

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

Розглянемо найпростіший випадок - пошук мінімуму цільової функції двох перемінних R(U1 ,U2 ).

Алгоритм пошуку наступний:

1.Розраховуються значення цільової функції у вершинах обраного вами симплекса S10, S20, S30 (рис.5.27).

2. Вибирається вершина, де значення R(U1 ,U2) найбільше - S10 .

3. Новий симплекс S11 ,S20 ,S30 будується таким засібом: - знаходиться середина грані S20 ,S30, яка розташована проти вершини S10 - крапка А.Через крапки S10 і А проводиться пряма. На цій прямій від крапки А відкладається відрізок АS11 , рівний по величині відрізку S10 А.

4. У новій вершині обчислюється значення цільової функції.





Дата добавления: 2014-11-18; Просмотров: 86; Нарушение авторских прав?;


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



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.196.2.131
Генерация страницы за: 0.03 сек.