Лабораторна робота 11. Лабораторна робота з Математичні методи дослідження операцій. Робота № 525413

Лабораторна робота 11

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра автоматизованих систем управління

Інформація про роботу

Рік:

2013

Тип роботи:

Лабораторна робота

Предмет:

Математичні методи дослідження операцій

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління / Лабораторна робота №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;

Лабораторна робота Математичні методи дослідження операцій

tinysinjka

27.12.2013 02:42

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись