|
|
Большая Советская Энциклопедия (цитаты)
|
|
|
|
|
Математическое программирование | Математическое программирование (далее М), математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).
М — раздел науки об исследовании операций (см. Операций исследование), охватывающий широкий класс задач управления, математическими моделями которых являются конечномерные экстремальные задачи. Задачи М находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий, например, при решении многочисленных проблем управления и планирования производственных процессов, в задачах проектирования и перспективного планирования.
Наименование "М" связано с тем, что целью решения задач является выбор программы действий.
Математическая формулировка задачи М: минимизировать скалярную функцию j(x) векторного аргумента х на множестве
X = {x: gi(x) ³ 0, hi(x) = 0, = 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;
 , yi ³ 0, i = 1, 2, …, k.
Таким образом, задача выпуклого программирования сводится к решению системы уравнений и неравенств.
На основе теоремы Куна — Таккера разработаны различные итерационные методы минимизации, сводящиеся к поиску седловой точки функции Лагранжа.
В М одно из главных мест принадлежит вычислительным методам решения экстремальных задач. Широким классом таких методов являются методы проектирования. Идея этих методов состоит в следующем. В точке xk Î X выбирается направление спуска sk, то есть одно из направлений, по которому функция j(x) убывает, и вычисляется xk+1 = p(xk + aksk), где p(xk + aksk) означает проекцию точки xk + aksk на множество X:
 ,
число ak > 0 выбирается при этом так, чтобы j(xk +1) < j(xk). Существуют различные варианты методов проектирования. Наиболее распространенным из них является метод проекции градиента, когда sk = —grad j(xk). В М доказано, что при определенных условиях на целевую функцию и допустимое множество, последовательность {хk}, построенная методом проекции градиента, такова, что  стремится к нулю со скоростью геометрической прогрессии.
Характерной особенностью вычислительной стороны методов решений задач М является то, что применение этих методов неразрывно связано с использованием электронных вычислительных машин, в первую очередь потому, что задачи М, связанные с ситуациями управления реальными системами, являются задачами большого объема, недоступными для ручного счета.
Важным направлением исследования в М являются проблемы устойчивости. Здесь существ. значение имеет изучение класса устойчивых задач — задач, для которых малые возмущения (погрешности) в исходной информации влекут за собой малые возмущения и в решении. В случае неустойчивых задач большая роль отводится процедуре аппроксимации неустойчивой задачи последовательностью устойчивых задач — так называемому процессу регуляризации.
М как наука сформировалось в 50—70-х годах 20 века. Это обусловлено главным образом развитием электронных вычислительных машин, а следовательно, с возможностью проводить математическую обработку больших потоков информации, и на этой основе решать задачи управления и планирования, где применение математических методов связано в первую очередь с построением математических моделей и соответствующих им экстремальных задач, в том числе задач М
Лит.: Зуховицкий С. И., Авдеева Л. И., Линейное и выпуклое программирование, 2 изд., М., 1967; Хедли Дж., Нелинейное и динамическое программирование, перевод с английского, М., 1967.
В. Г. Карманов. |
Для поиска, наберите искомое слово (или его часть) в поле поиска
|
|
 |
 |
 |
|
|
|
Новости 31.10.2025 15:29:56
|
|
|
|
|
|
|
|
|
|
|
