Нелинейное программирование. Некоторые методы решения задач нелинейного программирования

15. Нелинейное программирование. Некоторые методы решения задач нелинейного программирования. В общем виде задача нелин.програм-ния состоит в определении макс-ма или мин-ма знач-я ф-и fx1,x2,…,xn(1) при условии, что ее переменные удовл-т соотношениям gix1,x2,…,xn≤bi(i=1,…,k)gix1,x2,…,xn=bi (i=k+1,…,m) (2) где f и g – некоторые известные ф-и n-переменных, bi-заданные числа. В рез-те реш-я находится точка с координатами x*(x1*,x2*,…,xn*), координаты которой удовл-ют соотношению (2), и такая, что для всякой другой точки x(x1,x2,…,xn), удовлетворяющей усл-ям (2), выполн-ся нерав-во fx1*,x2*,…,xn*≥fx1,x2,…,xn-если max, fx1*,x2*,…,xn*≤fx1,x2,…,xn-если min. Если f и gi- линейные функции, то задача (1) – (2) является задачей лин.програм-ния. Соотношение (2) образует систему ограничений и включает в себя условия неотрицательности переменных, если такие условия имеются. В Евклидовом простр-ве система (2) опр-ет обл-ть допустимых реш-й задачи. В отличие от задачи лин.програм-ния, она не всегда является выпуклой. Если определена область допустимых реш-й, то нахождение реш-й задачи (1) – (2) сводится к отысканию точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня fx1,x2,…,xn=h. Указанная точка может находиться как на границе области допустимых реш-й, так и внутри нее. Процесс нахождения реш-я задачи нелин.програм-ния (1) – (2) с использ-ем ее геометрической интерпретации включает следующие этапы:

1) Находят область допустимых реш-й задачи, определяемую соотношениями (2). Если она пуста, то задача не имеет реш-я.

2) Строят гиперповерхность fx1,x2,…,xn=h.

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

4) Находят точку области допустимых реш-й, через которую проходят гиперповерхность наивысшего (наинизшего) уровня и определяют в ней значение ф-и (1). Например: необходимо найти max значение функции f. f=x2-x12+6x1 при условиях 2x1+3x2≤24x1+2x2≤153x1+2x2≤24x2≤4x1,x2≥0 область допустимых решений есть 4-х угольник OABC. Найдем max функции f. f=x2-x12+6x1, x2-x12+6x1=h, x2=x12-6x1 (0;0) (0;6) – парабола, max функции=13=(9+4).

Метод множителей Лагранжа. Рассмотрим частный случай задачи нелин.програм-ния (1) – (2). Предполагая, что система ограничений (2) содержит только ур-я. Условие неотрицательности переменных отсутствует, функции f и gi непрерывны вместе со своими частными производными: f(x1,x2,…,xn)→maxmin(3) gix1,x2,…,xn=bi, i=1,…,m (4). В курсе мат.анализа, задачи (3), (4) называют задачей на условный экстремум или классической задачей оптимизации. Чтобы найти реш-е этой задачи вводят набор переменных λ1,λ2,…,λn называемых множителями Лагранжа и составляют ф-ю Лагранжа Fx1,x2,…,xn,λ1,λ2,…,λm=fx1,x2,…,xn+i=1mλi(bi-gi(x1,…,xn)) (5). Находим частные производные ∂F∂xj (j=1,…,n) и ∂F∂λi (i=1,…,m) и рассматривают систему m+n уравнений. ∂F∂xi=∂f∂xi-j=1mλj∂gj∂xi i=1,…,m6, ∂F∂λi=bi-gix1,x2,…,xni=1,…,n(6).

Всякое реш-е системы (6) определяет точку X, которая может иметь место экстремум ф-и f, => решив систему (6), получают все точки, в которых ф-я (3) может иметь экстремальное значение. Дальнейшее исследование найденных точек проводят также как и в случае безусловного экстремума.Т.о. опр-ние экстремальных точек в задаче (3), (4) методом множителя Лагранжа включает след.этапы: 1) составляют ф-ю Лагранжа; 2) находят частную производную от ф-и Лагранжа по переменным x1,x2,…,xn,λ1,λ2,…,λm и приравнивают их к нулю; 3) решают систему ур-й (6), находят точки, в которых целевая ф-я задачи может иметь экстремум; 4) среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значение ф-и в этих точках.

Пример: по плану произв-ва продукции предприятию необх-мо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами: 1) при производстве x1- изделий первым способом, затраты равны (4x1+x12) – рублей. А при изготовлении x2- изделий вторым способом, они составляют (8x2+x22) – рублей. Определить, сколько изделий в каждом из способов следует изготовить так, чтобы общие затраты на произв-во продукции были min. x1+x2=180x1,x2≥0, f=4x1+x12+8x2+x22. Ф-я Лагранжа: Fx1,x2,λ=4x1+x12+8x2+x22+λ*180-x1+x2, ∂F∂x1=4+2x1-λ=0, ∂F∂x2=8+2x2-λ=0, ∂F∂λ=

180-x1-x2=0, 4+2x1-λ=08+2x2-λ=0180-x1-x2=0Находим x1 =91,x2=89,λ(=186), делаем проверку.

Метод штрафных ф-й: рассмотрим задачу опр-я максим-ного значения вогнутой ф-и f(x1,x2,…,xn) при условии, что gi(x1,x2,…,xn)≥0 при всех i=1,2,…,m. Все xj неотрицательны и gi - выпуклая функция. Вместо того чтобы непосредственно решать эту задачу, находят max значение функции: Fx1,x2,…,xn=fx1,x2,…,xn+Hx1,x2,…,xn, где f- целевая функция, а H определяется системой ограничений и называют ее штрафной функцией. Построить H можно различными способами, наиболее часто она имеет вид суммы: Hx1,x2,…,xn=i=1mαix1,x2,…,xngix1,x2,…,xn. αi- некоторые положительные постоянные числа, которые называются весовыми коэффициентами. αix1,x2,…,xn=0, если gi(x1,x2,…,xn)≥0αi, если gix1,x2,…,xn<0. Используя H, последовательно переходят от одной точки к другой до тех пор, пока не найдут решение: xj(k+1)=max0;xj(k)+λ[∂fxk∂xj+i=1mαi∂gi(x(k))∂xi] где o<λ<1- шаг вычислений. Из формул для αi(x1,x2,…,xn) следует, что если предыдущая точка находится в области допустимых решений, то второе слагаемое в квадратных скобках будет равно нулю, если же точка не принадлежит области допустимых решений, то благодаря этому второму слагаемому мы возвращаемся на область допустимых решений, при этом, чем меньше αi, тем быстрее находится приемлемое решение, однако точность его определения снижается , по этому итерационный процесс обычно начинает при сравнительно малых значениях αi и, продолжая эти значения, постепенно увеличивает. Процесс нахождения решения задачи методом штрафных функций, состоит из следующих этапов: 1) определяют исходное дополнительное решение; 2) выбирают шаг вычислений; 3) находят частные производные от целевой функции и функции, определяющих ОДР задачи; 4) по формуле xj(k+1) находят координаты точки, определяют новое возможное решение задачи; 5) проверяют: удовлетворяют ли координаты найденной точки, системе ограничений задачи. Если нет, то переходят к следующему этапу, если да – то исследуют необходимость перехода к последующему дополнительному решению. В случае такой необходимости переходят к этапу 4, в противном случае – решение уже найдено. 6) устанавливают значение весовых коэффициентов и переходят к этапу 4. Метод Эрроу-Гурвица. αi(k)=max0;αik-1-λgixk-1(i=1,2,…,m).

Число Фибоначчи6

. Члены последовательности

Фибоначчи определяются соотношениями: a1 = 1, a2 = 1, ak = ak-1+ak-2,

k³3. Найдите n-ый член этой последовательности, где n≥3.

(Turbo Pascal)

Program Fibonacci;

Uses CRT;

Var a,b,c,k,n:integer;

Begin

Write('Введите n ');

Readln(n);

a:=1; b:=1; k:=3;

Repeat

c:=a+b; a:=b; b:=c;

k:=k+1

Until k>n;

Writeln(c)

End.

(QBasic)

REM Число Фибоначчи

DIM a AS INTEGER, b AS INTEGER

DIM c AS INTEGER, k AS INTEGER

DIM n AS INTEGER

INPUT "Введите n "; n

a = 1

b = 1

k = 3

DO

│ вывод нс,"число Фибоначчи равно",c

кон

16. Циклические структуры ООП.Графическое представление, реализация, примеры.

← Предыдущая
Страница 1
Следующая →

Файл

шпора 15,16.docx

шпора 15,16.docx
Размер: 821 Кб

.

Пожаловаться на материал

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

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

Искать ещё по теме...

Похожие материалы:

Названия асан на санскрите

Названия асан на санскрите. Составные части Предметы, животные. Дополнительные общие термины.

Социальная медицина

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

Философия науки. Ответы

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

Положение о Выпускной квалификационной работе ВКР

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

Мифология, религия, философия - основные формы теоретического мышления

Эти три формы теоретического мышления никогда не существовали и не существуют в «чистом» виде. Элементы мифологии, религии, философии по-разному представлены в сознании любого человека.

Сохранить?

Пропустить...

Введите код

Ok