Метод ветвей и границ алгоритм. Пример решения задачи коммивояжера методом ветвей и границ. Решение задачи коммивояжера онлайн

В задаче безусловной оптимизации отсутствуют ограничения.

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

Градиент скалярной функции F (X ) в некоторой точке направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения F (X ), проходящей через точку X k ). Вектор, противоположный градиенту  антиградиент  направлен в сторону наискорейшего убывания функции F (X ). В точке экстремума grad F (X )= 0.

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

где  k  параметр шага на k -й итерации вдоль антиградиента. Для методов восхождения (поиска максимума) нужно двигаться по градиенту.

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

Метод с постоянным параметром шага. В этом методе параметр шага постоянен на каждой итерации. Возникает вопрос: как практически выбрать величину параметра шага? Достаточно малый параметр шага может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой параметр шага может привести к проскакиванию точки минимума и к колебательному вычислительному процессу около этой точки. Указанные обстоятельства являются недостатками метода. Поскольку невозможно заранее угадать приемлемое значение параметра шага  k , то возникает необходимость использования градиентного метода с переменным параметром шага.

По мере приближения к оптимуму вектор градиента уменьшается по величине, стремясь к нулю, поэтому при  k = const длина шага постепенно уменьшается. Вблизи оптимума длина вектора градиента стремится к нулю. Длина вектора или норма в n -мерном евклидовом пространстве определяется по формуле

, где n  число переменных.

Варианты остановки процесса поиска оптимума:

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

Рассмотрим пример. Найти минимум целевой функции F (X ) = (x 1  2) 2 + (x 2  4) 2 . Точное решение задачи X*= (2,0;4,0). Выражения для частных производных

,
.

Выбираем шаг  k = 0,1. Осуществим поиск из начальной точки X 1 = . Решение представим в виде таблицы.

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

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

F(X k+1 )=F(X k   k S k )=min F( k ), S k =  F(X);

 k >0

.

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

Пример. min F (x 1 , x 2 ) = 2x 1 2 + 4x 2 3 – 3. Тогда  F (X )= [ 4x 1 ; 12x 2 2 ]. Пусть точка X k = , следовательно  F (X )= [ 8; 12], F (X k   S k ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Необходимо найти , доставляющее минимум данной функции.

Алгоритм метода наискорейшего спуска (для поиска минимума)

Начальный шаг . Пусть   константа остановки. Выбрать начальную точку X 1 , положить k = 1 и перейти к основному шагу.

Основной шаг . Если || gradF (X )||< , то закончить поиск, в противном случае определить  F (X k ) и найти  k  оптимальное решение задачи минимизации F (X k   k S k ) при  k  0. Положить X k +1 = X k   k S k , присвоить k =

k + 1 и повторить основной шаг.

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

Метод дихотомии (бисекции) Начальный шаг. Выбирают константу различимости  и конечную длину интервала неопределенности l . Величина  должна быть по возможности меньшей, однако позволяющей различать значения функции F ( ) и F ( ) . Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить k =

Основной этап состоит из конечного числа однотипных итераций.

k-я итерация.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются. Решение x * = (a k + b k )/2. В противном случае

,
.

Шаг 2. Если F ( k ) < F ( k ), положить a k +1 = a k ; b k +1 =  k . В противном случае a k +1 =  k и b k +1 = b k . Присвоить k = k + 1 и перейти к шагу 1.

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

 = 0,618034 от конца интервала.

Алгоритм метода золотого сечения

Начальный шаг. Выбрать допустимую конечную длину интервала неопределенности l > 0. Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить  1 = a 1 +(1   )(b 1  a 1 ) и  1 = a 1 +  (b 1  a 1 ) , где  = 0,618 . Вычислить F ( 1 ) и F ( 1 ) , положить k = 1 и перейти к основному этапу.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются x * = (a k + b k )/ 2. В противном случае если F ( k ) > F ( k ) , то перейти к шагу 2; если F ( k )  F ( k ) , перейти к шагу 3.

Шаг 2. Положить a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Вычислить F ( k +1 ), перейти к шагу 4.

Шаг 3. Положить a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Вычислить F ( k +1 ).

Шаг 4. Присвоить k = k + 1, перейти к шагу 1.

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

Метод сопряженных градиентов (Флетчера-Ривса). В этом методе выбор направления движения на k + 1 шаге учитывает изменение направления на k шаге. Вектор направления спуска является линейной комбинацией направления антиградиента и предыдущего направления поиска. В этом случае при минимизации овражных функций (с узкими длинными впадинами) поиск идет не перпендикулярно оврагу, а вдоль него, что позволяет быстрее прийти к минимуму. Координаты точки при поиске экстремума методом сопряженных градиентов рассчитываются по выражению X k +1 = X k   V k +1 , где V k +1 – вектор, рассчитываемый по следующему выражению:

.

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

Алгоритм метода сопряженных градиентов

Шаг 1. Ввести начальную точку Х 0 , точность  , размерность n .

Шаг 2. Положить k = 1.

Шаг 3. Положить вектор V k = 0.

Шаг 4. Вычислить grad F (X k ).

Шаг 5. Вычислить вектор V k +1.

Шаг 6. Выполнить одномерный поиск по вектору V k +1.

Шаг 7. Если k < n , положить k = k + 1 и перейти к шагу 4, иначе к шагу 8.

Шаг 8. Если длина вектора V меньше , окончить поиск, иначе  перейти к шагу 2.

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

Недостатки градиентных методов

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

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

Метод релаксации

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

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

Пусть – осевое направление, т.е. .

Если знак производной отрицательный, функция убывает в направлении оси, если положительный – в обратном направлении:

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

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

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

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

(3.8)

где -значение варьируемой переменной на каждом шаге спуска;

Величина k+1 шага, которая может изменяться в зависимости от номера шага:

– функция знака z;

Вектор точки, в которой последний раз производилось вычисление производных ;

Знак “+” в алгоритме (3.8) принимается при поиске max I, а знак “-” – при поиске min I.Чем меньше шаг h., тем больше количество вычислений на пути движения к оптимуму. Но при слишком большой величине h вблизи оптимума может возникнуть зацикливание процесса поиска. Вблизи оптимума необходимо, чтобы выполнялось условие h

Простейший алгоритм изменения шага h состоит в следующем. В начале спуска задается шаг , равный например, 10% от диапазона d; изменения с этим шагом производится спуск по выбранному направлению до тез пор, пока выполняется условие для двух последующих вычислений

При нарушении условия на каком-либо шаге направление спуска на оси изменяется на обратное и спуск продолжается из последней точки с уменьшенной вдвое величиной шага.

Формальная запись этого алгоритма следующая:

(3.9)

В результате использования такой стратегии ша спуска будет уменьшатся в районе оптимума по данному направлению и поиск по направлению можно прекратить, когда станет меньше E.

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

Рисунок 3.5 – Траектория движения к оптимуму в методе релаксации

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

Шаг 1. – осевое направление,

; , если ;

Шаг 2. – новое осевое направление;

Метод градиента

В этом методе используется градиент функции . Градиентом функции в точке называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам (рис. 6.5)

Рисунок 3.6 – Градиент функции

.

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

Проекция градиента на плоскость переменных перпендикулярна касательной к линии уровня , т.е. градиент ортогонален к линиям постоянного уровня целевой функции (рис. 3.6).

Рисунок 3.7 – Траектория движения к оптимуму в методе

градиента

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

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

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

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

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

, (3.10)

или в векторной форме

, (3.11)

где – положительная константа;

“+” – при поиске max I;

“-” – при поиске min I.

Алгоритм градиентного поиска при нормировании градиента (деление на модуль) применяется в виде

; (3.12)

(3.13)

Определяет величину шага по направлению градиента.

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

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

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

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

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

Критерии окончания поиска оптимума:

; (3.16)

; (3.17)

где – норма вектора.

Поиск завершается при выполнении одного из условий (3.14) – (3.17).

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

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

Известны различные методы решения задачи оптимизации. Одним из наиболее широко применяемых является метод градиента, называемый также методом Бокса-Уилсона и методом крутого восхождения.

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

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

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

Согласно методу градиента в какой-то части факторного пространства выбирается исходная точка (исходные уровни) х 1 0 , х 2 0 . Относительно этих исходных уровней строится сим­метричный двухуровневый план эксперимента. Причем интер­вал варьирования выбирается настолько малым, чтобы ли­нейная модель оказалась адекватной. Известно, что любая кривая на достаточно малом участке может быть аппрокси­мирована линейной моделью.

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

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная мо­дель оказалась адекватной, то может быть определено на­правление градиента:

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

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осу­ществляем опыт в точке с координатами . Если значе­ние функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиен­та, т.е. осуществляем опыт в точке с координатами:

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, вы­ходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

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

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

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

3) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факто­ров в нормированном виде

.

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

Лекция № 8

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

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

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

а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x i . Потом снова определить наилучшее направление для перехода в очередную точку х 2 и т. д. На рис. 7.4 поисковая траектория представляет собой ломаную х 0 , x 1 , х 2 ... Таким образом, надо построить последовательность точек х 0 , x 1 , х 2 ,...,x k , ... так, чтобы она сходилась к точке максимума х *, т. е. для точек последовательности выполнялись условия

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

Движение из точки х k в новую точку x k+1 осуществляется по прямой, проходящей через точку х k и имеющей уравнение

(7.29)

где λ k - числовой параметр, от которого зависит величина шага. Как только значение параметра в уравнении (7.29) выбрано: λ k =λ k 0 , так становится определенной очередная точка на поисковой ломаной.

Градиентные методы отличаются друг от друга способом выбора величины шага - значения λ k 0 параметра λ k . Можно, например, двигаться из точки в точку с постоянным шагом λ k = λ, т. е. при любом k

Если при этом окажется, что , то следует возвратиться в точку и уменьшить значение параметра, например до λ /2.

Иногда величина шага берется пропорциональной модулю градиента.

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

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

Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъема. Суть его в следующем. После определения градиента в точке х к движение вдоль прямой производится до точки х к+ 1 , в которой достигается максимальное значение функции f (х ) в направлении градиента . Затем в этой точке вновь определяется градиент, и движение совершается по прямой в направлении нового градиента до точки х к+ 2 , в которой достигается максимальное в этом направлении значение f (x ). Движение продолжается до тех пор, пока не будет достигнута точка х *, соответствующая наибольшему значению целевой функции f (x ). На рис. 7.5 приведена схема движения к оптимальной точке х * методом наискорейшего подъема. В данном случае направление градиента в точке х k является касательным к линии уровня поверхности f (х ) в точке х к+ 1 , следовательно, градиент в точкех к+ 1 ортогонален градиенту (сравните с рис. 7.4).

Перемещение из точки х k в точку сопровождается возрастанием функции f (x ) на величину

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

(7.31)

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

Подставляя этот результат в равенство (7.31), получаем

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

построены линии уровня этой поверхности. С этой целью уравнение приведено к виду (x 1 -1) 2 +(x 2 -2) 2 =5-0,5f , из которого ясно, что линиями пересечения параболоида с плоскостями, параллельными плоскости x 1 Оx 2 (линиями уровня), являются окружности радиусом . При f =-150, -100, -50 их радиусы равны соответственно , а общий центр находится в точке (1; 2). Находим градиент данной функции:

I шаг . Вычисляем:

На рис. 7.6 с началом в точке х 0 =(5; 10) построен вектор 1/16, указывающий направление наискорейшего возрастания функции в точке х 0 . На этом направлении расположена следующая точка . В этой точке .

Используя условие (7.32), получаем

или 1-4=0, откуда =1/4. Так как , то найденное значение является точкой максимума . Находим x 1 =(5-16/4; 10-32/4)=(1; 2).

II шаг . Начальная точка для второго шага x 1 =(1; 2). Вычисляем =(-4∙1 +4; -4∙2+8)=(0; 0). Следовательно, х 1 =(1; 2) является стационарной точкой. Но поскольку данная функция вогнутая, то в найденной точке (1; 2) достигается глобальный максимум.

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

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

(7.34)

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

Начнем с геометрической иллюстрации процесса решения задачи (рис. 7.7). Пусть начальная точка х 0 расположена внутри допустимой области. Из точки х 0 можно двигаться в направлении градиента , пока f (x ) не достигнет максимума. В нашем случае f (x ) все время возрастает, поэтому остановиться надо в точке х , на граничной прямой. Как видно из рисунка, дальше двигаться в направлении градиента нельзя, так как выйдем из допустимой области. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выводит из допустимой области, а с другой - обеспечивает наибольшее возрастание f (x ). Такое направление определит вектор , составляющий с вектором наименьший острый угол по сравнению с любым другим вектором, выходящим из точки x i и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения . В данном случае вектор указывающий наивыгоднейшее направление, совпадает с граничной прямой.

Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает f (x ); в нашем случае - до точки х 2 . Из рисунка видно, что далее следует перемещаться в направлении вектора , который находится из условия максимизации скалярного произведения , т. е. по граничной прямой. Движение заканчивается в точке х 3 , поскольку в этой точке завершается оптимизационный поиск, ибо в ней функция f (х ) имеет локальный максимум. Ввиду вогнутости в этой точке f (х ) достигает также глобального максимума в допустимой области. Градиент в точке максимума х 3 =х * составляет тупой угол с любым вектором из допустимой области, проходящим через х 3 , поэтому скалярное произведение будет отрицательным для любого допустимого r k , кроме r 3 , направленного по граничной прямой. Для него скалярное произведение =0, так как и взаимно перпендикулярны (граничная прямая касается линии уровня поверхности f (х ), проходящей через точку максимума х *). Это равенство и служит аналитическим признаком того, что в точке х 3 функция f (x ) достигла максимума.

Рассмотрим теперь аналитическое решение задачи (7.33) - (7.35). Если оптимизационный поиск начинается с точки, лежащей в допустимой области (все ограничения задачи выполняются как строгие неравенства), то перемещаться следует по направлению градиента так, как установлено выше. Однако теперь выбор λ k в уравнении (7.29) усложняется требованием, чтобы очередная точка оставалась в допустимой области. Это означает, что ее координаты должны удовлетворять ограничениям (7.34), (7.35), т. е. должны выполняться неравенства:

(7.36)

Решая систему линейных неравенств (7.36), находим отрезок допустимых значений параметра λ k , при которых точка х k +1 будет принадлежать допустимой области.

Значение λ k * , определяемое в результате решения уравнения (7.32):

При котором f (x ) имеет локальный максимум по λ k в направлении, должно принадлежать отрезку . Если же найденное значение λ k выходит за пределы указанного отрезка, то в качестве λ k * принимается . В этом случае очередная точка поисковой траектории оказывается на граничной гиперплоскости, соответствующей тому неравенству системы (7.36), по которому при решении системы получена правая конечная точка . отрезка допустимых значений параметра λ k .

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

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

для тех t , при которых

где .

В результате решения задачи (7.37) - (7.40) будет найден вектор , составляющий с градиентом наименьший острый угол.

Условие (7.39) говорит о том, что точка принадлежит границе допустимой области, а условие (7.38) означает, что перемещение из по вектору будет направлено внутрь допустимой области или по ее границе. Условие нормализации (7.40) необходимо для ограничения величины , так как в противном случае значение целевой функции (7.37) можно сделать сколь угодно большим Известны различные формы условий нормализации, и в зависимости от этого задача (7.37) - (7.40) может быть линейной или нелинейной.

После определения направления находится значение λ k * для следующей точки поисковой траектории. При этом используется необходимое условие экстремума в форме, аналогичной уравнению (7.32), но с заменой на вектор , т. е.

(7.41)

Оптимизационный поиск прекращается, когда достигнута точка x k * , в которой .

Пример 7.5. Максимизировать функцию при ограничениях

Решение. Для наглядного представления процесса оптимизации будем сопровождать его графической иллюстрацией. На рис 7.8 изображено несколько линий уровня данной поверхности и допустимая область ОАВС, в которой следует найти точку х *, доставляющую максимум данной функции (см. пример 7 4).

Начнем оптимизационный поиск, например с точки х 0 =(4, 2,5), лежащей на граничной прямой АВ x 1 +4x 2 =14. При этом f (х 0)=4,55.

Найдем значение градиента

в точке x 0 . Кроме того, и по рисунку видно, что через допустимую область проходят линии уровня с пометками более высокими, чем f (x 0)=4,55. Словом, надо искать направление r 0 =(r 01 , r 02) перемещения в следующую точку x 1 более близкую к оптимальной. С этой целью решаем задачу (7.37) - (7.40) максимизации функции при ограничениях

Поскольку точка х 0 располагается только на одной (первой) граничной прямой (i =1) x 1 +4x 2 =14, то условие (7.38) записывается в форме равенства.

Система ограничительных уравнений этой задачи имеет только два решения (-0,9700; 0,2425) и (0,9700;-0,2425) Непосредственной подстановкой их в функцию T 0 устанавливаем, что максимум Т 0 отличен от нуля и достигается при решении (-0,9700; 0,2425) Таким образом, перемещаться из х 0 нужно по направлению вектора r 0 =(0,9700; 0,2425), т е по граничной прямой ВА.

Для определения координат следующей точки x 1 =(x 11 ; x 12)

(7.42)

необходимо найти значение параметра , при котором функция f (x ) в точке x

откуда =2,0618. При этом =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Если продолжить оптимизационный поиск, то при решении очередной вспомогательной задачи (7.37)- (7.40) будет установлено, что Т 1 =, а это говорит о том, что точка x 1 является точкой максимума х* целевой функции в допустимой области. Это же видно и из рисунка в точке x 1 одна из линий уровня касается границы допустимой области. Следовательно, точка x 1 является точкой максимума х*. При этом f max =f (x *)=5,4.

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

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