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

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

4.5.3. Методы безусловной оптимизации

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

В настоящее время разработано множество численных методов для задач как безусловной, так и условной оптимизации. Качество численного метода характеризуется многими факторами: скоростью сходимости, временем выполнения одной итерации, объемом памяти ЭВМ, необходимым для реализации метода, классом решаемых задач и т. д. Решаемые задачи также весьма разнообразны: они могут иметь высокую и малую размерность, быть унимодальными и многоэкстремальными и т. д. Один и тот же метод, эффективный для решения задач одного типа, может оказаться совершенно неприемлемым для задач другого типа.

Ниже приводится обзор основных методов решения задач нелинейного программирования. Следует иметь в виду, что весь перечень таких методов весьма широк и остается открытым. Кроме того, для ряда рассматриваемых методов известны различные модификации. Более подробную информацию можно получить, на-

пример, в .

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

Смысл прямых методов безусловной оптимизации состоит в построении последовательности точек X , X , …, X , таких,

что f (X )>f (X )>… …>f (X ). В качестве начальной точки X может быть выбрана произвольная точка, однако стремятся ее выбрать как можно ближе к точке минимума. Переход (итерация) от точки Х к точке Х , k =0,1,2,... состоит из двух этапов:

– выбор направления движения из точки Х ;

– определение шага вдоль этого направления.

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

Математически методы спуска описываются соотношением

X =X +a k p , k =0,1,2,...,

где p – единичный вектор, определяющий направление спуска;

a k – длина шага.

Различные методы спуска отличаются друг от друга способами выбора p и a k . На практике применяются только методы, обладающие сходимостью. Они позволяют за конечное число шагов получить точку минимума или подойти к ней достаточно близко. Качество сходящихся итерационных методов оценивают по скорости сходимости.

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

	аргумента		X[ k] − X[ k − 1 ]

f (X [ k ]) − f (X [ k − 1]) < γ . Здесь k – номер итерации; ε , γ – задан-

ные величины точности решения задачи.

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

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

при необходимости дополнительного вычисления вторых производных – методы второго порядка.

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

Методы одномерного поиска. Перечень методов одномерного поиска – численного поиска экстремума функции одного аргумента f(x) – достаточно широк и хорошо освещен в литературе . Поэтому здесь ограничимся рассмотрением только одного метода, который, по опыту авторов, является одним из наиболее эффективных, – метода «золотого сечения».

Идея метода состоит в последовательном сокращении интервала неопределенности – интервала значений аргумента x , содержащего искомую точку минимума, – до длины, не превышающей

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

Внутри любого интервала содержатся две точки x =y 0 и x =z 0 , выполняющие его «золотое сечение» – разбиение на две неравные части такие, что отношение большей части к длине всего интервала совпадает с отношением меньшей части к большей. Очевидно, эти точки расположены симметрично относительно центра интервала (рис. 26). Координаты точек «золотого сечения» могут быть найдены из соответствующих пропорций:

b − y0		y0 − a	= δ ,	z0 − a		b − z0			= δ,
b − a		b − y		b − a				− a

откуда нетрудно получить δ =(1–δ )/δ и прийти к уравнению: δ 2 +δ –1=0. В результате получим относительные доли, определяющие «золотое сечение» интервала: δ =0,618, 1–δ =0,382. «Золотое сечение» обладает важным свойством: точка y 0 является одной из точек «золотого сечения» интервала , точка z 0 – одной из точек «золотого сечения» интервала . В этом убе-

ждает простой расчет: 0,382/0,618 = 0,618 и (0,618–0,382)/0,618 = = 0,382.

Алгоритм поиска минимума, построенный на основе метода «золотого сечения», предусматривает на каждой итерации выбор в качестве одной из границ сокращенного интервала левой или правой точки «золотого сечения» таким образом, чтобы искомый минимум сохранялся внутри него:

1. Задают k =0, исходный интервал неопределенности , допустимую погрешность результата ε .

2. Вычисляют координаты точек «золотого сечения»:

y k =a k +0,382(b k –a k ), z k =a k +0,618(b k –a k ).

3. Вычисляют значения целевой функции в найденных точках

f (y k ) и f (z k ).

4. Если f (y k )≤f (z k ) (рис. 26, а ), присваивают a k + 1 =a k , b k + 1 =z k , z k + 1 =y k , y k + 1 =a k +z k –y k , k =k +1. В противном случае (рис. 26, б ) a k + 1 =y k , b k + 1 =b k , y k + 1 =z k , z k + 1 =y k +b k –z k , k =k +1.

5. Проверяют выполнение условия завершения поиска

b k + 1 − a k + 1 ≤ ε . В случае его выполнения в качестве решения выбирают точку x = (y k + 1 + z k + 1 ) 2 . В противном случае переходят к шагу 2.

Вычислительная эффективность метода «золотого сечения» обусловлена тем, что здесь на каждой итерации требуется только однократное вычисление значения целевой функции.

Метод прямого поиска (метод Хука-Дживса). Задаются неко-

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

Алгоритм метода прямого поиска в самом общем виде можно сформулировать следующим образом:

1. Задаются значениями координат х i , i= 1,2,…n , начальной точки (k =0), вектором начальных приращений координат

∆ X = (∆ х 1 , ∆ х 2 ,…, ∆ х n ) в процессе обследования окрестности, наименьшим допустимым значением ε компонент ∆ X , ускоряющим множителем λ ≥ 1, определяющим скорость спуска, масштабным коэффициентом d >1.

2. Принимают Х за «старый базис» : X б =Х . Вычисляют

значение f (X б ).

3. Поочередно изменяют каждую координату х б i , i= 1,2,…n ,

точки X б на величину ∆ х i , то есть принимают х i =х б i + ∆ х i , затем

х i =х б i –∆ х i . Вычисляют значения f (X ) в получаемых пробных точках и сравнивают их со значением f (X б ). Если f (X )< < f (X б ), то соответствующая координата х i приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n -й координаты f (X )

4. Осуществляют спуск в направлении от «старого» к «новому» базису через последний, т. е. вычисляют координаты новой точки

X : х i =х i +λ (х i –х бi ), i= 1,2,…n . Вычисляют значение f (X ). Если выполняется условие f (X )

«новый» базис принимают «старым» (X б =Х , f (X б )=f (X )) и переходят к п. 5. В противном случае принимают х i =х i , i= 1,2,…n .

5. Как и в п. 3, поочередно изменяют каждую координату точки X , сравнивая соответствующие значения функции f (Х ) со значением f (X ), полученным в п. 4. После изменения последней координаты сравнивают соответствующее значение

функции f (X ) со значением f (X б ), полученным в п. 4. Если f (X )

6. Если для всех i ∆ х i <ε , вычисления прекращаются. В противном случае уменьшают значения ∆ х i в d раз и переходят к п. 3.

Работа алгоритма проиллюстрирована рис. 27. Показаны линии

уровня минимизируемой функции f (x 1 ,x 2 ), т. е. линии, получаемые из условий f (x 1 ,x 2 )=f 1 =const, f (x 1 ,x 2 )=f 2 =const и так далее. Здесь f 1 >f 2 >f 3 . Сплошные линии – результаты однократного выполнения пп. 3...5 (поиск направления уменьшения функции и спуск), пунктирная линия – следующий спуск.

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

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

Метод деформируемого многогранника (метод Нелдера- Мида) состоит в том, что для минимизации функции n переменных f(X) в n-мерном пространстве строится многогранник, содержащий n+1 вершину. Очевидно, что каждая вершина соответствует некоторому вектору Xi . Вычисляют значения целевой функции f(Xi ), i=1,2,…, n+1, в каждой из вершин многогранника, определяют максимальное из этих значений и соответствующую ему вершину Xh . Через эту вершину и центр тяжести остальных вершин проводят проецирующую прямую, на которой находится точка Xq с меньшим значением целевой функции, чем в вершине Xh (рис. 28, а). Затем исключают вершину Xh . Из оставшихся вершин и точки Xq строят новый многогранник, с которым повторяют описанную процедуру. В процессе выполнения таких операций многогранник изменяет свои размеры, что и обусловило название метода.

Введем следующие обозначения: X – вектор координат i -й вершины многогранника на k -м шаге поиска, i= 1,2,…n +1, k= 1,2,…; h – номер вершины, в которой значение целевой

шин, за исключением X . Координаты центра тяжести вычис-

	xj [ n + 2, k] =		n+ 1
ляют по формуле			∑ xj [ i, k] − xj [ h, k]		J= 1,2,…n .
			j= 1

Примерный алгоритм метода деформируемого многогранника состоит в следующем:

1. Задаются коэффициентами отражения α , растяжения γ >1, сжатия β<1 , допустимой погрешностью определения координат

точки минимума ε . Выбирают координаты вершин исходного многогранника X , i= 1,2,…n +1, k= 1.

2. Вычисляют значения целевой функции во всех вершинах f (X ), i= 1,2,…n +1, и находят точки X , X (на рис. 28, б точки соответственно X 2 и X 1 ), а также X .

3. Осуществляют проецирование точки X через центр тя-

жести: X =X +α (X –X ).

4. Если f (X )≤ X , выполняют операцию растяже-

ния: X =X +γ (X –X ). В противном случае переходят к п. 6.

5. Строят новый многогранник: если f (X )

заменой X на X , в противном случае – заменой X на X . Продолжают вычисления с п. 2 при k =k +1.

6. Если X >f (X )>X для всех i , не равных h ,

выполняют операцию сжатия: X =X +β (X – X ). Строят новый многогранник заменой X на X и продолжают вычисления с п. 2 при k =k +1.

7. Если f (X )>X , то, сохраняя вершину X , строят новый многогранник, подобный текущему, уменьшением длин всех ребер в два раза: X =X +0,5(X –X ) и продолжают вычисления с п. 2 при k =k +1.

В пп. 6, 7 перед переходом к п. 2 необходима проверка выполнения условия завершения поиска минимума, например, по усло-

вию max n ∑ + 1 (x j [ i ,k ] − x j [ n + 2,k ] ) 2 < ε 2 .

i j = 1

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

α =1, 2≤ γ ≤3, 0,4≤β ≤0,6.

Метод вращающихся координат (метод Розенброка). Его суть состоит в последовательных поворотах системы координат в соответствии с изменением направления наиболее быстрого убывания целевой функции (рис. 29). Из начальной точки X осуществляют спуск в точку X по направлениям, параллельным координатным осям. На следующей итерации одна из осей должна проходить в направлении x’1 = X– X, остальные – в направлениях, перпендикулярных к x’1 . Спуск вдоль этих осей пр и- водит в точку X, что дает возможность построить новый вектор x’’1 = X– X и на его базе новую систему направлений поиска

точки минимума X .

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

В частности, данный метод в отличие от многих других эффективен при минимизации так называемых "овражных" функций (с сильно вытянутыми поверхностями уровня), так как результирующее направление поиска стремится расположиться вдоль оси «оврага».

Метод параллельных касательных (метод Пауэлла). Его суть состоит в последовательном проведении одномерного поиска минимума целевой функции по n+1 направлению каким-либо из известных одномерных методов. На первой итерации в качестве первых n направлений выбираются координатные, в качестве (n+1)-го направления используется первое из них (рис. 30). На каждой последующей итерации поиск начинается со второго направления предшествующей итерации, соответственно номера направлений уменьшаются на единицу; (n+1)-е направление последующей итерации задается вектором X– X[ n+1] – из точки минимума, найденной на первом шаге предшествующей итерации, через точку минимума, найденную на последнем ее шаге.

Задача 1 . Найти

где х = (х 1 ..х п) е Е п

Эта задача сводится к решению системы уравнений

и исследованию значения второго дифференциала

в точках (а-|, (*2, а п) решения уравнений (7.3).

Если квадратичная форма (7.4) отрицательно определена в точке, то она достигает в ней максимального значения, а если положительно определена, то минимального значения.

Пример:

Система уравнений имеет решения:

Точка (-1; 3,0) является точкой максимума, а точка (1; 3,2) - точкой минимума.

Задача 2. Найти

при условиях:

Эта задача 2 решается методом множителей Лагранжа, для чего находят решение системы (т + п) уравнений:

Пример 2. Найти стороны прямоугольника максимальной площади, вписанного в круг Площадь Л прямоугольника

можно записать в виде: А = 4ху, тогда

откуда

Задача 3. Найти при условиях:

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

Задача За.

при условиях

Она решается симплекс-методом , который с помощью аппарата линейной алгебры осуществляет целенаправленный перебор вершин многогранника, определяемого (7.13).

Симплекс-метод состоит из двух этапов.

Этап 1. Нахождение опорного решения х^ 0). Опорное решение - одна из точек многогранника (7.13).

Этап 2. Нахождение оптимального решения. Его находят последовательным перебором вершин многогранника (7.13), при котором значение целевой функции z на каждом шаге не уменьшается, то есть:

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

Транспортная задача. Пусть в пунктах а-1, а 2 , .... а л находятся склады, в которых хранятся товары в количестве х 1 , х 2 , ..., х л соответственно. В пунктах Ь-|, Ь 2 ,..., Ь т находятся потребители, которым необходимо поставить эти товары в количествах у-у 2 , у т соответственно. Обозначим Cjj стоимость перевозки единицы груза между пунктами а-| и by.

Исследуем операцию перевозки потребителями товаров в количествах, достаточных для того, чтобы удовлетворить потребности клиентуры. Обозначим через Ху количество товара, перевозимого из пункта а,- в пункт by.

Для того, чтобы удовлетворять запросы потребителя, необходимо, чтобы величины х,у удовлетворяли условиям:

В то же время со склада а нельзя вывезти продуктов в большем количестве, чем там имеется. Это означает, что искомые величины должны удовлетворять системе неравенств:

Удовлетворять условиям (7.14), (7.15), т.е. составить план перевозок, обеспечивающий запросы потребителей, можно бесчисленным числом способов. Для того чтобы исследователь операций мог выбрать определенное оптимальное решение, т.е. назначить определенные Xjj, должно быть сформулировано некоторое правило отбора, определяемое с помощью критерия, который отражает наше субъективное представление о цели.

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

Тогда задача о перевозках формулируется как задача линейного программирования: определить величины х,у > О, удовлетворяющие ограничениям (7.14), (7.15) и доставляющие функции (7.16) минимальное значение. Ограничение (7.15) - это условие баланса; условие (7.14) можно назвать целью операции, ибо смысл операции в том и состоит, чтобы обеспечить запросы потребителей.

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

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

На первом этапе решения задачи составляют первоначальный план перевозок, удовлетворяющий ограничениям (7.14), (7.15). Если

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

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

Задача 36. В общем случае задача (7.10-7.11) называется задачей нелинейного программирования. Рассмотрим ее в виде

при условиях

Для решения этой задачи используют так называемые релаксационные методы. Процесс построения последовательности точек называется релаксационным, если:

Методы спуска (общая схема) . Все методы спуска в решении задачи безусловной оптимизации (7.17) различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Методы спуска состоят в следующей процедуре построения последовательности {х к }.

В качестве начального приближения выбирается произвольная точка Xq. Последовательные приближения строятся по следующей схеме:

• точке х к выбирается направление спуска - S k ;
• находят (к + 1)-е приближение по формуле

где в качестве величины $ к выбирают любое число, удовлетворяющее неравенству

где число Х к - любое такое число, когда 0 Х к min f(x k - $ Sk).

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

Метод градиентного спуска. Поскольку антиградиент - Г(х к) указывает направление наискорейшего убывания функции f(x), то естественным является перемещение из точки х к по этому направлению. Метод спуска, в котором S k = f"{x k) называется методом градиентного спуска. Если Х к = 1, то релаксационный процесс называется методом скорейшего спуска.

Метод сопряженных направлений. В линейной алгебре этот метод известен как метод сопряженных градиентов решения систем линейных алгебраических уравнений АХ = Ь, а следовательно, как метод минимизации квадратичной функции f(x) = ((Дх - Ь)) 2 .

Схема метода:

Если f k = 0, то эта схема превращается в схему метода скорейшего спуска. Соответствующий выбор величины t k гарантирует сходимость метода сопряженных направлений со скоростью того же порядка, что и в методах градиентного спуска, и обеспечивает конечность числа итераций в квадратичном спуске (например,

Покоординатный спуск. На каждой итерации в качестве направления спуска S k выбирается направление вдоль одной из координатных осей. Метод имеет скорость сходимости процесса минимизации порядка 0 (1 //77), причем она существенно зависит от размерности пространства.

Схема метода:

где координатный вектор,

Если в точке х к имеется информация о поведении градиента функции f(x), например,

то в качестве направления спуска S k можно принять координатный вектор еу. В этом случае скорость сходимости метода в п раз меньше, чем при градиентном спуске.

На начальном этапе процесса минимизации можно использовать метод циклического покоординатного спуска, когда сначала спуск осуществляется по направлению е-|, затем - по в2 и т.д. вплоть до е п, после чего весь цикл повторяется. Более перспективным по сравнению с описанным является покоординатный спуск, в котором направления спуска выбираются случайным образом. При таком подходе к выбору направления существуют априорные оценки, гарантирующие для функции f(x) с вероятностью, стремящейся к единице при сходимость процесса со скоростью порядка 0(11т).

Схема метода:

На каждом шаге процесса из п чисел {1, 2, ..., п } случайным образом выбирается номер j(k) и в качестве s k выбирается единичный координатный вектор вщ, после чего осуществляется спуск:

Метод случайного спуска. На п-мерной единичной сфере с центром в начале координат выбирается случайная точка S k , подчиняющаяся на этой сфере равномерному распределению, и затем по вычисленному на /с-м шаге процесса элементу х к определяется х к+] :

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

Релаксационные методы математического программирования. Вернемся к задаче 36 ((7.17) - (7.18)):

при условиях

В оптимизационных задачах с ограничениями выбор направления спуска сопряжен с необходимостью постоянной проверки того, что новое значение х к +" должно так же, как и предыдущее х к, удовлетворять системе ограничений X.

Метод условного градиента. В этом методе идея выбора направления спуска состоит в следующем: в точке х к линеаризуют функцию

f(x), строя линейную функцию f(x) = f(x k) + {у"(х к), х-х к), и затем, минимизируя f(x) на множестве х, находят точку у к. После этого полагают S k = у к - х к и далее вдоль этого направления осуществляют спуск х к+ 1 = х к - $ к (х к -у к), так, чтобы g X.

Таким образом, для отыскания направления S k следует решить задачу минимизации линейной функции на множестве X. Если X, в свою очередь, задается линейными ограничениями, то она становится задачей линейного программирования.

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

Направление s в точке х е X называется возможным,_если существует такое число (3 > О, что х - (3s е х для всех (3 g . Для нахождения возможного направления необходимо решить задачу линейного программирования либо простейшую задачу квадратичного программирования: а?=> min при условиях

Пусть д к и s k - решение этой задачи. Условие (7.25) гарантирует, что направление s k возможное. Условие (7.26) обеспечивает максимальность величины (/"(х k),s), т.е. среди всех возможных направлений s, направление s k обеспечивает самое быстрое убывание функции f{x). Условие (7.27) избавляет от неограниченности решения задачи. Метод возможных направлений устойчив к возможным вычислительным ошибкам. Однако скорость его сходимости оценить в общем случае сложно, и эта задача пока остается нерешенной.

Метод случайного поиска. Реализация изложенных ранее методов минимизации в общем случае очень трудоемка, кроме простейших случаев, когда множество ограничений обладает простой геометрической структурой (например, является многомерным параллелепипедом). В общем случае весьма перспективным может быть метод случайного поиска, когда направление спуска выбирается случайным образом. При этом будет существенный проигрыш в скорости сходимости, однако простота выбора направления может компенсировать эти потери по величине общих затрат труда на решение задачи минимизации.

Схема метода:

на и-мерной единичной сфере с центром в начале координат выбирается случайная точка гу подчиняющаяся на этой сфере равномерному распределению, и затем направление спуска - s^ из условий

В качестве начального приближения выбирается хц е X. По вычисленной на каждой итерации точке х ? строится (k + 1)-я точка х^+ у:

В качестве выбирается любое число из удовлетворяющее неравенству

Доказана сходимость этого метода при весьма нежестких ограничениях на функцию / (выпуклость) и множество ограничений X (выпуклость и замкнутость).

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

Метод Розенброка является улучшенным вариантом покоординатного спуска.

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

Рис. 1. Траектория покоординатного спуска

При использовании метода покоординатного спуска велика вероятность "застревания" поиска на дне оврага вдали от точки экстремума. На рис. 2 видно, что после попадания в точку , расположенную на дне оврага, дальнейшие шаги возможны лишь в направлениях или , но они приводят к ухудшению целевой функции. Следовательно, поиск прекращается в точке .

Примечание 1

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

Рис. 3. Траектория покоординатного спуска при благоприятной ориентации координатных осей

Метод Розенброка заключается в таком повороте координатных осей, чтобы одна из них оказалась квазипараллельной дну оврага. Такой поворот осуществляют на основе данных, полученных после серии из шагов покоординатного спуска. Положение новых осей может быть получено линейным преобразованием прежних осей : ось совпадает по направлению с вектором ; остальные оси выбирают из условия ортогональности к и друг к другу.

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

Рис. 4. Иллюстрация метода конфигураций

Поиск экстремума методом деформируемого многогранника (Нелдера-Мида) основан на построении многогранника с вершинами на каждом шаге поиска, где — размерность пространства управляемых параметров. В начале поиска эти вершины выбирают произвольно, на последующих шагах выбор подчинен правилам метода.

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

шаг выбирается оптимальным с помощью одномерной оптимизации.

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

Один из приемов, использованный в методе сопряженных градиентов (называемом также методом Флетчера-Ривса), основан на понятии сопряженности векторов. Векторы и называют -сопряженными, если , где — положительно определенная квадратная матрица того же порядка, что и размер векторов и (частный случай сопряженности — ортогональность векторов, когда является единичной матрицей порядка ), — вектор-строка, — вектор-столбец.

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

Примечание 2

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

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

Поиск экстремума выполняют в соответствии с формулой

где — коэффициент. Кроме того, учитывают условие сопряженности

Поскольку шаг рассчитывается исходя из условия одномерной оптимизации, то, во-первых, справедливо соотношение

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

Чтобы определить коэффициент , решают систему уравнений (2)-(7) путем подстановки в (4) величин из (3) и из (2):

или

откуда

и с учетом (6) и (7)

Выражение (10) — это система линейных алгебраических уравнений. Ее корень есть очередное приближение к решению

Если процесс сходится, то решение достигается за малое число итераций, окончанием которых служит выполнение условия
где

Поэтому

Можно показать, что стремится к , — к при , где — размерность пространства управляемых параметров. Спустя шагов, нужно снова начинать с .

Задача 1. Найти

Задача 1 сводится к решению системы уравнений:

и исследованию значения второго дифференциала:

в точках решения уравнений (8.3).

Если квадратичная форма (8.4) отрицательно определена в точке, то она достигает в ней максимальное значение, а если положительно определена, то минимальное значение.

Пример:

Система уравнений имеет решения:

Точка (– 1/3,0) является точкой максимума, а точка (1/3,2) –точкой минимума.

Задача 2. Найти

при условиях:

Задача 2 решается методом множителей Лагранжа. Для этого находится решение системы (т + п) уравнений:

Пример. Найти стороны прямоугольника максимальной площади, вписанного в круг: . Площадь А прямоугольника можно записать в виде: А =4ху, тогда

Задача 3. Найти:

при условиях:

Эта задача охватывает широкий круг задач, определяемых функциями f и  .

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

Задача 3 а.

при условиях

Она решается симплекс-методом , который с помощью аппарата линейной алгебры производит целенаправленный перебор вершин многогранника, определяемого (8.13).

Симплекс-метод (состоит из двух этапов):

Этап 1. Нахождение опорного решения х (0) .

Опорное решение – одна из точек многогранника (8.13).

Этап 2. Нахождение оптимального решения.

Оптимальное решение находится последовательным перебором вершин многогранника (8.13), при котором значение целевой функции z на каждом шаге не уменьшается, то есть:

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

Транспортная задача. Пусть в пунктах находятся склады, в которых хранятся товары в количествесоответственно. В пунктахнаходятся потребители, которым необходимо поставить эти товары в количествахсоответственно. Обозначимc ij стоимость перевозки единицы груза между пунктами

Исследуем операцию перевозки потребителями товаров в количествах, достаточных, чтобы удовлетворить потребности потребителей. Обозначим через количество товара, перевозимого из пунктаа i в пункт b j .

Для того, чтобы удовлетворять запросы потребителя, необходимо, чтобы величины х ij удовлетворяли условиям:

В то же время со склада а; нельзя вывезти продуктов в большем количестве, чем там имеется. Это означает, что искомые величины должны удовлетворять системе неравенств:

Удовлетворять условиям (8.14), (8.15), то есть составить план перевозок, обеспечивающий запросы потребителей, можно бесчисленным числом способов. Для того, чтобы исследователь операций мог выбрать определенное решение, то есть назначить определенные х ij , должно быть сформулировано некоторое правило отбора, определяемое с помощью критерия, который отражает наше субъективное представление о цели.

Проблема критерия решается независимо от исследования операции – критерий должен быть задан оперирующей стороной. В данной задаче одним из возможных критериев будет стоимость перевозки. Она определяется следующим образом:

Тогда задача о перевозках формулируется как задача линейного программирования: определить величины , удовлетворяющие ограничениям (8.14), (8.15) и доставляющие функции (8.16) минимальное значение. Ограничение (8.15) – это условие баланса; условие (8.14) можно назвать целью операции, ибо смысл операции в том и состоит, чтобы обеспечить запросы потребителей.

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

Одним из известных методов решения транспортной задачи является метод потенциалов .

На первом этапе решения задачи составляется первоначальный план перевозок, удовлетворяющий

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

Задача 3б. В общем случае задача (8.10 – 8.11) называется задачей нелинейного программирования. Рассмотрим ее в более принятом виде:

при условиях

Для решения этой задачи используются так называемые релаксационные методы. Процесс построения последовательности точек называется релаксационным, если:

Методы спуска (общая схема) . Все методы спуска решения задачи безусловной оптимизации (8.17) различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Методы спуска состоят в следующей процедуре построения последовательности { x k }.

В качестве начального приближения выбирается произвольная точка x 0 . Последовательные приближения строятся по следующей схеме:

Точке x k выбирается направление спуска – s k ;

Находят (к + 1) – е приближение по формуле:

где в качестве величины выбирают любое число, удовлетворяющее неравенству

где число – любое такое число, когда

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

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

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

Схема метода:

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

Покоординатный спуск. На каждой итерации в качестве направления спуска – s k выбирается направление вдоль одной из координатных осей. Метод имеет скорость сходимости процесса минимизации порядка 0(1/m). Причем она существенно зависит от размерности пространства.

Схема метода:

где координатный вектор

Если в точке x k имеется информация о поведении градиента функции f (x ), например:

то в качестве направления спуска s k можно взять координатный вектор е j . В этом случае скорость сходимости метода в n раз меньше, чем при градиентном спуске.

На начальном этапе процесса минимизации можно использовать метод циклического покоординатного спуска, когда сначала спуск осуществляется по направлению е 1 , затем по е 2 и т. д. вплоть до е п , после чего весь цикл повторяется снова. Более перспективным по сравнению с предыдущим является покоординатный спуск, в котором направления спуска выбираются случайным образом. При таком подходе к выбору направления существуют априорные оценки, гарантирующие для функции f (x ) с вероятностью, стремящейся к единице при , сходимость процесса со скоростью порядка 0(1/m).

Схема метода:

На каждом шаге процесса из n чисел {1, 2, ..., n} случайным образом выбирается номер j (k ) и в качестве s k выбирается единичный координатный вектор е j ( k ) , после чего осуществляется спуск:

Метод случайного спуска. s k , подчиняющаяся на этой сфере равномерному распределению, и затем по вычисленному на k-м шаге процесса элементу х к определяется :

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

Релаксационные методы математического программирования. Вернемся к задаче 36 ((8.17) – (8.18)):

при условиях

В оптимизационных задачах с ограничениями выбор направления спуска сопряжен с необходимостью постоянной проверки того, что новое значение х k +1 должно также, как и предыдущее x k удовлетворять системе ограничений X .

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

Таким образом, для отыскания направления – s k следует решить задачу минимизации линейной функции на множестве X . Если X в свою очередь задается линейными ограничениями, то она становится задачей линейного программирования.

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

Направление – s в точке х  X называется возможным, если существует такое число , чтодля всех. Для нахождения возможного направления необходимо решить задачу линейного программирования, либо простейшую задачу квадратичного программирования:

При условиях:

Пусть – решение этой задачи. Условие (8.25) гарантирует, что направление –– возможное. Условие (8.26) обеспечивает максимальность величины (, то есть среди всех возможных направлений –s , направление –обеспечивает самое быстрое убывание функцииf (x ). Условие (8.27) избавляет от неограниченности решения задачи. Метод возможных направлений устойчив к возможным вычислительным ошибкам. Однако скорость его сходимости оценить в общем случае сложно и эта задача пока остается нерешенной.

Метод случайного поиска. Реализация изложенных выше методов минимизации в общем случае очень трудоемка, кроме простейших случаев, когда множество ограничений обладает простой геометрической структурой (например, является многомерным параллелепипедом). В общем случае весьма перспективным может быть метод случайного поиска, когда направление спуска выбирается случайным образом. При этом мы будем существенно проигрывать в скорости сходимости, однако простота выбора направления может компенсировать эти потери с точки зрения общих затрат труда на решение задачи минимизации.

Схема метода:

На n-мерной единичной сфере с центром в начале координат выбирается случайная точка r k , подчиняющаяся на этой сфере равномерному распределению, и затем направление спуска – s k из условий ,

В качестве начального приближения выбирается . По вычисленной на каждой итерации точкеx k строится (k + 1)-я точка x k +1 :

В качествевыбирается любое число из=, удовлетворяющее неравенству:

Доказана сходимость этого метода при весьма нежестких ограничениях на функцию f (выпуклость) и множество ограничений X (выпуклость и замкнутость).

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

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

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

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

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

Сущность методов исследования операций

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

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

• степень обоснованности выбранных вариантов решений;
• насколько они лучше альтернативных;
• степень учета определяющих факторов;
• каков критерий оптимальности выбранных решений.

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

Методы экспертных оценок

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

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

Рассматриваемые методы оптимизации ряда управленческих решений (экспертных оценок) эффективны в решении нижеперечисленных управленческих задач в сфере производства:

1. Изучение сложных процессов, явлений, ситуаций, систем, которые характеризуются неформализованными, качественными характеристиками.
2. Ранжирование и определение согласно заданному критерию существенных факторов, выступающих определяющими относительно функционирования и развития производственной системы.
3. Рассматриваемые методы оптимизации особо эффективны в области прогнозирования тенденций развития системы производства, а также ее взаимодействия с внешней средой.
4. Повышение надежности экспертной оценки преимущественно целевых функций, которые имеют количественный и качественный характер, посредством усреднения мнений квалифицированных специалистов.

И это лишь некоторые методы оптимизации ряда управленческих решений (экспертной оценки).

Классификация рассматриваемых методов

Методы решения задач оптимизации, исходя из числа параметров, можно подразделить на:

• Методы оптимизации одномерной.
• Методы оптимизации многомерной.

Их еще называют "численные методы оптимизации". Если быть точным, это алгоритмы ее поиска.

В рамках применения производных методы бывают:

• прямые методы оптимизации (нулевого порядка);
• градиентные методы (1-го порядка);
• методы 2-го порядка и др.

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

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

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

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

• метод Фибоначчи;
• дихотомии;
• золотого сечения;
• удвоения шага.

Метод Фибоначчи

Для начала необходимо установить координаты т. x на промежутке в качестве числа, равного отношению разницы (x - a) к разнице (b - a). Следовательно, a имеет относительно промежутка координату 0, а b - 1, средняя точка - ½.

Если допустить, что F0 и F1 между собой равны и принимают значение 1, F2 будет равно 2, F3 - 3, …, то Fn = Fn-1 + Fn-2. Итак, Fn - числа Фибоначчи, а поиск Фибоначчи - это оптимальная стратегия так называемого последовательного поиска максимума ввиду того, что она довольно тесно связана с ними.

В рамках оптимальной стратегии принято выбирать xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. При любом из двух интервалов ( либо ), каждый из которых может выступать в качестве суженного интервала неопределенности, точка (унаследованная) относительно нового интервала будет иметь либо координаты , либо . Далее, в качестве xn - 2 принимается точка, которая имеет относительно нового промежутка одну из представленных координат. Если использовать F(xn - 2), значение функции, которое унаследовано от прежнего промежутка, становится возможным сокращение интервала неопределенности и передача в наследство одного значения функции.

На финишном шаге получится прейти к такому интервалу неопределенности, как , при этом средняя точка унаследована от предыдущего шага. В качестве x1 устанавливается точка, которая имеет относительную координату ½+ε, а окончательный интервал неопределенности будет или [½, 1] по отношению к .

На 1-м шаге длина данного интервала сократилась до Fn-1: Fn (с единицы). На финишных шагах сокращение длин соответствующих интервалов представляется числами Fn-2: Fn-1, Fn-3: Fn-2, …, F2: F3, F1: F2 (1 + 2ε). Итак, длина такого интервала, как окончательный вариант примет значение (1 + 2ε) : Fn.

Если пренебречь ε, то асимптотически 1: Fn будет равно rn, при этом n→∞, а r = (√5 - 1) : 2, что приблизительно равно 0,6180.

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

Метод дихотомии

Если представить некую целевую функцию, то для начала потребуется найти ее экстремум на промежутке (a; b). Для этого ось абсцисс делится на четыре эквивалентные части, затем необходимо определить значение рассматриваемой функции в 5 точках. Далее выбирается минимум среди них. Экстремум функции должен лежать в пределах промежутка (a"; b"), который прилегает к точке минимума. Границы поиска сужаются в 2 раза. А если минимум расположен в т. a либо b, то он сужается во все четыре раза. Новый интервал также разделяется на четыре равных отрезка. В связи с тем, что значения данной функции в трех точках были определены на предыдущем этапе, далее требуется вычислить целевую функцию в двух точках.

Метод золотого сечения

Для существенных значений n координаты таких точек, как xn и xn-1 приближены к 1 - r, равное 0,3820, а r ≈ 0,6180. Толчок с данных значений весьма близок к искомой оптимальной стратегии.

Если предположить, что F(0,3820) > F(0,6180), то тогда очерчивается интервал . Однако ввиду того, что 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, то в данной точке F уже известна. Следовательно, на каждом этапе, начиная со 2-го, необходимо только одно вычисление целевой функции, при этом каждый шаг сокращает длину рассматриваемого интервала с коэффициентом 0,6180.

В отличие от поиска Фибоначчи, в данном методе не требуется фиксация числа n еще до начала поиска.

«Золотое сечение» участка (a; b) - сечение, при котором отношение его r длины к более крупной части (a; c) идентично отношению большей части r к меньшей, то есть (a; с) к (c; b). Нетрудно догадаться, что r определяется по вышерассмотренной формуле. Следовательно, при существенных n метод Фибоначчи переходит в данный.

Метод удвоения шага

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

Сначала определяем начальную координату M0 функции F(M), минимальное значение шага h0, направление поиска. Затем определяем функцию в т. M0. Далее совершаем шаг и находим значение данной функции в данной точке.

В случае если функция меньше значения, которое было на предыдущем шаге, следует произвести следующий шаг в том же направлении, предварительно увеличив его в 2 раза. При ее значении, которое больше предыдущего, потребуется поменять направление поиска, а затем начать двигаться в выбранном направлении с шагом h0. Представленный алгоритм можно модифицировать.

Методы многомерной оптимизации

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

Группу методов 1-го порядка еще называют градиентными, потому что для установления направления поиска применяют градиент данной функции - вектор, составляющими которого выступают частные производные минимизированной функции по соответствующим оптимизированным параметрам.

В группе методов 2-го порядка применяются 2 производные (их использование достаточно ограничено ввиду наличия трудностей в их вычислении).

Перечень методов безусловной оптимизации

При использовании многомерного поиска без применения производных методы безусловной оптимизации следующие:

• Хука и Дживса (осуществление 2 видов поиска - по образцу и исследующий);
• минимизации по правильному симплексу (поиск точки минимума соответствующей функции посредством сравнения на каждой отдельной итерации ее значений в вершинах симплекса);
• циклического координатного спуска (использование в качестве ориентиров поиска координатных векторов);
• Розенброка (основан на применении одномерной минимизации);
• минимизации по деформированному симплексу (модификация метода минимизации по правильному симплексу: добавление процедуры сжатия, растяжения).

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

Также выделяют еще такие методы, которые используют сопряженные направления (Метод Дэвидона-Флетчера-Пауэлла). Его суть - преставление направлений поиска как Dj*grad(f(y)).

Классификация математических методов оптимизации

Условно, исходя из размерности функций (целевых), они бывают:

• с 1 переменной;
• многомерные.

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

По критерию применения производных математические методы оптимизации подразделяются на:

• методы вычисления 1 производной целевой функции;
• многомерные (1-я производная-векторная величина-градиент).

Исходя из эффективности вычисления, существуют:

• методы быстрого вычисления экстремума;
• упрощенного вычисления.

Это условная классификация рассматриваемых методов.

Оптимизация бизнес-процессов

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

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

Налоговая оптимизация: методы

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

Общие методы налоговой оптимизации следующие:

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

Вторую группу методов также могут использовать все фирмы, однако они все же имеют достаточно узкую область применения. Специальные методы оптимизации налогов следующие:

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