Параметричне програмування
Параметричне програмування (англ. Parametric Programming) – це розділ математичного програмування, пов'язаний із дослідженням оптимальних розв'язків на стійкість щодо зміни вихідних даних. Розроблене паралельно аналізу чутливості, параметричне програмування вперше було згадане в дисертації 1952 року[1]. Параметричне програмування пов'язане з прогнозною моделлю контролю, створення якої у 2000 році сприяло підвищенню інтересу до даної теми[2][3].
Загальна задача лінійного програмування
містить сталі величини: коефіцієнти , і вільні члени . З одного боку, у практичних ситуаціях ці величини змінюються, з іншого, знайшовши оптимальний план деякої задачі за фіксованих значень , ,, потрібно знати, в яких допустимих межах їх можна змінювати, щоб план залишався оптимальним.
Тому виникає необхідність досліджень поведінки оптимального розв'язку задачі лінійного програмування при зміні її коефіцієнтів і вільних членів. Ці дослідження складають предмет параметричного програмування.
Параметричне програмування виникло у зв'язку з вирішенням завдань планування виробництва і є основою оптимального планування різних економічних процесів.
Якщо величини змінні, то це можна пов'язати з коливаннями цін на товар, із змінами витрат на виробництво та змінами прибутку за одиницю продукту. Якщо змінюються величини , то це пов'язано з коливаннями обсягу ресурсів на підприємствах, динамікою постачання сировини, зміною рівня запасів тощо.
Тому практична цінність параметричного програмування полягає в аналізі оптимальних планів у випадку зміни вихідних даних.
Задача, в якій коефіцієнти цільової функції лінійно залежать від параметра , може бути подана у вигляді
де , , , — сталі величини, а змінюється в деяких межах.
Якщо від параметра лінійно залежать вільні члени системи обмежень, то задачу параметричного програмування можна записати у вигляді
Тут , , , — сталі, а змінюється в певних межах.
Розв'язки сформульованих задач можна знайти симплексним методом. Під час розв'язування потрібно визначити проміжки значень параметра, для яких існують оптимальні плани.
У деяких задачах параметричного програмування від параметра лінійно залежать як коефіцієнти цільової функції, так і вільні члени системи обмежень:
Тут , , , , — сталі величини, а змінюється в деяких межах.
Узагальненням задач параметричного програмування є задача, в якій від параметра лінійно залежать коефіцієнти , і вільні члени . Її можна подати у вигляді
де , , , , , — сталі, а змінюється в певних межах.
Загального підходу до розв'язування цієї задачі поки що не розроблено, її розв'язки знайдені тільки для окремих випадків.
- ↑ T Gal, H.J. Greenberg Advances in Sensitivity Analysis and Parametric Programming. Springer, 1997.
- ↑ Bemporad, A.; Morari, M.; Dua, V.; Pistikopoulos, E. N. (2000) The explicit solution of model predictive control via multiparametric quadratic programming. Proceedings of the American Control, vol. 2, 872–876.
- ↑ Bemporad, Alberto; Morari, Manfred; Dua, Vivek; Pistikopoulos, Efstratios N. (2002) The explicit linear quadratic regulator for constrained systems. Automatica, 38 (1), 3–20.
- Бех О.В., Городня Т.А., Щербак А.Ф. Математичне програмування. – Львів: “Магнолія 2006”, 2007. – 200 с.
- Іє О.М. Дослідження операцій. – Луганськ: Вид-во ДЗ “ЛНУ імені Тараса Шевченка”, 2011. – 128 с.
- Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высш. школа, 1980. – 300 с.