НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД. Лабораторна робота з Математичні методи дослідження операцій. Робота № 516968

НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

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

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

Рік:

2012

Тип роботи:

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

Предмет:

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

Група:

КН

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління / Лабораторна робота №10 з дисципліни “Математичні методи дослідження операцій” на тему «НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД.» Мета роботи: ознайомлення з задачами нелінійного програмування, набуття навиків їх розв’язку та аналізу графічним методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad. Порядок роботи: Короткі теоретичні відомості. Розв’язати графічно задану задачу нелінійного програмування. Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям графічного методу нелінійного програмування. Використовуючи засоби MathCad , розв’язати задану нелінійного програмування. Змінити умову задачі таким чином, щоб центр функції мети знаходився в області визначення і повторити пп. 2-4. Проінтерпретувати отримані результати для вихідної задачі. Хід Роботи Короткі теоретичні відомості Неліні́йне програмува́ння (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 - 5 )2 + 2 (x2 - 7)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 - 5 )2 + 2 (x2 - 7)2 = h Центр еліпса знаходиться в точці Q(9,8) , а півосі дорівнюють √h/4 і √h/2 відповідно.Зі зростанням еліпс збільшується(розширюється) і значенн цільової функції збільшується . Знайдемо hmin F(x1, x2) = 4 (x1 - 5 )2 + 2 (x2 - 7)2 =h (1) X1=7-x2 (2) Підставивши 2 рівність в 1 отримаєм : 4 ((7-x2) - 5 )2 + 2 (x2 - 7)2 =h 4 ((7-x2) 2 – 2(7-x2)*5+25 ) + 2 (x2 - 7)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. 2.2 Змінюю умову задачі таким чином, щоб центр функції мети знаходився в області визначення . Для h>0 F=h визначає на площині x1Ox2 еліпс. Ln : F= 4 (x1 - 3 )2 + 2 (x2 - 2)2 = h x1= 0;(вісь Оx2) x2= 0;( вісь Оx1) / Центр еліпса знаходиться в точці Q(3,2) , а півосі дорівнюють √h/4 і √h/2 відповідно.Зі зростанням еліпс збільшується(розширюється) і значенн цільової функції збільшується . Обчислюю по тому самому алгоритму що і в 2.1 Знайдемо hmin точка С має такі координати С(3,596; 3,088) Звідси підставивши значення у цільову функцію можна побачити що hmin =3.7883 Тепер можна знайти hmax підставивши всі інші значення в цільову функцію. hmax= 4*(0-3)^2+ 2*(7-2)^2 = 86 тобто максимум досягається у точці A(0,7). Розв’язок даної задачі з роз’ясненнями в Exel і MatCad подані у розділах 3 , 4. 3. Розв’язання за допомогою MS Exel. 3.1 Алгоритм розв’язку задачі в Exel Вписую в певні комірки свої рівняння. Відділяю певні комірки під певні точки перетину для наглядності. Створюю графік за домогою майстра графіків у MS Office 2010 Знаходжу max I min значення підставивши у певні комірки точки перетину і висначаю значення по визначеній формулі наприклад (=4*(K9-3)^2+ 2*(L9-2)^2) / Рис 1 Задача з еліпсом який знаходиться за границями ОДЗ / 4. Розв’язання за допомогою математичного пакету програм MathCad 4.1 Задача в якій центр функції мети знаходиться за границями ОДЗ. Записуємо умову: Умова: 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. Перетворення: x2 = 2 – 3/2*x1 x2 = 7 – x1; x2 = 11 –11/5*x1; Алгоритм розв’язку в MatCad Cпочатку потрібно вести рівняння обмежуючих пямих в область розв’язку. Далі на панелі інструментів вибрати інструмент graph. Зробити межі по x і по y . Вийти в область і натиснути Пробіл на клавіатурі. За допомогою функцій обчислення задач НЛП які вбудовані в Matcad вписати цільову функцію . За допомогою «given» в Matcad і обмежуючих прямих знайти значення які потрібні (за допомогою функцій «minimize» або «maximize»). Графіки обмежуючих прямих: / Рис 1 Задача з еліпсом який знаходиться за границями ОДЗ . Отже, мінімальне значення цільова функція досягає в точці з координатами min (3,596 ; 3,088), а максимальне – в точці (0; 3) 4.2 Задача в якій центр функції мети знаходиться в ОДЗ. / Отже, мінімальне значення цільова функція досягає в точці з координатами (3;2), а максимальне – в точці (0; 7) Висновок: я ознайомився з задачами нелінійного програмування, набув навиків їх розв’язку та аналізу графічним методом, вивчив та оволодів навичками адресації та роботи з формулами в таблицях в Еxcel, вивчив та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad.

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

savruksergiy

04.05.2012 18:41

Коментарі

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

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

поділитись