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

Математи́чне програмува́ння — це прикладна математична дисципліна, яка досліджує екстремум функції (задачі пошуку максимуму або мінімуму) і розробляє методи їх розв'язання. Такі задачі ще називають оптимізаційними[1].

Історія

Як самостійний науковий напрямок математичне програмування сформувалось на початку 40-х років ХХ століття. У 1939 році відомий російський математик Л. В. Канторович опублікував роботу «Математичні методи організації та планування виробництва», в якій сформулював принципово новий клас екстремальних задач з обмеженнями і розробив ефективний метод їх розв'язання. Так було започатковано новий розділ прикладної математики, який пізніше отримав назву «лінійне програмування». Дослідження Л. В. Канторовича в цій галузі сприяли створенню строго наукового інструментарію для розв'язання фундаментальних економічних проблем (ефективності капіталовкладень, ціноутворення, теорії ренти тощо), за що в 1975 р. Л. В. Канторович був удостоєний (разом з Т. Ч. Купмансом) Нобелівської премії з економіки[2].

Методам лінійного програмування присвячено багато робіт зарубіжних вчених. У 1949 р. американським вченим Хічкоком поставлена транспортна задача, Дж. Данцигом був розроблений симплекс-метод розв'язання задачі ЛП, Д. Гейлом, Г. У. Куном, А. У. Таккером сформульована теорема двоїстості та розроблена теорія розв'язання задач опуклого програмування. Крім того, французьким математиком Лагранжем та американцем Беллманом розроблені методи множників і теорія функціональних рівнянь розв'язання відповідно задач опуклого та динамічного програмування[3].

За останні роки розроблено багато ефективних методів розв'язання математичних задач оптимізації на ЕОМ (ПК).

Класифікація галузей математичного програмування
  • Залежно від виду цільової функції та системи обмежень, галузі математичного програмування поділяють на[4]:
    • Лінійне програмування – цільова функція і функції обмежень, що входять в систему обмежень є лінійними (рівняння першого порядку)
    • Нелінійне програмування – цільова функція або одна із функцій обмежень, що входять в систему обмежень є нелінійними (рівняння вищих порядків)
    • Цілочисельне (дискретне) програмування — якщо на хоча б одну змінну  накладена умова цілочисельності
    • Динамічне програмування — якщо параметри цільової функції і/або система обмежень змінюються в часі або цільова функція має адитивний/мультиплікативний вигляд чи сам процес прийняття рішення має багатокроковий характер.
  • Залежно чи відома вся інформація про процес заздалегідь, галузі математичного програмування поділяють на:
    • Стохастичне програмування — відома не вся інформація про процес заздалегідь: параметри що входять в цільову функцію або в функцію обмежень є випадковими або доводиться приймати рішення в умовах ризику
    • Детерміноване програмування — відома вся інформація про процес заздалегідь

Класифікація задач оптимізації

Залежно від кількості цільових функцій, задачі поділяють на:

  1. Однокритеріальні
  2. Багатокритеріальні

За властивостями системи обмежень і цільової функції задачі оптимізації класифікують наступним чином[3]:

  1. Задачі безумовної оптимізації або задачі без обмежень — в них не накладаються обмеження на кількісні змінні.
  2. Задачі умовної оптимізації або задачі з обмеженнями — в цих задачах на кількісні змінні накладаються обмеження. 
  3. Задачі оптимізації при неповних даних — в них функція цілі або система обмежень залежать від деякого параметру р (числового, векторного), значення якого повністю невизначено на момент розв'язання задачі.  

Примітки
  1. Білогурова Г. В., Самойленко М. І. Математичне програмування: Конспект лекцій (для студентів денної і заочної форми навчання освітньо-кваліфікаційного рівня бакалавр у галузі знань 0306 «Менеджмент і адміністрування» за напрямом підготовки 6.030601 «Менеджмент»). — Х.: ХНАМГ, 2009. — 72 с.
  2. Гончаренко Я. В. Математичне програмування. — К.: НПУ імені М. П. Драгоманова, 2010. — 184 с. 
  3. Кононенко А. І., Храповицький І. С., Щелкунова Л. І. Математичне програмування: Тексти лекцій. — Харків, ХДТУБА, 2010. — 114 с.
  4. Математичне програмування. Перевірено 20.10.2014.

Джерела
  • Кузнецов А. В. Математичне програмування. — М: Вища школа, 1994. — 282 c.
  • Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452 с.

Література
  • Математичне програмування : навч. посіб. / Г. Г. Цегелик ; Львів. нац. ун-т ім. Івана Франка. - Л. : ЛНУ ім. Івана Франка, 2011. - 337 с. : рис., табл. - ISBN 978-966-613-875-3
  • Математичне програмування : Навч. посіб. / М. М. Глушик, І. М. Копич, О. С. Пенцак, В. М. Сороківський; Укоопспілка, Львів. комерц. акад. - Л. : Видавництво Львівської комерційної академії, 2004. - 238 с. - ISBN 966-8561-16-3
  • Математичне програмування: теорія та практикум : навч. посібн. / М. Л. Вдовин, Л. Г. Данилюк. – Львів : “Новий  Світ-2000”, 2015. – 160 с. – ISBN 978‐966‐418‐100‐3
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.