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

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

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

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

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

наз. целевой функцией, функцией цели, а также критерием качества, множество 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.

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


  1. математическое программирование—МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ математическая дисциплина посвящнная теории и методам решения задач о нахождении экстремумов функций на множествах определяемых линейными ...Большая советская энциклопедия
  2. математическое программирование—математическая дисциплина посвященная теории и методам решения задач о нахождении экстремумов функций на множествах определяемых линейными и нелинейными ограничениями рав...Большая Советская энциклопедия II
  3. математическое программирование—оптимальное программирование матем. дисциплина разрабатывающая теорию и методы нахождения экстрем. значений фций мн. переменных в некрой области в т. ч. на границе облас...Большой энциклопедический политехнический словарь
  4. математическое программирование—раздел математики посвященный теории иметодам решения задач о нахождении экстремумов функций на множествахопределяемых некоторыми ограничениями равенствами или неравенств...Большой энциклопедический словарь II
  5. математическое программирование—МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ раздел математики посвященный теории и методам решения задач о нахождении экстремумов функций на множествах определяемых некоторыми ограни...Большой энциклопедический словарь III
  6. математическое программирование—МАТЕМАТИЧЕСКОЕ программирование раздел математики посвященный теории и методам решения задач о нахождении экстремумов функций на множествах определяемых некоторыми огран...Большой Энциклопедический словарь V
  7. математическое программирование—матем. дисциплина разрабатывающая теорию и методы нахождения экстремальных значений функций мн. переменных в некрой областей раздел исследования операций. В воен. деле пр...Военный энциклопедический словарь
  8. математическое программирование—раздел математики посвящнный теории и методам решения задач о нахождении экстремумов функций на множествах определяемых некрыми ограничениями равенствами или неравенствам...Естествознание. Энциклопедический словарь
  9. математическое программирование—Метод исследования операций при помощи которого решаются проблемы связанные с тем что оптимальная стоимость стандартно является предметом определенных ограничений. Матема...Инвестиционный словарь
  10. математическое программирование—programmation mathmatique...Политехнический русско-французский словарь
  11. математическое программирование—mathematical programming...Русско-английский машиностроительный словарь
  12. математическое программирование—mathematical programming...Русско-английский политехнический словарь
  13. математическое программирование—mathematical programming...Русско-английский словарь по электронике
  14. математическое программирование—mathematical programming...Русско-английский экономический словарь
  15. математическое программирование—матэматычнае праграмаванне...Русско-белорусский математический словарь
  16. математическое программирование—programacin matemtica...Русско-испанский экономический словарь
  17. математическое программирование—programmazione matematica...Русско-итальянский политехнический словарь
  18. математическое программирование—matematick programovn...Русско-чешский словарь
  19. математическое программирование—МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ раздел математики посвященный теории и методам решения задач о нахождении экстремумов функций на множествах определяемых некоторыми ограни...Современный энциклопедический словарь
  20. математическое программирование—МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ раздел математики посвященный теории и методам решения задач о нахождении экстремумов функций на множествах определяемых некоторыми огран...Энциклопедический словарь естествознания