Методы нелинейной и дискретной оптимизации

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

(1).

при условии.

(2).

где — некоторые известные функции n переменных, а — заданные числа.

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

а целевая функция является сепарабельной (суммой n функций), или квадратической.

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

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

находят частные производные.

и рассматривают систему n + m уравнений.

(3).

с n + m неизвестными,. Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции при ограничениях.

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

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

Из второго и третьего уравнений следует, что; тогда.

Решив данную систему, получим:

и.

Функция, заданная на выпуклом множестве Х, называется выпуклой, если для любых двух точек из Х и любого выполняется соотношение.

. (4).

Функция, заданная на выпуклом множестве Х, называется вогнутой, если для любых двух точек из Х и любо;

го выполняется соотношение.

. (5).

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

Рисунок 1.

Если.

— выпуклые (вогнутые) функции на некотором выпуклом множестве, то функция _ также выпуклая (вогнутая) на Х.

Основные свойства выпуклых и вогнутых функций:

• 1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, _ выпукло.
• 2. Пусть _ выпуклая функция, заданная на замкнутом выпуклом множестве. Тогда локальный минимум на Х является и глобальным.
• 3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.
• 4. Если _ строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.
• 5. Пусть функция _ выпуклая функция, заданная на выпуклом множестве Х, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках Х. Пусть — точка, в которой

Тогда в точке достигается локальный минимум, совпадающий с глобальным минимумом.

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

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

(6).

(7).

(8).

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

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

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

Точка.

называется седловой точкой функции Лагранжа, если.

для всех и .

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

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

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

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

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

Xj — целые неотрицательные.

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

• — метод отсечения;
• — метод дерева решений;
• — эвристические (приближенные) методы.

Метод отсечения ориентированы на использования в задачах целочисленного линейного программирования (ЦЛП). Идея отсечения состоит в том, что однократное решение задачи ЦЛП сводится к многократному решению некоторой последовательности задач ЛП. Каждый раз решается новая ЗЛП, полученная из предыдущей дополнением к ней нового ограничения, обладающего двумя свойствами:

• — только что полученное нецелочисленное оптимальное решение ЗЛП не удовлетворяет новому ограничению;
• — любое целочисленное решение (не только оптимальное) ему удовлетворяет.

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

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

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