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

Большая Советская Энциклопедия. Статьи для написания рефератов, курсовых работ, научные статьи, биографии, очерки, аннотации, описания.


А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я 1 2 3 4 8 A L M P S T X
МА МБ МВ МГ МД МЕ МЁ МЖ МЗ МИ МК МЛ МН МО МП МР МС МТ МУ МХ МЦ МШ МЫ МЬ МЭ МЮ МЯ
МАА
МАБ
МАВ
МАГ
МАД
МАЕ
МАЁ
МАЖ
МАЗ
МАИ
МАЙ
МАК
МАЛ
МАМ
МАН
МАО
МАП
МАР
МАС
МАТ
МАУ
МАФ
МАХ
МАЦ
МАЧ
МАШ
МАЭ
МАЮ
МАЯ

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

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

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

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

 

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

  , 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.

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

Так же Вы можете узнать о...


Терско-Сунженская возвышенность, возвышенность в юго-восточной части Предкавказья, к Ю.
Фучик Юлиус Фучик (Fučik) Юлиус (23.
Экспансивный (от франц. expansif), порывистый, несдержанный, резко, бурно проявляющий свои чувства.
Ариды, фазы иссушения климата в зонах пустынь и полупустынь, внеледниковых областей, примерно соответствующие межледниковьям областей, подвергавшихся оледенению во время антропогенового периода.
Бурый уголь, горючее ископаемое растительного происхождения, представляющее собой переходную форму от торфа к каменному углю.
Герцфельд Эрнст Эмиль Герцфельд (Herzfeld) Эрнст Эмиль (1879—1948), немецкий археолог; см.
Дренте (Drenthe, Drente), провинция на северо-востоке Нидерландов.
Каменномостский, посёлок городского типа в Майкопском районе Адыгейской АО Краснодарского края РСФСР.
Красный Маяк (до 1925 — Якунчиков), посёлок городского типа в Ковровском районе Владимирской области РСФСР.
Марафонский бег, бег по шоссе на самую длинную в программе Олимпийских игр и других официальных спортивных соревнований дистанцию — 42 км 195 м.
Нестеров (город в Львовской обл.) Нестеров (до 1951 — Жолква), город (с 1940), центр Нестеровского района Львовской области УССР.
Пим Джон Пим (Рут) Джон (около 1584, Браймор, Сомерсетшир, — 8.
Реюньон (франц. Réunion), страна в Индийском океане, расположена на острове в группе Маскаренских островов.
Сонсонате (Sonsonate), город в Сальвадоре, административный центр департамента .
Тромбофлебит (от тромб и флебит), воспаление стенки вены с образованием тромба, закрывающего её просвет.
Хурритский язык, язык хурритов. Засвидетельствован в текстах 3—2 тыс.
Юраки, употреблявшееся в прошлом название ненцев Западной Сибири.
Бактериофаги (от бактерии и греч. phagos — пожиратель; буквально — пожиратели бактерий), фаги, бактериальные вирусы, вызывающие разрушение (лизис) бактерий и других микроорганизмов.