Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ГРАФІЧНИЙ МЕТОД
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2025
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №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.
04.05.2012 18:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора