Математическое Программирование

Математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). М. п.- раздел науки об исследовании операций, охватывающий широкий класс задач управления, математич. моделями к-рых являются конечномерные экстремальные задачи. Задачи М. п. находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий, напр, при решении многочисленных проблем управления и планирования производственных процессов, ,в задачах проектирования и перспективного планирования. Наименование "М. п." связано с тем, что целью решения задач является выбор программы действий. Математич. формулировка задачи М. п.: минимизировать скалярную функцию векторного аргумента на множестве где и — скалярные функции. Функцию наз. целевой функцией, функцией цели, а также критерием качества, множество X- допустимым множеством, или множеством планов, решение задачи М. п.- оптимальной точкой (вектором), точкой глобального минимума, а также оптимальным планом. В М. п. принято выделять следующие разделы. Линейное программирование:целевая функция и ограничения и линейны; квадратичное программирование:целевая функция квадратична и выпукла, допустимое множество определяется линейными равенствами и неравенствами; выпуклое программирование: целевая функция и допустимое множество выпуклы; дискретное программирование:решение ищется лишь в дискретных, напр, целочисленных, точках множества X;стохастическое программирование: в отличие от детерминированных задач здесь входная информация носит элемент неопределенности. Напр., в стохастич. задачах о минимизации линейной функции при линейных ограничениях либо все величины либо часть из них случайны. Задачи линейного, квадратичного и выпуклого программирования обладают общим свойством: всякая точка локального минимума является оптимальной точкой. Значительно более сложными и менее изученными являются так. наз. многоэкстремальные задачи — задачи, для к-рых указанное свойство не выполняется. В основе теории выпуклого программирования, в в частности линейного и квадратичного, лежит теорема Куна — Такера о необходимых и достаточных условиях существования оптимальной точки х*:для того чтобы точка х* была оптимальной, т. е. необходимо и достаточно, чтобы существовала такая точка чтобы пара точек образовывала седло функции Лагранжа Последнее означает, что для любых и всех . Если ограничения нелинейны, то теорема справедлива при нек-рых дополнительных предположениях о допустимом множестве, напр, в предположении существования такой точки; , что — условия регулярности Слейтера. Если функции и дифференцируемы, то следующие соотношения определяют седловую точку Таким образом, задача выпуклого программирования: сводится к решению системы уравнений и неравенств. На основе теоремы Куна — Такера разработаны различные итерационные методы минимизации, сводящиеся к поиску седловой точки функции Лагранжа. В М. п. одно из главных мест принадлежит вычислительным методам решения экстремальных задач. Широкое распространение среди этих методов получил метод возможных направлений. В этом методе последовательность точек множества Xстроится по формуле На каждой итерации для вычисления точки х р + 1 решаются задачи выбора направления (вектора) sp и длины шага (числа). В качестве sp выбирают то из возможных направлений (направлений в точке х р, малое перемещение вдоль каждого из к-рых не выводит из множества X), к-рое составляет острый угол с направлением g(xp). скорейшего убывания целевой функции (с вектором , если j(x)- дифференцируемая функция) .Таким образом, вдоль этого направления функция убывает. Число выбирают так, чтооы выполнялись условия и . Для вычисления sp в точке х р определяют конус возможных направлений, к-рый задается системой линейных неравенств, и формулируют задачу (линейного программирования) отыскания Такого возможного направления, по к-рому целевая функция убывает быстрее всего. Решение этой задачи без труда получают, напр., по стандартной программе симплексного метода. Величину шага вычисляют, решая задачу минимизации одномерной функции . При весьма общих предположениях доказано, что расстояние между точками х р. и множеством стационарных точек исходной задачи (т. е. множеством точек, в к-рых выполняются необходимые условия локального минимума функции на множестве X)стремится к нулю при . В случае, если исходная задача является задачей выпуклого программирования, то х р при стремится к множеству решений (оптимальных точек) исходной задачи. Метод возможных направлений допускает приближенное решение указанных задач определения sp и a р, и в этом смысле он устойчив по отношению к погрешностям вычислений. Для допустимых множеств специальной структуры (с точки зрения простоты решения задачи выбора направления sp). находят применение методы минимизации, отличные от метода возможных направлений. Так, в методе проекции градиента в качестве направления спуска в точке выбирают где -проекция точки , на множество X. Если множество Xзадано линейными ограничениями, весьма перспективным является метод условного градиента: в точке х р линеаризуют целевую функцию, строя функцию , затем, минимизируя l(х)на множестве X, находят точку ее минимума у р, после чего полагают sp=y р-x р. Успешно разрабатываются методы минимизации негладких функций. Одним, из представителей этого класса методов является метод обобщенного градиента. Обобщенным градиентом в точке х р наз. любой вектор удовлетворяющий для любой точки неравенству Этот метод отличается от метода проекции градиента тем, что в качестве проектируемой точки выбирают точку Весьма распространены также стохастические методы минимизации. В простейшем варианте метода случайного спуска в качестве sp выбирают случайную точку на n-мерной единичной сфере с центром в начале координат, и если sp лвляется возможным направлением и, кроме того, функция убывает вдоль этого направления, то осуществляют шаг, т. е. переходят к точке xp+1. В противном случае процедуру выбора s р повторяют. Характерной особенностью вычислительной стороны методов решений задач М. п. является то, что применение этих методов неразрывно связано с использованием ЭВМ, в первую очередь потому, что задачи М. п., формализующие ситуации управления реальными системами, являются задачами большого объема, недоступными для ручного счета. Одним из распространенных методов исследования задач М. п. является штрафных функций метод. Суть этого метода состоит в замене исходной задачи М. п. такой последовательностью параметрич. задач безусловной минимизации, что при стремлении параметра к бесконечности (в иных случаях — к нулю) решения этих задач стремятся к решению исходной задачи М. п. Заметим, что в задачах безусловной минимизации любое направление является возможным, вследствие чего отыскание вектора sp сопряжено с меньшей затратой усилий по сравнению с аналогичной задачей в методе возможных направлений (напр., в методе скорейшего спуска выбирают . То же самое относится и к задаче отыскания числа Важным направлением исследований в М. п. являются проблемы устойчивости. Здесь существенное значение имеет изучение класса устойчивых задач — задач, для к-рых малые возмущения (погрешности) в исходной информации влекут за собой малые возмущения и в решении. В случае неустойчивых задач большая роль отводится процедуре аппроксимации неустойчивой задачи последовательностью устойчивых задач — так наз. процессу регуляризации. Наряду с конечномерными задачами М. п. рассматриваются также задачи М. п. в бесконечномерных пространствах. К этим задачам относятся различные экстремальные задачи математич. экономики, техники, задачи оптимизации физич. характеристик ядерных реакторов и др. В терминах М. п. в соответствующих функциональных пространствах формулируются задачи вариационного исчисления и оптимального управления. М. п. как наука сформировалось в 50-70-х гг. 20 в. Это в первую очередь связано с развитием ЭВМ, а следовательно, с возможностью проводить математич. обработку больших потоков информации и на этой основе решать задачи управления и планирования, где применение математич. методов связано в первую очередь с построением математич. моделей и соответствующих им экстремальных задач, в том числе задач М. п. Лит.:[1] Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М., Методы оптимизации, М., 1978; [2] Карманов В. Г., , М., 1975; [3] Полак Э., Численные методы оптимизации. Единый подход, пер. с англ., М., 1974; [4] Ермольев Ю. М., Методы стохастического программирования, М., 1976. В. Г. Карманов.