К У Р  С О В А     Р О Б  О Т А

з курсу:

“Детерміновані моделі дослідження операцій та оптимізації інформаційних систем”

      на  тему:

“Методи прямого пошуку для оптимізації унімодальних функцій якості без обмежень” 
 

 

Зміст

 

Вступ

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

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

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

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

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

 

1. Змістовна постановка задачі

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

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

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

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

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

- кількість  продукції -  "витрата сировини"

- кількість  продукції -  "якість продукції" 

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

При постановці задачі оптимізації  необхідно:

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

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

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

      Правильна постановка задачі могла бути наступна:

а) отримати максимальну продуктивність при  заданій собівартості;

б) отримати мінімальну собівартість при заданій продуктивності;

      У першому випадку критерій оптимізації - продуктивність, а у другому - собівартість.  

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

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

      4. Облік обмежень.

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

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

1. Складання календарного плану експлуатації джерел  нафти, що забезпечує максимальний прибуток при заданих потужностях обладнання  і з урахуванням обмежень, зумовлених фізичними умовами відкачки.
2. Визначення чистого прибутку за рахунок обміну нафтосировиною  з іншими нафтокомпаніями при заданих характеристиках і місцях дислокації нафтоперегінних заводів і при відомих економічних показниках для процесу обробки сирої нафти, що поставляється по обміну.
3. Підрахунок додаткового прибутку за рахунок збільшення обсягу разових поставок готової продукції (наприклад, за рахунок виробництва певної кількості палива  для реактивних двигунів за урядовим контрактом) при збереженні раніше встановлених планових показників  для інших видів продукції, що випускається.
4. Щотижневе складання найбільш економічних (тобто пов’язаних з мінімальними витратами) графіків крекінг-процесів і операцій по  складанню різного роду горючих сумішей з урахуванням нафтосировини, що є в наявності,  обмежень, пов'язаного з числом діючих крекінг-установок і іншого обладнання, технічних характеристик для кожного виду продукції (таких, як октанове число), а також раніше встановлених вимог на поставку готової продукції і заданих транспортних умов.  
5. Визначення прибутку з капіталовкладень на будівництво додаткової крекінг-установки з урахуванням всіх виробничо-економічних показників існуючих установок.
6. Складання такого маршрутного розкладу перевезень готової продукції  з нафтоперегінних заводів до місць збуту, яке зв'язане  з мінімальними транспортними витратами і враховує відмінність у вартостях виробництва різних видів продукції на різних нафтоперегінних заводах, різницю у витратах,  пов'язаних з перевантаженням,  і календарні варіації попиту.
7. Розробка зведеного річного плану, об'єднуючого найбільш важливі керуючі рішення, що відносяться до діяльності компанії загалом.

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

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

     Критерієм оптимальності називається кількісна  оцінка якості об'єкта, що оптимізується.

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

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

      Розглянемо більш детально вимоги, які повинні пред'являтися до критерію оптимальності.

      1. Критерій оптимальності повинен  виражатися кількісно. 

      2. Критерій оптимальності повинен  бути єдиним.

      3. Критерій оптимальності повинен відображати найбільш істотні сторони процесу.

4. Бажано  щоб критерій оптимальності мав  ясний фізичний сенс і легко  розраховувався.

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

 

2. Формальна постановка задачі

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