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

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

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

F (х)→min (max)

при условии

g(x)≤ 0,

где х - вектор искомых переменных; F (х) - целевая числовая функция; g(x) - вектор-функция системы ограничений.

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

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

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

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

Функция Лагранжа для функции имеет вид:

где - вектор множителей Лагранжа.

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

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

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

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

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

Пусть х₁, х₂ - объемы производимой продукции 1-го и 2-го видов, с₁, с₂ - цена единицы продукции 1-го и 2-го видов соответственно. Затраты на приобретение и доставку сырья представляют собой нелинейную функцию, зависящую от объема закупаемого товара, f₁(x₁), f₂(x₂). Таким образом, экономическая рентабельность планируемых мероприятий оценивается формулой

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

Теперь можно сформулировать задачу: определить такие х₁­, х₂, которые бы обеспечивали максимум функционала

при ограничениях

x₁ ,x₂≤0

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

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

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

где х - n-мерный вектор-столбец; х' - n-мерная вектор-строка; с' - n-мерная вектор-строка; b - m-мерный вектор-столбец; А - матрица размера m×n; D - симметрическая квадратная матрица порядка n;

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

где Ώ - множество допустимых планов задачи, определяемое системой ограничений Ах = b, х > 0 .

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

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

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

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

В соответствии с общим принципом двойственности для задачи двойственная задача имеет вид:

при условиях

где A’ - матрица, транспонированная по отношению к А; с - n-мерный вектор-столбец; λ - m-мерный вектор-столбец.

В линейном случае (при D = 0) определение двойственной задачи совпадает с принятым в линейном программировании.

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

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

Условие Куна-Такера для выпуклой задачи имеет вид:

Ах = b;

Таким образом, для того чтобы вектор х° был решением задачи, необходимо и достаточно существование вектора v° ≥ 0 и вектора λ⁰ таких, чтобы система векторов х°, v°, λ⁰ удовлетворяла условию . Любой (2n+m)-мерный вектор {х, v, λ.}, который является решением системы при условии х≥0, v≥0, будет крайней точкой многогранного множества, т.е. базисным решением системы:

Ах = b;

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

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