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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Інші задачі

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

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

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

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

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

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

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

${\displaystyle \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 )};}$

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

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

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

Див. також

• Математичне програмування
• Лінійне програмування
• Нелінійне програмування

Примітки

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.

Використані джерела

• Бех О.В., Городня Т.А., Щербак А.Ф. Математичне програмування. – Львів: “Магнолія 2006”, 2007. – 200 с.
• Іє О.М. Дослідження операцій. – Луганськ: Вид-во ДЗ “ЛНУ імені Тараса Шевченка”, 2011. – 128 с.
• Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высш. школа, 1980. – 300 с.