Постановка и решение задач нелинейного программирования

5.1. Методы решения задач
нелинейного программирования

5.1.1. Основные понятия

Согласно определению признака экстремума функция f(x) имеет максимум (минимум) в точке х*, если в достаточной близости от этой точки всем значениям х соответствуют значения f(x) меньшие (большие), чем f(x*). Для случая максимума это показано на рис. 5.1.1.

Рис. 5.1.1

Рис. 5.1.2

Максимум и минимум функции объединяются понятием экстремум, который может быть как локальным, так и глобальным. На рис. 5.1.2 функция f(x) принимает максимальные значения в вершинах В и D. При этом B > D. В таком случае говорят, что точка В является глобальным максимумом, а точка D — локальным. Аналогично функция f(x) принимает минимальные значения в точках А, С, Е, причем С < A < E. В этом случае С будет глобальным минимумом, а А и Е — локальными минимумами. Из приведенных примеров видно, что глобальным максимумом (минимумом) называют такой максимум (минимум), который больше (меньше) всех остальных.

Рис. 5.1.3

Достаточно часто при введении граничных условий типа х Ј b, показанных на рис. 5.1.3, наибольшее значение функции находится на границе в точке х = b. При этом величина f(b) не удовлетворяет приведенному выше признаку экстремума.

В таких случаях говорят, что в точке х = b находится оптимум функции f(b) = B.

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

Существующие методы дают возможность находить только локальные оптимумы. Если же есть подозрение, что в заданном интервале а_j Ј x_j Ј b_j целевая функция f(x_j) может иметь несколько оптимумов, то этот интервал следует разбить на n интервалов, в каждом интервале определить свои локальные оптимумы, а затем из всех локальных оптимумов выбрать глобальный. В таком случае задача нахождения глобального оптимума сводится к решению ряда задач, в которых ищется локальный оптимум.

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

задачи безусловной оптимизации;

задачи условной оптимизации.

Задача безусловной оптимизации представляет собой поиск оптимума целевой функции без всяких дополнительных условий, что записывается:

f(x) ® max(min).

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

Задача условной оптимизации в общем случае записывается в уже известном виде (1.1.9):

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

5.1.2. Поиск решения
при безусловной оптимизации

Задачи нелинейной оптимизации могут решаться различными методами. Методы, реализованные в Excel, относятся к методам поиска, который рассмотрим на таком примере. Представим себе человека, находящегося у подножия горы и стремящегося покорить вершину. Для этого ему нужно идти все выше, выше и выше. Но как идти? Каким маршрутом? Чтобы составить маршрут, нужно, во-первых, знать начальную точку, во-вторых, выбрать путь движения и, наконец, определить, достижение какой точки следует считать достижением цели.

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

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

Прежде всего надо задаться координатами начальной точки поиска х_j⁰, . Желательно, чтобы выбранная начальная точка х_j⁰ была как можно ближе к искомому экстремуму, что сократит время поиска. Но как же такую точку выбрать? Если решается реальная задача, то специалист всегда знает ожидаемую область нахождения экстремума, в которой и следует задать начальную точку.

Рис. 5.1.4

Если решающий задачу не является специалистом в данной области, то это к добру не приведет и не только потому, что начальная точка поиска будет выбрана неудачно. Некоторые рекомендации по выбору начальной точки приведены ниже при рассмотрении решения задачи в Excel. Но не будем впадать в пессимизм, будем считать, что задачами оптимизации занимается специалист, знающий свое дело.

Итак, х_j⁰, выбрана. Блок-схема алгоритма поиска приведена на рис. 5.1.4. Графическое изображение такого движения для случая поиска максимума при j = 1,2 показано на рис. 5.1.5.

Идея поиска экстремума заключается в следующем:

Задать начальную точку х_j⁰, .

В заданной точке х_j⁰ определить направление движения на первом шаге b₁.

Принять величину шага t₁.

Определить координаты конца первого шага х_j¹.

Рис. 5.1.5

Вычислить значения признака экстремума на первом шаге.

Проверить выполнение признака экстремума.

Если условие признака выполняется, то принимается что экстремум находится в точке х_j⁰, если нет — аналогично выполняется второй шаг и так далее до выполнения условия, характеризующего достижение экстремума.

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

.

Экстремум считается достигнутым, если выполняется условие

DF_k £ DF_зад,

где DF_зад — точность, назначаемая при решении задачи.

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

Методами поиска называются такие методы, которые для определения направления b и величины шага t используют только значение целевой функции. Такие методы называют также методами нулевого порядка.

Градиентные методы или методы первого порядка — это такие методы, в которых для определения направления b и шага t используются значения первых производных целевой функции и определяется ее градиент.

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

Чем выше порядок методов, тем больше вычислений на каждой итерации, но тем меньше требуется итераций. И, естественно, наоборот. Наиболее распространенными являются градиентные методы. Такое положение объясняется тем, что с одной стороны, они не требуют на каждой итерации очень больших вычислений, т. к. вычисляется только целевая функция и ее первые производные, а с другой — у этих методов достаточно хорошая сходимость, т. е. они обеспечивают нахождение экстремума за небольшое число итераций.

Градиентные методы по способу определения направления b и шага t имеют много разновидностей. Заметим, что для практического решения задачи суть этих методов знать совершенно не обязательно.

Таковы основные идеи поиска решения в задачах безусловной оптимизации.

5.1.3. Решение задачи условной оптимизации

Общий случай задачи оптимизации (1.1.9)

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

Преобразовать ограничения-неравенства в уравнения

v_i(x_j) = g_i(x_j) - b_i,

_.

Записать ограничения в виде

v_i(x_j) = 0,

.

Аналогично преобразовать граничные условия.

Тогда задача условной оптимизации будет иметь вид:

(5.1.1)

Задачу (5.1.1) представить в виде функции Лагранжа

(5.1.2)

где l_i — множитель Лагранжа.

Физический смысл множителей Лагранжа поясним чуть позже при рассмотрении примера.

Определить частные производные и составить систему уравнений

(5.1.3)

Решая систему (5.1.3), определить значения l_i.

Подставить значения l_i в (5.1.2). При этом (5.1.2) будет представлять собой задачу безусловной оптимизации.

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

Проиллюстрируем метод множителей Лагранжа следующим примером:

(5.1.4)

Запишем систему (5.1.4) в форме (5.1.1):

(5.1.5)

тогда

Рис. 5.1.6

Графическое представление задач линейного программирования было рассмотрено в главе 2. Те же подходы применимы и для задач нелинейного программирования. Графическая интерпретация задачи (5.1.5) приведена на рис. 5.1.6.

Составим функцию Лагранжа

(5.1.6)

В (5.1.6) видно, что множитель Лагранжа определяет, как изменится целевая функция при изменении правой части в данном ограничении на единицу. Следовательно, множитель Лагранжа в нелинейной задаче — это аналог двойственной оценки в линейной задаче.

Запишем систему уравнений

(5.1.7)

В результате решения системы (5.1.7) найдем

. (5.1.8)

Подставим (5.1.8) в функцию Лагранжа (5.1.6):

(5.1.9)

Задача (5.1.9) является задачей безусловной оптимизации, решение которой производится методами, рассмотренными выше.

5.2. Решение задач нелинейного
программирования в Excel

5.2.1. Пример задачи
нелинейного программирования

Решение задачи нелинейного программирования рассмотрим на следующем примере. Требуется определить размеры бака, имеющего форму параллелепипеда (рис. 5.2.1) заданного объема.

Рис. 5.2.1

Объем бака

V = abh.

Полная поверхность

S = 2(ab) + 2(a + b)h = 2(ab + (a + b)h). (5.2.1)

Принимаем, что стоимость материала

С = kS, (5.2.2)

где k - стоимость единицы площади материала.

Подставив в (5.2.2) значение (5.2.1), получим

C = 2k(ab + (a + b)h). (5.2.3)

После введения рассмотренных величин сформулируем задачу оптимизации следующим образом:

(5.2.4)

В этой постановке требуется определить размеры бака а, b, h, стоимость которого не должна превышать С_зад, чтобы его объем V был максимальным.

Для решения задачи (5.2.4) принимаем следующие конкретные значения:

k = 10 т.руб./м²,

C_зад = 100 т.руб.

Тогда (5.2.4) будет иметь вид

(5.2.5)

Система (5.2.5) и будет той задачей, на примере которой мы рассмотрим решение задач нелинейного программирования в Excel.

5.2.2. Решение задачи нелинейного
программирования в Excel

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

назначаются начальные значения искомых переменных х_j⁰;

в диалоговом окне Параметры поиска решения не надо вводить Линейная модель.

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

Начальные значения х_j⁰, как отмечалось ранее, желательно назначать близкими к ожидаемым оптимальным значениям, что ускорит решение задачи. Но это — пожелание. А обязательные требования заключаются в том, чтобы целевая функция в начальной точке не была равна нулю.

F(х_j⁰) ¹ 0.

Это необходимо, чтобы не было деления на ноль при вычислении DF_k.

Решение задачи нелинейного программирования рассмотрим на примере задачи (5.2.5), сформулированной в разделе 5.2.1.

Алгоритм 5.2.1. Ввод данных для задачи
нелинейного программирования

Сделать форму для ввода условий задачи (рис. 5.2.2).

Ввести:

зависимости для объема и стоимости;

начальные значения х_j⁰;

в ячейки B3, С3, D3, E3 ввести 1 для обеспечения требования F(х_j⁰) № 0.

Рис. 5.2.2

В ячейках, в которых будет представлен результат, назначить число знаков после запятой. В нашем примере назначаем в ячейках 2 знака после запятой.