52)Понятие о методах нелинейного планирования.

Ответ: Задачи математического программирования

max (min) Z = ƒ(x); (6.1) φ_i (x) {≤ , = , ≥ }b_i (i – 1,….m), x ≥ 0, x = (x₁,…., x_n), (6.2) в которой либо целевая функция (6.1), либо ограничения (6.2), либо и то и другое не линейны, называются нелинейными. Сложность решения задач нелинейного планирования заключается кроме нелинейности условий задачи еще и в том, что некоторые переменные могут изменяться не непрерывно, а принимать ряд заданных фиксированных значений. Кроме того, сложность решений и в том, что целевые функции могут иметь не один, а несколько максимумов (минимумов), и нужно найти глобальный экстремум. Геометрическая интерпретация задач нелинейного планирования аналогична задачам линейного планирования.

53)Общая постановка задачи нелинейного планирования.

Ответ: Общая постановка задачи нелинейного планирования может быть сформулирована следующим образом: найти параметры Х^* (х₁, х₂,…, х_п), обращающих целевую функцию W = ƒ(х₁, х₂,…, х_п) в mах(min) при условии наложенных ограничений φ₁(х₁, х₂,…, х_п) ≤ b₁;

φ₂(х₁, х₂,…, х_п) = b₂;

……………………….

φ_i(х₁, х₂,…, х_п) ≥ b_i;

……………………….

φ_m(х₁, х₂,…, х_п) ≤ b_m;

х_j ≥ 0 j = 1,2,…n; число ограничений меньше числа переменных; и (или) целевая функция, и (или) ограничения представляются нелинейными зависимостями. Нелинейные задачи составляют широкий класс настолько сложных задач, что до сих пор невозможно разработать общие методы, подобные симплекс-методу в линейном программировании, которые позволяли бы решать любые нелинейные задачи. Но, несмотря на отсутствие универсальных методов, разработаны способы решения специальных классов задач, и прежде всего задач с выпуклыми (вогнутыми) функциями ƒ(х) и φ_i(x).

54)Особенности решения задачи нелинейного планирования.

Ответ: При решении задач нелинейного программирования очень важно знать: 1) выпукло или не выпукло множество решений? 2) является ли критериальная функция W = ƒ(х) выпуклой или вогнутой, или не относится ни к тому, ни к другому классу? Множество выпукло, если оно содержит точки А и В, а так же все точки прямой АВ. Функция у = ƒ(х), определенная на выпуклом множестве Х, называется выпуклой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается выше его (рис. 6.1. а). Функция у= ƒ(х), определенная на выпуклом множестве Х, называется вогнутой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается ниже его (рис. 6.1. б).

Рис. 6.1

Аналогичные понятия можно привести и для функций многих переменных.

В математике доказывается ряд теорем, которые позволяют определять глобальные экстремумы. Так, для задач, в которых множество допустимых решений выпукло: 1) если ƒ(х) – выпуклая функция, то локальный минимум, определенный на выпуклом множестве Х, совпадает с ее глобальным минимумом на этом множестве; 2) если ƒ(х) – вогнутая функция на заданном выпуклом множестве Х, то локальный максимум ƒ(х) является глобальным.

55)Градиентный метод решения задачи нелинейного планирования.

Ответ: Градиентным методом можно решать, вообще говоря, любую нелинейную задачу. Однако при этом находится лишь локальный экстремум. Поэтому применять этот метод рационально при решении задач выпуклого программирования, в которых любой локальный экстремум является одновременно и глобальным. Задачи без ограничений. Рассмотрим задачу максимизации нелинейной дифференцируемой функции f(Х). Суть градиентного поиска точки максимума Х^*очень проста: надо взять произвольную точку Х₀ и с помощью градиента   , вычисленного в этой точке, определить направление, в котором возрастает с наибольшей скоростью, а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку Х₁. Потом снова определить наилучшее направление  для перехода в очередную точку Х₂ и т.д. Таким образом, надо построить последовательность точек Х₀, Х₁, Х₂, …, Х_к, …так, чтобы она сходилась к точке Х^*, т.е. для точек последовательности выполнялись условия f(Х₀) < f(Х₁) < f(Х₂) < … < f(Х_к) < …. Градиентные методы позволяют получать точное решение за бесконечное число шагов и только в некоторых случаях – за конечное. В связи с этим градиентные методы относят к приближенным методам решения. Движение из точки Х_к в новую точку Х_к+1 осуществляется по прямой, проходящей через точку Х_к и имеющей уравнение

Х_к+1 = Х_к +   , (6.7) где   числовой параметр, от которого зависит длина шага.

Градиентные методы отличаются друг от друга способом выбора величины шага – значения параметра α_к. Можно, например, двигаться из точки в точку с постоянным шагом α_к = α, т.е. при любом к Х_к+1 = Х_к +   . Если при этом окажется, что f(Х_к+1) < f(Х_к), то следует возвратиться в точку Х_к и уменьшить значение параметра α, например до α/2. Если ищется приближенное решение, то поиск можно прекратить, основываясь на следующих соображениях. После каждой серии из определенного числа шагов сравнивают достигнутые значения целевой функции f(Х). Если после очередной серии изменение f(Х) не превышает некоторого наперед заданного малого числа ε, поиск прекращают и достигнутое значение f(Х) рассматривают как искомый приближенный максимум, а соответствующее ему Х принимают за Х^*. Если целевая функция f(Х) вогнутая (выпуклая), то необходимым и достаточным условием оптимальности точки Х^* является равенство нулю градиента функции в этой точке. Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъема (наискорейшего спуска – если решается задача минимизации). Суть его в следующем. После определения   f(Х_к) в точке Х_кдвижение вдоль прямой Х = Х_к +   производится до точки Х_к+1, в которой достигается максимальное значение функции f(Х) в направлении градиента   f(Х_к). затем в этой точке вновь определяется градиент, и движение совершается по прямой Х = Х_к+1 +   в направлении нового градиента   f(Х_к+1) до точки Х_к+2, в которой достигается максимальное в этом направлении значение f(Х). Движение продолжается до тех пор, пока не будет достигнута точка Х^*, соответствующая наибольшему значению целевой функции f(Х). На рис.х.х приведена схема движения к оптимальной точке Х^* методом наискорейшего подъема. В данном случае направление градиента   f(Х_к) в точке Х_к является касательным к линии уровня поверхности f(Х) в точке Х_к+1, следовательно, градиент   в точке Х_к+1ортогонален градие   f(Х_к).

 

Рис.6.2

Перемещение из точки Х_к в точку Х_к+1 = Х_к +   сопровождается возрастанием функции f(Х) на величину

 

Δ f(Х) = f(Х_к+1) - f(Х_к) = f(Х_к+1,1;…; Х_к+1,п) - f(Х_к,1;…; Х_к,п) =

 

=   . (6.8)

Из выражения (6.8) видно, что Δf является функцией переменной α_к, т.е. Δf = Δf(α_к). При прохождении максимума функции f(x) в направлении градиента   f(Х_к) необходимо выбирать шаг перемещения (множитель   , обеспечивающий наибольшее возрастание приращению функции, именно функции Δƒ(   . Величина   при которой достигается наибольшее значение Δƒ(   , может быть определена из необходимого условия экстремума функции Δƒ(   : d(Δƒ(   )/dα_k = 0. (6.9)

Найдем выражение для производной, дифференцируя равенство (6.9) по α_к как сложную функцию:

 

 f(Х_к+1)   f(Х_к).

Подставляя этот результат в равенство (х.х1), получаем d(Δƒ(   )/dα_k   f(Х_к+1)   f(Х_к).

Это равенство имеет простое геометрическое истолкование: градиент в очередной точке Х_к+1 ортогонален градиенту в предыдущей точке Х_к.

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

max Z = ƒ(x); (6.10)

ax ≤ a_i0 (i = 1, 2,...m) (6.11)

x ≥ 0, (6.12)

где х = (х₁; х₂;...; х_п); а_i = (a_i1; a_i2;...; a_in). Предполагается, что ƒ(x) является вогнутой функцией и имеются непрерывные частные производные в каждой точке допустимой области. Начнем с геометрической иллюстрации процесса решения задачи (рис.х.хх). Пусть начальная точка Х₀ расположена внутри допустимой области. Из точки Х₀ можно двигаться в направлении градиента   f(Х₀), пока ƒ(Х) не достигнет максимума. В нашем случае ƒ(Х) все время возрастает, поэтому остановиться надо в точке Х₁ на граничной прямой.

Рис. 6.3

Как видно из рисунка, дальше двигаться в направлении градиента   f(Х₁) нельзя, т.к. выйдем из области допустимых решений. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выходит из допустимой области, а с другой – обеспечивает наибольшее возрастание ƒ(Х). Такое направление определяет вектор r₁, составляющий с вектором   f(Х₁) наименьший острый угол по сравнению с любым другим вектором, выходящим из точки Х₁и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения   f(Х₁) r₁ > 0. В данном случае вектор r₁, указывающий наивыгоднейшее направление, совпадает с граничной прямой. Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает ƒ(Х); в нашем случае – до точки Х₂. Из рисунка видно, что далее следует перемещаться в направлении вектора r₂, который находится из условия максимизации скалярного произведения   f(Х₂) r₂ > 0, т.е. по граничной прямой. Движение заканчивается в точке Х₃, поскольку в этой точке завершается оптимизационный поиск, т.к. в ней функция ƒ(Х) имеет локальный максимум. Ввиду вогнутости оптимизационной функции, в этой точке ƒ(Х) достигает глобального максимума в допустимой области. Градиент в точке максимума Х₃ = Х^* составляет тупой угол с любым вектором r_к из допустимой области, проходящей через Х₃, поэтому скалярное произведение   f(Х₃) r_к будет отрицательным для любого допустимого r_к, кроме r₃, направленного по граничной прямой. Для него скалярное произведение   f(Х₃) r₃ = 0, т.к.   f(Х₃) и r₃ взаимно перпендикулярны (граничная прямая касается линии уровня поверхности ƒ(Х), проходящей через точку максимума Х^*). Это равенство и служит аналитическим признаком того, что в точке Х₃ функция ƒ(Х) достигла максимума. Аналитическое решение задачи (х.хх1) – (х.хх3) требует, чтобы при выборе α_копределение очередной точки Х_к+1 = Х_к + α_к   f(Х_к) осталось в допустимой области. Существуют различные методы оптимизации длины шага (α_к) и проверки принадлежности очередной точки Х_к допустимой области. Задачи с нелинейными ограничениями. Если в задачах с линейными ограничениями движение по граничным прямым оказываетя возможным и даже целесообразным, то при нелинейных ограничениях, определяющих выпуклую область, любое сколь угодно малое перемещение из граничной точки может сразу вывести за пределы области допустимых решений, и возникает необходимость в возвращении в допустимую область (рис. 6.4). Подобная ситуация характерна для задач, в которых экстремум функции ƒ(Х) достигает на границе области. В связи с этим

Рис 6.4

применяются различные способы перемещения, обеспечивающие построение последовательности точек, расположенных вблизи границы и внутри допустимой области, или зигзагообразное движение вдоль границы с пересечением последней. Как видно из рисунка, возврат из точки Х₁ в допустимую область следует осуществлять вдоль градиента той граничной функции φ_к(Х), которая оказалась нарушенной. Это обеспечит отклонение очередной точки Х₂ в сторону тоски экстремума Х^*. Признаком экстремума в подобном случае будет коллинеарность векторов   ƒ и   φ_к.