Значение МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ в Большой советской энциклопедии, БСЭ

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

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

Наименование 'М. п.' связано с тем, что целью решения задач является выбор программы действий.

Математическая формулировка задачи М. п.: минимизировать скалярную функцию j( x ) векторного аргумента х на множестве

X { x : gi ( x ) ³ 0, hi ( x ) 0, I 1, 2, ..., k },

где gi ( x ) и hi ( x ) - также скалярные функции; функцию j( x ) называют целевой функцией, или функцией цели, множество X - допустимым множеством, решение х* задачи М. п. - оптимальной точкой (вектором).

В М. п. принято выделять следующие разделы. Линейное программирование : целевая функция j( x ) и ограничения gi ( x ) и hi ( х ) линейны; выпуклое программирование: целевая функция и допустимое множество выпуклы; квадратичное программирование: целевая функция квадратична и выпукла, допустимое множество определяется линейными равенствами и неравенствами; дискретное программирование: решение ищется лишь в дискретных, например целочисленных, точках множества X ; стохастическое программирование: в отличие от детерминированных задач, здесь входная информация носит элементы неопределённости; например, в стохастических задачах о минимизации линейной функции

при линейных ограничениях

, i 1, 2, -, m ,

либо все величины cj , aij , bi , либо часть из них случайны.

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

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

,

X { x : gi ( x ) ³ 0, i 1, 2, ..., k },

необходимо и достаточно, чтобы существовала такая точка у* ( у*1 , у*2 , ..., у*k ), чтобы пара точек х* , у* образовывала седло функции Лагранжа

Последнее означает, что

L ( x*, y ) £ L ( x*, y* ) £ L ( x, у* )

для любых х и всех у ³ 0 . Если ограничения gi ( x ) нелинейны, то теорема справедлива при некоторых дополнительных предположениях о допустимом множестве.

Если функции j( x ) и gi ( x ) дифференцируемы, то следующие соотношения определяют седловую точку

, j 1, 2, -, n ;

; ; i 1, 2, -, k ;

, y i ³ 0, i 1, 2, -, k .

Таким образом, задача выпуклого программирования сводится к решению системы уравнений и неравенств.

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

В М. п. одно из главных мест принадлежит вычислительным методам решения экстремальных задач. Широким классом таких методов являются методы проектирования. Идея этих методов состоит в следующем. В точке xk Î X выбирается направление спуска sk , то есть одно из направлений, по которому функция j( x ) убывает, и вычисляется xk+1 p ( xk + a ksk ) , где p ( xk + a ksk ) означает проекцию точки xk + a ksk на множество X :

,

число ak > 0 выбирается при этом так, чтобы j( xk +1) < j( xk ). Существуют различные варианты методов проектирования. Наиболее распространённым из них является метод проекции градиента, когда sk -grad j( xk ) . В М. п. доказано, что при определённых условиях на целевую функцию и допустимое множество, последовательность { хk }, построенная методом проекции градиента, такова, чтостремится к нулю со скоростью геометрической прогрессии.

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

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

М. п. как наука сформировалось в 50-70-х годах 20 века. Это обусловлено главным образом развитием электронных вычислительных машин, а следовательно, с возможностью проводить математическую обработку больших потоков информации, и на этой основе решать задачи управления и планирования, где применение математических методов связано в первую очередь с построением математических моделей и соответствующих им экстремальных задач, в том числе задач М. п.

Лит.: Зуховицкий С. И., Авдеева Л. И., Линейное и выпуклое программирование, 2 изд., М., 1967; Хедли Дж., Нелинейное и динамическое программирование, перевод с английского, М., 1967.

В. Г. Карманов.

Большая советская энциклопедия, БСЭ. 2012