Глава 1. ЗАДАЧА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

В этой главе дается постановка задачи нелинейного программирования (НЛП), приводится несколько частных случаев задачи, которые иллюстрируются детально рассмотренными примерами. Частные случаи включают задачи геометрического программирования (ГП), оптимального управления (ОУ) и квадратичного программирования, а примеры демонстрируют эффективность НЛП при решении разнообразных и существенно различающихся на вид задач.

1.1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

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

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

Стандартная форма. Чтобы сформулировать задачу НЛП в стандартной форме, требуются некоторые обозначения. Фраза является функцией, означает, что А, действуя на любую точку х из дает из Е.

В стандартной форме задачи НЛП ищется оптимальная точка (решение) х, в которой достигается при

где

Функция является целевой функцией, ограничениями. Любой вектор х, удовлетворяющий всем ограничениям, т. е. любой х, для которого называется допустимым вектором или планом. Множество всех допустимых точек назовем допустимым множеством (множеством планов) и обозначим через Чтобы избежать ненужных осложнений, предположим, что где — пустое множество.

Пример. Рассмотрим следующую задачу, где , а верхний индекс обозначает операцию транспонирования:

при

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