Большая Советская Энциклопедия (МА) - Большая Советская Энциклопедия "БСЭ" - Страница 406

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

  Математическая формулировка задачи М. п.: минимизировать скалярную функцию 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 ; стохастическое программирование: в отличие от детерминированных задач, здесь входная информация носит элементы неопределённости; например, в стохастических задачах о минимизации линейной функции

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

либо все величины 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 ) дифференцируемы, то следующие соотношения определяют седловую точку

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

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

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

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

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

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

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

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

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

Матенадаран

Матенадара'н , Институт древних рукописей «Матенадаран» имени Месропа Маштоца при Совете Министров Армянской ССР, крупнейшее в мире хранилище древнеармянских рукописей и научно-исследовательский институт в Ереване. Создан на базе национализированной в 1920 коллекции рукописей Эчмиадзинского монастыря. Здание М. построено в 1959 (архитектор М. Григорян). Фонды М. (на 1972) насчитывают 12 960 армянских манускриптов и свыше 100 тысяч старинных архивных документов, около 2000 рукописей на арабском, персидском и других языках. Рукописи М. имеют большую научную и историческую ценность как важнейшие первоисточники для изучения истории и духовной культуры Армении, а также соседних народов Кавказа, Ближнего и Среднего Востока. В М. хранятся рукописи 5—18 веков, уникальная коллекция первопечатных и старопечатных армянских книг 16—18 веков, сочинения древних и средневековых армянских историков, писателей, философов, математиков, географов, врачей, переводы трудов древнегреческих, сирийских, арабских и латинских учёных, в том числе ряд сочинений, не сохранившихся на языке оригинала. В музее М. экспонируются лучшие образцы древнеармянской письменности и миниатюры. Многие рукописи представляют большую художественную ценность (например, «Лазаревское евангелие», 887, «Эчмиадзинское евангелие», 989, «Евангелие Мугни», 11 век). В М. ведётся научно-исследовательская работа: изучение и публикация памятников армянской письменности, исследование проблем армянской текстологии, источниковедения, палеографии, средневековой книжной живописи, историографии, научные переводы памятников на русский и другие языки. С 1940 издаётся сборник «Банбер Матенадарани» («Вестник Матенадарана» на армянском языке с резюме на русском и французском языках).