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

Графический метод решения задачи нелинейного программирования принимается в случае двух переменных.

Напомним, (см. раздел 3, подраздел 3.2), что множество точек называется выпуклым, если оно вместе с любыми своими двумя точками содержит и весь отрезок, соединяющий эти точки. Если [a;b]- отрезок на числовой прямой и x [a;b], то при 0 1, x= а + (1- )b, или x= a + b при + =1 и 0 и 0. По определению функция F(X)=F(x₁,x₂,…,x_n) определенная на выпуклом множестве М n –го пространства называется выпуклой на этом множестве, если F( x₁+(1- ) x₂) F(x₁₎+(1- )F(x) (13)

Для любых точек х₁, х₂, М и любого числа (-[0:1]).Сказанное из рассмотрения графика выпуклой функции. То есть значение выпуклой функции в промежуточной точке х всегда не меньше ее значений на границе рассматриваемого интеграла. Для вогнутой функции знак неравенства не меняется на противоположный.

F(x) Примечание. Множество всех точек

X=(x₁, x₂, …,x_n) образует n- мерное точеч

ное пространство. При n>3 точки и фигу-

F(x₂) ры n-мерного пространства не имеют реа-

льного геометрического смысла.

F(x₁) F(x)

x₁ x₂

x= + (1 - )x₂

Рис. 17. Выпуклая функция

Использование графического метода предопределяет вычисление и построение линий уровня, которыми называется множество всех точек (x;y), в которых функция принимает постоянное значение. В случае линейной функции все линии уровня представляют собой прямые , перпендикулярные общему вектору нормали.

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

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

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

1.Рассматривается множество всех допустимых решений на основе системы ограничений вида

(x₁,x₂,..x_n) b_i, i= . ( (x₁,x₂,) b_i, I= ) и в системе координат OX, х₂ строится это множество.

2.Проверка множества на предмет пустого x= ,если оно пусто , то задача неразрешима. M= , что множество М не имеет ни одного элемента (такие множества называются пустыми).

3.Если М , то необходимо рассчитать, вычислить и построить линии уровня f=a при монотонном изменении u от - до + .Напомним, что линией уровня целевой функции Z= f(x;y) называется линия на плоскости OXY в которой функция сохраняет постоянное значение. Совокупность линий уровня, соответствующих различным сечениям – называется сетью, которая наглядно графически характеризует поведение целевой функции .( Примеры: изобары и изотермы – метеорология , горизонтали, топография(рельеф) , изокванты – экономика и др. ) При увеличении u линия Z=(x;y)=a смещается эквидистантно в направлении вектора q , нормального в данной точке к линии уровня. При этом , если А - первая точка встречи линии уровня с областью X, Y, f(x;y)=a₀ то линия уровня f(x;y)=a при а<a₀ не имеет общих точек с областьюXY.Отсюда следует, что а₀=min f наX,Y. Аналогично, если А- последняя точка пересечения линии уровня с областью X,Yто f(A)=max fна X,Y. Таким образом из графического представления видно, имеются ли у допустимого множества вершины, имеет она решение или нет. Если у области f (x;y) есть хотя бы одна вершина, то (при ограниченной целевой функции) оптимальное значение может быть найдено методом перебора вершин. Для вычисления целевой функции в некоторой вершине допустимого множества необходимо знать точное значение ее координат, определение которых осуществляется решением ограничений (11)

где I и j – номера линий ограничивающих область D(x;y), на пересечении которых находится искомая вершина. Основным преимуществом графического метода является ,то что он позволяет избежать полного перебора вершин, т.е. нет необходимости вычислять координаты других вершин при обнаружении оптимального решения. Необходимо решить следующую задачу выпуклого программирования: найти минимум функции Z=2+(x₁-1)²+(x₂-1)²:

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

x₁²+x₂² 4

x₁ 2x₂

x₂ 2x₁

x₁ 0, x₂ 0

Решение. Строим область допустимых решений:

а) x₁²+x₂²=4- окружность с центром в начале координат и радиусом R=2.

Область решений неравенства x₁²+x₂² 4 состоит из точек, лежащих

внутри этой области окружности и на ее границе;

x₂ A

В

B x₁

X₁=2x₂

X₂=2x₁

Рис. 18. График целевой функции

б) x₁=2x₂-прямая, которую можно построить, например , по точкам (0;0) и (2;1) область решений неравенства x₁ 2x₂ – полуплоскость лежащая на этой прямой , включая и саму прямую;

в) x₂=2x₁- прямая , которая строится аналогично прямой x₁=2x₂ , только по точкам (0;0) и (1;2) .Область решений неравенства x₂ 2x₁ - полуплоскость , лежащая под этой прямой , включая и саму прямую.

Таким образом , с учетом условий не отрицательности переменных областью допустимых решений данной задачи является замкнутый сектор ОАВ.

Теперь построим линию уровня Z и определим направление ее убывания . По определению все линии уровня имеют уравнение Z=c т.е. (x₁-1)²+(x₂-1)²=C-2. Пусть const C=3. Тогда линия уровня (x₁-1)²+(x₂-1)²=1 –это окружность с центром в точке О₁ (1;1) и радиусом r=1. Из рассмотрения представленных на рисунке графиков очевидно, что при перемещении от центра О₁ к границе окружности функция возрастает и наоборот убывает (стрелками указано направление убывания функции Z). Таким образом минимум Z достигается в точке (1;1), а Z_min=2. Нетрудно убедиться, что точка(1;1) является стационарной точкой функции Z. Решение этой задачи предлагается студентам осуществить самостоятельно.

Дата добавления: 2015-07-26; просмотров: 276; Нарушение авторских прав

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