Параметричне програмування

Параметричне програмування (англ. Parametric Programming) – це розділ математичного програмування, пов'язаний із дослідженням оптимальних розв'язків на стійкість щодо зміни вихідних даних. Розроблене паралельно аналізу чутливості, параметричне програмування вперше було згадане в дисертації 1952 року^[1]. Параметричне програмування пов'язане з прогнозною моделлю контролю, створення якої у 2000 році сприяло підвищенню інтересу до даної теми^[2]^[3].

Предмет параметричного програмування ред.

Загальна задача лінійного програмування

$L=\sum _{j=1}^{n}c_{j}x_{j}\rightarrow \min ;$
$\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}\qquad {\bigl (}i={\overline {1,m}}{\bigr )};$

$x_{j}\geqslant 0\qquad {\bigl (}j={\overline {1,n}}{\bigr )}$
містить сталі величини: коефіцієнти $c_{j}$ , $a_{ij}$ і вільні члени $b_{i}\,{\bigl (}i={\overline {1,m}};\,j={\overline {1,n}}{\bigr )}$ . З одного боку, у практичних ситуаціях ці величини змінюються, з іншого, знайшовши оптимальний план деякої задачі за фіксованих значень $a_{ij}$ , $b_{i}$ , $\,c_{j}$ , потрібно знати, в яких допустимих межах їх можна змінювати, щоб план залишався оптимальним.

Тому виникає необхідність досліджень поведінки оптимального розв'язку задачі лінійного програмування при зміні її коефіцієнтів і вільних членів. Ці дослідження складають предмет параметричного програмування.

Економічна інтерпретація задач параметричного програмування ред.

Параметричне програмування виникло у зв'язку з вирішенням завдань планування виробництва і є основою оптимального планування різних економічних процесів.

Якщо величини $c_{j}$ змінні, то це можна пов'язати з коливаннями цін на товар, із змінами витрат на виробництво та змінами прибутку за одиницю продукту. Якщо змінюються величини $b_{i}$ , то це пов'язано з коливаннями обсягу ресурсів на підприємствах, динамікою постачання сировини, зміною рівня запасів тощо.

Тому практична цінність параметричного програмування полягає в аналізі оптимальних планів у випадку зміни вихідних даних.

Найпростіші задачі ред.

Задача, в якій коефіцієнти цільової функції лінійно залежать від параметра $t$ , може бути подана у вигляді

$L=\sum _{j=1}^{n}{\bigl (}c_{j}'+c_{j}''t{\bigr )}x_{j}\rightarrow \min ;$
$\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}\qquad {\bigl (}i={\overline {1,m}}{\bigr )};$

$x_{j}\geqslant 0\qquad {\bigl (}j={\overline {1,n}}{\bigr )},$

де $c_{j}'$ , $c_{j}''$ , $a_{ij}$ , $b_{i}$ — сталі величини, а $t$ змінюється в деяких межах.

Якщо від параметра $t$ лінійно залежать вільні члени системи обмежень, то задачу параметричного програмування можна записати у вигляді

$L=\sum _{j=1}^{n}c_{j}x_{j}\rightarrow \min ;$
$\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}'+b_{i}''t\qquad {\bigl (}i={\overline {1,m}}{\bigr )};$

$x_{j}\geqslant 0\qquad {\bigl (}j={\overline {1,n}}{\bigr )}.$

Тут $\,c_{j}$ , $a_{ij}$ , $b_{i}'$ , $b_{i}''$ — сталі, а $t$ змінюється в певних межах.

Розв'язки сформульованих задач можна знайти симплексним методом. Під час розв'язування потрібно визначити проміжки значень параметра, для яких існують оптимальні плани.

Інші задачі ред.

У деяких задачах параметричного програмування від параметра $t$ лінійно залежать як коефіцієнти цільової функції, так і вільні члени системи обмежень:

$L=\sum _{j=1}^{n}{\bigl (}c_{j}'+c_{j}''t{\bigr )}x_{j}\rightarrow \min ;$

$\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}'+b_{i}''t\qquad {\bigl (}i={\overline {1,m}}{\bigr )};$

$x_{j}\geqslant 0\qquad {\bigl (}j={\overline {1,n}}{\bigr )}.$

Тут $c_{j}'$ , $c_{j}''$ , $a_{ij}$ , $b_{i}'$ , $b_{i}''$ — сталі величини, а $t$ змінюється в деяких межах.

Узагальненням задач параметричного програмування є задача, в якій від параметра $t$ лінійно залежать коефіцієнти $c_{j}$ , $a_{ij}$ і вільні члени $b_{i}$ . Її можна подати у вигляді

$L=\sum _{j=1}^{n}{\bigl (}c_{j}'+c_{j}''t{\bigr )}x_{j}\rightarrow \min ;$

$\sum _{j=1}^{n}{\bigl (}a_{ij}'+a_{ij}''t{\bigr )}a_{ij}x_{j}=b_{i}'+b_{i}''t\qquad {\bigl (}i={\overline {1,m}}{\bigr )};$

$x_{j}\geqslant 0\qquad {\bigl (}j={\overline {1,n}}{\bigr )},$

де $c_{j}'$ , $c_{j}''$ , $a_{ij}'$ , $a_{ij}''$ , $b_{i}'$ , $b_{i}''$ — сталі, а $t$ змінюється в певних межах.

Загального підходу до розв'язування цієї задачі поки що не розроблено, її розв'язки знайдені тільки для окремих випадків.

Див. також ред.

Примітки ред.

↑ 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 с.

[1] T Gal, H.J. Greenberg Advances in Sensitivity Analysis and Parametric Programming. Springer, 1997.

[2] 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.

[3] Bemporad, Alberto; Morari, Manfred; Dua, Vivek; Pistikopoulos, Efstratios N. (2002) The explicit linear quadratic regulator for constrained systems. Automatica, 38 (1), 3–20.

[1]

[2]

[3]