50127

Методи послідовного пошуку екстремуму у критеріальному моделюванні

Реферат

Математика и математический анализ

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

Украинкский

2014-06-10

630.34 KB

2 чел.

Міністерство освіти і науки  України

Вінницький національний технічний університет

Реферат

З дисципліни ОНДР

на тему:

«Методи послідовного пошуку екстремуму
у критеріальному моделюванні»

Перевірив :

Науковий керівник к.т.н.,доцент

Бевз С.В.

Виконав:                                                                                                                                                      ст.гр.2ЕСМ-11                                                                                                                 

Баранюк В.Ю.

Вінниця

2013

вступ

Критеріальний метод як метод оптимізації почав розвиватися на початку 70-х років на кафедрі електричних систем Московського енергетичного інституту під керівництвом Ю.М. Астахова. Ним сформульовані та обгрунтовані основні положення нового методу оптимізації і напрямки його розвитку. Активну участь в розробці та застосуванні критеріального методу в електроенергетиці брали і беруть члени кафедри електричних станцій та систем Вінницького національного технічного університету.

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

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

Критеріальний метод пристосований до розв’язування нелінійних оптимізаційних задач великої розмірності. Таких, що виникають в складних динамічних системах типу електроенергетичних. Він складається з критеріального моделювання (КМ), критеріального програмування (КП) і критеріального аналізу (КА).

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

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

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

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


1 КРИТЕРІАЛЬНЕ МОДЕЛЮВАННЯ

1.1 Узагальнені методи теорії подібності і моделювання фізичних процесів та явищ

1.1.1 Моделювання і узагальнення подібних явищ і процесів

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

Поняття моделі завжди вимагає введення поняття подібності. Таким чином‚ найбільш вдалим може бути визначення моделі як  об`єкта (явища‚ процесу‚ установки‚ знакового утворення)‚ що знаходиться у відношенні подібності до модельованого об`єкта (оригіналу).

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

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

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

Існує два альтернативних підходи до встановлення подібності. Згідно з першим, насамперед, визначається подібність явищ як подібність,  отримана шляхом перетворення розміру кожного його параметра у визначену кількість разів. Тобто, виконавши, так звані, подібні перетворення, отримуємо відношення подібності:

,

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

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

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


1.1.2 Приведення до критеріальної форми

Припустимо, що існуючі зв'язки між параметрами процесу керування і параметрами елементів системи, в якій цей процес протікає, можна представити у вигляді:

,                                        (1.1)

де y(x) - деякий узагальнений техніко-економічний показник; ai, ji - сталі коефіцієнти, які визначаються властивостями системи; xj - змінний параметр системи; m1 - кількість членів функції; n - кількість змінних.

В оптимізаційних задачах показник є критерієм оптимальності, а вираз (1.1) - цільовою функцією. Для розв'язання таких оптимізаційних задач необхідно проводити порівняння варіантів і за визначеним критерієм вибирати кращий. Тому слід адаптувати його для такого класу задач. Порівняння варіантів треба проводити з базисними величинами , . Будь-який варіант процесу або об'єкта можна виразити через ці величини. Це можна зробити таким чином. Позначимо

,                         (1.2)

де , - відносні значення параметрів.

Підставивши (1.2) в (1.1), отримаємо

.

Зробивши тотожне перетворення і ввівши заміну

,                                            (1.3)

отримаємо критеріальну форму запису задачі:

.                                         (1.4)

Зауважимо, що для базисного варіанта, коли y = yб, критеріальне рівняння (1.4) прийме такий вигляд:

1 = 1 + 2 + ... + n.                                        (1.5)

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

1.1.3 Використання критеріальних моделей

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

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

а) б)

Рис. 1.1. Пряма (а) та зворотна (б) задачі чутливості

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

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

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

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

2 КРИТЕРIАЛЬНЕ ПРОГРАМУВАННЯ

2.1 Пряма задача критеріального програмування

2.1.1 Пошук екстремуму функції без обмежень

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

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

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

мінімізувати

  (2.1)

за умови, що .

Якщо функція   опукла і диференційовна на заданому інтервалі значень змінних величин , то дана задача, як відомо, розв'язується, виходячи з таких умов :

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

або з урахуванням (1.3)

  (2.2)

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

Таким чином, разом з (1.5) умова мінімуму функції запишеться як

  (2.3)

Bираз (2.2) можна розглядати як скалярне множення двох векторів , . Оскільки воно дорівнює нулю, то вектори і  oртогональні. Тому співвідношення (2.2) називається умовою ортогональності.

Проілюструємо важливість отриманого результату на конкретному прикладі.

Приклад 2.1. 

Нехай

y= + + (2.4)

де

Для даного прикладу умова (2.3) запишеться так :

або з урахуванням числових значень коефіцієнтів

Розв'язуючи цю лінійну систему трьох рівнянь з трьома невідомими, отримаємо

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

Наприклад, при відхиленні від оптимального значення на 10% ( ) значення функції y відносно зміниться на

,

або на 0.23%. При такому ж відхиленні функція зміниться на 0.7%.

Критеріальний аналіз у даному випадку виконується без визначення і відповідних , . Проте так просто задача розв'язується тільки при певному співвідношенні числа членів математичної моделі m і кількості змінних . З (2.3) видно, що система рівнянь відносно визначена тільки при .

Якщо показник s, який далі буде називатися мірою складності, не дорівнює нулю, то розглянутий підхід використовувати так просто неможливо. Тут потрібні додаткові дослідження. Окрім цього, необхідно також узагальнити отримані результати на випадок, коли задача (2.1) охоплює функціональні обмеження. Розпочнемо з останнього.

2.1.2 Пошук мінімуму задачі з обмеженнями

Сформулюємо задачу пошуку мінімуму функції :

мінімізувати

  (2.5)

за умов:

 . (2.6)

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

У поставленій задачі слід шукати мінімум функції Лагранжа, записаної згідно з теоремою Куна-Таккера так:

де - неозначені множники Лагранжа.

Умови екстремуму відповідають рівності нулю часткових похідних від L за всіма змінними і :

+  (2.7)

Помножимо праві й ліві частини цих виразів на . Тоді з урахуванням (1.3) отримаємо :

  (2.8)

де m - сумарне число членів цільової функції і обмежень;

  (2.9)

Умову нормування (1.5) для функції Лагранжа L отримаємо методом інтегральних аналогів. З урахуванням того, що згідно з теоремою Куна-Таккера вона запишеться як:

 ,

або    

 , (2.10)

нормуються тільки критерії подібності цільової функції.

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

У точці відносного мінімуму градієнти функцій і спрямовані по одній прямій, але в протилежні напрямки, тобто:

.

З останнього виразу множник Лагранжа

 . (2.11)

Записавши значення градієнтів і через логарифмічні похідні і підставивши їх у (2.11), отримаємо такий вираз для невизначених множників Лагранжа:

В останньому виразі

  (2.12)

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

З урахуванням (2.12) для активних обмежень вираз для множників Лагранжа запишеться так:

.

Звідки

 , (2.13)

тобто, величину можна розглядати як нормований множник Лагранжа.

Скористаємося тепер співвідношенням , або в іншому вигляді:

.

Тепер з урахуванням (2.9):

 . (2.14)

З (2.14) видно, що нормований множник Лагранжа є сумою критеріїв подібності -го обмеження.

Отримані співвідношення (2.9) і (2.10) для критеріїв подібності дають можливість записати функцію Лагранжа в критеріальній формі.

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

  (2.15)

Очевидно, що дана форма запису нічим, окрім індексів, не відрізняється від (1.4).

У свою чергу, розділивши вираз (2.6) на і взявши до уваги (2.10) і (2.11), будемо мати:

 . (2.16)

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

Приклад 2.2. Нехай

  (2.17)

при

Функція Лагранжа запишеться так:

.

Згідно з (2.8) і (2.10), критерії подібності можна визначити з системи рівнянь:

Розв’язавши дану систему, отримаємо

=0,6923; =0,3077; =2,3066.

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

;

.

2.2 Двоїста задача критеріального програмування

2.2.1 Застосування загальних положень теорії двоїстості

в критеріальному програмуванні

При розв'язанні задачі мінімізації (2.5), (2.6), по суті, розв'язування системи нелінійних рівнянь (2.7), записаних на основі методу Лагранжа, замінили дослідженням умов (2.3) і розв'язуванням системи рівнянь:

 , (2.18)

де

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

Неоднорідна система рівнянь (2.18) має розв'язок тоді, коли матриця коєфіцієнтів квадратна і її визначник не рівний нулю. Вектор критеріїв подібності в цьому випадку .

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

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

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

Згідно з теоремою двоїстості, якщо і - оптимальний розв'язок задачі критеріального програмування, то

 , (2.19)

де -максимальне значення двоїстої функції .

Функції і перебувають у такому співвідношенні:

 

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

Рис. 2.1. Принцип мінімаксу

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

Раніше були встановлені умови мінімізації функції — спільне розв'язання ортонормованої системи рівнянь (2.3). Виходячи з цього і використовуючи (2.19), сформуємо двоїсту функцію . Згідно з теоремою двоїстості, , але, оскільки,

;  ,

то можна записати

  (2.20)

При відсутності обмежень у вихідній задачі () з урахуванням значень критеріїв подібності, знайдених методом інтегральних аналогів (1.3), після тотожних перетворень

 .

Якщо до вихідної задачі входить одне активне обмеження , то рівняння (2.20) після спрощень набуде вигляду:

,

де - нормований множник Лагранжа.

Аналогічно розмірковуючи для випадку з обмеженнями, знаходимо, що

,

де

Таким чином, двоїста задача, відповідна вихідній прямій, остаточно може бути сформульована так:

максимізувати

  (2.21)

за умов ортогональності

  

та нормування

 .

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

Скористаємося тепер отриманими результатами і знайдемо оптимальні значення   для раніше розглянутих прикладів 2.1 і 2.2.

Для прикладу 2.1

,

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

=5,825.

Для прикладу 2.2 при =2; =4; =3і  

,

де .

Підставивши числові значення, отримаємо:

.

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

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

2.3 Чисельні методи

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

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

2.3.1 Зниження міри складності

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

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

Проілюструємо цей прийом. Об’єднаємо  i - й та  v - й  члени  функції  (2.5):

 , (2.27)

де  

.

Змінні x з індексами p та r підбираються так, що . Може статися, що зробити це не вдається. Тоді i-й та v-й члени не можуть бути замінені одним. Необхідно розглянути наступну пару членів. Якщо відповідних членів у функції не знайдеться, то стратегію затримки з метою зменшення міри складності застосувати  не вдасться.

Припустимо, що i-й та v-й члени відповідають необхідним умовам і можуть бути замінені одним. Замінимо в (2.27) вираз у дужках степеневою функцією, яка дорівнює йому в деякій точці  і похідна від якої в цій точці дорівнює похідній від виразу, який вона замінює. Такою степеневою функцією є:

  (2.28)                                                                                                         

де

Перепишемо (2.27)  з урахуванням (2.28):

  (2.29)

Оскільки в (2.29) у результаті проведеної заміни кількість членів порівняно з (2.27) зменшилася на одиницю, то, значить, на одиницю зменшилася й міра складності . Аналогічним чином можна розглянути й інші пари членів і зменшити до потрібного значення.

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

Проілюструємо прийом зменшення міри складності на такому прикладі.

Приклад 2.4. Мінімізувати

  (2.30)

за умов

  (2.31)

Міра складності цієї задачі  .

Використаємо стратегію затримки вибору для зменшення кількості членів цільової функції, об'єднавши перший та другий члени (2.30) з врахуванням (2.28) :

  (2.32)         

за умов

 , (2.33)

де      

;

q(zk)=. (2.34)

Міра складності задачі (2.32)-(2.33) , тобто зменшилася, як і очікувалося, на одиницю.

Запишемо згідно з (2.3) ортонормовану систему рівнянь для задачі (2.32)-(2.33) :

Звідси

 1=1, 2=2(1-q), 3=2q. (2.35)

Для визначення оптимальних значень , виразимо їх через z10. З останніх співвідношень маємо

З (2.33) випливає, що                                                                              

.

Отже

 

Звідси     

.

З урахуванням (2.34)

                                                                              

Скористаємося тепер правом вибору z10. В результаті отримуємо, що z10=2. Підставивши це значення z1 в (2.34), маємо

.

Тоді, згідно з (2.35),

Знайдемо значення коефіцієнта а'1 в (2.32):

Максимум двоїстої функції

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

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

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

2.3.2 Лінеаризація двоїстої задачі

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

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

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

i , ,

де   

.

Кожному набору пронормованих критеріїв подібності відповідають свої критеріальні залежності, побудовані згідно з виразом (1.4). Для прикладу на рис. 2.5 подано критеріальні залежності, які відповідають оптимальним (крива 1) і близьким до оптимальних (криві 2 і 3) умовам. При цьому критеріальні рівняння мають вигляд :

 ;

  ; (2.36)

  ,        

де   — вектор оптимальних критеріїв подібності (вектор, який оптимізує двоїсту функцію (2.21)); — довільні вектори, які відповідають умовам (2.3).

Очевидно, що для задачі з мірою складності , коли система рівнянь (2.18) не визначена, можна вибрати безліч таких векторів і  побудувати відповідні залежності. У тому числі можна послуговуватися й такими векторами   та , між якими буде лежати в гіперплощині умов (2.3) вектор  . У цьому випадку і замикають ОДР (див. рис. 2.5, а).

Щоб визначити межі області, всередині якої потрібно здійснювати пошук оптимального розв’язку, вчинимо так. Виберемо в околі мінімуму функції  деяку точку , для якої виконуються умови (2.6). Згідно з (2.36) маємо три значення функції (рис. 2.5, б).

Введемо позначення :

,

.

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

Остаточно задача визначення меж ОДР формулюється так :

мінімізувати

  (2.37)

за умов

мінімізувати

  (2.38)  

за умов  

а)

б)

Рис. 2.5. Визначення області існування розв’язку

двоїстої задачі

У (2.37) і (2.38)    — матриця показників степеня прямої задачі КП (в теорії подібностей відома як матриця розмірностей).

Щоб звести задачі (2.37) та (2.38) до задач ЛП, необхідно тепер вибрати з урахуванням обмежень прямої задачі КП координати точки   у просторі допустимих розв’язків. Тоді з урахуванням (1.4) задачі (2.37) і (2.38)  перепишуться :

мінімізувати

  (2.39)   

за умов

мінімізувати

  (2.40)

за умов

У (2.39) та (2.40)       — постійні коефіцієнти.

Як бачимо, ці, та сформульовані раніше в загальному вигляді задачі оптимізації (2.37) та (2.38),  є задачами ЛП і можуть бути розв’язані його методами. Для цього можна послуговуватися стандартними програмами ЛП.

У результаті виконання лінійної програми можливі два випадки. Перший — знайдені інтервали () відповідають  практичним вимогам до точності оптимального розв’язку. Тоді за оптимальні приймаються середні значення

.                                                  

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

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

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

2.3.3 Алгоритми пошуку оптимальних рішень

Застосування методів дихотомії.

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

Застосуємо метод п'яти точок до опуклої функції (рис. 2.6.).

На першому кроці, за результатами лінійного програмування i'(1) , i''(1), визначаємо ще три значення i для всіх m двоїстих змінних, діленням інтервалу навпіл :

 ; ;

.

За (2.21) визначаємо ординати п'яти точок двоїстої функції: d('), d(''), d(ср), d('ср), d(''ср). Знаходимо серед них максимальне значення: maxdi(). На рис. 2.6 це .

На другому та подальших кроках вибираємо точки i'(k) , i''(k), які лежать справа та зліва від максимуму функції  d() попереднього кроку та обмежують звужену ОДР. Як середнє арифметичне визначаємо абсциси, з (2.21) — ординати ще двох точок.

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

  (2.41)                                                                                          виконується вже на другому або третьому кроці.

Рис. 2.6. Визначення максимуму функції методом дихотомії

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

                       .  (2.42)                                       

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

Метод золотого перерізу — один з різновидів методів дихотомії.

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

Рис. 2.7. Графічна ілюстрація поділу відрізка

за методом золотого перерізу

Ці відношення дорівнюють золотій пропорції :  , яка є додатнім коренем рівняння золотого перерізу :    .

Нашим безпосереднім завданням є знаходження максимуму двоїстої функції d( ) на проміжку АВ, що обмежує ОДР. Знайдемо його методом золотого перерізу.

На першому кроці при відомих координатах А [a1,a2], В [b1,b2] знайдемо абсциси точок С і Д відповідно з формул, які випливають із золотої пропорції:

Визначаємо ординати точок С і Д за формулою двоїстої функції (2.21).

Для алгоритмізації задачі перепозначаємо точки : точку С замінюємо точкою А (тобто a1(k)=c1(k-1)) при с2  d2 , в іншому випадку точку Д замінюємо точкою В (b1(k)=d1(k-1)). У першому випадку  c1(k)=d1(k-1) , у другому — d1(k)=c1(k-1) (рис. 2.7). Абсцису другої точки знаходимо згідно з виразами :

 ;

 ,                                                                   

На кожному кроці відрізок АВ зменшується в   разів.

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

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

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

Застосування методу квадратичної інтерполяції

Суть методу полягає в інтерполюванні функції (крива 2 на рис. 2.8), яка приблизно збігається з досліджуваною кривою (крива 1 на рис. 2.8). Iнтерпольована функція подана у вигляді параболи , яку будуємо за відомими точками досліджуваної функції, дві з яких — точки, що обмежують ОДР:     -1 = ' , d-1 = d('), +2 = '' , d+2 = d('') ; третю знаходимо як середнє арифметичне попередніх : , відповідно      d+1 = d(+1).

Рис. 2.8. Пошук максимуму функції методом

квадратичної інтерполяції

Визначимо координати вершини квадратичної параболи за умови

,                                                      

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

;

;  

;                                          

отримаємо :

.

Тепер визначимо , що відповідає  і від нього залежить:   = h + 1 ;   = ( +1 - -1 ) + l    ; де l, у свою чергу, залежить від того, в якому проміжку лежить максимум параболи:

— при  <0 —  l =-1 -(+1 --1 ) ;

— при  01 — l =-1 ;

— при  1< 2 — l =+1 ;

— при  >2 — l =+2 .

Ординату вершини знаходимо з (2.21).

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

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

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

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

На рис. 2.9. показана його логічна схема. На ній виділено три основних блоки: 1 — представлення критеріальної програми у вигляді лінійної, як це було показано в п. 2.3.2,  та розв’язання її симплекс-методом з метою отримання меж ОДР, чи безпосередньо оптимального розв’язку у разі досить малого інтервалу ОДР; 2 — уточнення, у разі необхідності, отриманого симплекс-методом розв’язку, методами дихотомії (див. п. 2.3.3); 3 — уточнення отриманого розв’язку методом квадратичної інтерполяції, який описано в п. 2.3.3.

Вибір методу для уточнення оптимального розв’язку здійснюється залежно від умов контролю точності розрахунків, враховуючи форму цільової функції в межах ОДР. Якщо точність контролюється за (2.41), то доцільно скористатися методами дихотомії. У цьому разі результати оптимізаційних розрахунків можуть бути ефективно використані для критеріального аналізу розв’язку. У випадку пошуку оптимального розв’язку точність може контролюватися за умовою (2.42). У цьому разі, більш ефективним, у плані швидкого знаходження оптимуму, є метод квадратичної інтерполяції.


Початкові дані

Формування

критеріальної  моделі

Формування

лінійної   програми

Виділення області оптимальних

розв'язків симплекс-методом

ні

  

1

так

Уточнення оптимальних розв'язків методом інтерполяції

Уточнення оптимальних розв'язків методом дихотомії

ні

ні

   

 

3

2

так

так

так

Контролюється

точність по ?

ні

    Виведення    результатів

Рис. 2.9. Алгоритм розв’язання задач високої міри складності

Висновок

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

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


ЛІТЕРАТУРА

  1.   Аоки М.  Введение в методы оптимизации. Пер. с англ. - М.: Наука, 1977. - 344 с.
  2.   Астахов Ю.Н., Лежнюк П.Д. Применение критериального  метода в электроэнергетике. - Киев: УМК ВО. - 1989. - 137 с.
  3.   Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. - М.: Наука, 1987. - 600 с.
  4.   Веников В.А. Теория подобия и моделирования. - М.: Высшая школа, 1976. - 479 с.
  5.   Даффин Р., Питерсон Э., Зенер К. Геометрическое программирование. Пер. с англ. - М.: Мир, 1972. - 312 с.


 

А также другие работы, которые могут Вас заинтересовать

11203. Ливия в системе международных отношений в конце XX – начале XXI веков 226 KB
  Целью моей работы является рассмотрение вопроса Ливии в системе международных отношений, региональной и глобальной безопасности. Исходя из цели работы, я ставлю перед собой такие основные задачи, как: изучение истории государства Ливия; анализ кризисного государства и угрозы глобальной и региональной безопасности; рассмотрение потенциала Ливии
11204. Общие черты и особенности правового положения сельскохозяйственных коммерческих организаций и предприятий 51.5 KB
  Общие черты и особенности правового положения сельскохозяйственных коммерческих организаций и предприятий. Говоря о сельскохозяйственных организациях можно выделить их общие черты присущие любой коммерческой организации. Все они имеют обособленное имущество отв...
11205. Правовые основы проведения аграрной реформы в России 61.5 KB
  Тема: Правовые основы проведения аграрной реформы в России. Объективные предпосылки реорганизации колхозов и совхозов. Порядок определения земельных долей и имущественных паёв в процессе реорганизации сельскохозяйственных предприятий. Особенност...
11206. Аграрные правоотношения 60.5 KB
  Аграрные правоотношения. Понятие аграрных правоотношений. Внутренние и внешние аграрные правоотношения. 1. Понятие аграрных правоотношений. Аграрными правоотношениями являются отношения складывающиеся в процессе производства сельскохозяйств
11207. Акцентная структура слова 118 KB
  ЛЕКЦИЯ 10 Акцентная структура слова. Словесное ударение. Акустикофизиологическая природа словесного ударения в английском языке в сравнении с русским. Виды словесного ударения. Функции словесного ударения. Место словесного ударения. Градация сло...
11208. ИНТОНАЦИЯ И ПРОСОДИЯ 96.5 KB
  ЛЕКЦИЯ 11. ИНТОНАЦИЯ И ПРОСОДИЯ. Понятия интонации и просодии и их соотношение как лингвистического и акустикофизиологического явления. Компоненты интонации: мелодика громкость темп качество голоса пауза. Методы записи интонации. Функции просодии. ...
11209. Региональная и социальная вариантология. Американский, австралийский и канадский варианты английского языка. 102 KB
  ЛЕКЦИЯ 13 Региональная и социальная вариантология. Американский австралийский и канадский варианты английского языка. Американский вариант английского языка. Американский вариант английского языка детально описывался многими учёными из разных стран. С точ
11210. Региональная и социальная вариантология. Британский вариант английского языка 151.5 KB
  ЛЕКЦИЯ 12 Региональная и социальная вариантология. Британский вариант английского языка. Понятие национальный язык региональный стандарт национальная модификация языка. Билингвизм и диглоссия. Современные британские произносительные нормы. Географичес
11211. Фонетика и фонология изучаемого языка. Специфика структуры английского произношения 48 KB
  ЛЕКЦИЯ 2 Фонетика и фонология изучаемого языка. Специфика структуры английского произношения Литературное произношение. Понятие орфоэпии. Языковая фонетическая интерференция. Понятие фонетической базы Артикуляционная и просодическая база. Артикуля...