Xreferat.com » Рефераты по математике » Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

нелінійних оптимізаційних задач та задач лінійного цілочислового програмування" width="153" height="43" align="BOTTOM" border="0" />. Для цього спочатку знайдемо частинні похідні першого і другого порядку від функції Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування:


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


Отже матриця Гессе матиме вигляд:


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

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

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

Задачу такого типу можна розв’язувати методом Франка-Вулфа. Цей метод відноситься до групи градієнтних методів.

Розглянемо задачу:


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


Алгоритм методу Франка-Вулфа:

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

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

Будують функцію Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування і розв’язують задачу максимізації для функції Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування в області 2-3, тобто таку задачу:


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Нехай Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування - оптимальний розв’язок задачі 4,2,3.

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

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

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

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

Розв’яжемо за допомогою симплекс методу задачу:


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


оптимізаційний одновимірний мінімізація дихотомія ньютон


і Базис Сб В 4 2 0 0




А1 А2 А3 А4
1 А3 0 21 3 7 1 0
2 А4 0 1 1 -1 0 1
3 0 - 4 -2 0 0
1 А3 0 18 0 10 1 -3
2 А1 4 1 1 -1 0 1
3 8 0 -6 0 4
1 А2 2 9/5 0 1 1/10 -3/10
2 А1 4 14/5 1 0 1/10 7/10
3 74/5 0 0 3/5 11/5

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


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


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

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

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.

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

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування.

Знаходимо за допомогою симплекс-методу максимум функції


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


і Базис Сб В 3 6/5 0 0




А1 А2 А3 А4
1 А3 0 21 3 7 1 0
2 А4 0 1 1 -1 0 1
3 0 - 3 -6/5 0 0
1 А3 0 18 0 10 1 -3
2 А1 3 1 1 -1 0 1
3 3 0 -21/5 0 3
1 А2 6/5 9/5 0 1 1/10 -3/10
2 А1 3 14/5 1 0 1/10 7/10
3 264/5 0 0 21/50 87/50

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


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


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

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

Цей метод відноситься до групи непрямих методів розв’язання задач нелінійного програмування виду:


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування


Він зводить задачу з обмеженнями в послідовність задач безумовної оптимізації деяких допоміжних функції. Останні отримуються шляхом модифікації цільової функції за допомогою функій-обмежень таким чином, щоб обмеження в явному вигляді в задачі оптимізації не фігурували. Це забезпечує можливість застосування методів безумовної оптимізації. В загальному випадку допоміжна функція має вигляд: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування, де функція Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування визначається з обмежень вихідної задачі і називається штрафною функцією. Необхідно, щоб при порушенні обмеження вона “штрафувала” функцію Z, тобто збільшувала її значення. В такому випадку Z буде знаходитися всередині області обмежень. Штрафну функцію можна будувати різними способами. Розглянемо один з варіантів, коли Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування, де Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування, Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування- параметр штрафної функції.

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

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

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

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

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

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


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

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


Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

За точність обчислень оберемо Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування ,

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: