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

— раздел прикладной математики, занимающийся изучением задач отыскания экстремума функций на некотором множестве и разработкой методов решения этих задач. Первыми исследованиями по П. м. следует считать работы франц. математика Ж. Л. Лагранжа (1736—1813), посвященные отысканию условного экстремума ф-ции, т. е. отысканию экстремума ф-ции на мн-ве . Лагранж сформулировал условия (см. Лагранжа правило множителей), которым должна удовлетворять точка, доставляющая экстремум ф-ции на мн-ве Q. Эти условия являются исторически первыми характеристическими свойствами относительного экстремума ф-ции. Хотя первые работы по П. м. появились более двухсот лет назад, своими современными достижениями П. м. обязано исследованиям, выполненным в течение нескольких последних десятилетий. Особенно бурное развитие теории экстремальных задач и методов их решения произошло в

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

где Q — некоторое мн-во в пространстве векторов х. Пространство это может быть как конечномерным, так и бесконечномерным (см. Пространство абстрактное в функциональном анализе). Функция целевой, а мн-во допустимым множеством. Задача (1) принципиально отличается от классической задачи отыскания условного экстремума тем, что в ней имеются ограничения в виде неравенств. Но, как правило, экстремум в задаче (1) достигается на границе, поэтому для использования при ее решении метода множителей Лагранжа необходимо знать, каким граничным поверхностям мн-ва принадлежит экстремум. Но определение этих поверхностей, по существу, эквивалентно решению опять-таки исходной задачи (1). Так что воспользоваться классическимв методами для решения задачи (1) практически невозможно. Поэтому для исследования задач типа (1) созданы самостоятельные теории и методы. Отыскание характеристических свойств экстремума в задаче (1) и является главным в П. м. Эти свойства экстремума и численные методы решения задач П. м. определяются свойствами задач, которые в свою очередь зависят от свойств ф-ций , и мн-ва

Раздел П. получивший название программирование линейное, изучает задачи типа (1), когда все функции линейны, а мн-во Q состоит из точек (векторов) с неотрицательными компонентами, т. е. задачу отыскания экстремума ф-ции

где скалярное произведение элементов с и х, а матрица А имеет строк и столбцов. Эту задачу, названную общей задачей линейного программирования, впервые поставил и изучил в математик Л. В. Канторович. Широкое применение теории и методов линейного программирования началось в конце 40-х и начале после того как амер. математик Дж. Данциг открыл симплекс-метод для решения задачи (2).

Теоремы двойственности (см. Двойственности теория в программировании линейном) устанавливают связь между решением задачи (2) и решением другой, т. н. двойственной к (2) задачи. Кроме симплекс-метода, для решения задачи линейного программирования построен двойственный симплекс-метод, а также метод для одновременного решения прямой и двойственной задачи линейного программирования.

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

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

Особое место в линейном программировании занимают задачи линейного программирования целочисленного, в которых на допустимую точку (вектор) накладывается дополнительное требование целочисленности всех или части его компонент. Требование целочисленности компонент оптим. вектора вытекает из физ. смысла многих практических задач. Иногда структура матрицы А такова, что при решении задачи (2) каким-либо общим методом линейного программирования удается получить целочисленное решение, но для большинства задач линейного программирования получение целочисленного решения невозможно без процедуры поиска. Впервые общий метод решения задач целочисленного программирования построил амер. математик Р. Гомори (см. Гомори метод). Важным классом задач целочисленного программирования являются задачи, в которых или часть, или все переменные принимают лишь два значения: «0» либо «1». К задачам целочисленного программирования такого типа сводятся весьма сложные комбинаторные задачи о коммивояжере, задачи теории расписаний, размещения производства, раскраски графа, задачи об ортогональных латинских квадратах и многие др. Для решения указанного класса задач целочисленного программирования используются алгоритмы, основанные на методе упорядоченного перебора, ветвей и границ методе и др.

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

В 1951 амер. математики Г. Кун и А. Таккер установили связь задачи выпуклого программирования с задачей отыскания седловой точки ф-ции Лагранжа. Эту связь устанавливает следующая теорема. Пусть вогнута, а все выпуклы и мн-во содержит внутр. точки (Q удовлетворяет условию Слейтера). В таком случае для того, чтобы вектор х был решением задачи выпуклого программирования, необходимо и достаточно, чтобы нашелся такой неотрицательный вектор и, который вместе с вектором х является седловой точкой ф-ции

т. е. имеют место следующие неравенства:

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

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

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

Раздел П. м., изучающий методы решения задач управления и планирования в условиях риска или неопределенности, получил название программирования стохастического. Простейшей задачей стохастического программирования является задача линейного стохастического программирования, заключающаяся в отыскании точки х, для которой математическое ожидание достигает максимума при вероятностных ограничениях Существует ряд приемов сведения задач стохастического программирования к детерминированным задачам П. м., что и позволило построить методы решения задач стохастического программирования.

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

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

В последние годы значительно возрос интерес к неклассическим задачам вариационного исчисления, к которым приводят часто встречающиеся на практике задачи оптим. управления. Задачи оптим. управления отличаются от классических задач вариационного исчисления тем, что управление объекта может выбираться не на всем пространстве, а на некотором мн-ве, называемом мн-вом допустимых управлений. Необходимые условия, которым должно удовлетворять оптим. управление, сформулированы сов. математиком Л. С. Понтрягиным и его учениками в виде Понтрягина принципа максимума.

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

Лит.: Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. М., 1967; Юдин Д. В., Гольштейн Е. Г. Линейное программирование. М., 1969 [библиогр. с. 418—421]; Пшеничный В. Н. Необходимые условия экстремума. М., 1969 [библиогр. с. 148—151]; Веллман Р. Динамическое программирование. Пер. с англ. М., 1960; Эрроу К. Дж., Гурвиц Л., Удзава X. Исследование по линейному и нелинейному программированию. Пер. с англ. м., 1962; Данциг Дж. Линейное программирование, его применения и обобщения. Пер. с англ. М., 1966 [библиогр. с. 564—589]. Р. А. Поляк, М.Е. Примак.