Математичне програмування , математична дисципліна, присвячена теорії і методам вирішення завдань про знаходження екстремумів функцій на безлічі, визначуваній лінійними і нелінійними обмеженнями (рівністю і нерівностями).
М. п. — розділ науки про дослідження операцій (див. Операцій дослідження ), що охоплює широкий клас завдань управління, математичними моделями яких є скінченномірні екстремальні завдання. Завдання М. п. знаходять вживання в різних областях людської діяльності, де необхідний вибір один з можливих образів дій, наприклад, при вирішенні багаточисельних проблем управління і планерування виробничих процесів, в завданнях проектування і перспективного планерування.
Найменування «М-коду. п.» пов'язане з тим, що метою рішення завдань є вибір програми дій.
Математичне формулювання завдання М. п.: мінімізувати скалярну функцію j( x ) векторного аргументу х на безлічі
X = { x : g i ( x ) ³ 0, h i ( x ) = 0, I = 1, 2 ..., до },
де g i ( x ) і h i ( x ) — також скалярні функції; функцію j( x ) називають цільовою функцією, або функцією мети, безліч X — допустимим безліччю, рішення х* задачі М. п. — оптимальною крапкою (вектором).
В М. п. прийнято виділяти наступні розділи. Лінійне програмування : цільова функція j( x ) і обмеження g i ( x ) і h i ( х ) лінійні; опукле програмування: цільова функція і допустима безліч опуклі; квадратичне програмування: цільова функція квадратична і опукла, допустима безліч визначається лінійною рівністю і нерівностями; дискретне програмування: рішення шукається лише в дискретних, наприклад цілочисельних, точках безлічі X ; стохастичне програмування: у відмінність від детермінованих завдань, тут вхідна інформація носить елементи невизначеності; наприклад, в стохастичних завданнях про мінімізацію лінійної функції
при лінійних обмеженнях
, i = 1, 2 ., m ,
або всі величини c j , a ij , b i , або частина з них випадкові.
Завдання перерахованих розділів володіють загальною властивістю: всяка точка локального мінімуму є оптимальною крапкою. Декілька осторонь знаходяться так звані багатоекстремальні завдання — завдання, для яких вказана властивість не виконується.
В основі теорії опуклого програмування і, зокрема, лінійного і квадратичного, лежить теорема Куна — Таккера про необхідних і достатніх умовах існування оптимальної точки x* : для того, щоб точка х* була оптимальною, тобто
,
X = { x : g i ( x ) ³ 0, i = 1, 2 ..., до },
необхідне і досить, щоб існувала така точка у* = ( у* 1 , у* 2 ..., у* до ), щоб пара точок х* , у* утворювала сідло функції Лагранжа
Останнє означає, що
L ( x*, в ) £ L ( x*, y* ) £ L ( x, у* )
для будь-яких х і всех в ³ 0. Якщо обмеження g i ( x ) нелінійні, то теорема справедлива при деяких додаткових припущеннях про допустиму безліч.
Якщо функції j( x ) і g i ( x ) діфференцируєми, то наступні співвідношення визначають седловую точку
, j = 1, 2 ., n ;
; ; i = 1, 2 ., до ;
, в i ³ 0, i = 1, 2 ., до .
Таким чином, завдання опуклого програмування зводиться до вирішення системи рівнянь і нерівностей.
На основі теореми Куна — Таккера розроблені різні ітераційні методи мінімізації, що зводяться до пошуку седлової точки функції Лагранжа.
В М. п. одне з головних місць належить обчислювальним методам вирішення екстремальних завдань. Широким класом таких методів є методи проектування. Ідея цих методів полягає в наступному. У точці x до Î X вибирається напрям спуску s до , тобто один з напрямів, по якому функція j( x ) убуває, і обчислюється x k+1 = p ( x до + a до s до ) , де p ( x до + a до s до ) означає проекцію точки x до + a до s до на безліч X :
,
число a до > 0 вибирається при цьому так, щоб j( x до +1 )< j( x до ). Існують різні варіанти методів проектування. Найбільш поширеним з них є метод проекції градієнта коли s до = —grad j( x до ) . В М. п. доведено, що за певних умов на цільову функцію і допустиму безліч, послідовність { х до }, побудована методом проекції градієнта, така, що прагне до нуля із швидкістю геометричної прогресії.
Характерною особливістю обчислювальної сторони методів вирішень завдань М. п. є те, що вживання цих методів нерозривно зв'язано з використанням електронних обчислювальних машин, в першу чергу тому, що завдання М. п., пов'язані з ситуаціями управління реальними системами, є завданнями великого об'єму, недоступними для ручного рахунку.
Важливим напрямом дослідження в М. п. є проблеми стійкості. Тут істот. значення має вивчення класу стійких завдань — завдань, для яких малі обурення (погрішності) в початковій інформації спричиняють за собою малі обурення і в рішенні. В разі нестійких завдань велика роль відводиться процедурі апроксимації нестійкого завдання послідовністю стійких завдань — так званому процесу регулярізациі.
М. п. як наука сформувалося в 50—70-х роках 20 століть. Це обумовлено головним чином розвитком електронних обчислювальних машин, а отже, з можливістю проводити математичну обробку великих потоків інформації, і на цій основі вирішувати завдання управління і планерування, де вживання математичних методів пов'язане в першу чергу з побудовою математичних моделей і відповідних їм екстремальних завдань, у тому числі завдань М. п.
Літ.: Зуховіцкий С. І., Авдєєва Л. І., Лінійне і опукле програмування, 2 видавництва, М., 1967; Хедлі Дж., Нелінійне і динамічне програмування, переклад з англійського, М., 1967.
