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

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

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

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

$L = \sum_{j = 1}^{n} c_{j} x_{j} \to \min;$
$\sum_{j = 1}^{n} a_{i j} x_{j} = b_{i} (i = \overline{1, m});$

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

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

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

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

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

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

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

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

$L = \sum_{j = 1}^{n} ({c_{j}}^{'} + {c_{j}}^{″} t) x_{j} \to \min;$
$\sum_{j = 1}^{n} a_{i j} x_{j} = b_{i} (i = \overline{1, m});$

$x_{j} ⩾ 0 (j = \overline{1, n}),$

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

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

$L = \sum_{j = 1}^{n} c_{j} x_{j} \to \min;$
$\sum_{j = 1}^{n} a_{i j} x_{j} = {b_{i}}^{'} + {b_{i}}^{″} t (i = \overline{1, m});$

$x_{j} ⩾ 0 (j = \overline{1, n}) .$

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

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

Інші задачі

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

$L = \sum_{j = 1}^{n} ({c_{j}}^{'} + {c_{j}}^{″} t) x_{j} \to \min;$

$\sum_{j = 1}^{n} a_{i j} x_{j} = {b_{i}}^{'} + {b_{i}}^{″} t (i = \overline{1, m});$

$x_{j} ⩾ 0 (j = \overline{1, n}) .$

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

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

$L = \sum_{j = 1}^{n} ({c_{j}}^{'} + {c_{j}}^{″} t) x_{j} \to \min;$

$\sum_{j = 1}^{n} (a_{i^{'} j} + a_{i^{″} j} t) a_{i j} x_{j} = {b_{i}}^{'} + {b_{i}}^{″} t (i = \overline{1, m});$

$x_{j} ⩾ 0 (j = \overline{1, n}),$

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

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

Див. також

Примітки

Шаблон:Reflist

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

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

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

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

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

Зміст

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

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

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

Інші задачі

Див. також

Примітки

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

Навігаційне меню

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

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

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

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

Інші задачі

Див. також

Примітки

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

Навігаційне меню

Пошук