Дослідження систем на основі моделей математичного програмування
З метою оптимізації структури та процесу функціонування системи доцільно використовувати моделі математичного програмування, які за своїми функціональними ознаками складаються з цільової функції (критерій оптимізації) та відповідної системи обмежень, що враховує технічні, технологічні, правові та інші умови.
У першому наближенні, коли цільову функцію та систему обмежень можливо представити у вигляді лінійних залежностей, виникає задача лінійного програмування, стандартним виглядом якої є:
– цільова функція
– система обмежень
; 
– коефіцієнти; 
; 
– невідомі змінні.
Матричний вигляд моделі є наступним:
де 
– матриця коефіцієнтів;
– скалярний добуток вектору Х та вектору С.
Для вирішення цієї задачі використовують сімплекс-метод. Якщо система рівнянь та обмежень сумісна, а область припустимих рішень закрита, то задача має, як правило, єдине рішення.
У випадку, коли невідомі 
можуть приймати тільки цілі значення, тобто система функціонує у дискретному фазовому просторі, виникає задача лінійного цілочисельного програмування:
Зокрема такі задачі є актуальними при виборі варіантів структури системи (проекту), а також у плануванні та управлінні, якщо для всієї сукупності можливих проектів існують спільні обмеження по ресурсах. В задачах вибору варіантів змінні можуть приймати тільки одне з двох значень: 
. Значення 
означає, що проект з номером 
включаємо до плану, а 
– що проект з номером відкидаємо. У якості прикладу, розглянемо задачу вибору оптимальних варіантів розміщення та спеціалізації системи підприємств окремої галузі промисловості. Вона зводиться до наступної моделі лінійного цілочисельного програмування:
|
|
|
при обмеженнях:
,
де k – номер підприємства; j – номер варіанту його будівництва або реконструкції;
mk – кількість варіантів будівництва або реконструкції підприємства;
i – вид продукції, що виробляється;
- обсяг випуску і-го виду продукції на k-му підприємстві при j – му варіанті;
- потреба в і-му виді продукції;
- приведені витрати, що відповідають j-му варіанту розвитку
k-го підприємства.
означає, що для k-го підприємства обирається j-й варіант.
Процедура вирішення задач цілочисельного програмування значно складніша за процедуру вирішення задач лінійного програмування, що обумовлено дискретним характером множини припустимих рішень. Існує ряд методів для вирішення задач цього класу.
Перша група методів – це методи відсічення (зокрема, метод Гоморі), що представляють собою послідовність розширених задач лінійного програмування з додатковими обмеженнями у вигляді гіперплощин, які відсікають нецілочисельні рішення. Ці методи характеризуються значною трудоємністю.
|
|
|
Друга група – це методи комбінаторного аналізу, що представлені операціями відбирання підмножин та упорядкованості елементів. Найбільш ефективним з них є метод гілок та границь.
Третя група – наближені методи, які мають найбільш практичне значення, але прив’язані до специфіки задач. Ці методи умовно підрозділяють на евристичні методи та методи випадкового пошуку.
Якщо при оптимізації структури та процесу функціонування системи неможливо знехтувати нелінійностями в цільовій функції та в системах обмежень, для дослідження системи доцільно використовувати моделі нелінійного програмування. Зокрема, ці моделі більш адекватно описують функціонування транспортної системи в умовах коливань на ринку транспортних послуг та наявності конкурентного середовища.
При формуванні логістичних систем, які включають такі підсистеми, як підприємство – виробник матеріального потоку, транспортні компанії, що реалізують принципи «точно в строк», та «від дверей до дверей», підприємство – споживач та ін., виникає задача оптимізації технічних і технологічних параметрів елементів системи. Ці задачі вирішують шляхом максимізації синергетичного ефекту логістичної системи. При цьому критерієм оптимізації, як правило, виступає нелінійна адитивна цільова функція, яка представляє собою сумарні експлуатаційні витрати по кожній ланці логістичного ланцюга, що припадають на одиницю матеріального потоку, а у якості системи обмежень виступають нормативні, технічні, технологічні та правові умови. Тобто формально вирішують задачу нелінійного програмування.
|
|
|
Задачі нелінійного програмування виникають тоді, коли або цільова функція, або система обмежень, або разом цільова функція і система обмежень є нелінійними. Формально ці задачі мають наступний вигляд:
- нелінійна
При обмеженнях:
Наявність нелінійностей значно ускладнює вирішення задач цього класу в порівнянні із задачами лінійного програмування. Так, нелінійність в системі обмежень призводить до того, що область припустимих рішень може бути не опуклою та мати нескінченну множину кутових точок. Нелінійна цільова функція 
може досягати свого екстремуму не тільки на границі області припустимих рішень, але й у середині неї та мати декілька локальних екстремумів.
|
|
|
Ці особливості обумовлюють те, що задачі нелінійного програмування не мають загальних методів вирішення аналогічних сімплекс-методу для задач лінійного програмування. Але існує цілий ряд приватних методів для вирішення такого типу задач.
Якщо цільова функція представлена поліномом другого ступеню, а система обмежень є лінійною, то виникає задача квадратичного програмування, яка має процедуру вирішення, що завжди сходиться. В інших випадках можливо використовувати аналітичний метод множників Лагранжа або чисельні методи.
Метод множників Лагранжа є найбільш потужним класичним методом для вирішення задач нелінійного програмування, але він має обмежену область застосування, бо потребує наявності наступних умов: система обмежень повинна бути представлена у вигляді рівностей 
; відсутня умова 
функції 
та 
повинні бути неперервними разом зі своїми частковими похідними. Для вирішення вводять набір змінних 
, які називають множниками Лагранжа. Складають функцію Лагранжа вигляду: 
. Далі знаходять часткові похідні: 
та 
та вирішують систему з n+m рівнянь:
Серед рішень системи рівнянь знаходять точку, в якій 
досягає свого екстремуму.
Чисельні методи (метод релаксації, метод градієнту, метод найшвидшого підйому) дозволяють знайти оптимальне рішення задачі із заданою похибкою. Ці методи можуть бути реалізовані в середовищі MathCAD або Matlab.
Якщо система за обумовленістю взаємодії є стохастичною, то для її оптимізації використовують моделі стохастичного програмування. Задача стохастичного програмування виникає тоді, коли параметри або змінні в цільовій функції або в системі обмежень носять невизначений (імовірнісний) характер і представлені функціями розподілу, щільностями розподілу або функціями приналежності. Цей клас задач вирішують виключно чисельними методами на ПЕОМ, а результати рішення представляють поверхнею відгуку.
Дата добавления: 2018-02-15; просмотров: 797; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!