Задачи нелинейного программирования

• ВВЕДЕНИЕ
• 1. КЛАССИЧЕСКИЙ МЕДОД РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
• 1.1 Постановка задачи
• 1.2 Экстремум функции одной переменной
• 1.3 Экстремумы функций многих переменных
• 1.4 Метод неопределенных множителей Лагранжа
• 1.4.1 Основные положения
• 1.4.2 Геометрическая интерпретация метода множителей Лагранжа
• 1.4.3 Экономическая трактовка метода множителей Лагранжа
• 1.4.4 Особые случаи
• 1.5 Особенности реальных задач
• 2. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
• 2.1 Общая характеристика методов решения задач нелинейного программирования
• 2.2 Методы одномерной оптимизации
• 2.2.1 Метод прямого сканирования
• 2.2.2 Метод половинного деления
• 2.2.3 Метод «золотого сечения»
• 2.2.4 Метод Фибоначчи
• 2.3 Методы многомерной оптимизации
• 2.3.1 Метод Гаусса-Зайделя
• 2.3.2 Метод градиента
• 2.3.3 Метод наискорейшего спуска
• 2.3.4 Метод квантования симплексов
• 2.3.5 Поиск при наличии «оврагов» целевой функции
• 2.4 Методы поиска условного экстремума
• 2.4.1 Метод проектирования вектора-градиента
• 2.4.2 Метод ажурной строчки
• 2.5 Проблемы поиска глобального экстремума
• 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
• 3.1 Графический метод решения задач нелинейного программирования
• 3.2 Метод множителей Лагранжа
• 3.3 Компьютерная реализация решений задач нелинейного программирования
• 3.3.1 Решение задач нелинейного программирования в среде приложения Excel
• 3.3.2 Решение задач нелинейного программирования в среде приложения Matlab
• ВЫВОДЫ
• ПЕРЕЧЕНЬ ССЫЛОК
• ПРИЛОЖЕНИЕ, А Блок-схемы методов

Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в сфере деловых отношений и в науке управления государством.

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

Метод «затраты — эффективность» также укладывается в схему нелинейного программирования. Данный метод был разработан для использования при принятии решений в управлении государством. Общей функцией эффективности является благосостояние. Здесь возникают две задачи нелинейного программирования: первая — максимизация эффекта при ограниченных затратах, вторая — минимизация затрат при условии, чтобы эффект был выше некоторого минимального уровня. Обычно эта задача хорошо моделируется с помощью нелинейного программирования.

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

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

Целью дипломного проекта является решение задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования.

Для достижения поставленной цели необходимо выполнить следующее

— решить выбранные задачи нелинейного программирования графическим методом;

— решить выбранные задачи нелинейного программирования методом множителей Лагранжа;

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

Общая характеристика диплома: количество страниц — 68, количество таблиц — 1, количество рисунков — 33, количество ссылок — 6.

1. КЛАССИЧЕСКИЙ МЕДОД РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

В задаче нелинейного программирования требуется найти значение многомерной переменной х=(), минимизирующее целевую функцию f (x) при условиях, когда на переменную х наложены ограничения типа неравенств, i=1,2,…, m, а переменные, т. е. компоненты вектора х, неотрицательны: .

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

1.2 Экстремум функции одной переменной

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

Пусть требуется найти экстремум функции одной переменной Q (u) при отсутствии ограничений на диапазон изменения переменной u.

Необходимым условием существования экстремума непрерывной функции Q (u) является равенство нулю первой производной (dQ /du = 0) или ее отсутствие. Графически равенство нулю производной означает, что касательная к кривой Q (u) в этой точке параллельна оси абсцисс (рис. 1.1, а), на рис. 1.1, б изображен случай, когда производные в точках экстремума не существуют.

Рисунок 1.1 — Различные типы экстремума функции одной переменной:

а — производная в точке экстремума существует;

б — производная в точке экстремума не существует.

Названные условия являются лишь необходимыми условиями. Их выполнение не означает еще, что в данных точках функция имеет экстремум (рис. 1.2).

Рисунок 1.2 — Функции Q(u), удовлетворяющие необходимым условиям экстремума: а — производная равна нулю; б — производная не существует; в — производная равна бесконечности

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

1) Сравнение значений функций. Этот способ сводится к определению значений функции в точках, расположенных слева и справа в достаточной близости от исследуемой точки, т. е. в точках где — малая положительная величина. Если то в точке u1 существует максимум (рис. 1.3).

Если, то в точке u1 существует минимум (рис. 1.3, б). Если же Q (u1) будет занимать промежуточное между положение например,

то в точке u1 экстремума не будет (рис. 1.3,в).

Рисунок 1.3 — Проверка достаточных условий экстремума:

а — максимум; б — минимум; в — экстремума нет

2) Сравнение знаков производной. При этом способе определяется знак первой производной функции в точках и Если знаки производных различны, то в точке u1 имеется экстремум функции Q(u), причем, если при переходе от точки к точке знак производной изменяется с «+» на «-», то в точке u1 — максимум (рис. 1.3, а). Если же знак меняется с «-» на «+», то в точке u1 — минимум (рис. 1.3, б).

Если же знаки производных в точках и одинаковы, то в точке u1 экстремума нет (рис. 1.3, в).

3)Исследование знаков высших производных. Этот способ применяется в тех случаях, когда исследуемая функция имеет производные высших порядков. Если в точке u1 выполняется необходимое условие экстремума, т. е. и существует вторая производная —, значение которой вычисляется в «подозреваемой» точке u1, то точка u1 является точкой максимума, если < 0, и точкой минимума, если .

Если же, то для дальнейших исследований вычисляются и т. д.

При решении практических задач, как правило, приходится исследовать функции, имеющие несколько экстремумов. В этом случае говорят о нахождении наибольшего и наименьшего значения функции, которые называют глобальными экстремумами. Остальные экстремумы называются локальными. Также в практических задачах диапазон изменения переменной u часто бывает ограничен заданным интервалом [a, b], поэтому в число «подозреваемых» точек должны быть включены и крайние точки этого интервала, так как в них может достигаться глобальный экстремум.

1.3 Экстремумы функций многих переменных

В большинстве задач оптимизации критерий оптимальности является функцией нескольких независимых переменных — Если он является непрерывной функцией, имеющей непрерывные частные производные первого и второго порядка по всем переменным uй (й = 1, n), то необходимым условием экстремума в точке является равенство нулю в этой точке первых производных по всем переменным, т. е. точки, в которой функция может достигать экстремума, определяются решением системы уравнений, t=.

Достаточные условия существования экстремума определяются в результате анализа знака квадратичной формы B=, коэффициенты которой определяются соотношениями

; i, j=.

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

т.е. все главные миноры матрицы

A=

должны быть строго положительны.

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

Если квадратичная форма является положительно определенной, то исследуемая точка является точкой минимума, если же квадратичная форма будет отрицательно определенной, то в точке {uй} имеет место максимум.

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

Пусть в реакторе идеального смешения протекает реакция первого порядка (A > P). Требуется определить оптимальные условия — время пребывания и температуру, при которой себестоимость продукта P будет минимальной.

Критерий оптимальности — себестоимость задается функцией

Q (

где u1 — время пребывания, u2 — константа скорости химической реакции, связанная с температурой уравнением Аррениуса u2 = exp (- E / RT), E и R — константы; СА — стоимость единицы расходуемого сырья; Сq — стоимость дополнительного оборудования реактора, исчисляемая с учетом амортизации; Сv -стоимость единицы объема реактора, исчисляемая с учетом его амортизации; U — нагрузка реактора по исходному сырью; xA0 — начальная концентрация вещества А.

Необходимые условия экстремума функции Q(u1, u2) дают систему уравнений:

Последнее уравнение не удовлетворяет ни каким значениям u1, u2, поэтому разумно выдерживать максимально возможную температуру ведения процесса, что определит значение u2. Оптимальное значение времени пребывания, соответствующее принятому значению температуры в этом случае определится как

Минимальная себестоимость составит

.

Найти экстремум функции Q (u1, u2) = Необходимые условия экстремума записываются в виде системы:

Решение полученной системы уравнений дает три подозрительные точки на экстремум: (0, 0); (1, 1); (-1, -1). Для определения существования экстремума в найденных точках требуется проверить достаточные условия. С этой целью составляется матрица

.

В найденных точках

Матрица — знаконеопределенна, следовательно, точка (0, 0) не является экстремальной. Матрицы положительно определенные поэтому в точках (1, 1) и (-1,-1) будет минимум -.

1.4 Метод неопределенных множителей Лагранжа

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

Для решения таких задач в классическом анализе используется метод неопределенных множителей Лагранжа. Сами задачи получили название задач на условный экстремум.

1.4.1 Основные положения

Пусть требуется найти экстремум функции, например, минимум

Q (, при условии

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

где, = - неопределенные множители Лагранжа.

Таким образом, задача нахождения условного экстремума функции сводится к задаче нахождения безусловного экстремума функции, но число неизвестных в ней n + k (uй, й = 1, n; лj, j = 1, k).

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

.

и дает n уравнений для определения неизвестных. Эта система уравнений дополняется к уравнениям и, следовательно, получается (n + k) неизвестных и (n + k) уравнений.

Метод множителей Лагранжа дает лишь необходимые условия существования условного экстремума для непрерывных функций, имеющих также непрерывные производные, поэтому найденные значения переменных могут и не давать экстремума функции Q (u1, …, un), их надо проверить с использованием достаточных условий экстремума функции многих переменных.

В окончательном решении задачи фактически множители Лагранжа не известны, поэтому задача совместного решения системы, иногда ставится как задача исключения «k» неизвестных переменных uй с последующим решением остающейся системы n уравнений с n неизвестными.

Задача Лагранжа имеет «n — k» степеней свободы.

1.4.2 Геометрическая интерпретация метода множителей Лагранжа

Интерес представляют геометрический смысл множителей Лагранжа. Для такой интерпретации лучше рассмотреть задачу с двумя неизвестными и одним ограничением.

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

На рис. 4, б изображены на плоскости переменных u1, u2 линии уровня функции Q (u1, u2) и ограничение ц (u1, u2) = 0, представляющее собой линию. Составляется вспомогательная функция Q (u1, u2) = Q (u1, u2) + лц (u1, u2). Необходимое условие экстремума дает:

Рисунок 1.4 — Геометрический смысл множителей Лагранжа:

а — пространственное изображение;

б — изображение проекции на плоскость u2 — u1

или

В точке А — точке касания линии с линией равного уровня функции и имеют общую касательную и необходимое условие минимума представляет собой условие пропорциональности двух векторов: вектора — градиента функции и вектора — градиента функции

Два вектора пропорциональны друг другу лишь в том случае, если они коллинеарные. Так как градиент функции перпендикулярен касательной к линии уровня, то в точке А выполняется условие, и множитель является коэффициентом пропорциональности между векторами и

1.4.3 Экономическая трактовка метода множителей Лагранжа

В некоторых задачах множители Лагранжа допускают и экономическое толкование. Если толковать целевую функцию Q (u1, …, un) как прибыль, получаемую некоторым предприятием при использовании ресурсов, а условия k ограничения на дефицит ресурсов, то при (u1, …, un) < 0 прибыль, то максимум целевой функции будет расти.

Экономист такую задачу будет решать следующим образом. Он назначит некоторые цены на единицы ресурсов и предложит потребителю купить их по этой цене. Последний, максимизируя чистую прибыль, найдет (u1, …, un) и скажет, сколько ресурсов он хотел бы купить. В экономике почти всегда бывает так, что чем больше, тем меньше (u1, …, un), и чем меньше, тем больше (u1, …, un). Если окажется, что (u1, …, un) > 0, то экономист повысит цену, если (u1, …, un) < 0 — понизит. Так будет происходить до тех пор, пока при некоторой цене, называемой равновесной, потребителю будет выгодно, чтобы дефицит ресурсов (u1, …, un) был равен нулю, при этом чистая прибыль будет максимальна, т. е. будут выполняться условия

Таким образом, равновесная цена с точностью до знака равна множителю Лагранжа.

1.4.4 Особые случаи

В заключение следует отметить особые случаи, когда градиент функции равен нулю и когда градиент ц₁(u1, …, un) равен нулю

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

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

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

тогда можно утверждать, что для условного экстремума Q (u1, …, un) необходимо существование таких чисел, , одновременно не равных нулю, что в точке предполагаемого решения выполнены условия? 0

(u1, …, un) =0.

Если? 0, то его можно выбрать положительным числом, обычно полагают = 1, это никак не отражается на решении.

Требуется найти минимум функции = при условии .

Для решения записывается функция Лагранжа

,

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

откуда Используя уравнение связи, получают и соответственно

.

По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве u1 изделий первым способом затраты равны (4u1 +), а при изготовлении u2 изделий вторым способом они составляют (8u2+). Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальными.

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

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

Необходимое условие экстремума функции Лагранжа дает

откуда

Подстановка найденных значений в условие u1 + u2 = 180 дает

? и, следовательно,=186 и, соответственно, u1 = 91, u2 = 89.

По вторым частным производным можно показать, что найденная точка доставляет минимум функции Q (u1, u2), т. е. если будет изготовлено 91 изделие первым технологическим способом и 89 изделий вторым технологическим способом, общие затраты будут минимальны и составят Qmin = 17 278.

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

1.5 Особенности реальных задач

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

1) Целевая функция не является гладкой, она может быть «колючей» (рис. 1.5), и тогда применять необходимые условия экстремума не представляется возможным.

Рисунок 1.5 — «Колючая» целевая функция

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

Рисунок 1.6 — Целевая функция с минимумом на границе

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

4) Метод множителей Лагранжа предполагает наличие связей в виде равенств. В реальных задачах существуют ограничения и в виде неравенств.

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

2. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

2.1 Общая характеристика методов решения задач нелинейного программирования

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

В большинстве методов нелинейного программирования используется идея движения в n-мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния ui осуществляется переход в следующее состояние ui+1 изменением вектора ui на величину Д ui, называемую шагом.

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

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

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

Методы нелинейного программирования в зависимости от способа задания шага подразделяются на три основных класса: 1) градиентные методы; 2) безградиентные методы; 3) методы случайного поиска. Некоторые методы организуются как комбинированные алгоритмы, использующие достоинства методов различных классов. Кроме того различают методы одномерной оптимизации (u-скаляр) и многомерной оптимизации (u-вектор).

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

Если целевая функция непрерывна в области U, то вокруг точки uопт всегда можно провести в данной плоскости замкнутую линию, вдоль которой значение Q (u) постоянно (рис. 2.1, а). Эти замкнутые линии называются линиями равного уровня функции и отвечают различным значениям =qй. Вокруг точки uопт можно провести сколько угодно линий уровня, причем каждая из них будет целиком охватывает любую линию, для которой значение целевой функции меньше (или больше).

Рисунок 2.1 — Геометрическое представление целевой функции:

а — линии равного уровня; б — линии равного уровня и связи типа равенств; в — линии равного уровня и ограничения типа неравенств

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

Ограничения типа неравенств независимо от их числа наглядно представлены на рис. 2.1, в. Здесь заходить в заштрихованную область нельзя.

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

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

где u, u* - точки, расположенные на прямой l. Эта производная характеризует скорость изменения функции Q (u) в точке и в направлении l, она может быть выражена через производные по координатам, число которых конечно и равно размерности n. Согласно правилу дифференцирования сложных функций, можно записать

.

Рассмотрим расчет ?uй /?l в пространстве двух переменных (рис. 2.2).

Рисунок 2.2 — К определению направляющих косинусов

Из прямоугольного треугольника АВС можно записать

l=.

Таким образом, величины /dl есть не что иное, как направляющие косинусы выбранного направления l по отношению к осям координат. Следовательно, можно переписать следующим образом

.

Если теперь рассмотреть поверхность равного уровня, которая имеет (n-1) независимых переменных, то в каждой точке этой поверхности, называемой гиперповерхностью, можно провести (n-1) взаимно перпендикулярных касательных в соответствии с числом измерений этой поверхности. Кроме того, в этой же точке можно провести ось, перпендикулярную всем касательным и, следовательно, направленную по нормали к поверхности. Подобное построение для случая (n = 3) изображено на рис. 2.3

Рисунок 2.3 — Система координат, связанная с произвольной точкой

поверхности постоянного уровня

Касательные и нормаль могут рассматриваться как система координат с началом в выбранной точке поверхности. Данная система координат обладает тем важным свойством, что частные производные от

функции Q(u) по направлениям осей равны нулю, так как вдоль этих направлений функция Q(u) сохраняет постоянное значение. В соответствии со сказанным производная по произвольному направлению l запишется как

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

Максимальное значение по абсолютной величине не превышает единицы, аргумент при этом равен нулю, следовательно, направление, по которому производная имеет максимальное значение, совпадает с направлением нормали к поверхности постоянного уровня функции Если теперь по направлению нормали отложить вектор длиной равной, то полученный вектор называется градиентом скалярной функции в точке u и обозначается (u) (читается «набла ку») или ().

Формулу можно записать как — проекция градиента функции по направлению l. Отсюда следует, что проекции вектора градиента на оси координат равны производным функции Q (u) по соответствующим переменным, т. е. .

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

2.2 Методы одномерной оптимизации

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

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

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

2.2.1 Метод прямого сканирования

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

Рисунок 2.4 — Локализация экстремума методом сканирования:

а — геометрическая интерпретация; б — блок-схема алгоритма

2.2.2 Метод половинного деления

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

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке с точностью. Отрезок делится пополам и вычисляются значения функции Q (x1) = F1 и Q (x2) = F2 в точках

x_1,2=.

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

Рисунок 2.5 — Метод деления отрезка пополам:

а — геометрическая интерпретация; б — блок-схема

2.2.3 Метод «золотого сечения»

Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод «золотого сечения»: интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении Это соотношение выполняется при …

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x1 (см. рис. 2.6, б) по формуле

x1 = b — (b — a) / 1,618 033 989…

Рисунок 2.6 — Метод «золотого сечения» :

а — золотое сечение; б — геометрическое представление

Точка x2 определяется как точка, симметричная точке x1 на отрезке (a-b).

На основе анализа значений F1 = Q (x1) и F2 = Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий уни-модальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т. д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше. Блок-схема алгоритма метода «золотого сечения» представлена на рис. 2.7.

Рисунок 2.7 — Блок-схема метода «золотого сечения»

2.2.4 Метод Фибоначчи

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением

F0 = F1 = 1; Fk = Fk-1 + Fk-2; k = 2, 3, …

При большом «k» отношение соседних чисел Фибоначчи близко к отношению «золотого сечения» .

Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от, число вычислений значений функции Q (u).

По заданному определяется количество вычислений n и соответствующее ему число Фибоначчи Fn, исходя из соотношения

В остальном схема метода близка к методу «золотого сечения» в котором значение x1 и x2 (см. рис. 2.8) определяются отношением соответствующих чисел Фибоначчи.

Рис. 2.8- Блок-схема метода Фибоначчи

2.3 Методы многомерной оптимизации

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

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

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

В зависимости от принятого алгоритма и выбора начальной точки этим пределом может быть локальный или глобальный экстремум функции Q (u).

2.3.1 Метод Гаусса-Зайделя

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

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

Рисунок 2.9 — Характер движения к оптимуму в методе Гаусса-Зейделя

2.3.2 Метод градиента

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

Идея метода заключается в том, что находятся значения частных производных по всем независимым переменным, = 1, n, которые определяют направление градиента в рассматриваемой точке

=, и осуществляется шаг в направлении обратном направлению градиента, т. е. в направлении наибыстрейшего убывания целевой функции (если ищется минимум). Итерационный процесс имеет вид

где параметр задает длину шага.

Алгоритм метода градиента при непосредственном его применении включает в себя следующие этапы.

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

2) Рассчитывается значение целевой функции в начальной точке ().

3) Определяется направление градиента в начальной точке (рис. 2.10).

Рисунок 2.10 — Характер движения к оптимуму в методе градиента

4) Делается шаг в направлении антиградиента при поиске минимума, в результате чего попадают в точку .

5) Процесс поиска продолжается, повторяя все этапы с п. 2, т. е. вычисляется) определяется направление градиента в точке u¹, делается шаг и т. д.

Важной задачей в этом методе является выбор шага. Если размер шага слишком мал, то движение к оптимуму будет долгим из-за необходимости расчета целевой функции и ее частных производных в очень многих точках. Если же шаг будет выбран слишком большим, то в районе оптимума может возникнуть «рыскание», которое либо затухает слишком медленно, либо совсем не затухает. На практике сначала шаг выбирается произвольно. Если окажется, что направление градиента в точке u1 существенно отличается от направления в точке u², то шаг уменьшают, если отличие векторов по направлению мало, то шаг увеличивают. Изменение направления градиента можно определять по углу поворота градиента рассчитываемого на каждом шаге по соответствующим выражениям.

Итерационный процесс поиска обычно прекращается, если выполняются неравенства, ?,

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

2.3.3 Метод наискорейшего спуска

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

n — размерность вектора u, Q — алгоритм вычисления целевой функции Q (u),

L -количество шагов по конкретному направлению градиента функции Q.

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

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

2.3.4 Метод квантования симплексов

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

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

Рисунок 2.11 — Блок-схема метода наискорейшего спуска

Алгоритм поиска заключается в следующем.

1) Определяются значения целевой функции в трех точках S10, S20, S30, соответствующих вершинам симплекса. Из найденных значений выбирается наибольшее. В рассматриваемом примере — это S10 (рис. 2.12).

Рисунок 2.12 — Поиск оптимума симплексным методом

2) Строится новый симплекс, для этого вершина S10 исходного симплекса заменяется вершиной S11, расположенной симметрично вершине S10 относительно центра грани, расположенной против вершины S10. Построение нового симплекса S20 S30 S11 осуществляется определением центра А стороны S20 S30 треугольника S10 S20 S30, после чего проводится прямая S10A, на продолжении которой откладывается отрезок АS11 равный S10А.

3) Вычисляется значение целевой функции в вершине S11, которое сравнивается с известными значениями в вершинах S20 и S30. В результате определяется вершина S30 с наибольшем значением целевой функции, подлежащая исключению при построении следующего симплекса S11 S20 S31.

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

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

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

2.3.5 Поиск при наличии «оврагов» целевой функции

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

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

2) Выбирается начальная точка u0, из которой производится поиск, будем считать для определенности, минимума любым методом локального поиска. Этот поиск закончится на дне «оврага», в результате чего будет найдена некоторая критическая точка u1… (рис. 2.13).

Рисунок 2.13 — Метод «оврагов»

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

4) Из состояния производится поиск минимума, в результате которого определяется еще одна критическая точка u2, расположенная на дне «оврага» (рис. 2.13).

5) Две найденные критические точки u1 и u2 соединяются прямой и выполняется «шаг по оврагу» в направлении убывания целевой функции. Это дает новое исходное состояние .

6) Из состояния производится спуск на «дно оврага» и находится критическая точка u3. Далее определяется состояние и т. д. (рис. 2.13).

Процесс поиска продолжается до тех пор, пока значение целевой функции во вновь найденной критической точке не окажется больше, чем в предыдущей точке. Минимум в этом случае находится между точками uk-1 и uk+1. Далее процесс поиска можно повторить, но уже с меньшими «шагами по оврагу», пока не будет достигнута требуемая точность.

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

2.4 Методы поиска условного экстремума

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

Задача нелинейного программирования в этом случае формулируется следующим образом: требуется найти оптимум (минимум) функции Q () при и условия, что .

Число условий типа неравенств может быть любым, т. е. меньше или больше числа независимых переменных.

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

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

2.4.1 Метод проектирования вектора-градиента

При решении задач поиска максимума функции с ограничениями типа неравенств вида часто используется метод проектирования вектора-градиента. Согласно этому методу движение к оптимуму происходит вдоль границы допустимой области. Степень нарушения ограничений определяется функцией H (u)=,, т. е. внутри допустимой области U функция H (u) тождественно равна нулю. При таком подходе к решению задачи положение точки при выполнении очередного шага должны оставаться за пределами области U, где градиент функции H (u) отличен от нуля. Если в результате выполнения очередного шага произойдет слишком большое нарушение ограничений, то коррекция этого нарушения должна осуществляться до того положения, пока функция H (u) еще отлична от нуля.

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

Если условие < 0 оказывается нарушенным, то происходит «отрыв» от границы области U и дальнейший подъем будет происходить уже без влияния ограничений (рис. 2.14, точка u3).

Рисунок 2.14 — Поиск оптимума методом проектирования

вектора-градиента при наличии ограничений типа неравенств

2.4.2 Метод ажурной строчки

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

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

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

Рисунок 2.15 — Поиск оптимума методом ажурной строчки

Вычисляется градиент функции? (u) и осуществляется возврат в допустимую область. Следующий шаг делается опять по градиенту целевой функции Q (u) и т. д. Сложность метода заключается в выборе алгоритма уменьшения шага и правила остановки. Это зависит от опыта и способностей программиста и определяется его творчеством.

2.5 Проблемы поиска глобального экстремума

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

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