Приближенные методы решения ЗНЛП
Используя градиентные методы, можно найти решение любой ЗНЛП.
Метод Франка-Вульфа применим, если ƒ(x1, x2, …, xn)→max и является вогнутой функцией на выпуклом множестве Ω, т.е.
При условиях ∑aijxj≤bi; i=1;m; xj≥0, то применяется следующий алгоритм:
Найти исходное допустимое решение задачи
; найти ее максимальное значение Z(k)
По формуле , где — произвольно, или находится как наименьшее решение уравнения , найти новое приближение х(k).
Проверить необходимость перехода к последующему допустимому решению, приняв в качестве критерия оценки неравенство
. Если неравенство не выполнено, тогда переходим к пункту 2, где x(0)=х (к), в противном случае решение задачи найдено.
Метод штрафных функций применим, если ƒ(x1, x2, …, xn)→max
и ƒ вогнутая на Ω Ω: gi(x1, x2,…, xn)≤bi xj≥0, где gi — выпуклые функции.
1. Найти исходное допустимое решение задачи
Начинают итерационный процесс при малых αi, постепенно их увеличивая.
5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу, если да, то определяют необходимость перехода к следующему допустимому решению по формуле
В случае необходимости переходят к этапу 2, в противоположном случае решение найдено.
6. Устанавливают значение весовых коэффициентов и переходят к этапу 4
Замечание: произвольный выбор значений αi приводит к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи методом Эрроу – Гурвица, согласно которому на очередном шаге числа αi выбирают по формуле: , где αi (0) – произвольное положительное число.
Пример. Найти методом штрафных функций максимальное значение функции f = -x 2 1 – x 2 2
Решение. Целевая функция данной задачи представляет собой отрицательно-определенную квадратичную форму и, значит, вогнута. В то же время область допустимых решений задачи, определяемая ограничениями (14) и (15), — выпуклая. Следовательно, данная задача является задачей выпуклого программирования. Для нахождения ее решения применяется метод штрафных функций.
Полагается Х (0) = (6, 7). Берется λ = 0,1. Обозначается через
g (x1, x2) = 18 — (x1 – 7) 2 — (x2 – 7) 2 и определяются частные производные от функций f (x1, x2) и g (x1, x2) по переменным х1 и х2:
Теперь, используя формулу (12), строятся последовательности точек, одна из которых определит приемлемое решение.
I итерация. Так как точка Х (0) = (6, 7) принадлежит области допустимых решений задачи, то второе слагаемое в квадратных скобках формулы (12) равно нулю. Значит координаты следующей точки Х (1) вычисляются по формулам
Проверяется теперь, принадлежит ли эта точка области допустимых решений задачи. Для этого находится g (X (1) ) = 18 – 4,48 – 1,96 = 11,2. Так как g (X (1) ) > 0, тоX (1) принадлежит области допустимых решений. В этой точке f (X (1) ) = -54,4.
II итерация. Находятся
g (X (2) ) = 18 – 9,9856 – 6,3504 = 1,664 > 0;
III итерация. Находятся
g (X (3) ) = 18 –15,429184 – 11,669056 ≈ -9,0981.
IV итерация. Точка Х (3) не принадлежит области допустимых решений задачи. Следовательно,
Чтобы выбрать число α, целесообразно взять его так, чтобы точка Х (4) не слишком далеко удалялась то границы области допустимых решений и вместе с тем принадлежала этой области. Этим требованиям удовлетворяет, в частности, α = 1,9. При данном значении получается
g (X (4) ) = 18 – 9,3025 – 8,037225 ≈ 0,66;
V итерация. Находятся
g (X (5) ) = 18 – 14,7456 – 13,454224 ≈ -10,2.
VI итерация. Находятся
g (X (6) ) = 18 – 9,078169 – 8,649481 ≈ 0,272;
VII итерация. Находятся
g (X (7) ) = 18 – 10,169721 – 10,543009 ≈ -2,713.
VIII итерация. Находятся
g (X (8) ) = 18 – 9,006001 – 8,856576 ≈ 0,137;
IX итерация. Находятся
g (X (9) ) = 18 – 14,447601 – 14,295961 ≈ -10,744.
X итерация. Находятся
g (X (10) ) = 18 – 8,976016 – 8,928144 ≈ 0,096;
XI итерация. Находятся
g (X (11) ) = 18 – 14,417209 – 14,3641 ≈ -10,781.
XII итерация. Находятся
Сравнивая значения целевой функции, найденные в точках, полученных после X и XII итераций, видно, что они с точностью до 10 -1 совпадают. Это означает близость точки, найденной на последней итерации, к точке максимального значения целевой функции. Так как точка Х (12) находится вблизи границы области допустимых решений (поскольку g(X (12) )≈0,078), то х * 1=4,005 и х * 2=4,012 можно считать приемлемым решением задачи. Это решение при необходимости можно уточнить дальнейшими шагами.
Пример. Используя метод Эрроу-Гурвица, найти решение предыдущей задачи.
Решение. Как следует из решения предыдущей задачи, при нахождении решения этой задачи методом Эрроу-Гурвица первые три итерации при одинаковых значениях λ = 0,1 в обоих случаях совпадают. Это объясняется тем, что каждая из последовательно получаемых точек принадлежит области допустимых решений, а поэтому αi ( k) = 0 (k = 1, 2, 3) независимо от того, находится ли оно по формуле (1) или (3).
Число α (4) находится по формуле (2.21):
Таким образом, х1 (4) ≈ 3,172; х2 (4) ≈ 3,489; g (X (4) ) ≈ -8,981.
V итерация. Найденная точка Х (4) = (3,172; 3,489) не принадлежит области допустимых решений исходной задачи. Поэтому отыскиваются координаты следующей точки, предварительно найдя α.
VI итерация. Находятся
VII итерация. Находятся
VIII итерация. Находятся
IX итерация. Находятся
X итерация. Находятся
XI итерация. Находятся
XII итерация. Находятся
g (X (12) ) ≈ 10,207; f (X (12) ) ≈ -50,521.
XIII итерация. Находятся
g (X (13) ) ≈ 0,251; f (X (13) ) ≈ -32,337.
Полученное на данной итерации решение х * 1 = 4,021 и х * 2 = 4,021 можно считать приемлемым. Это решение при необходимости следует улучшить, продолжив итерационный процесс до получения результата требуемой точности.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Лекция 7. Выпуклое программирование. Градиентный метод Эрроу — Гурвица
При этом предполагается, что все функции F(x), ф1(х). фт(х) являются выпуклыми, выпуклой является и область Q, заданная ограничениями (7.2).
Для решения задачи с ограничениями (7.2) обычно используется метод неопределенных множителей Лагранжа, который заключается во введении функции Лагранжа:
Говорят, что , X > 0, х є Q — седловая точка функции Лагранжа (7.3), если для всех х є Q выполняются неравенства
Теорема Куна — Таккера. Если для задачи (7.1), (7.2), (7.3) выполняются условия седловой точки (7.4), то х — оптимальное решение задачи. При этом должно выполняться дополнительное условие
Докажем достаточные условия (7.4), (7.5). Итак, пусть х>0 и X >0 есть седловая точка функции Ф(х, X) в смысле (7.4).
Запишем неравенство (7.4) в исходных функциях:
Из левого неравенства в (7.6) следует:
Неравенство (7.7) должно выполнятся при любом X > 0. Возьмем X = 0, тогда 0 T g(x), но с другой стороны g(x) 0, тогда X T g(x) T g(x), из которого в силу X > 0, a g(x) 0 — неопределенные множители Лагранжа.
При оптимальном значении вектора х должно выполняться условие седловой точки:
Метод Эрроу — Гурвица представляет собой процедуру отыскания седловой точки функции Лагранжа (7.12).
Для решения выполняется ряд последовательных приближений согласно уравнениям:
где коэффициент ц- можно определить из решения задачи
или каких-либо других соображений. Можно принимать в простейшем случае ру = 0,05 = 0,1 = const.
Заканчивать итерации следует тогда, когда частные производные по абсолютной величине станут меньше допустимых значений ex, т. е. когда
Частные производные определяются на основе метода конечных разностей, например:
Доказано, что если функции F(x) и фу(х) выпуклые, то существует седловая точка функции Лагранжа Ф(х, X) при х є Q, X > 0, —> 0,
рц > 0, причем последовательность (7.14), (7.15) сходится к седловой точке: F(x fc ) minxeQ F(x), т. е. одна из предельных точек по
следовательности принадлежит множеству решений.
Требуется минимизировать целевую функцию при условиях
Прежде всего рассмотрим геометрическую интерпретацию данной задачи. Допустимая область решения задачи представлена на рис. 7.2. Эта область ограничена прямой хг = 4-2х2, дугой окружности радиусом R = л/б с центром в начале системы координат прямой = 0 и пря
Целевая функция представляет собой окружность с центром в точке х2 = 2>. При отсутствии ограничений минимальное значение целевой функции достигается в точке 2 =2> и F(x) = 0, но эта точка не принадлежит допустимой области решения. Окружность минимального радиуса с центром в точке х2 -2>, касающаяся допустимой точке х2 =1>, соответствует минимальному значению целевой функции при заданных ограничениях F(x) = 2.
Таким образом, в результате геометрического решения задачи получаем оптимальное решение: лу = 2, х2 =1.
Теперь найдем решение с помощью метода Эрроу — Гурвица.
Составим функцию Лагранжа
Коэффициент ц возьмем постоянным и равным р = 0,1.
В качестве начальной возьмем точку с координатами х% =1> при = 1, =1>.
2- й шаг:
Самостоятельно решите следующий пример. Минимизировать выпуклую целевую функцию
Написать программу, находящую решение задачи нелинейного программирования методом Эрроу-Гурвица с точностью 0.0001
Написать программу, находящую решение задачи нелинейного программирования методом Эрроу-Гурвица с точностью 0.0001. В качестве значения возьмите 0.001.
Помогите исправить ошибки пожалуйста
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
#include "pch.h" #include #include #include #include using namespace std; int fx1 = -2,fx2 = -2; Производные найдены не верно. Выделены ошибки здесь и ниже. int gx1 = -2,gx2 = -2; int number_iteration=1; float lambda = 0.001; float alpha = 0; float new_alpha; float G; float X[2] = {4,6}; float g[2] = {12,8}; float F=-24; float new_F; double tochnost; int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); cout " Iskhodnye dannye:" endl; cout " f(x1,x2) = -2(x1-1)^2-x2 -> max" endl; cout " (x1-6)^2+(x2-4)^2 endl; cout " x1;x2 >=0" endl; cout " 1.Voz'mem lyuboe reshenie v kachestve nachal'nogo priblizheniya:" endl; cout " X0=(4;6); f(X0)=-2(4-1)^2-6=-24" endl; cout " 2.V kachestve nachal'nogo shaga vychislenij vyberem Lambda= " lambda "a0=0" endl; cout " 3.Preobrazuem neravenstvo:" endl; cout " 25-(x1-6)^2 - (x2-4)^2 >= 0"; cout " Vvedem oboznachenie g(x1,x2) = 25-(x1-6)^2 - (x2-4)^2" endl; cout " 4.Opredelim chastnye proizvodnye ot funkcii f i g:" endl; cout " f`x1 = -2x1" endl; cout " f`x2 = -2x2" endl; cout " g`x1 = -2x1+12" endl; cout " g`x2 = -2x2+8" endl; cout " 5.Zapuskaem process. Koordinaty sleduyushchej tochki budem nahodit' po formulam:" endl; cout " Xj(k+1) = max(0; Xj(k) + lambda[f`Xj(Xk)+a(k+1)*g`Xj(Xk)])" endl; cout " a(k+1)=< 0, если g(Xk) >= 0\n < a(k)-lambda*g(Xk), если g(Xk) < 0" endl; cout endl; //for (int j = 0; j < 100; j++) do { cout " " number_iteration "Iteraciya №: " endl; cout " Najdem koordinaty sleduyushchej tochki:" endl; cout " Alfa = " alpha endl; for (int i = 0; i 2; i++) { X[i] = (X[i] + lambda*(fx1*X[i] + alpha*(gx1*X[i]+g[i]))); //Сказали что здесь ошибка cout " X"i+1"(" number_iteration")=" X[i] endl; } cout " Poluchim novuyu tochku X(" number_iteration ")=(" X[0] ";" X[1] ")" endl; //Проверим принадлежит ли точка области допустимых решений G = 25-pow((X[0]-6),2)- pow((X[1]-4),2); cout " g(x" number_iteration ")=" G endl; if (G>0) { alpha = 0; cout " Tochka prinadlezhit oblasti dopustimyh znachenij" endl; new_F = -2 * pow((X[0] - 1), 2) - X[1]; cout " F(x" number_iteration")=" new_F endl; tochnost = fabs(new_F - F); F = new_F; cout " Tochnost'= " fixed setprecision(5) tochnost endl; }else { cout " Tochka ne prinadlezhit prinadlezhit oblasti dopustimyh znachenij" endl; new_alpha = alpha - lambda*G; alpha = new_alpha; cout " Alfa=" alpha endl; } number_iteration++; cout "----------------------------" endl; cout endl; } while (tochnost > 0.0001); cout " Trebuemaya tochnost' dostignuta"endl; cout " Otvet: " endl; cout " Iteraciya №: " number_iteration endl; cout " Tochka = (" X[0] "; " X[1] ")" endl; system("pause"); }
Решение нелинейного уравнения методом хорд: выдает ошибку при вводе точности = 0,0001
я создал программу для решения нелинейного уравнения методом хорд,все вроде делал по.
Найти приближенное решение нелинейного уравнения методом Ньютона на заданном отрезке. Точность вычислений Е =0.0001. sin
Найти приближенное решение нелинейного уравнения методом Ньютона на заданном отрезке. Точность.
Решение задачи нелинейного программирования
Задание состоит в нахождении решения задачи нелинейного программирования используя метод штрафных.