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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Математичне програмування
Тема вивчення/дослідження оптимізація і Метод невизначених множників

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

Історія

[ред. | ред. код]

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

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

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

Класифікація галузей математичного програмування

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

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

[ред. | ред. код]

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

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

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

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

Примітки

[ред. | ред. код]
  1. ↑ Білогурова Г. В., Самойленко М. І. Математичне програмування [Архівовано 20 жовтня 2014 у Wayback Machine.]: Конспект лекцій (для студентів денної і заочної форми навчання освітньо-кваліфікаційного рівня бакалавр у галузі знань 0306 «Менеджмент і адміністрування» за напрямом підготовки 6.030601 «Менеджмент»). — Х.: ХНАМГ, 2009. — 72 с.
  2. ↑ Гончаренко Я. В. Математичне програмування [Архівовано 3 вересня 2013 у Wayback Machine.]. — К.: НПУ імені М. П. Драгоманова, 2010. — 184 с. 
  3. ↑ а б Кононенко А. І., Храповицький І. С., Щелкунова Л. І. Математичне програмування: Тексти лекцій [Архівовано 2 лютого 2016 у Wayback Machine.]. — Харків, ХДТУБА, 2010. — 114 с.
  4. ↑ Математичне програмування [Архівовано 26 квітня 2017 у Wayback Machine.]. Перевірено 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
Отримано з https://uk.wikipedia.org/wiki/Математичне_програмування