Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

200 Глава 12. Многомерная оптимизация с ограничениями

Так как f и gi выпуклы, то выпуклы и g˜i, преобразованная задача есть задача с линейной целевой функцией и выпуклыми ограничениями. Легко видеть, что новая задача эквивалентна исходной.

Теория

Пусть имеется задача минимизации л и н е й н о й

метода

целевой функции при выпуклых нелинейных ограни-

чениях (если задача преобразовывалась, то рассматривается уже преобразованная задача, нумерация переменных и ограничений новая, знаки тильды опущены):

По концепции он близок методу Гомори в целочисленном программировании [9, гл. 7], также основанному на отсечениях.

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

лит полупространство, а совокупность m неравенств в сочетании с ограничениями на неотрицательность задаст выпуклое многогранное множество M (0).

Легко убедиться, что оно включает в себя множество планов исходной задачи (12.33), которое мы обозначим через D. Действи-

подставить координаты этой точки в уравнение гиперплоскости, получим

202 Глава 12. Многомерная оптимизация с ограничениями

Добавляя полученное отсечение к ограничениям задачи 0, получаем задачу 1

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

M (0) M (1) · · · M (k) · · · D.

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

→−X (k) → −→X .

В отличие от метода Гомори, метод Кэлли не гарантирует сходимости за конечное число итераций, при этом на каждой итерации точка приближенного решения остается з а п р е д е л а м и области допустимых значений.

Для того чтобы определить, какую конкретно отсекающую

плоскость следует построить на k-й итерации, рекомендуется под-

→− (k)

ставить текущее приближение X во все ограничения и найти то из них, которое нарушается в наибольшей степени. Ему соответствует индекс

−→

p = arg max cut[gi(X (k)],

i

где cut[x] — функция срезки (с. 158 ). Если при этом текущее приближение оказывается достаточно близко к допустимой области,

−→

о чем свидетельствует выполнение соотношения gp(X (k)) < ε, где ε — предустановленный параметр точности, то работа алгоритма завершается.

−→

Замечание. Если gi(X ) – линейная функция, то дополнительно линеаризовать ее не нужно, на любой итерации линеаризованная

П о д г о т о в и т е л ь н ы й э т а п

Если целевая функция задачи нелинейна, производится ее линеаризация, для чего вводится дополнительная переменная и дополнительное ограничение (да-

лее функции ограничений gi уже новые).

Н а ч а л ь н а я з а д а ч а

П о д г о т о в и т е л ь н ы й э т а п

Введя дополнительную переменную x3 и дополнительную ограничивающую функцию g˜4, сформулируем новую задачу с линейной целевой функцией и нелинейными ограничениями. Функции g˜1, . . . , g˜4 теперь зависят от т р е х переменных (для упрощения обозначений знаки тильды далее опускаем):

x3 → min;

g1(x1, x2, x3) = x21 + x22 − 4 0, g2(x1, x2, x3) = −x1 + x2 0, g3(x1, x2, x3) = x2 − 1 0,

g4(x1, x2, x3) = (x1 − 2)2 + (x2 − 2)2 − x3 0, x1, x2, x3 0.

Н а ч а л ь н а я з а д а ч а

Ш а г 2. Строим начальную задачу линейного программирования. Поскольку функции g2 и g3 линейные, то потребуется знание

Таким образом, задача линейного программирования для нахождения первого приближения имеет вид

x1, x2, x3 0.

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

И т е р а ц и я 1

Ш а г 3. Решаем данную задачу симплексным методом, полу-

−→

чаем оптимальный план X (1) = (68.8506, 0.9951, 0)T , он выходит

далеко за допустимую область.

−→(1)

Ш а г 4. Подставляя X в каждое из ограничений, получа-

ем четыре числа: (4737.4, −67.9, 0, 4470.0). Нарушаются первое и четвертое ограничения, причем первое нарушается сильнее, поэтому индекс p = 1, δ(1) = 4737.4. На основе этого ограничения строим новое отсечение. Вычисляем

И т е р а ц и я 2

Ш а г 3. Решаем новую задачу симплексным методом, полу-

→−

чаем оптимальный план X (1) = (33.6886, 0.5549, 0.0000)T .

−→(1)

Ш а г 4. X также выходит за допустимую область, но уже меньше, так как δ(2) = 1131.2 < δ(1) = 4737.4.

Ш а г 5. Достраиваем задачу линейного программирования, переходим к новой итерации и т. д.

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

Таблица 12.3. Итерации метода секущих плоскостей для примера

208 Глава 12. Многомерная оптимизация с ограничениями

12.7. Исторические замечания

Численные методы нелинейной оптимизации с ограничени-

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

тье5, опубликованной еще в 1943 г. Ее автором был выдающийся математик XX века Рихард Курант (Courant,

Richard; 1888–1972). Курант повторил судьбу многих европейских ученых еврейского происхождения. С 1920 по 1933 г. он был профессором Гёттингенского университета в Германии, после прихода нацистов к власти и разгрома Математического института Курант эмигрировал в США. С 1936 г. работал профессором Нью-Йоркского университета, где ему было поручено создание специального математического института (с 1964 г. называется Куран-

Рихард Курант товский институт математических наук). Расцвет численных методов нелинейного

программирования пришелся на 1960–1970-е годы, в эпоху общего бума исследования операций. Активные исследования велись параллельно во многих научных коллективах, в мировой математической литературе появились тысячи публикаций на эту тему, некоторые впоследствии были признаны классическими. Хотя национальная принадлежность их авторов была весьма широкой, наиболее существенные результаты были получены в США и Великобритании, где на базе ведущих университетов и крупнейших корпораций развились научные коллективы, возникшие во време-

5Courant R. Variational methods for the solution of problems of equilibrium and vibrations // Bull. Amer. Math. Soc. 1943. V. 49. P. 1–23.