Математи́ческое программи́рование, раздел математики, посвящённый теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями. Эти ограничения могут задаваться равенствами и неравенствами. Математическое программирование охватывает широкий класс задач управления, математическими моделями которых являются конечномерные экстремальные задачи. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий, например при решении проблем управления и планирования производственных процессов, в задачах проектирования и перспективного планирования. Название «математическое программирование» связано с тем, что целью решения задач является выбор программы действий.

Задача математического программирования состоит в том, чтобы минимизировать скалярную функцию $φ (x)$ векторного аргумента $х∈\mathbf{R}^n$ , принимающего значения из множества $$X=\{x: g_i(x) ⩾ 0, i=1,2,...,k; h_j(x)=0, j=1,2,...,m\},$$ где $g_i(x), \ i=1,2,...,k,\: и\ \ \:h_j(x), j= 1,2,...,m,$– скалярные функции; функцию $φ(x)$ называют целевой функцией, или функцией цели, множество $X$ – множеством допустимых решений, решение задачи математического программирования – оптимальной точкой.

В математическое программирование входят линейное программирование, где целевая функция $φ (x)$ и функции $g_i(x), i=1,2,...,k,$ и $h_j(х), j=1,2,...,m,$ линейны; выпуклое программирование, где целевая функция и множество допустимых решений выпуклы; квадратичное программирование, где целевая функция квадратична и множество допустимых решений определяется линейными равенствами и неравенствами; дискретное программирование, где решение ищется лишь в дискретных, например целочисленных, точках множества $X$; стохастическое программирование, где, в отличие от детерминированных задач, входная информация носит элементы неопределённости.

Задачи перечисленных разделов математического программирования обладают следующим свойством: всякая точка локального минимума является оптимальной точкой. По-иному обстоит дело в т. н. многоэкстремальных задачах, в которых указанное свойство не имеет места.

В основе выпуклого программирования, и в частности линейного и квадратичного, лежит теорема Куна – Таккера о необходимых и достаточных условиях существования оптимальной точки$x^*$: для того чтобы точка $x^*$ была оптимальной, т. е.

$$\varphi (x^*)=\min_{x\in X}\varphi (x),$$$$X=\{x: f_i(x) ⩾ 0,\: i=1,2,...,k\},$$необходимо и достаточно, чтобы существовала такая точка $y^*= (y^*_1, y^*_2,...,y^*_k)$, чтобы пара точек $x^*$, $y^*$ была седловой точкой функции Лагранжа

$$L(x,y)=\varphi (x)+\sum_{i=1}^{k}y_ig_i(x).$$Последнее означает, что $L(x^*, y) ⩽ L(x^*, y^*) ⩽ L(x, у^*)$ для любых $х$ и всех $у ⩾ 0$. Если ограничения нелинейны, то эта теорема справедлива при некоторых дополнительных предположениях о множестве допустимых решений. Если функции $φ(x)$ и $f_i(x), \:i=1,2,…,k,$ дифференцируемы, то седловую точку определяют соотношения

 $$\frac{\partial L}{\partial x_j}\geqslant 0,\ \ \ \ \:j=1,2,...,n;$$ $$\sum_{j=1}^{k}\frac{\partial L}{\partial x_j}x_j=0,\ \ \ \ \:\frac{\partial L}{\partial y_i}\leqslant 0,\ \:i=1,2,...,k;$$$$\sum_{j=1}^{k}\frac{\partial L}{\partial y_j}y_j=0,\ \ \ \ \:\ y_i\leqslant 0,\ \:i=1,2,...,k.$$Таким образом, задача выпуклого программирования сводится к решению системы уравнений и неравенств.

На основе теоремы Куна – Таккера разработаны различные итерационные методы минимизации, сводящиеся к поиску седловой точки функции Лагранжа.

В математическом программировании важную роль играют вычислительные методы решения экстремальных задач. Широким классом таких методов являются методы проектирования. Идея этих методов состоит в следующем. В точке $x^k∈X$ выбирается направление спуска $s^k$, т. е. одно из направлений, по которому функция $φ(x)$ убывает, и вычисляется $x^{k+1}=p(x^k+α_ks^k)$, где $p(x^k+α_ks^k)$ означает проекцию точки $x^k+α_ks^k$ на множество $X$:

$$\left | p(x^k+\alpha _ks^k) -(x^k+\alpha _ks^k)\right |=\min_{x\in X}\left | x-(x^k+\alpha _ks^k) \right |,$$число $α_k > 0$ выбирается при этом так, чтобы $φ (x^{k+1}) < φ (x^k)$. Существуют различные варианты методов проектирования. Наиболее распространённым из них является метод проекции градиента, когда $s^k=-\text{grad}φ(x^k)$.

Характерной особенностью вычислительных методов решения задач математического программирования является использование ЭВМ, в первую очередь потому, что задачи математического программирования, связанные с ситуациями управления реальными системами, – задачи большого объёма.

Важное направление исследований в математическом программировании – проблемы устойчивости. Здесь существенное значение имеет изучение класса устойчивых задач, т. е. задач, для которых малые возмущения (погрешности) в исходной информации влекут за собой малые возмущения и в решении. В случае неустойчивых задач большая роль отводится процедуре аппроксимации неустойчивой задачи последовательностью устойчивых задач – т. н. процессу регуляризации.

Математическое программирование как наука сформировалось в 1950–1970-х гг. Это обусловлено главным образом развитием ЭВМ, что дало возможность проводить математическую обработку больших объёмов информации.