Подякувати Студентському архіву довільною сумою
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. Знайти координати точки оптимуму і визначити в ній значення ЦФ.
Відзначимо, що на відміну від завдання ЛП точка оптимуму в задачі НП не обов'язково знаходиться на границі ОДЗ. Нею також може бути внутрішня точка цієї множини.
Метод множників Лагранжа.
Метод дозволяєзнаходити максимум абомінімумфункції при обмеженняхрівностях. Основнаідея метода полягає в переходівідзадачі на умовнийекстремум до задачізнаходженнябезумовногоекстремумадеякоїспеціальнопобудованоїфункції Лагранжа.
Постановка задачі
Розв’язати задачу дробово-лінійного програмування графічно і симплексним методом.
Варіант 73
F(x1,x2) = (x1 - 9)2 + (x2 - 8)2min, max
x1 + x2= 8,
x1 0, x2 0.
2. Розв’язатиграфічнозадану задачу нелінійногопрограмування.
Областю допустимих значень є багатокутник ABCDE, який обмежений відрізками прямих.
L1- 3x1+ 2x2 = 6,
L2- x1 + x2 = 8
L3- 11x1 + 5x2 = 55
x1= 0;(вісь Оx2) x2= 0;( вісь Оx1)
/
Для h>0 F=hвизначає на площині x1Ox2 коло.
Ln :F= (x1 - 9 )2 + (x2 - 8)2= h
Центр кола знаходиться в точці Q(9,8) , відповідно зі зростанням значень коло збільшується(розширюється) і значення цільової функції збільшується .
Знайдемо hmin
F(x1, x2) = (x1 - 9 )2 + (x2 - 8)2 =h (1)
х1=8 – x2 (2)
Підставивши 2 рівність в 1 отримаємо :
X2 – 18x + 81 + y2 – 16y +64 = R2
X2 – 18x + 81 + (8 - x)2 – 16(8 - x) +64 = R2
X2 – 18x +81 + 64 – 16x + x2 – 128 + 16x – 64 = R2
2x2 – 18x – 47 = R2
X= 11.11
Y = -3.11
отже радіус кола 11.308
3.Розв’язанняаналітично задані задачу нелінійногопрограмування методом заміщення.
F(x1,x2) = (x1 - 9)2 + (x2 - 8)2min, max ;
x1 + x2 8,
x1 0, x2 0.
F(x1,x2) = (x1 - 9)2 + (x2 - 8)2min, max (1)
Знайду х1 через х2: х1=8-х2 (2)
Підставлю (2) в функцію (1):
F(x1,x2) = ((8 - x2) - 9)2 + (x2 - 8)2 = 2x22 – 14x2 + 65
F’ = 0
F’(x2) = 4x2 – 14 => x2 = 3,5
Знайдемо знак похідної зліва і справа від стаціонарної точки:
F’(3) <0
F’(4)<0
Отже в точці x2 = 3,5 досягається Max.
З системи рівнянь знаходимо x1= 8 –3.5 = 4.5
F(4.5 ; 3.5) = 40.5
4. Розв’язання задачінелінійногопрограмування методом множників Лагранжа.
ЗнайдемоекстремумфункціїF(X) = (x1-9)2+(x2-8)2 , використовуючифункціюЛагранжа:
де F (X) - цільовафункціявектораX φi(X) - обмеженнявнеявномувигляді (i=1..n) В якостіцільовоїфункції, що підлягає оптимізації,вцій задачівиступаєфункція: F(X) = (x1-9)2+(x2-8)2 Перепишемообмеженнязавдання унеявномувигляді: СкладемодопоміжнуфункціюЛагранжа: НеобхідноюумовоюекстремумуфункціїЛагранжає рівністьнулюїїприватнихпохіднихза зміннимихiіневизначеномумножникуλ. Складемосистему: ∂L/∂x1 = 2•x1+λ-18 = 0
∂L/∂x2 = λ+2•(x2-8) = 0
∂F/∂λ = x1+x2-8 = 0
Метод Гаусса.
Запишемо систему у вигляді:
Додамо другий рядок до першого:
Домножемо другий рядок на (2). Домножемо третій рядок на (-1). Додамо третій рядок до другого:
Домножемо другий рядок на (-1). Додамо другий рядок до першого:
З першого рядка визначаємо x3
З другого рядка визначаємо x2
З третього рядка визначаємо x1
4. Розв’язання задачінелінійногопрограмування методом множників Лагранжа зі зміною обмеження.
Знайдемо екстремум функції F(X) = (x1-9)2+(x2-8)2, використовуючи функцію Лагранжа: де F (X) - цільова функція вектора X φi (X) - обмеження в неявному вигляді (i = 1 .. n) В якості цільової функції, що підлягає оптимізації, в цій задачі виступає функція: F(X) = (x1-9)2+(x2-8)2 Перепишемо обмеження завдання у неявному вигляді: Складемо допоміжну функцію Лагранжа: Необхідною умовою екстремуму функції Лагранжа є рівність нулю її приватних похідних за змінними хi і невизначеному множнику λ. Складемо систему: ∂L/∂x1 = 2•x1+λ-4 = 0
∂L/∂x2 = λ+2•x2-4 = 0
∂F/∂λ = x1+x2-8 = 0
Запишем систему в виде:
ПослідовнобудемовибиратидозволяєелементРЕ,якийлежитьна головнійдіагоналіматриці. Дозволяєелементдорівнює(2). Намісцідозволяєелементаотримуємо1, авсамомустовпцізаписуємонулі. Всііншіелементиматриці,включаючиелементистовпцяB, визначаютьсяза правиломпрямокутника. Дляцьоговибираємочотири числа, якірозташованіувершинахпрямокутника ізавждивключаютьдозволяєелементРЕ. НЕ=СЕ- (А * В)/РЕ РЕ-дозволяєелемент(2),Аі В- елементиматриці, щоутворюютьпрямокутникз елементамиСТЕіРЕ. Уявіморозрахуноккожногоелементау виглядітаблиці:
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
4 / -1 = -4
x1 = 4
x2 = 4
x3 = -4
6.Розв’язання за допомогоюMSExel.
/
Розв’язання за допомогою математичного пакету програм MathCad
Записуємо умову:
Умова:
F(x1, x2) = 4 (x1 - 9 )2 + 2 (x2 - 8)2min, max ;
x1 + x2 7,
x1 0, x2 0.
Перетворення:
x2 = 7 – x1;
27.12.2013 02:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора