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

Таблица 3.2.

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

2. В качестве управляемых переменных задачи следует взять:

x₁ - количество комплектов корпусной мебели 1;

x₂ - количество комплектов корпусной мебели 2.

3. Целевая функция:

или

4. Ограничения:

4.1. По использованию сосны, м³:

4.2. По использованию березы, м³:

4.3. По использованию дуба, м³:

4.4. Обязательства по контракту, шт.:

4.5. Областные ограничения:

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

• методы штрафных функций;
• методы прямого поиска;
• методы линеаризации.

где

R - набор штрафных параметров;

К штрафу выдвигаются следующие требования:

• решение подзадач должны стремиться к решению исходной задачи нелинейного программирования ;
• сложность оптимизации P(x,R) должна быть такого же порядка, что и W(x).

Методы штрафных функций классифицируются в соответствии со способами учета ограничений - неравенств g(x), так как ограничения-равенства h(x) учитываются во всех методах одинаково с помощью квадратичного штрафа

Для учета ограничений - неравенств используют следующие штрафы:

• "Бесконечный" штраф

где

• Логарифмический штраф

• Штраф обратной функции

• Штраф квадрата срезки

где

g(x) =

В данном методе недопустимые точки не создают проблем (в отличие от предыдущих), поэтому он весьма удобен. Кроме того функция P(x,R) определена и непрерывна всюду. Вычисления следует проводить с положительными R_i; после решения очередной подзадачи безусловной оптимизации R необходимо увеличивать.

Алгоритм методов штрафных функций:

Шаг 4. Проверить, выполняется ли условие

• если "да" - положить x^t+1=x^T и закончить процесс решения;
• если "нет" - перейти к следующему шагу.

Перед непосредственным применением методов прямого поиска необходимо провести ряд мероприятий по подготовке задачи к решению, а именно

• исключить ограничения в виде равенств;
• определить начальную допустимую точку.

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

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

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

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

• метод комплексов;
• метод случайного поиска.

Алгоритм:

Шаг 1. Построение начального комплекса, состоящего из P допустимых точек(рекомендуется P=2N). Для каждой точки p = 1, 2,...,P-1

1. случайным образом определить координаты x^p;
2. если x^p - недопустимая точка, то найти центр тяжести x_цт уже найденных точек и положить x^p = x^p + (x_цт - x^p); повторять процедуру до тех пор, пока x^p не станет допустимой;
3. если x^p - допустимая точка, повторять a) до тех пор, пока p=P;
4. вычислить W(x^p) для p=0,1,...,P-1.

Шаг 2. Отражение комплекса:

Шаг 3. Корректировка для обеспечения допустимости:

1. если x_i^m < x_i^L(нижняя граница допускаемой области), то положить x_i^m = x_i^L; если x_i^m > x_i^U(верхняя граница допускаемой области), то положить x_i^m = x_i^U;
2. если x^m - недопустимая точка, то уменьшить в два раза расстояние до центра тяжести; продолжать до тех пор, пока x^m не станет допустимой точкой.

Шаг 4. Проверка условий окончания вычислений:

1. положить и ;
2. если и , то вычисления прекратить; в противном случае перейти к шагу 2a.

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

где

r_i - случайная величина, равномерно распределенная на интервале [0,1].

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

Шаг 1. Для i = 1,2,...,N вычислить

где

• Если x^p - недопустимая точка и p < P, то повторить шаг 1.
• Если x^p - допустимая точка, то запомнить x^p и W(x^p) и

• если p < P, то повторить шаг 1.
• если p = P, то найти среди всех допустимых точек x^p точку с наименьшим значением W(x^p) и положить ее равной x^q.

• Если q > Q, то закончить вычисления.
• В противном случае увеличить q = q + 1 и продолжить вычисления, начиная с шага 1.

Идея методов заключается в сведении задачи нелинейного программирования к задаче линейного программирования. С этой целью нелинейные функции целевой функции W(x) и ограничений g(x), h(x) в ряд Тейлора до членов первого порядка в окрестности точки линеаризации x^t, что позволяет W(x), g(x), h(x) аппроксимировать линейными функциями и свести общую задачу нелинейного программирования

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

Решая ее при помощи методов линейного программирования, находим новое приближение x^t+1. В случае нелинейных функций точка x^t+1 обычно недопустимая точка. Однако для сходимости к оптимуму достаточно, чтобы последовательность точек {x^t}, полученных в результате решения последовательности подзадач линейного программирования, выполнялось следующее условие: значение целевой функции W и невязки по ограничениям в x^t+1 меньше их значений в точке x^t.