Математическая энциклопедия - математическое программирование

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

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

где и скалярные функции. Функцию

наз. целевой функцией, функцией цели, а также критерием качества, множество Xдопустимым множеством, или множеством планов, решение задачи М. п.оптимальной точкой (вектором), точкой глобального минимума, а также оптимальным планом.

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

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

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

необходимо и достаточно, чтобы существовала такая точка чтобы пара точек

образовывала седло функции Лагранжа

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

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

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

В М. п. одно из главных мест принадлежит вычислительным методам решения экстремальных задач. Широкое распространение среди этих методов получил метод возможных направлений. В этом методе последовательность {х т} точек множества Xстроится по формуле На каждой итерации для вычисления точки х р + 1 решаются задачи выбора направления (вектора) sp и длины шага (числа). В качестве sp выбирают то из возможных направлений (направлений в точке х р, малое перемещение вдоль каждого из к-рых не выводит из множества X), к-рое составляет острый угол с направлением g(xp). скорейшего убывания целевой функции (с вектором , если j(x)дифференцируемая функция) .Таким образом, вдоль этого направления функция убывает. Число выбирают так, чтооы выполнялись условия и . Для вычисления sp в точке х р определяют конус возможных направлений, к-рый задается системой линейных неравенств, и формулируют задачу (линейного программирования) отыскания Такого возможного направления, по к-рому целевая функция убывает быстрее всего. Решение этой задачи без труда получают, напр., по стандартной программе симплексного метода. Величину шага вычисляют, решая задачу минимизации одномерной функции . При весьма общих предположениях доказано, что расстояние между точками х р. и множеством стационарных точек исходной задачи (т. е. множеством точек, в к-рых выполняются необходимые условия локального минимума функции на множестве X)стремится к нулю при . В случае, если исходная задача является задачей выпуклого программирования, то х р при стремится к множеству решений (оптимальных точек) исходной задачи. Метод возможных направлений допускает приближенное решение указанных задач определения sp и a р, и в этом смысле он устойчив по отношению к погрешностям вычислений.

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

,

на множество X.