Геометрическая интерпретация задачи нелинейного программирования

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

В евклидовом пространстве Е_n система ограничений                                    g_i (x₁, x₂, ..., x_n)=b_i, i=1, 2, ..., k,     определяет область допустимых решений задачи (ОДР). В отличие от ЗЛП она не всегда является выпуклой.

           Если определена ОДР, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f (x₁, x₂, ..., x_n)=h. Указанная точка может находиться как на границе ОДР, так и внутри нее. 

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

           Рассмотрение ЗНЛП начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (3.2) содержит только уравнения, отсутствуют условия не отрицательности и цело численности переменных, а функции g_i (x₁, x₂, ..., x_n) и f (x₁, x₂, ..., x_n) непрерывны и имеют частные производные не ниже второго порядка. Классические методы оптимизации при этом являются теоретическим аппаратом, позволяющим в ряде случаев обосновать разработку соответствующего вычислительного метода.

 

                                                          

Глобальный (абсолютный) и локальный экстремум функции

Т . Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Условный экстремум функции

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

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

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

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

           1. Составление функции Лагранжа.

           2. Нахождение частных производных от функции Лагранжа по переменным x_j и l_i и приравнивание их к нулю.

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

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

54. Определение выпуклой и вогнутой функции

А=l₁А₁+l₂А₂,                                                                                                                  (2.44) 

l₁³0,l₂³0, l₁+l₂=1.                                                                                                         (2.45)

Точка А, для которой выполняются условия (2.44) и (2.45), называется выпуклой линейной комбинацией точек А₁ и А₂. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий.

 

Общая постановка задачи выпуклого программирования. Теорема о существовании решения задачи ВП (формулировка)

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

f (x₁, x₂, ..., x_n)®max,                                                                       (3.3)

g_i (x₁, x₂, ..., x_n)£b_i (i=1, ..., m),                                                        (3.4)

x_i³0 (j=1, ..., n),                                                                               (3.5)

где f и g_i — некоторые функции n переменных x₁, x₂, ..., x_n.

           Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и g_i, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (3.3) — (3.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (3.4) — (3.5), — выпуклая.

           Функция f(x₁, x₂, ..., x_n), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X₁ и X₂ из X и любого 0£l£1 выполняется соотношение

Функция f(x₁, x₂, ..., x_n), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X₁, X₂ из X  и любого 0£l£1 выполняется соотношение

Если f (X) — выпуклая функция, то –f (X) — вогнутая функция, и наоборот.

           Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция. Задача (3.3) — (3.5) является задачей выпуклого программирования, если функция f(x₁, x₂, ..., x_n) является вогнутой (выпуклой), а функции g_i (X) (i=1, ..., m) — выпуклыми.

           Т е о р е м а. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

           Говорят, что множество допустимых решений задачи (3.3) — (3.5) удовлетворяет условию регулярности, если существует по крайней мере одна точка X_i, принадлежащая ОДР такая, что g_i (X_i)<b_i (i=1,..., m).

 

---

Дата добавления: 2018-05-12; просмотров: 1380; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!