Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Приклад 3.2 ⇐ ПредыдущаяСтр 4 из 4 Знайти точку умовного екстремуму функції при обмеженнях: Розв’язання: Складемо функцію Лагранжа + і продиференціюємо її по змінних і . Прирівнюючи отримані вирази до нуля, отримаємо наступну систему рівнянь: З першого і третього рівнянь випливає, що , тоді Розв’язуючи дану систему, знаходимо: . Побудуємо матрицю Гессе, що складається з елементів . . . Отже — точка, у якій функція досягає максимального значення . 4. Опуклі й угнуті функції Нехай задано -вимірний лінійний простір . Функція що задана на опуклій множині , називається опуклою, якщо для будь-яких двох точок та з множини і будь-яких значень , виконується співвідношення: (4.1)
Якщо нерівність строга і виконується для , то функція називається строго опуклою. Функція , яка задана на опуклій множині , (4.2)
Якщо нерівність строга і виконується для , то функція називається строго угнутою. Слід зазначити, що опуклість та угнутість функції визначаються лише відносно опуклих множин у , оскільки за наведеними означеннями разом з двома будь-якими точками та множині належать також точки їх лінійної комбінації: для всіх значень , що можливо лише у разі, коли множина є опуклою. Теорема 4.1. Нехай — опукла функція, що задана на замкненій опуклій множині , тоді будь-який локальний мінімум на цій множині є і глобальним. Теорема 4.2. Нехай — опукла функція, що визначена на опуклій множині , і крім того, вона неперервна разом з частинними похідними першого порядку в усіх внутрішніх точках . Нехай — точка, в якій . Тоді в точці досягається локальний мінімум, що збігається з глобальним. 5. Теорема Куна-Таккера Розглянутий метод множників Лагранжа уможливлює знаходження лише локальних сідлових точок функції Лагранжа. Теорема Куна-Таккера дає змогу встановити типи задач, для яких на множині допустимих розв’язків існує лише один глобальний екстремум зумовленого типу. Вона тісно пов’язана з необхідними та достатніми умовами існування сідлової точки. Розглянемо задачу нелінійного програмування, яку, не зменшуючи загальності, подамо у вигляді: (5.1) за умов: (5.2) (5.3) Теорема 5.1. (Теорема Куна-Таккера). Вектор є оптимальним розв’зком задачі (5.1)-(5.3) тоді і тільки тоді, коли існує такий вектор , що при , для всіх , точка є сідловою точкою функції Лагранжа , і функція мети для всіх угнута, а функції — опуклі. 6. Опукле програмування Опукле програмування розглядає методи розв’язування задач нелінійного програмування, математичні моделі яких містять опуклі або угнуті функції. Загальний вигляд задачі опуклого програмування такий: (6.1) за умов: (6.2) (6.3) де — угнуті функції. Аналогічний вигляд має задача для опуклих функцій. Позначимо: , тоді , і маємо: (6.4) за умов: (6.5) (6.6) де — опуклі функції. Оскільки ці задачі еквівалентні, то нижче розглянемо задачу (6.1)—(6.3). Множина допустимих планів задачі, що визначається системою (6.2), є опуклою. Як наслідок теорем 4.1 та 4.2 справджується таке твердження: точка локального максимуму (мінімуму) задачі опуклого програмування (6.1)—(6.3) є одночасно її глобальним максимумом (мінімумом). Отже, якщо визначено точку локального екстремуму задачі опуклого програмування, то це означає, що знайдено точку глобального максимуму (мінімуму). У разі обмежень-нерівностей задачу опуклого програмування розв’язують, застосовуючи метод множників Лагранжа. Функція Лагранжа для задачі (6.1)—(6.3) має вид: (6.7) де — множники Лагранжа. Використовуючи теорему Куна-Таккера, маємо необхідні та достатні умови існування оптимального плану задачі опуклого програмування. Теорема 6.1. Якщо задано задачу нелінійного програмування виду (6.1)—(6.3), де функції диференційовні і вгнуті по , то для того, щоб вектор , був розв’язком цієї задачі, необхідно і достатньо, щоб існував такий вектор , що пара була б сідловою точкою функції Лагранжа, тобто щоб виконувалися умови: (6.8) (6.9)
(6.10) (6.11) Умови (6.9) і (6.11) називаються умовами доповнюючої нежорсткості. Умови (6.9) відносяться до всіх змінних, на які накладені умови невід’ємності, а (6.11) — до всіх обмежень-нерівностей виду (6.2). Користуючись теоремою Куна-Таккера, задачу опуклого програмування розв’язують за наступним алгоритмом: 1. Складають функцію Лагранжа для задачі (6.1) - (6.3): . 2. Записують умови оптимальності (6.8)—(6.11). 3. Знаходять розв’язок системи рівнянь (6.9) і (6.11) та нерівностей (6.8) і (6.10). Зазначимо, що в даному випадку вектор повинен задовольняти умові невід’ємності. Для розв’язування деяких класів задач нелінійного програмування застосовуються методи, які передбачають певний вид цільової функції. Так, для задач з опуклими цільовими функціями у вигляді квадратичної форми , (6.12) використовуються методи квадратичного програмування, які ґрунтуються на теоремі Куна-Таккера про існування екстремуму функції Лагранжа для досліджуваної задачі. Якщо цільова функція задачі є сепарабельною, тобто її можна подати у вигляді алгебраїчної суми однорідних функцій відносно однієї змінної: + (6.13) тоді наближені екстремуми функцій визначаються методами лінійно-кускової апроксимації, їх основна ідея полягає в кусково-лінійній апроксимації початкової нелінійної функції лінійними залежностями, які розглядаються для кожної складової сепарабельної функції в інтервалах, що визначені точками сітки. Досліджуючи зміни цих функцій на кінцях інтервалів, можна перетворити початкову нелінійну задачу на задачу лінійного програмування, яка оперує з приростами цільової функцій та обмежень.
7. Розв’язування задачі нелінійного програмування за допомогою пакету Mathcad За допомогою системи комп’ютерної алгебри Mathcad знайдемо максимальне і мінімальне значення функцій із заданими умовами. Розглянемо порядок дій для вирішення задачі нелінійного програмування у програмі Mathcad: 1. Розмістимо курсор (червоний хрестик) на місці, де ми хочемо ввести цільову функцію. Вводимо ім’я критерію оптимізації і в дужках його аргументи через кому. Вводимо знак присвоювання “:=”, після якого вводимо вираз. Ініціалізуємо змінні і надаємо їм початкові наближення. 2. Вводимо ключове слово Given. Після цього вводимо обмеження, використовуючи знаки з меню Boolean. 3. За допомогою меню Vector & Matrix створюємо вектор змінних. Вводимо знак присвоювання після якого вводимо функцію minimize або maximize і в дужках параметри . Нижче створюємо, ще один вектор змінних, після якого вводимо знак рівності. Отримаємо точку, в якій функція набуває критичного значення. Також можемо знайти значення функції в цій точці. Демонстрація алгоритму на прикладах 3.1 і 3.2. та ін.: 1. , за умови: Рис. 7.1 2. , за умови: Рис. 7.2
3. , за умов: Рис. 7.3 4. , за умов: Рис. 7.4 5. , за умови Рис. 7.5
6. , за умов Рис. 7.6 7. , за умов Рис 7.7 З рис. 7.1 бачимо, що дана програма рахує наближено і результат залежить від значень, які ви надасте змінним при ініціалізації. Початкові наближення потрібно вибирати так, щоб вони задовольнялись обмеженням, які накладаються на цільову функцію.
Висновок В даній курсовій роботі ми розглянули розв’язування задач нелінійного програмування і застосували до їх розв’язання математичний пакет Mathcad. В теоретичній частина було розглянуто знаходження екстремальних значень методом множників Лагранжа. На практиці був описаний алгоритм для знаходження розв’язку оптимізаційної задачі на ЕОМ, а саме на базі математичного пакету Mathcad. Як бачимо, розглянуті методи не завжди дають точний результат, але його можна завжди легко покращити задавши інші початкові дані. Переваги таких методів в тому, що алгоритм розв’язку можна легко запрограмувати, а відповідна програма буде потребувати мало ресурсів і часу виконання на ЕОМ. Список використаної літератури
|