46. Градиентные методы. Методы наиск-его подъёма.

Градиентные методы приводят лишь к локальному экстремуму и поэтому оказываются более эффективными при решении задач выпуклого программирования , в которых любой локальный экстремум является одновременно и глобальным. Суть градиентного поиска точки max х*: в дополнительной области необходимо взять производственную точку х₀ и с помощью градиента определить направление наискорейшего возрастания целевой функции. Сделав небольшой шаг в найденном направлении перейти в новую точку х₁, в которой снова определить наилучшее направление для перехода очередную точку х₂ и т.д. Таким образом, надо построить последовательность тех х₀,х₁,…х_n , так чтобы она сходилась в точке х*, т.е. для точек последовательности выполнились условия F_0<F_1<F_2<…

Градиентные методы отличаются способом выбора величины шага. Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъёма или спуска, при котором шаг перемещения выбирается таким образом, чтобы обеспечить наибольшее возрастание приращения функции ΔFk.

Градиентные методы, как правило, позволяют получать точное решение за бесконечное число шагов. И только в некоторых случаях за конечное. В связи с этим градиентные методы относят к приближенным методам решения. Очередная точка перехода определяется из уравнения Хк+1=Хк+λк*gradF(Хк) (4.4)

где λк – числовой параметр (шаг перехода, который определяется, в частности, в методе наискорейшего подъёма из условия. gradF(Хк+1)* gradF(Хк)=0 (4.5)

Геометрический смысл равенства (4.5): градиент в очередной точке Хк+1 ┴ grad предшествующеё точки Хк.

Признак оптимальности: Если целевая функция выпуклая, то необходимым и достаточным условием оптимальности точки х* является равенство 0 градиента функции в этой точке. Т.е gradF(х*)=0

33. Различные формы записи задач линейного программирования.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях

(1.4)???А 1 х 1 + А 2 x 2 + ... + А N x N = А о , X 0

где С = (с 1 , с 2 , ..., с N ); Х = (х 1 , х 2 , ..., х N ); СХ - скалярное произведение; векторы

A 1 , A 2 ,..., A N , A 0

состоят соответственно из коэффициентов при неизвестных и свободных членах. Матричная форма записи . Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А 0 , Х 0, где С = (с 1 , с 2 , ..., с N ) - матрица-cтрока; А = (а ij ) - матрица системы;

Х - матрица-столбец, А 0 - матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = С j х j при ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х 1 , х 2 , ..., х N ), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х 1 , х 2 , ..., х N ) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми. Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М. 0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным. 0пределение 4 . Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции. В дальнейшем рассмотрено решение задач линейного программирования, связанных с нахождением минимального значения линейной функции. Там, где необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального значения, определяем максимальное значение исходной линейной функции.