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

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

«ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ»

ФАКУЛЬТЕТ ИНФОРМАТИКИ

КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ

Допущен к защите

Заведующий кафедрой

д.т.н., профессор Ромм Я.Е.

РЕФЕРАТ

НА ТЕМУ: Схема многомерной оптимизации на основе устойчивой сортировки в случае решения задач линейного и нелинейного программирования

Выполнил студент 53 группы

отделения заочного обучения

Быков Максим Александрович

Научный руководитель

Доцент кафедры информатики

к.т.н. Заика И.В.

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

Пусть среди неизвестных , удовлетворяющих системе вида

(3.7)

требуется найти такие, при которых линейная функция

, (3.8)

достигает своего наименьшего (наибольшего) значения.

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

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

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

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

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

Граница допустимой области представляется графически в виде многогранника, каждая точка которого удовлетворяет системе равенств вида:

(3.9)

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

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

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

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

Пример 3.3. Решить задачу линейного программирования

Построим в плоскости многоугольник системы ограничений

Графической представление области допустимых решений

Рис. 3.4.

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

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

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

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

В программе переменная обозначается .

program USLOVmax1;

{$APPTYPE CONSOLE}

Uses SysUtils;

{$APPTYPE CONSOLE}

label 22;

const eps0=0.1 ;h=eps0/10;n00=2000;

nn=trunc(n00 div 2);x00=3.706; x11=7;

type vekt=array [0..n00] of extended;

vekt1=array [0..nn*2+nn] of longint;

var i,j,k,k0k,l,ee,nn0,k0k0,ii: longint;

c: vekt; e: vekt1; x,x0,x1,xk,xk0,xk1,h0,max,eps1,hh: extended;

function func (var x: extended): extended;

begin func:= 2*x+3*(35-5*x)/7 end;

Описание процедуры сортировки sort

begin nn0:=n00;hh:=nn0*h;x0:=x00;x1:=x11; while x0 <= x1 do begin

for i:=1 to nn0 do begin x:=x0+i*h; c[i]:=func(x);end;

sort(nn0,c,e);k:=1; while k<= nn0 do begin

FOR l := 1 TO n00-k do if abs(e[k+l]-e[k]) <= eps0/h then goto 22;

xk:= x0+e[k]*h;

//условия ограничений

if (abs(5*xk+7*(35-5*xk)/7)<=35) and (abs(4*xk+9*(35-5*xk)/7)<=36)

and (xk>=0) and ((35-5*xk)/7>=0) then

writeln(' ',xk:20:5,' ',(35-5*xk)/7:20:5,' ', func(xk):30:5);

22: k := k + 1; end;x0:=x0+hh;end;

// проверка

writeln('5x1+7x2=',5*xk+7*(35-5*xk)/7:2:5);

writeln('4x2+9x2=',4*xk+9*(35-5*xk)/7:2:5);readln;end.

Результат работы программы:

Значение переменной	Значение максимума	Проверка условий 5x1+7x2<=35;4x2+9x2<=36
X1=3.71600 X2=2.34571	Max=14.46914	5x1+7x2=35.00000 4x2+9x2=35.97543

По ходу работы программа при исследовании области АВО идентифицирует точки , не удовлетворяющие системе ограничений, они отсекается непосредственной подстановкой в систему (3.10) - (3.12).

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

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

Пример 3.4. Решить задачу линейного программирования

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



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

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

В программе переменные , обозначаются, соответственно , .

PROGRAM ;

{$APPTYPE CONSOLE}

USES SysUtils;

LABEL 21,22,23;

CONST eps=1.1e-444;eps0=0.001; h=eps0/1; n00=1000; x00=0; x11=1/2;

y00=0; y11=1/2;nn=n00+round(n00/2)+1; mm=64;

TYPE vect1=ARRAY [0..2*nn+nn] OF extended;

vect2=ARRAY [0..2*nn+nn] OF longint;

VAR i,ii,j,k,k1,r,ee,ee1,tty,nn0,k0k,k0k0x,k0k0y,l, n00n: longint;

c,a1,a01x,a01y,c01x,c01y: vect1;e,e3, e33, e01x,e01y: vect2;

x,x0,x1,xk,xk0,xk1,hx,hy,max,eps1,eps11,eps12,eps13: extended;

y,y0,y1,yk,yk0,yk1, ykk0,aak,bbk,hh,z,v,p: extended;

FUNCTION func (x,y:extended;):extended;

BEGIN func:=2*y-x+1 END;

PROCEDURE maxy (VAR x,y,max:extended;VAR ee1:integer);

BEGIN max:=func(x,y); ee1:=0; FOR i:=1 TO tty DO BEGIN y:=ykk0+i*hy;

IF max < func(x,y) THEN BEGIN max:=func(x,y);ee1:=i END END;END;

Описание процедуры сортировки sort

Begin x0:=x00; x1:=x11; y0:=y00; y1:=y11; nn0:=n00;

hh:=nn0*h;WHILE x0 <= x11 DO BEGIN WHILE y0 <= y11 DO BEGIN

FOR r:=1 TO nn0 DO BEGIN x:=x0+r*h;ykk0:=y0; y:=y0; tty:=n00; hy:=h;

maxy (x,y,max,ee1); a1[r]:=max END;

sort(nn0, a1, e3); k:=1;WHILE k<= nn0 DO BEGIN FOR r := 1 TO nn0-k DO

IF abs(e3[k]-e3[k+r]) <= eps0/h THEN GOTO 23; xk:= x0+E3[K]*h;

k0k0y:=1;FOR r:=1 TO nn0 DO BEGIN y:=y0+r*h; a1[r]:=func(xk,y);END;

sort( nn0, a1, e33);k1:=1; WHILE k1<= nn0 DO BEGIN

FOR r := 1 TO nn0-k1 DO IF abs(e33[k1]-e33[k1+r]) <=eps0/h THEN GOTO 22;

yk:= y0+E33[K1]*h;

// система ограничений

if (abs(2*xk+(1-2*xk-yk)+yk)<=1) and (xk+yk>=0)

and (yk>=0) and (xk>=0)then begin

writeln ('',xk:30:5,' '); writeln(' ',(1-2*xk-yk):20:2);

writeln ('',yk:30:2,' ', func(xk,yk,p):20:2);end; writeln;

22: k1:=k1+1;END;

23: k:=k+1;END; y0:=y0+hh;END; x0:=x0+hh;y0:=y00;END;

writeln(' 2x1+x2+x3=',2*xk+(1-2*xk-yk)+yk);

writeln('x2+x3=',yk+(1-2*xk-yk));writeln('end');readln;END.

Результат работы программы:

Значение переменной	Значение максимума	Проверка условий 2x1+x2+x3>=1;x2+x3>=0
X1=0.00 X2=0.00 x3=1.00	3.00	2x1+x2+x3=1.00 x2+x3=1.00

Программа при исследовании области, ограниченной неравенством (3.14), идентифицирует значения, не удовлетворяющие условиям системы ограничений (3.13) - (3.15), поэтому такой результат отсекается.

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

Результат работы программы :

Значение переменной	Значение экстремума	Проверка условий x1+x2-x4<=1;-x1+x2+x4<=1;X2+x3=1
X1=0.00 X2=1.00 X3=0.00 X4=0.00	Min=-1.00	X1+x2-x4=1.00 -x1+x2+x4=1.00 X2+x3=1.00

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

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

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

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

алгоритм программирование оптимизация

, (3.16)

при системе ограничений

.(3.17)

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

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

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

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

Для нахождения экстремумов на границе области из каждого равенства системы

(3.18)

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

Схема иллюстрируется следующим примером.

Пример 3.5. Найти наибольшее и наименьшее значение функции

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

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

Результат работы программы (внутри области допустимых значений):

Значение переменной	Значение минимума	Проверка условий x1+x2+5>=0;x1<=0;x2<=0
X1=-2.00 X2= -1.00	Min=-3.00	X1+x2+5=2.00

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

Результат работы программы (на границе области допустимых значений):

Значение переменной	Значение максимума	Проверка условий x1+x2+5>=0;x1<=0;x2<=0
x1=-4.99 x2= -0.01	Max=10.96	x1+x2+5=0.00
x1=0.00 x2= -5.00	Max=41.00	X1+x2+5=0.00

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

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

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

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

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



После этого целевая функция двух независимых переменных сводится к функции одной переменной, если выразить из первого равенства (3.22). Программа одномерной оптимизации идентифицирует точки, в которых преобразованная функция достигает своего оптимума. На выходе проверяются ограничения (3.19) - (3.21). Программа идентификации минимума представлена в приложении к главе 3, п.3.10.

Результат работы программы:

Значение переменной	Значение экстремума	Проверка условий ;
X1=0.50 X2= -3.00	Min= - 3.25	4*x1*x1-4=-3.00 x2=-3.00

Таким образом, найдена точка наименьшего значения функции на границе допустимой области.

Замечание 3.7. Если уравнения системы ограничений задачи нелинейного программирования заданы в неявном виде, то необходимо осуществить линеаризацию исходной задачи одним из известных /8, 39, 100/ методов. После этого задачу линейного программирования можно решать с помощью изложенной схемы.

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

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

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

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

При изложении данного подхода к решению задач условной оптимизации не ставилась задача улучшить существующие методы /4, 58, 63, 65, 91, 92, 107-111/. Целью было исследовать применимость схемы автоматической идентификации экстремумов на основе сортировки для решения задач условной оптимизации и указать границы такой применимости.

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

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

Размещено на Allbest.ru

...