НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Унимодальной функцией на [a;b] называется функция, имеющая на этом отрезке единственную точку глобального минимума. При этом слева от этой точки функция является строго убывающей, с справа - строго возрастающей.

Унимодальная функция имеет важное свойство. Если , то < , если , то x

МЕТОД «ЗОЛОТОГО СЕЧЕНИЯ»

Рассмотрим задачу оптимизации для унимодальной функции на отрезке [a;b]. В принципе простейшим методом решения является методика перебора всех значений целевой функции на заданном интервале. В условиях применения средств вычислительной техники такая идея представляется не очень-то и абсурдной, но все-таки достаточно трудоемкой. Поэтому, несли идею перебора значений целевой функции в целом оставить, но уточнить алгоритм выбора точек, в которых необходимо осуществить вычисление целевой функции. Одним из таких алгоритмов и является метод «золотого сечения». Для этого значение целевой функции вычисляется в произвольных точках x . Возможно Так как функция унимодальна, то согласно ее свойству экстремум ее будет находиться на отрезке [a;x , а во втором случае . Таким образом, произошло сужение интервала поиска экстремума и следующую точку необходимо брать внутри укороченного интервала.

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

Золотым сечением отрезка называется точка, отстоящая на расстоянии длины от одного из ее концов). Опишем алгоритм.

ШАГ 0. Вычисляются координаты точек, осуществляющих золотое сечение исходного отрезка:

Вычисляются значения целевой функции в этих точках, то есть

ШАГ k ( Cравниваем значения и, используя эти числа, вычисляем координату симметричной точки (слева от имеющейся)

Если же то следует принять a и вычисляем координату симметричной точки (справа от имеющейся) и значение .

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

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

МЕТОД ФИБОНАЧЧИ

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

На нулевом шаге координаты точек вычисляются по формулам:

где число Фибоначчи, определяемые по реккурентной формуле

Запишем первые десять чисел Фибоначчи

;

Дальнейшая методика вычислений осуществляется так же, как и в методе «золотое сечение».Отличие заключается в том, что не надо вычислять величину интервала , так как при k=n-1 процесс заканчивается и принимается за приближенное значение экстремума.

Для построения итерационного процесса служат следующие формулы

В остальном алгоритм полностью подчиняется методу «золотого сечения».

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

При метод Фибоначчи совпадает с методом «золотого сечения».

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

МЕТОДЫ СПУСКА

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

Сущность методов спуска заключается в следующем. Известна точка x , тогда выбирается направление спуска и длина шага вдоль этого направления Cледующая точка получается в результате вычислений по формуле:

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

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

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

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

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

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

ПРИМЕР

У предприятия имеются свободные средства для инвестирования. Предприятие вложило эти средства в облигации с определенным сроком погашения (как правило 3, 6 или 12 месяцев). Курсовая стоимость облигации возрастает по мере приближения срока погашения этой облигации. Действия предприятия могут быть различными:

* дожидаться срока погашения облигации после чего получить проценты по ней и ее нарицательную стоимость;

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

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

Обозначим:

К - величина расходов на операцию реинвестирования в процентах;

П - потенциал роста стоимости облигаций до погашения в процентах в день;

Т - период оптимального реинвестирования, подлежащий определению.

Целевая функция, определяемая как полный доход за три месяца приходящийся на единицу первоначально вложенных средств, имеет вид:

при этом, как правило, значения коэффициентов П и К имеют следующий диапазон изменений 0,2 < П < 0,6 и 0,3 < К < 1,7.

Запишем задачу, как задачу минимизации

и решим ее методом «золотого сечения», задав точность вычислений до 7 дней (значения коэффициентов П и К приведены в таблице)

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

Осуществим решение этой же задачи методом чисел Фибоначчи (данные приведены в таблице).

ЗАДАНИЕ

Определить оптимальный период реинвестирования средств при периоде погашения 6 месяцев. Исходные данные приведены в таблице

МЕТОД ПОКООРДИНАТНОГО СПУСКА

Согласно этому методу, направление спуска выбирается параллельным координатным осям. Сначала производится спуск вдоль оси ОХ , затем - вдоль оси ОХ и т.д.

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

х=

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

f(.

Если это неравенство выполняется, то вдоль оси ОХ значение функции уменьшилось и поэтому полагают , .

Если неравенство не выполняется, то проверяют неравенство

f(. И если оно выполняется, то в качестве следующего приближения принимают .

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

f(x

Если оно выполняется, то полагают

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

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

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

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

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

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

ГРАДИЕНТНЫЕ МЕТОДЫ

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

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

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

ПРИМЕР

Требуется определить, в каком количестве необходимо выпускать продукцию вида А и вида Б, чтобы полученная прибыль была максимальной. Данные приведены в таблице № 1

Таблица № 1

Продукция	А	Б	Ресурсы
Выпуск кол-во			-
Трудоемкость, чел.-мес.
Прибыль, тыс.руб.			-

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

Запишем исходную задачу, как задачу минимизации

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

Таблица № 2

0,5	0,5	-1,25	1,25
0,6	0,5	-1,34	1,47
0,6	0,6	-1,44	1,8
0,7	0,6	-1,51	2,06
0,7	0,7	-1,61	2,45
0,8	0,7	-1,66	2,75
0,8	0,8	-1,76	3,2
0,9	0,8	-1,79	3,54
0,9	0,9	-1,89	4,05
	0,9	-1,9	4,43
		-2
1,1		-1,99	5,42
	1,1	-2,1	5,63
	1,2	-2,2	6,32

Полученное решение уточняем градиентным методом. Результаты приведены в таблице № 3.

Таблица № 3

0,5		-1,75	3,5	-1	-1
0,51	1,01	-1,7699	3,5805	-0,98	-1
0,5198	1,02	-1,78941	3,661584	-0,9604	-1
0,529404	1,03	-1,80854	3,743237	-0,94119	-1
0,538816	1,04	-1,82731	3,825445	-0,92237	-1
0,54804	1,05	-1,84573	3,908195	-0,90392	-1
0,557079	1,06	-1,86382	3,991474	-0,88584	-1
0,565937	1,07	-1,88159	4,07527	-0,86813	-1
0,574618	1,08	-1,89905	4,159573	-0,85076	-1
0,583126	1,09	-1,91622	4,244372	-0,83375	-1
0,591464	1,1	-1,9331	4,329658	-0,81707	-1
0,599634	1,11	-1,94971	4,415423	-0,80073	-1
0,607642	1,12	-1,96605	4,501657	-0,78472	-1
0,615489	1,13	-1,98215	4,588353	-0,76902	-1
0,623179	1,14	-1,99801	4,675504	-0,75364	-1
0,630715	1,15	-2,01363	4,763104	-0,73857	-1
0,638101	1,16	-2,02903	4,851146	-0,7238	-1
0,645339	1,17	-2,04422	4,939625	-0,70932	-1
0,652432	1,18	-2,0592	5,028536	-0,69514	-1
0,659384	1,19	-2,07398	5,117874	-0,68123	-1
0,666196	1,2	-2,08857	5,207634	-0,66761	-1
0,672872	1,21	-2,10299	5,297814	-0,65426	-1
0,679415	1,22	-2,11723	5,388409	-0,64117	-1
0,685826	1,23	-2,13129	5,479416	-0,62835	-1
0,69211	1,24	-2,1452	5,570832	-0,61578	-1
0,698268	1,25	-2,15896	5,662655	-0,60346	-1
0,704302	1,26	-2,17256	5,754883	-0,5914	-1
0,710216	1,27	-2,18603	5,847514	-0,57957	-1
0,716012	1,28	-2,19935	5,940546	-0,56798	-1
0,721692	1,29	-2,21254	6,033978	-0,55662	-1

ЗАДАНИЕ

Определить в каком количестве необходимо выпускать продукцию двух видов для получения максимальной прибыли. Данные даны в таблице № 4

Таблица № 4

Вариант	Трудоемкость 1 вида	Трудоемкость 2 вида	Прибыль от 1 вида	Прибыль от 2 вида	Ресурсы
	3	2	3 -
	4	3	4 -	2
	5	4	5 -2	3
	3	5	6 -2	4
	4	2	7 -2	2
	5	3	8 -3
	3	2	9 -3	2
	4	3	10 -3	4
	5	3	2 -2
	3	4	3 -	2
	4	5	4 -2	3
	5	3	5 -3	2
	3	4	4 -2	2
	4	5	2 -	3
	5	6	3 -	2
	6	4	4 -
	2	4	5 -2	2
	3	4	6 -2	2
	4	2	3 -	2
	5	3	4 -2	2
	6	4	5 -2	2
	2	3	3 -
	3	4	3 2	2
	4	5	4 -
	5	6	5 -2
	6	4	4 -
	2	4	3 -	2
	3	5	4 -2
	4	5	5 -2
	5	4	3 -	2

Не нашли, что искали? Воспользуйтесь поиском: