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

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, математическая дисциплина, посвящённая теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).

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

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

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

Х = {х:gi(x)>=0, hi(x) = 0, i=1,

2, ..., k}, где gi(x) и hi(x)- также скалярные функции; функцию ф(х) наз. целевой функцией, или функцией цели, множество X - допустимым множеством, решение х* задачи М. п.- оптимальной точкой (вектором).

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

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

либо всё величины cj, аij, bi, либо часть из них случайны.

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

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

необходимо и достаточно, чтобы существовала такая точка у*= (у1*, у2*, ..., у1k*), чтобы пара точек х*, у* образовывала седло функции Лагранжа

для любых х и всех у^О. Если ограничения gi(x) нелинейны, то теорема справедлива при нек-рых дополнительных предположениях о допустимом множестве.

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

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

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

В М. п. одно из главных мест принадлежит вычислит, методам решения экстремальных задач. Широким классом таких методов являются методы проектирования. Идея этих методов состоит в следующем.

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

стремится к нулю со скоростью геометрич. прогрессии.

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

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

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

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




Смотреть больше слов в «Большой советской энциклопедии»

МАТЕНАДАРАН →← МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ

Смотреть что такое МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ в других словарях:

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

        математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и ... смотреть

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

- математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах конечномерного векторного прост... смотреть

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

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел математики, посвященный теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых некоторыми ограничениями (равенствами или неравенствами). Если изучаемая функция линейна (1-й степени) и задана на множестве, заданном линейными равенствами и неравенствами, то соответствующий раздел математического программирования называется линейным программированием. Математическое программирование называется также оптимальным программированием. Следует отличать от программирования на ЭВМ.<br><br><br>... смотреть

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

МАТЕМАТИЧЕСКОЕ программирование - раздел математики, посвященный теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых некоторыми ограничениями (равенствами или неравенствами). Если изучаемая функция линейна (1-й степени) и задана на множестве, заданном линейными равенствами и неравенствами, то соответствующий раздел математического программирования называется линейным программированием. Математическое программирование называется также оптимальным программированием. Следует отличать от программирования на ЭВМ.<br>... смотреть

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

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ , раздел математики, посвященный теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых некоторыми ограничениями (равенствами или неравенствами). Если изучаемая функция линейна (1-й степени) и задана на множестве, заданном линейными равенствами и неравенствами, то соответствующий раздел математического программирования называется линейным программированием. Математическое программирование называется также оптимальным программированием. Следует отличать от программирования на ЭВМ.... смотреть

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

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел математики, посвященный теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых некоторыми ограничениями (равенствами или неравенствами). Если изучаемая функция линейна (1-й степени) и задана на множестве, заданном линейными равенствами и неравенствами, то соответствующий раздел математического программирования называется линейным программированием. Математическое программирование называется также оптимальным программированием. Следует отличать от программирования на ЭВМ.... смотреть

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

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

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

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

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

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

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

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

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

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

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

матэматычнае праграмаванне

T: 192