Тема «Математичне програмування»
Нелінійне програмування – випадок математичного програмування, у якому цільової функцією чи обмеженням є нелінійна функція.
Нелінійне програмування поділяється на:
- опукле програмування (функції опуклі);
- Квадратичне програмування (цільова функція f (x) – квадратична та увігнута).
Нелінійне програмування відрізняється за різними ознаками:
За кількістю локальних критеріїв цільової функції методи діляться:
По довжині вектора методи поділяються на:
- однопараметричні або одновимірні (n=1),
-багатопараметричні або багатовимірні (n>1).
За наявності обмежень методи поділяються на:
- без обмежень (безумовна оптимізація),
- З обмеженнями (умовна оптимізація).
За типом інформації, що використовується в алгоритмі пошуку екстремуму:
- методи прямого пошуку, тобто. методи, у яких під час пошуку екстремуму цільової функції використовуються лише її значення;
- градієнтні методи першого порядку, у яких під час пошуку екстремуму функції використовуються значення перших похідних;
- градієнтні методи другого порядку, у яких під час пошуку екстремуму функції поруч із першими похідними використовують і другі похідні.
2.1 Випукло програмування
Випукло програмування – це завдання нелінійного програмування, яка має всі функції опуклими функціями. Таким чином, завдання опуклого програмування є завданням мінімізації опуклої функції на опуклій множині, утвореній системою опуклих нерівностей.
Визначення: Функція , задана на опуклій множині X, називається опуклою, якщо для будь-яких двох точок з X і будь-якого виконується співвідношення
(4)
Визначення: Функція, задана на опуклій множині X, називається увігнутою, якщо для будь-яких двох точок з X і будь-якого виконується співвідношення
(5)
Якщо нерівності (4) і (5) вважати строгими вони виконуються при , то функція є строго опуклою (суворо увігнутою). Випуклість і увігнутість функцій визначається лише щодо опуклих множин.
Якщо , де , - опуклі (увігнуті) функції деякому опуклому множині , то функція f(x) - також опукла (увігнута) на X.
Основні властивості опуклих та увігнутих функцій:
1. Безліч точок мінімуму опуклої функції, заданої на опуклій множині, - опукло.
2. Нехай f(x) - опукла функція, задана на замкнутій опуклій множині. Тоді локальний мінімум f(x) на X є глобальним.
3. Якщо глобальний мінімум досягається у двох різних точках, то він досягається і в будь-якій точці відрізка, що з'єднує ці точки.
4. Якщо - суворо опукла функція, її глобальний мінімум на опуклому множині X досягається у єдиній точці.
5. Нехай функція f(x) - опукла функція, задана на опуклій множині X, і, крім того, вона безперервна разом зі своїми похідними приватними першого порядку у всіх внутрішніх точках X. Нехай - точка, в якій . Тоді в точці досягається локальний мінімум, що збігається з глобальним мінімумом.
6. Безліч точок глобальних (отже, і локальних) мінімумів опуклої функції , заданої на обмеженому замкнутому опуклому множині X, включає хоча б одну крайню точку; якщо безліч локальних мінімумів включає у собі хоча б одну внутрішню точку множини X, є функцией-константой.
2.2 Квадратичне програмування
Квадратичне програмування - особливийтип оптимізаційної задачі. Це завдання оптимізації (зведення до мінімуму або максимуму) квадратичної функції кількох змінних при лінійних обмеженнях на ці змінні.
До завдань квадратичного програмування відносять спеціальний клас задач НП, для яких цільова функціяf(x)- квадратична та увігнута (або опукла) а всі обмеження лінійні.
Для вирішення задач квадратичного програмування призначена функція quadprog.
Приклад задач нелінійного програмування можна переглянути у додатку 2.
3 Цілочисленне програмування.
Цілочисне програмування– один з наймолодших, перспективних і швидко розвиваються розділів математичного програмування. Можна перерахувати велику кількість різноманітних завдань планування економіки, організації виробництва, дослідження конфліктних ситуацій, синтезу схем автоматичного регулювання, які формально зводяться до вибору найкращих, у певному сенсі, значень параметрів із певної дискретної сукупності заданих величин. До них можна віднести і екстремальні комбінаторні завдання, що виникають у різних розділах дискретної математики.
Завдання та способи, які стосуються перерахованого кола питань, у літературі називаються по-різному. Найбільшого поширення набув термін «цілочисленне програмування», проте трапляються й такі як «дискретне програмування», рідше «комбінаторне програмування».
p align="justify"> Найбільш вивченими завданнями цього класу є цілочисельні завдання лінійного програмування, в яких на всі змінні (або на їх частину) накладено додаткову вимогу ціле чисельності. Від них прийнято відрізняти так звані дискретні завдання лінійного програмування, в яких областьдопустимої зміни кожної змінної - не безліч цілих невід'ємних чисел, а деяке задане кінцеве безліч.
Цілочисленні завдання математичного програмування можуть бути різними шляхами.
1. Існують завдання лінійного програмування, які формально до цілих не відносяться, але при відповідних вихідних даних завжди мають цілий план. Приклади таких завдань – транспортне завдання та його модифікації (завдання про призначення, про потоки в мережах).
2. Поштовхом до вивчення цілих завдань у сенсі слова стало розгляд завдань лінійного програмування, у яких змінні представляли фізично неподільні величини. Вони були названі завданнями з неподільністю. Такі, наприклад, завдання про оптимізацію комплексу засобів доставки вантажів, про знаходження мінімального порожнього пробігу автомобілів при виконанні заданого плану перевезень, про визначення оптимального машинного парку та його оптимального розподілу за вказаними роботами за умови мінімізації сумарної вартості (машинного парку та робіт), про знаходження мінімальної кількості судів для здійснення цього графіка перевезень тощо.
3. Іншим важливим поштовхом до побудови теорії цілісного програмування став їх потрібно знайти екстремум цілої лінійної функції, заданої на кінцевій множині елементів. Такі завдання прийнято називати завданнями з альтернативними змінними. Як приклади можна назвати завдання комівояжера (бродячого торговця), про оптимальне призначення, теорію розкладу, або календарного планування, та завдання з додатковими логічними умовами (наприклад, типу «або – або», «якщо – то» тощо) .
Тоді математична модель набуде наступного вигляду:
за умов
Цілочисленне програмування включає:
- умовну оптимізацію (пошук мінімуму функції однієї змінної для фіксованого інтервалу коли x, x1 і x2 є скаляри, а f(x) - функція, яка повертає скаляр);
- Безумовну оптимізацію (f(x) – функція, що повертає скаляр).
Оптимізація - в математиці, інформатиці та дослідженні операцій завдання знаходження екстремуму (мінімуму або максимуму) цільової функції в деякій області кінцевого векторного простору, обмеженої набором лінійних та/або нелінійних рівностей та/або нерівностей.
Щоб коректно поставити завдання оптимізації, необхідно задати:
Допустиме безліч - безліч;
Цільову функцію - відображення;
Критерій пошуку (max чи min).
Тоді розв'язати завдання означає одне з:
Показати, що цільова функція не обмежена знизу.