Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота 11
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
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. Знайти координати точки оптимуму і визначити в ній значення ЦФ.
Відзначимо, що на відміну від завдання ЛП точка оптимуму в задачі НП не обов'язково знаходиться на границі ОДЗ. Нею також може бути внутрішня точка цієї множини.
Метод множників Лагранжа.
Метод дозволяє знаходити максимум або мінімум функції при обмеженнях рівностях. Основна ідея метода полягає в переході від задачі на умовний екстремум до задачі знаходження безумовного екстремума деякої спеціально побудованої функції Лагранжа.
Постановка задачі
Розв’язати задачу дробово-лінійного програмування графічно і симплексним методом.
Варіант 48
F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 min, max ;
3x1 + 2x2 6,
x1 + x2 7,
11x1 + 5x2 55,
x1 0, x2 0.
2. Розв’язати графічно задану задачу нелінійного програмування.
2.1
Областю допустимих значень є багатокутник ABCDE , який обмежений відрізками прямих.
L1- 3x1 + 2x2 = 6,
L2- x1 + x2 = 7
L3- 11x1 + 5x2 = 55
x1= 0;(вісь Оx2) x2= 0;( вісь Оx1)
/
Для h>0 F=h визначає на площині x1Ox2 еліпс.
Ln : F= 4 (x1 - 9 )2 + 2 (x2 - 8)2 = h
Центр еліпса знаходиться в точці Q(9,8) , а півосі дорівнюють √h/4 і √h/2 відповідно.Зі зростанням еліпс збільшується(розширюється) і значенн цільової функції збільшується .
Знайдемо hmin
F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 =h (1)
X1=7-x2 (2)
Підставивши 2 рівність в 1 отримаєм :
4 ((7-x2) - 9 )2 + 2 (x2 - 8)2 =h
4 ((7-x2) 2 – 2(7-x2)*9+81 ) + 2 (x2 - 8)2 =h
4 (4+4x2+x22)+ 2 (x22 - 16x2+64)2 =h
16+16x2+6x22 -32x2+128=h
142-16x2+6x2 =h
x1=x1’ =3,596
x2=x2’ =3,088
отже точка С має такі координати С(3,596; 3,088)
Звідси підставивши значення у цільову функцію можна побачити що
hmin =165.052
Тепер можна знайти hmax підставивши всі інші значення в цільову функцію.
hmax= (81*4+50)=374 тобто максимум досягається у точці A(0,3).
Розв’язок даної задачі з роз’ясненнями в Exel і MatCad подані у розділах 3 , 4.
3.Розв’язання аналітично задані задачу нелінійного програмування методом заміщення.
Умова
Варіант 48
F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 min, max ;
x1 + x2 = 7,
x1 0, x2 0.
F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 (1)
Знайду x1 через x2
x1 = 7-x2(2)
Підставлю (2) в функцію (1).
F=4*((7-x2)-9)2+2(x2-8)2=56-8x2-72+4x2+32=16-4x2
F’=0 , 16-4x2=0
-x2=4/16; x2=-1/4
Звідси можу знайти x1.
X1=7+1/4=29/4;
A(29/4;-1/4)
Розв’язання зі зміною цільової функції на (x1-2)2+(x2-2)2=1;
Знайду x1 через x2
x1 = 7-x2(2)
Підставлю (2) в функцію (1).
F= ((7-x2)-2)2+(x2-2)2=14-2x2-4+2x2-4=6
-x2=0 Тому x1=7
4. Розв’язання задачі нелінійного програмування методом множників Лагранжа.
4.1 Розв’язування стандартної функції мети.
Знайдемо екстремум функції F (X) = 4 • (x1-9) 2 +2 • (x2-8) 2, використовуючи функцію Лагранжа:
де F (X) - цільова функція вектора X
φi (X) - обмеження в неявному вигляді (i = 1 .. n)
В якості цільової функції, що підлягає оптимізації, в цій задачі виступає функція:
F(X) = 4•(x1-9)2+2•(x2-8)2
Перепишемо обмеження завдання у неявному вигляді:
Складемо допоміжну функцію Лагранжа:
∂L/∂x1 = 8•x1+λ-72 = 0
∂L/∂x2 = λ+4•x2-327 = 0
∂F/∂λ = x1+x2-7 = 0
Систему можна вирішити методом Жордана - Гаусса
Запишемо систему у вигляді:
Послідовно будемо вибирати дозвільний елемент ДЕ, який лежить на головній діагоналі матриці.
Дозвільний елемент дорівнює (8).
На місці ДЕ отримуємо 1, а в самому стовпці записуємо нулі.
Всі інші елементи матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають ДЕ.
Покажемо розрахунок кожного елемента у вигляді таблиці:
x1
x2
x3
B
8 / 8 = 1
0 / 8 = 0
1 / 8 = 0.13
72 / 8 = 9
ДЕ дорівнює (4).
На місці ДЕ отримуємо 1, а в самому стовпці записуємо нулі.
Всі інші елементи матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають дозволяє ДЕ.
Покажу розрахунок кожного елемента у вигляді таблиці:
x1
x2
x3
B
0 / 4 = 0
4 / 4 = 1
1 / 4 = 0.25
32 / 4 = 8
ДЕ дорівнює (-0.38).
На місці ДЕотримуємо 1, а в самому стовпці записуємо нулі.
Всі інші елементи матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають ДЕ.
Покажу розрахунок кожного елемента у вигляді таблиці:
x1
x2
x3
B
0 / -0.38 = 0
0 / -0.38 = 0
-0.38 / -0.38 = 1
-10 / -0.38 = 26.67
x1 = 5.67
x2 = 1.33
λ = 26.67
4.2 Розв’язання задачі НЛП методом множників Лагранжа зі зміною обмеження.
Умова
F(X) = 4•(x1-9)2+2•(x2-8)2
(x1-2)2+(x2-2)2=1
Знайдемо екстремум функції F (X) = 4 • (x1-9) 2 +2 • (x2-8) 2, використовуючи функцію Лагранжа:
де F (X) - цільова функція вектора X
φi (X) - обмеження в неявному вигляді (i = 1 .. n)
В якості цільової функції, що підлягає оптимізації, в цій задачі виступає функція:
F(X) = 4•(x1-9)2+2•(x2-8)2
Перепишемо обмеження завдання у неявному вигляді:
Складемо допоміжну функцію Лагранжа:
∂L/∂x1 = 2•x1+λ-4 = 0
∂L/∂x2 = λ+2•x2-4 = 0
∂F/∂λ = x1+x2-7 = 0
Систему можна вирішити методом Жордана – Гаусса
Запишемо систему у вигляді:
Послідовно будемо вибирати дозвільний елемент ДЕ, який лежить на головній діагоналі матриці.
Дозвільний елемент дорівнює (2).
На місці ДЕ отримуємо 1, а в самому стовпці записуємо нулі.
Всі інші елементи матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають ДЕ.
Покажемо розрахунок кожного елемента у вигляді таблиці:
x1
x2
x3
B
2 / 2 = 1
0 / 2 = 0
1 / 2 = 0.5
4 / 2 = 2
Послідовно будемо вибирати дозвільний елемент ДЕ, який лежить на головній діагоналі матриці.
Дозвільний елемент дорівнює (2).
На місці ДЕ отримуємо 1, а в самому стовпці записуємо нулі.
Всі інші елементи матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають ДЕ.
Покажемо розрахунок кожного елемента у вигляді таблиці:
x1
x2
x3
B
0 / 2 = 0
2 / 2 = 1
1 / 2 = 0.5
4 / 2 = 2
Послідовно будемо вибирати дозвільний елемент ДЕ, який лежить на головній діагоналі матриці.
Дозвільний елемент дорівнює (-1).
На місці ДЕ отримуємо 1, а в самому стовпці записуємо нулі.
Всі інші елементи матриці, включаючи елементи стовпця B, визначаються за правилом прямокутника.
Для цього вибираємо чотири числа, які розташовані у вершинах прямокутника і завжди включають ДЕ.
Покажемо розрахунок кожного елемента у вигляді таблиці:
x1
x2
x3
B
0 / -1 = 0
0 / -1 = 0
-1 / -1 = 1
3 / -1 = -3
x1 = 3.5
x2 = 3.5
λ = -3
6. Розв’язання за допомогою MS Exel.
/
Рис 1 Задача з еліпсом який знаходиться за границями ОДЗ
Розв’язання за допомогою математичного пакету програм MathCad
Записуємо умову:
Умова:
F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2 min, max ;
x1 + x2 7,
x1 0, x2 0.
Перетворення:
x2 = 7 – x1;
Графіки обмежуючих прямих:
/
Висновок: ознайомився з задачами нелінійного програмування, набув навиків їх розв’язку та аналізу методом множників Лагранжа, вивчив та оволодів навиками адресації та роботи з формулами в таблицях в Еxcel та розв’язання оптимізаційних задач в середовищі MathCad.
27.12.2013 02:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора