Специальная часть

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

Решением задачи называется х, при котором Rx Rx для любого значения а х b. При решении задач не будем различать два значения хi, и хi1, если хi хi1 е, где е задаваемая погрешность решения.

Метод сканирования заключается в последовательном переборе всех значений а х b c шагом е погрешность решения с вычислением критерия оптимальности R в каждой точке.

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

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

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

Главный недостаток этого варианта метода возможность пропуска острого глобального максимума Rx. Метод деления пополам основан на делении текущего отрезка a, b, где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на е2, где e погрешность решения задачи оптимизации.

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

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

Если Rc1 Rc2, то в качестве следующего отрезка выбираем отрезок а, c1, если же Rc1 Rc2, то берут новую точку в середине правой половины точка c3 и в ней вычисляют функцию. В зависимости от сравнения значений функции в точках c3 и c1 выбирают новый отрезок c1, b или с2, c3 и т.д. Второй вариант метода не имеет с точки зрения эффективности принципиального отличия от первого, так как эффективность принято оценивать по наихудшему варианту т.е. по двум вычислениям fx на каждом шаге. В первом варианте метода есть одна особенность, которая его делает очень эффективным при экспериментальном отыскании экстремума например, при автоматической настройке технических систем или при практическом поиске наилучших условий деятельности экономического объекта.

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

Ему удовлетворяют две точки с и d, расположенные симметрично относительно середины отрезка рис 3. abcbcbac abadaddb Путем сравнения Rc и Rd определяют следующий отрезок, где содержится максимум. Если Rd Rc, то в качестве следующего отрезка выбирается отрезок c, b, в противном случае отрезок a, d. Новый отрезок снова делится на неравные части по правилу золотого сечения.

Следует отметить, что точка d является и точкой золотого сечения отрезка a, b, т.е. dbcd cdcb Поэтому на каждой следующей итерации кроме запуска метода на исходном отрезке нужно вычислять только одно значение критерия оптимальности. Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение Rx Условие окончания поиска величина отрезка, содержащего максимум, меньше заданной погрешности. Метод обеспечивает более быструю сходимость к решению, чем многие другие методы, и применим, только для одно-экстремальных функций, На рис. приведены два этапа поиска максимума функции методом золотого сечения.

Под одно-экстремальной функцией понимают функцию, содержащую один экстремум того типа, который ищется в задаче. Метод параболической аппроксимации заключается в замене нелинейной функции Rx квадратичной параболой R2х, построенной по трем точкам, принадлежащим Rx, с последующим нахождением max параболической функции, используя аналитические условия оптимальности dRdx0. На первом этапе в качестве исходных трех точек используютcя x1a, x2b и x3аb2. В этих точках вычисляется Rx и по полученным точкам Rx1, Rx2, Rx3 строится парабола R2С2х2 C1хС0, коэффициенты которой находятся из решения соответствующей системы уравнений R2x1Rх1, R2х2Rx2, R2х3Rx3. Условие оптимальности приводит к уравнению х4 С12С2, где х4 точка максимума параболы R2x. Далее выбирается новый отрезок, внутри которого находится точка х4, и, используя х3, х4, строится новая парабола, по которой уточняется положение максимума Rx и т.д. до тех пор, пока величина отрезка, внутри которого находится максимум, не будет меньше заданной погрешности е. Таким образом, метод имеет итерационный характер.

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

В противном случае первый вариант даст лучший результат. К достоинству метода относится высокая скорость сходимости к оптимуму, хотя метод может не всегда сходиться к нему. На рис.4 приведены два случая применения метода параболической аппроксимации а рассмотрена ситуация, когда метод параболической аппроксимации сходится к решению, уже на третьем этапе парабола, построенная по точкам х3, х4, х5, практически совпадает с исходной функцией б парабола не имеет максимума уже на втором этапе. 2.2 Описание алгоритма Интерфейс созданной программы рис. 5 Сравнение методов оптимизации - состоит 1 из семи полей ввода вводятся значения A, B, C, D, погрешность и интервал min и max 2 из четырех переключателей Метод сканирования, Метод деления пополам, Метод золотого сечения, Метод параболической аппроксимации 3 кнопки Вычислить 4 поля, в котором будет выводиться ответ 5 кнопки Выход, а так же главного меню Что бы получить ответ необходимо выбрать метод решения и нажать на кнопку Вычислить.

На этой кнопке прописан основной текст программы. Условно его можно разделить на пять частей.

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

Так же в программе прописана функция одна для всех методов, на основе решения которой мы будем получать приближенные значения. Описание алгоритма при выборе переключателя Метод сканирования 1 первым делом обнулим счетчик, который считает количество итераций it0 2 оформим цикл типа repeat - until до тех пор пока потом разбиваем отрезок на четыре части Intmax-min4 и присваиваем некоторой переменной значение минимума PERmin оформляем цикл для нахождения массива чисел xi на заданном интервале на каждом интервале находим значение функции находим максимальное значение находим индекс максимального значения некоторой новой переменной присваиваем значение xk вычисляем новые значения минимума и максимума считаем количество итераций itit1 3 на экран выводится ответ рис. 6 . Приведем пример дана функция RxD sinAxB C, где коэффициенты имеют следующие значения А1,0, В1,0, С1,0, D1,0. Найти максимум на интервале -1, 2. Ошибка задается по х е0,05. Результаты расчетов.

Разобьем весь интервал на четыре подинтервала крупный шаг, координаты х будут следующими x1 0,25, x20,5, x31,25. Соответственно значения критерия равны R10,68163, R20,9974, R30,77807. Следовательно, в качестве нового отрезка выбираем отрезок 0,25, 1,25, так как внутри него находится максимальное значение x00,5, R00,99749499, 0 номер итерации после первого этапа.

Разбиваем его снова на четыре части, имеем значения х10,125, х20,5, x30,875. Вычислив Rx в этих точках, получим, что новый интервал, внутри которого лежит экстремум, равен 0,125, 0,875. Далее в табл. 1 приводятся только координаты середин отрезков, при которых критерий имеет наибольшее значение, номер итерации и значение критерия.

Табл. 1 Расчеты данных по этапам методом сканирования XR10,50,9974949920,50,9974949930,5937500 00,9997365840,570312500,98860,593750000, 99973658Всего проведено 63 18 вычислений критерия оптимальности. Описание алгоритма при выборе переключателя Метод деления пополам 1 обнулим счетчик который считает количество итераций it0 2 оформим цикл типа repeat - until до тех пор пока вычислим середину отрезка ser и точки стоящие от середины отрезка на еp2 G и H далее вычисляем критерий оптимальности в этих точках ser, H, G проверяем условие, если критерии оптимальности от точки G больше критерия оптимальности чем от точки H R1 R2, то минимальное значение равно середине отрезка minser проверяем второе условие, если критерии оптимальности от точки G меньше критерия оптимальности чем от точки H R1 R2, то максимальное значение равно середине отрезка maxser считаем количество итераций itit1 проверяем условие окончания вычислений разница между максимумом и минимумом должна быть меньше заданной погрешности until max-min ep 3 на экран выводится ответ рис. 7. Приведем пример дана функция RxD sinAxB C, где коэффициенты имеют следующие значения А1,0, В1,0, С1,0, D1,0. Найти максимум на интервале -1, 2. Ошибка задается по х е0,05. Результаты расчетов.

Середина отрезка x0 0,5000, значение критерия R00,9975, значение R0,5 e2 R0,4750,97922273, значение R0,5e2R0,5250,9989513. Следовательно, искомый максимум лежит в правой половине отрезка, т.е. теперь отрезком является 0,5, 2. Далее приводятся только координаты середин отрезков с номером итерации, значения критерия в них и указывается новый отрезок правый или левый. x11,250 R10,77807320 левый х20,8750 R20,95408578 левый х30,68750000 R30,99319785 левый x40,59375000 R40,99973658 левый x50,54687500 R50,99971390 x4 х5 e, поэтому в качестве решения можно принять любое из этих значений или середину между ними. Всего восемь раз 428 вычислялся критерий оптимальности не считая вычислений непосредственно в середине отрезка, которые не используются в алгоритме метода.

Описание алгоритма при выборе переключателя Метод золотого сечения 1 обнулим счетчик который считает количество итераций it0 2 оформим цикл типа repeat - until до тех пор пока некоторому числу m приравнивается минимум, а n максимум делим отрезок на неравные части по правилу золотого сечения находим точки Lev и Prav вычисляем критерий оптимальности в точках Lev и Prav проверяем условие, при котором минимум отрезка принимает значение Prav если критерий оптимальности от точки Lev больше критерия оптимальности от точки Prav выводим на экран получившийся критерий оптимальности проверяем второе условие, при котором максимум отрезка принимает значение Lev если критерий оптимальности от точки Lev меньше критерия оптимальности от точки Prav выводим на экран получившийся критерий оптимальности считаем количество итераций itit1 проверяем условие окончания вычислений разница между максимумом и минимумом должна быть меньше заданной погрешности until max-min ep 4 на экран выводится ответ рис. 8. Приведем пример дана функция RxD sinAxB C, где коэффициенты имеют следующие значения А1,0, В1,0, С1,0, D1,0. Найти максимум на интервале -1, 2. Ошибка задается по х е0,05. Результаты расчетов.

Для запуска метода найдем две симметричные точки золотого сечения для отрезка -1, 2 х1 0,145898, х2 0,85410197. Значения критериев в этих точках соответственно Rx10,911080, Rx20,960136. Следовательно, новым отрезком является 0,1458982, внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрезка будет х30,58359214, a Rx30,99991813. Далее приведены только координаты лучших точек при очередном шаге, номер шага и значения критерия в этих точках. х30,58359214 R30,99991813 х40,58359214 R40,99991813 x50,58359214 R50,99991813 x60,58359214 R60,99991813 х70,58359214 R70,99991813 x80,55920028 R80,99993277 x90,55920028 R90,99993277 Всего было проведено 10 вычислений критерия оптимальности. Описание алгоритма при выборе переключателя Метод параболической аппроксимации 1 обнулим счетчик который считает количество итераций it0 2 обнулим счетчик который считает сколько раз вычисляются коэффициенты параболы i0 3 рассчитываем середину отрезка sermax-min2min 4 оформим цикл типа repeat - until до тех пор пока вычисляем критерий оптимальности в точке min, max и ser минимум, максимум и середина находим общий делитель dtl необходим чтобы использовать метод Крамера методом Крамера находим коэффициенты X, Y, Z находим коэффициенты параболы C0, C1, C2 считаем ii1 приравниваем значению минимума значение середины minser находим значение при котором парабола имеет максимум Parabi-C12C2 считаем количество итераций itit1 проверяем условие окончания вычислений until absParabi-Parabi-1 ep разница между последним и предпоследним значениями должна быть меньше заданной погрешности 5 выводится ответ рис. 9. Приведем пример дана функция RxD sinAxB C, где коэффициенты имеют следующие значения А1,0, В1,0, С1,0, D1,0. Найти максимум на интервале -1, 2. Ошибка задается по х е0,05. Результаты расчетов.

Первая аппроксимирующая парабола строится по точкам х1 -1, R-10 х20,5 R0,50,9975 х32,0, R2,00,141120. Запишем систему уравнений для нахождения коэффициентов параболы 1С2-1С1Со0, 0,25С2 0,5C1 С0 0,9975, 4C22C1C00,14112. Решением этой системы является С2-0,41197, С10,459012, С00,87089. Находим х, при котором парабола имеет максимум х С12С2 0,4119720,4590120,55709139, при этом R0,99990609. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола, максимум которой оказывается в точке х 0,57823785, а R 0,99997231. Разница между двумя точками максимума менее заданной погрешности, следовательно, можно заканчивать поиск.

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

Как уже сказано выше в программе присутствует главное меню в котором всего два пункта Файл и Справка.

Пункт меню Файл содержит следующие подпункты рис. 10 1. Метод сканирования 2. Метод деления пополам 3. Метод золотого сечения 4. Метод параболической аппроксимации 5. Выход Выбирая один из первых четырех пунктов пользователь выбирает один из методов после чего он может нажать кнопку Вычислить для получения ответа.

Если пользователь выберет пятый пункт Выход то произойдет выход из программы.

Пункт меню Справка содержит один подпункт Вызов справки, при выборе этого пункта появится диалоговое окно которое состоит из двух вкладок Разработчик и О программе, на рис. 11 приведены эти вкладки. 2.3 Текст программы с описанием unit Unit1 interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Buttons, ExtCtrls, Menus type TForm1 classTForm GroupBox1 TGroupBox Edit1 TEdit Label1 TLabel Label2 TLabel Label3 TLabel Label4 TLabel Edit2 TEdit Edit3 TEdit Edit4 TEdit Label5 TLabel Edit5 TEdit Edit6 TEdit Label6 TLabel Edit7 TEdit SpeedButton1 TSpeedButton Label7 TLabel GroupBox2 TGroupBox RadioButton1 TRadioButton RadioButton2 TRadioButton BitBtn1 TBitBtn RadioButton3 TRadioButton RadioButton4 TRadioButton Label8 TLabel Bevel1 TBevel MainMenu1 TMainMenu N1 TMenuItem N11 TMenuItem N21 TMenuItem N31 TMenuItem N41 TMenuItem N2 TMenuItem N3 TMenuItem N4 TMenuItem procedure SpeedButton1ClickSender TObject procedure N3ClickSender TObject procedure N4ClickSender TObject procedure N11ClickSender TObject procedure N21ClickSender TObject procedure N31ClickSender TObject procedure N41ClickSender TObject private Private declarations public Public declarations end var Form1 TForm1 max, min real Переменные используемые в программе A,B,C,D,ep, int, per, maxmn, newP,R real R0,R1,R2,ser, dlt, dltX,dltY,dltZ,C0,C1,C2 real x, mass array 1 25 of real parab array 0 99 of real G,H,J,K real RLev, RPrav real implementation uses Unit4 R .dfm function ScanA,B,C,D,x real real Вычисляется функция вида RxD sinAxB C var PRM real i integer begin PRM1 for i1 to truncB do PRMPRMx ScanDsinAPRMC end procedure TForm1.SpeedButton1ClickSender TObject Действие при нажатии кнопки Вычислить var i, k,it integer Переменные используемые в программе m, n,Lev,Prav real begin try epstrtofloatEdit7.Text ep погрешность из строки переводится в число if ep 0 then exit AstrtofloatEdit1.Text А из строки переводится в число BstrtofloatEdit2.Text B из строки переводится в число CstrtofloatEdit3.Text C из строки переводится в число DstrtofloatEdit4.Text D из строки переводится в число minstrtofloatEdit5.Text min из строки переводится в число maxstrtofloatEdit6.Text max из строки переводится в число if min max then exit except ShowMessageНекорректное значение exit end If RadioButton1.Checked then Вычисляется Метод Сканирования begin it0 Количество итераций равно 0 repeat Intmax-min4 Отрезок разбивается на 4 части PERmin Некоторой переменной присваивается значение минимума for i1 to 3 do Находим массив чисел xi begin PERPERInt xiPER end for i1 to 3 do MASSiScanA,B,C,D,xi На каждом интервале находим значение функции maxmnmass1 k1 for i2 to 3 do if maxmn massi then Находим максимальное значение begin maxmnmassi ki Индекс максимального значения end newPxk minnewP-int Находим минимум maxnewPint Находим максимум itit1 Считается количество итераций until max-min ep Условие окончания вычислений Label7.CaptionОтвет x floattostrnewP 1013 R floattostrmassk Выводится ответ Label8.Caption Количество итераций inttostrit Выводится количество итераций end If RadioButton3.Checked then Вычисляется Метод деления пополам begin it0 Количество итераций равно 0 repeat sermaxmin2 Вычисляется середина отрезка ser и точки стоящие от середины отрезка на еp2 G и H Gserep2 Hser-ep2 R0scanA,B,C,D,ser вычисляется критерий оптимальности в точке ser R1scanA,B,C,D,G вычисляется критерий оптимальности в точке G R2scanA,B,C,D,H вычисляется критерий оптимальности в точке H if R1 R2 then begin Условие при котором середина равняется минимуму minser end if R1 R2 then begin Условие при котором середина равняется максимуму maxser end itit1 считается количество итераций until max-min ep условие окончания вычислений Label7.CaptionОтвет x floattostrser1013 R FloattostrR0 На экран выводится ответ ser, R0 Label8.Caption Количество итераций inttostrit Выводится количество итераций end If RadioButton4.Checked then Вычисляется метод Золотого сечения begin it2 Количество итераций равно 2 т.к. две точки даны repeat mmin m приравнивается к минимуму nmax n приравнивается к максимуму Levmn-msqrt5-12 Отрезок делится на неравные части по Pravn-n-msqrt5-12 Правилу золотого сечения точки Lev и Prav RLevscanA,B,C,D,Lev Вычисляется критерий оптимальности в точке Lev RPravscanA,B,C,D,Prav вычисляется критерий оптимальности в точке Prav if RLev RPrav then Условие при котором минимум отрезка принимает значение Prav begin minPrav Label7.CaptionОтвет x floattostrLev1013 R FloattostrRLev На экран выводится ответ Lev, RLev end if RLev RPrav then Условие при котором максимум отрезка принимает значение Lev begin maxLev Label7.CaptionОтвет x floattostrPrav1013 R FloattostrRPrav На экран выводится ответ Prav, RPrav end itit1 Считается количество итераций until max-min ep Условие окончания вычислений Label8.Caption Количество итераций inttostrit Выводится количество итераций end if RadioButton2.Checked then Вычисляется метод Параболической аппроксимации begin it0 Количество итераций равно 0 i0 sermax-min2min Рассчитывается середина отрезка repeat R0scanA,B,C,D,min Вычисляется критерий оптимальности в точке min R1scanA,B,C,D,ser Вычисляется критерий оптимальности в точке ser R2scanA,B,C,D,max Вычисляется критерий оптимальности в точке max dltsqrminser-max-minsqrser-sqrmaxsqrserm ax-sersqrmax Находим общий делитель dltXR0ser-max-minR1-R2R1max-R2ser dltYsqrminR1-R2-R0sqrser-sqrmaxsqrserR2- R1sqrmax dltZsqrminserR2-maxR1-minsqrserR2-R1sqrm axR0sqrsermax-sersqrmax Методом Крамера находим X, Y, Z. C2dltXdlt Находим коэффициенты параболы C0, C1, C2 C1dltYdlt C0dltZdlt ii1 minser Parabi-C12C2 Значение при котором парабола имеет максимум serParabi if i1 then Parabi-1-Parabi itit1 Считается количество итераций until absParabi-Parabi-1 ep Условие окончания вычислений RScanA,B,C,D,Parabi Label7.CaptionОтвет x floattostrParabi1013R floattostrR Label8.Caption Количество итераций inttostrit Выводится количество итераций end end procedure TForm1.N3ClickSender TObject begin Close Выход end procedure TForm1.N4ClickSender TObject begin PagesDlg. Show Вызов справки end procedure TForm1.N11ClickSender TObject begin RadioButton1.Checkedtrue Выбирается Метод сканирования end procedure TForm1.N21ClickSender TObject begin RadioButton3.Checkedtrue Выбирается Метод деления пополам end procedure TForm1.N31ClickSender TObject begin RadioButton4.Checkedtrue Выбирается Метод золотого сечения end procedure TForm1.N41ClickSender TObject begin RadioButton2.Checkedtrue Выбирается Метод параболической аппроксимации end end. 2.4 Описание процесса отладки программы Отладка программы представляет собой нахождение ошибок используя контрольные примеры.

В данной программе ошибки могут быть если введены неточные некорректные значения в полях ввода, чтобы этого не произошло используется система tryexceptend. begin try epstrtofloatEdit7.Text ep погрешность из строки переводится в число if ep 0 then exit AstrtofloatEdit1.Text А из строки переводится в число BstrtofloatEdit2.Text B из строки переводится в число CstrtofloatEdit3.Text C из строки переводится в число DstrtofloatEdit4.Text D из строки переводится в число minstrtofloatEdit5.Text min из строки переводится в число maxstrtofloatEdit6.Text max из строки переводится в число if min max then exit except ShowMessageНекорректное значение exit end Наибольшее затруднение в написании программы было в методе золотого сечения пришлось долго думать как вывести ответ проблема в том, что если критерий оптимальности от левой точки больше критерия оптимальности чем от правой точки, то минимумом должна стать правая точка, а если критерий оптимальности от левой точки меньше критерия оптимальности чем от правой точки, то максимумом становится левая точка и что выводить правую точку минимум или левую максимум, решение в конце концов стало простым выводить значение обеих точек на одну метку мы увидим самое последние значение, т.е. правильное а это уже не важно левая это точка или правая.

В процессе отладки возникали следующие ошибки - Undeclared identifier используется переменная, не объявленная в разделе var - Missing operator or semicolon после инструкции не поставлена точка с запятой - expected - забыл закрыть скобку - Incompatible types несоответствие типов и т.д.