Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

4. Функции f (x) может иметь несколько экстремумов, а именно:

-локальный и глобальный экстремумы (пусть это будет максимум);

-функция f (x) , определенная на области D, достигает на ней гло-

бального максимума в точке x 0 D , если неравенство f (x) ≤ f (x 0 )

рой окрестности точки x0 .

5. В математическом анализе для нахождения экстремума функций используются производные. Эти методы называются классическими методами оптимизации.

Различают задачи безусловного и условного экстремумов.

Задача на безусловный экстремум – задача максимизации функции f (x) при отсутствии ограничений. Необходимые условия экстремума в

этом случае записываются в виде системы уравнений:

∂f (x1 , …, xn ) = 0 , j =1, n .

∂xj

Решая данную систему уравнений, находят стационарные точки, а затем после их анализа – оптимальную точку.

Задача на условный экстремум предусматривает ограничения в виде равенств: т.е. минимизировать f (x) при ограничениях g(x) = b.

В векторной форме g и b – m-мерные векторы.

Эта задача сводится к задаче на безусловный экстремум с помощью множителей Лагранжа. С этой целью образуют функцию Лагранжа:

m

L(x, λ) = f (x) + ∑λi [bi − gi (x)],

i=1

где λi – множители Лагранжа.

Функция L(x, λ) зависит от т+п переменных, на которые наложены

ограничения.

Оптимальную точку находят в результате решения и последующего анализа системы уравнений:

11

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

• Для использования методов надо, чтобы функции f (x) и g(x)

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

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

•С помощью классических методов можно найти экстремум функции только внутри области.

Если оптимальная точка находится на границе области, то методы эти бессильны.

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

12

Г л а в а 1

МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Постановка задачи

Общая задача нелинейного программирования формулируется так. Найти min f (x1 , …, xn ) при ограничениях

gi (x1, …, xn ) ≤ bi , i =1, m .

Пример. Задача о размещении. Эта задача напоминает

пунктов производства. Будем считать, что для каждого i-го пункта производства известна зависимость стоимости производства fi от объема производства xi , т.е. функции fi (xi ) ,

i =1, m – это, как правило, нелинейные функции (рис. 1.1).

fi (xi )

xi

Рис. 1.1. Типичный вид зависимости стоимости производства от объема производства

Из рисунка следует, что чем больше объем, тем меньше себестоимость единицы продукции.

13

Наконец, задана матрица транспортных расходов cij ,

элементами которой являются стоимости перевозок единицы продукции из i-го пункта производства в j-й пункт потребления.

Требуется найти такие объемы перевозок xij из i-го в j-й пункт и

n

такие объемы производства xi = ∑xi j , которые обеспечивают

j=1

потребности по всем продуктам в j -м пункте назначения

m

( b j = ∑xi j ) и минимизируют суммарные расходы.

i=1

В результате возникает следующая задача нелинейного программирования с ограничениями:

найти

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

1.1.1. Минимизация функции одной переменной

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

14

На первый взгляд кажется, что задача минимизации функции одной переменной является, довольно, элементарной. В самом деле, если функция f(x), которую нужно минимизировать на отрезке [a, b], дифференцируема, то достаточно найти нули производной, присоединить к ним концы отрезка, выделить из этих точек локальные минимумы и, наконец, среди последних найти ту точку, в которой достигается абсолютный (глобальный) минимум. Этот метод является классическим методом. Он основан на дифференциальном исчислении и довольно подробно описан в литературе.

Однако для широкого класса функций эта задача не так уж проста, и классический метод имеет весьма ограниченное применение, поскольку задача решения уравнения f ′(x) = 0 может

оказаться весьма сложной. К тому же в практических задачах часто неизвестно, является ли f (x) дифференцируемой функцией. Кроме

того, во многих практических задачах часто невозможно найти явную зависимость f (x) . Поэтому существенное значение

приобретают методы минимизации, не требующие вычисления производной.

Существование локальных минимумов функции f (x) , почти

всегда затрудняет поиск глобального минимума. Поэтому многие приближенные методы минимизации применимы только тогда, когда любой локальный минимум функции f (x) является

одновременно и глобальным. Это дает гарантию сходимости методов. Если же такие сведения о функции не известны, то методы применять можно, но без гарантии сходимости.

Одним из классов функций, удовлетворяющих указанному условию, является класс унимодальных функций.

Определение. Функция f (x) называется унимодальной на

отрезке [a, b], если она непрерывна на [a, b] и существуют такие числа α и β (a ≤ α ≤ β ≤ b) , что:

1)на отрезке [a, α] при a < α, функция монотонно убывает;

2)на отрезке [β, b] при β < b, функция монотонно возрастает;

3) f ( x) = f * = min f ( x) при x [α, β], т.е. данная функция

[ a ,b ]

имеет минимум.

15