Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. МЕТОД МНОЖНИКІВ ЛАГРАНЖА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
Лабораторна робота №11
з дисципліни “Математичні методи дослідження операцій”
на тему
“НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. МЕТОД МНОЖНИКІВ ЛАГРАНЖА”
Мета роботи: ознайомлення з задачами нелінійного програмування, набуття навиків їх розв’язку та аналізу методом множників Лагранжа, вивчення та оволодіння навиками адресації та роботи з формулами в таблицях в Еxcel та розв’язання оптимізаційних задач в середовищі MathCad.
Порядок роботи:
Короткі теоретичні відомості.
Розв’язати аналітично задану задачу нелінійного програмування графічним методом.
Розв’язати аналітично задану задачу нелінійного програмування методом заміщення.
Розв’язати аналітично задану задачу нелінійного програмування методом множників Лагранжа.
Замінити обмеження на (x1 - 2 )2 + (x2 - 2)2 = 1і повторити пп. 1-3.
Проінтерпретувати отримані результати для вихідної задачі.
Хід Роботи
Короткі теоретичні відомості
Неліні́йне програмува́ння (NLP, англ. NonLinear Programming) — випадок математичного програмування, у якому цільовою функцією чи обмеженнями є нелінійна функція.
Задача нелінійного програмування ставиться як задача знаходження оптимуму певної цільової функції при виконанні умов
,
де — параметри, — обмеження, n — кількість параметрів, s — кількість обмежень.
На відміну від задачі лінійного програмування в задачі нелінійного програмування оптимум не обов'язково лежить на границі області, визначеної обмеженнями.
Методи розв'язування задачі
Одним із методів, які дозволяють звести задачу нелінійного програмування до розв'язування системи рівнянь є метод невизначених множників Лагранжа.
Якщо цільова функція F є лінійною, а обмеженим простором є політоп, то задача є задачею лінійного програмування, яка може бути розв'язана за допомогою добре відомих рішень лінійного програмування.
Якщо цільова функція є угнутою (задача максимізації), або опуклою (задача мінімізації) і множина обмежень є опуклою, то задачу називають опуклою і в більшості випадків можуть бути використані загальні методи опуклої оптимізації.
Якщо цільова функція є відношенням увігнутих і опуклих функцій (у разі максимізації) і обмеження опуклі, то задача може бути перетворена в задачу опуклої оптимізації використанням технікдробового програмування.
Існують декілька методів для розв'язування неопуклих задач. Один підхід полягає у використанні спеціальних формулювань задач лінійного програмування. Інший метод передбачає використання методів гілок і меж, де задача поділяється на підкласи, щоби бути розв'язаною з опуклими (задача мінімізації) або лінійними апроксимаціями, які утворюють нижню межу загальної вартості у межах поділу. При наступних поділах у певний момент буде отримано фактичний розв'язок, вартість якого дорівнює найкращій нижній межі, отриманій для будь-якого з наближених рішень. Цей розв'язок є оптимальним, хоча, можливо, не єдиним. Алгоритм можна також припинити на ранній стадії, з упевненістю, що оптимальний розв'язок знаходиться в межах допустимого відхилення від знайденої кращої точки; такі точки називаються ε-оптимальними. Завершення біля ε-оптимальних точок, як правило, необхідне для забезпечення скінченності завершення. Це особливо корисно для великих, складних задач і задач з невизначеними витратами або значеннями, де невизначеність може бути оцінена з відповідної оцінки надійності.
Графічний метод розв’язку задач нелінійного програмування
Графічний метод можна використовувати для вирішення задачі НЛП, яка містить дві змінні х1 і х2, наприклад завдання такого вигляду:
Z = f(x1, x2) → min (max);
gi(x1, x2) ≤ bi, .
Щоб знайти її оптимальне рішення, потрібно виконати наступні дії:
1. Знайти ОДЗ, яка визначається обмеженнями завдання. Якщо виявиться, що ця область порожня, то це означає, що задача не має рішення.
2. Побудувати сімейство ліній рівня цільової функції f (х1, х2) = C при різних значеннях числового параметра С.
3. При виконанні завдання на мінімум визначити напрямок зменшення, а для задачі на максимум - напрям зростання ліній рівня ЦФ.
4. Знайти точку ОДЗ, через яку проходить лінія рівня з найменшим в задачі на мінімум (відповідно, найбільшим в завдання на максимум) значенням параметра С. Ця точка буде оптимальним рішенням. Якщо ЦФ не обмежена знизу в задачі на мінімум (зверху - в задачі на максимум), то це означає, що задача не має оптимального рішення.
5. Знайти координати точки оптимуму і визначити в ній значення ЦФ.
Відзначимо, що на відміну від завдання ЛП точка оптимуму в задачі НП не обов'язково знаходиться на границі ОДЗ. Нею також може бути внутрішня точка цієї множини.
Метод множників Лагранжа.
Метод дозволяє знаходити максимум або мінімум функції при обмеженнях рівностях. Основна ідея метода полягає в переході від задачі на умовний екстремум до задачі знаходження безумовного екстремума деякої спеціально побудованої функції Лагранжа.
Постановка задачі
Розв’язати задачу дробово-лінійного програмування графічно і симплексним методом.
Варіант 32
F(x1, x2) = 4 (x1 - 5 )2 + 2 (x2 - 7)2 min, max ;
x1 + x2 = 7,
x1 0, x2 0.
2. Розв’язати графічно задану задачу нелінійного програмування.
2.1
Областю допустимих значень є трикутник ABC , який обмежений осями Ox1 Ox2 та відрізком прямої x1 + x2 = 7.
x1= 0;(вісь Оx2) x2= 0;( вісь Оx1)
Для h>0 F=h визначає на площині x1Ox2 коло.
Ln : F= 4 (x1 - 5 )2 + 2 (x2 - 7)2 = h
Центр кола знаходиться в точці Q(5,7) , зі зростанням коло збільшується(розширюється) і значення цільової функції збільшується .
Знайдемо hmin
F(x1, x2) = (x1 - 8 )2 + (x2 - 9)2 =h (1)
X1=8-x2 (2)
Підставивши 2 рівність в 1 отримаєм :
(8-x2-8)2+( x2 - 9)2 =h
X22+ X22-18x2+81=h
2 X22-18x2+81=h
x1=x1’ =3.5
x2=x2’ =4.5
отже точка D має такі координати D(3.5; 4.5)
Звідси підставивши значення у цільову функцію можна побачити що
hmin =40.5
Тепер можна знайти hmax підставивши всі інші значення в цільову функцію.
hmax= 145 тобто максимум досягається у точці A(0,0) .
3.Розв’язання аналітично заданої задачі нелінійного програмування методом заміщення.
Умова
Варіант 74
F(x1, x2) = (x1 - 8 )2 + (x2 - 9)2 min, max ;
x1 + x2 <= 8,
x1 0, x2 0.
F(x1, x2) = (x1 - 8 )2 + (x2 - 9)2 (1)
Знайду x1 через x2
x1 = 8-x2(2)
Підставлю (2) в функцію (1).
F=(8-x2-8) 2+(x2-9) 2=2x22-18x2+81
F’=0 , 4x2-18=0
x2=9/2
Звідси можу знайти x1.
X1=8-9/2=7/2;
A(7/2;9/2)
Розв’язання зі зміною цільової функції на (x1-2)2+(x2-2)2=1;
Знайду x1 через x2
x1 = 8-x2(2)
Підставлю (2) в функцію (1).
F= (8-x2-2)2+(x2-2)2=2x22-16x2+40
F’=0; 4x2-16=1
x2=17/4 Тому x1=15/4
4. Розв’язання задачі нелінійного програмування методом множників Лагранжа.
4.1 Розв’язування стандартної функції мети.
Знайдемо екстремум функції F (X) = 4 • (х 1 до 5) 2 +2 • (х 2 -7) 2, використовуючи функцію Лагранжа:
Де
В якості цільової функції, що підлягає оптимізації, в цій задачі виступає функція:
F (X) = 4 • (х 1 до 5) 2 +2 • (х 2 -7) 2
Перепишемо обмеження завдання у неявному вигляді:
Складемо допоміжну функцію Лагранжа:
Необхідною умовою екстремуму функції Лагранжа є рівність нулю її приватних похідних за змінними х я і невизначеному множнику λ.
Складемо систему:
∂ L / ∂ х 1 = 8 • х 1 + λ-40 = 0
∂ L / ∂ х 2 = λ +4 • (х 2 -7) = 0
∂ F / ∂ λ = х 1 + х 2 -7 = 0
Систему можна вирішити методом Гаусса
Метод Гаусса.
Запишемо систему у вигляді:
Для зручності обчислень поміняємо рядки місцями:
Додамо 2-й рядок до 1-ої:
Помножимо другого рядка на (8). Помножимо 3-й рядок на (-1). Додамо 3-й рядок до 2-ой:
Помножимо 1-у рядок на (2). Помножимо другого рядка на (-1). Додамо 2-й рядок до 1-ої:
З 1-го рядка висловлюємо х 3
З 2-го рядка висловлюємо х 2
З 3-го рядка висловлюємо х 1
6. Розв’язання за допомогою MS Exel.
Рис 1 Задача з колом, що знаходиться за межами ОДЗ
Розв’язання за допомогою математичного пакету програм MathCad
Записуємо умову:
Умова:
F(x1, x2) = (x1 - 8 )2 + (x2 - 9)2 min, max ;
x1 + x2 8,
x1 0, x2 0.
Перетворення:
x2 = 8 – x1;
Графіки обмежуючих прямих:
Висновок: виконуючи цю лабораторну роботу я ознайомився з задачами нелінійного програмування, набув навиків їх розв’язку та аналізу методом множників Лагранжа, вивчив та оволодів навиками адресації та роботи з формулами в таблицях в Еxcel та розв’язання оптимізаційних задач в середовищі MathCad.
04.05.2012 18:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора