Основы теории оптимизации (стр. 2 )

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

Историческая справка

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

Присутствие в названии дисциплины термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин «линейное программирование» был предложен Дж. Данцигом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Поэтому наименование «Математическое программирование» связано с тем, что целью решения задач является выбор оптимальной программы действий.

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; лауреат Нобелевской премии (1975 г.) , сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

совместно с в 1949 г разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах , , А. Брудно, , и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных ученых. В 1941 г. поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 г Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Куна (англ.), А. Таккера (англ.), Гасса (Gass S. I.), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 г была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области.

Начиная с 1955 г опубликовано много работ, посвященных квадратическому программированию (работы Била, Э. Баранкина (Barankin E.) и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Г. Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.

1.1. Задачи оптимизации

1.1.1. Обозначения.

Всюду ниже R — множество вещественных, N — натуральных, а C — комплексных чисел. С самого начала мы будем использовать векторные обозначения. Всегда через Rm обозначается m-мерное вещественное линейное пространство. При этом мы всегда считаем, что в Rm фиксирован базис и отождествляем Rm с арифметическим m-мерным пространством (пространством упорядоченных наборов m вещественных чисел). Буква Θ будет обозначать нуль пространства Rm. Индекс внизу всегда обозначает координату вектора, например, xi — это i-ая координата вектора x. Последовательности мы обычно будем обозначать индексом вверху: {xn}.

Через (· ,·) обозначается каноническое скалярное произведение в Rm: (x, y) = ∑mi=1xiyi. Если не оговорено противное, порожденную скалярным произведением: || · || = (∑mi=1xi2)1/2.

Обозначение B(x0, r) закреплено для шара в пространстве Rm с центром в x0 радиуса r: B(x0, r) = {x Rm: ||x – x0|| ≤ r}.

Если A={aij}n, mi=1, j=1  — n×m-матрица, то через A также обозначается и линейный оператор из Rn в Rm, задаваемый этой матрицей.

Для двух векторов x, y Rm мы будем писать x ≤ y, если xi ≤ yi при всех i = 1, ..., m; здесь xi и yi — i-е координаты векторов x и y, соответственно.

Мы будем различать обозначение f: X → Y отображения, действующего из множества X во множество Y, и обозначение f: x → y (или x → f(x)) отображения, переводящего точку x в точку f(x), а также обозначение f отображения и обозначение f(x) значения отображения f в точке x.

1.1.2. Задача наилучшего приближения.

Если рассматривать систему n линейных уравнений с m неизвестными

Ax = b

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

f(x) = ||Ax – b||.

(1)

Эту задачу символически записывают в виде

f(x) → min

Норму в (1) можно брать разную. Например, если взята евклидова норма, то получается задача о наилучшем квадратичном приближении

( n ∑ i = 1 | m ∑ j = 1 aijxj – bi | 2 ) 1/2  → min,

или, что эквивалентно,

n ∑ i = 1 || m ∑ j = 1 aijxj – bi || 2  → min,

Геометрически эта задача интерпретируется как задача о нахождении на гиперплоскости A(Rm) в пространстве Rn точки, ближайшей к точке b = (b1, ..., bn).

1.1.3. Задача Штейнера.

Классическая задача Штейнера формулируется так: требуется найти точку x Rm, сумма расстояний от которой до заданных точек x1, ..., xn Rm минимальна. Эта задача типично оптимизационная:

f(x) ≝  n ∑ i = 1 ||x – xi|| → min

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

1.1.4. Задача о рационе.