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

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

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

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



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

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

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

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

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

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

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

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


де , , , — сталі величини, а змінюється в деяких межах.

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


Тут , , , — сталі, а змінюється в певних межах.

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

Інші задачі

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

Тут , , , , — сталі величини, а змінюється в деяких межах.

Узагальненням задач параметричного програмування є задача, в якій від параметра лінійно залежать коефіцієнти , і вільні члени . Її можна подати у вигляді

де , , , , , — сталі, а змінюється в певних межах.

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

Див. також

Примітки

  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 с.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.